Best-first Enumeration Based on Bounding Conflicts, and its Application to Large-scale Hybrid Estimation

With the rise of autonomous systems, there is a need for them to have high levels of robustness and safety. This robustness can be achieved through systems that are self-repairing. Underlying this is the ability to diagnose subtle failures. Likewise, online planners can generate novel responses to e...

Mô tả chi tiết

Lưu vào:

Hiển thị chi tiết
Tác giả chính:	Timmons, Eric, Williams, Brian C.
Đồng tác giả:	Brian Williams
Thông tin xuất bản:	2018
Chủ đề:	belief revision and update diagnosis heuristics search
Truy cập trực tuyến:	http://hdl.handle.net/1721.1/115882 http://lib.yhn.edu.vn/handle/YHN/741
Từ khóa:	Thêm từ khóa bạn đọc Không có từ khóa, Hãy là người đầu tiên gắn từ khóa cho biểu ghi này!

id	oai:localhost:YHN-741
record_format	dspace
spelling	oai:localhost:YHN-7412023-04-13T11:22:33Z Best-first Enumeration Based on Bounding Conflicts, and its Application to Large-scale Hybrid Estimation Timmons, Eric Williams, Brian C. Brian Williams Model-based Embedded and Robotic Systems belief revision and update diagnosis heuristics search With the rise of autonomous systems, there is a need for them to have high levels of robustness and safety. This robustness can be achieved through systems that are self-repairing. Underlying this is the ability to diagnose subtle failures. Likewise, online planners can generate novel responses to exceptional situations. These planners require an accurate estimate of state. Estimation methods based on hybrid discrete/continuous state models have emerged as a method of computing precise state estimates, which can be employed for either diagnosis or planning in hybrid domains. However, existing methods have difficulty scaling to systems with more than a handful of components. Discrete state estimation capabilities can scale to this level by combining best-first enumeration and conflict-directed search. Best-first methods have been developed for hybrid estimation, but the creation of conflict-directed methods has previously been elusive. While conflicts are used to learn from constraint violation, probabilistic hybrid estimation is relatively unconstrained. In this paper we present an approach to hybrid estimation that unifies best-first enumeration and conflict-directed search through the concept of "bounding" conflicts, an extension of conflicts that represent tighter bounds on the cost of regions of the search space. This paper presents a general best-first search and enumeration algorithm based on bounding conflicts (ABC) and a hybrid estimation method based on this enumeration algorithm. Experiments show that an ABC powered state estimator produces estimates faster than the current state of the art, particularly on large systems. 2018-05-24T21:15:06Z 2018-05-24T21:15:06Z 2018-05-24 2018-05-24T21:15:06Z 2023-04-13T11:22:33Z 2023-04-13T11:22:33Z http://hdl.handle.net/1721.1/115882 http://lib.yhn.edu.vn/handle/YHN/741 MIT-CSAIL-TR-2018-016 27 p. application/pdf application/pdf
institution	Trường Cao đẳng Y tế Hà Nội
collection	DSpace
topic	belief revision and update diagnosis heuristics search
spellingShingle	belief revision and update diagnosis heuristics search Timmons, Eric Williams, Brian C. Best-first Enumeration Based on Bounding Conflicts, and its Application to Large-scale Hybrid Estimation
description	With the rise of autonomous systems, there is a need for them to have high levels of robustness and safety. This robustness can be achieved through systems that are self-repairing. Underlying this is the ability to diagnose subtle failures. Likewise, online planners can generate novel responses to exceptional situations. These planners require an accurate estimate of state. Estimation methods based on hybrid discrete/continuous state models have emerged as a method of computing precise state estimates, which can be employed for either diagnosis or planning in hybrid domains. However, existing methods have difficulty scaling to systems with more than a handful of components. Discrete state estimation capabilities can scale to this level by combining best-first enumeration and conflict-directed search. Best-first methods have been developed for hybrid estimation, but the creation of conflict-directed methods has previously been elusive. While conflicts are used to learn from constraint violation, probabilistic hybrid estimation is relatively unconstrained. In this paper we present an approach to hybrid estimation that unifies best-first enumeration and conflict-directed search through the concept of "bounding" conflicts, an extension of conflicts that represent tighter bounds on the cost of regions of the search space. This paper presents a general best-first search and enumeration algorithm based on bounding conflicts (ABC) and a hybrid estimation method based on this enumeration algorithm. Experiments show that an ABC powered state estimator produces estimates faster than the current state of the art, particularly on large systems.
author2	Brian Williams
author_facet	Brian Williams Timmons, Eric Williams, Brian C.
author	Timmons, Eric Williams, Brian C.
author_sort	Timmons, Eric
title	Best-first Enumeration Based on Bounding Conflicts, and its Application to Large-scale Hybrid Estimation
title_short	Best-first Enumeration Based on Bounding Conflicts, and its Application to Large-scale Hybrid Estimation
title_full	Best-first Enumeration Based on Bounding Conflicts, and its Application to Large-scale Hybrid Estimation
title_fullStr	Best-first Enumeration Based on Bounding Conflicts, and its Application to Large-scale Hybrid Estimation
title_full_unstemmed	Best-first Enumeration Based on Bounding Conflicts, and its Application to Large-scale Hybrid Estimation
title_sort	best-first enumeration based on bounding conflicts, and its application to large-scale hybrid estimation
publishDate	2018
url	http://hdl.handle.net/1721.1/115882 http://lib.yhn.edu.vn/handle/YHN/741
work_keys_str_mv	AT timmonseric bestfirstenumerationbasedonboundingconflictsanditsapplicationtolargescalehybridestimation AT williamsbrianc bestfirstenumerationbasedonboundingconflictsanditsapplicationtolargescalehybridestimation
_version_	1811121826493890560

Best-first Enumeration Based on Bounding Conflicts, and its Application to Large-scale Hybrid Estimation

Tài liệu tương tự