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...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Published: |
2018
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/115882 |
| _version_ | 1811068236630851584 |
|---|---|
| author | Timmons, Eric Williams, Brian C. |
| author2 | Brian Williams |
| author_facet | Brian Williams Timmons, Eric Williams, Brian C. |
| author_sort | Timmons, Eric |
| collection | MIT |
| 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 (A*BC) and a hybrid estimation method based on this enumeration algorithm. Experiments show that an A*BC powered state estimator produces estimates faster than the current state of the art, particularly on large systems. |
| first_indexed | 2024-09-23T07:53:22Z |
| id | mit-1721.1/115882 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T07:53:22Z |
| publishDate | 2018 |
| record_format | dspace |
| spelling | mit-1721.1/1158822019-04-09T15:19: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 (A*BC) and a hybrid estimation method based on this enumeration algorithm. Experiments show that an A*BC 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 http://hdl.handle.net/1721.1/115882 MIT-CSAIL-TR-2018-016 27 p. application/pdf |
| 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 |
| title | 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_short | 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 |
| topic | belief revision and update diagnosis heuristics search |
| url | http://hdl.handle.net/1721.1/115882 |
| work_keys_str_mv | AT timmonseric bestfirstenumerationbasedonboundingconflictsanditsapplicationtolargescalehybridestimation AT williamsbrianc bestfirstenumerationbasedonboundingconflictsanditsapplicationtolargescalehybridestimation |