Enabling fast flexible planning through incremental temporal reasoning
Thesis (M. Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2003.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2005
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/18035 |
| _version_ | 1826205988480352256 |
|---|---|
| author | Shu, I-hsiang, 1979- |
| author2 | Brian C. Williams. |
| author_facet | Brian C. Williams. Shu, I-hsiang, 1979- |
| author_sort | Shu, I-hsiang, 1979- |
| collection | MIT |
| description | Thesis (M. Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2003. |
| first_indexed | 2024-09-23T13:22:12Z |
| format | Thesis |
| id | mit-1721.1/18035 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T13:22:12Z |
| publishDate | 2005 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/180352019-04-11T14:38:17Z Enabling fast flexible planning through incremental temporal reasoning Shu, I-hsiang, 1979- Brian C. Williams. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Electrical Engineering and Computer Science. Thesis (M. Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2003. Includes bibliographical references (leaves 70-71). In order for a team of autonomous agents to successfully complete its mission, the agents must be able to quickly re-plan on the fly as unforeseen events arise in the environment. This requires temporally flexible plans that allow the agent to adapt to execution uncertainties by not overcommitting on time constraints, and a continuous planner that replans at any point when the current plan fails. To achieve both of these requirements, planners must have the ability to reason quickly about timing constraints. This thesis provides a fast incremental algorithm, ITC, for determining the temporal consistency of temporally flexible plans. Additionally, the temporal reasoning capability of ITC is able to return the conflict or the nature of the inconsistency to the planner, such that the planner can resolve inconsistencies quickly and intelligently. The ITC algorithm combines the speed of shortest-path algorithms known to network optimization with the spirit of incremental algorithms such as Incremental A* and those used within truth maintenance systems (TMS). The algorithm has been implemented and integrated into a temporal planner, called Kirk. It has demonstrated an order of magnitude speed increase on cooperative air vehicle scenarios. by I-hsiang Shu. M.Eng. 2005-06-02T19:43:03Z 2005-06-02T19:43:03Z 2003 2003 Thesis http://hdl.handle.net/1721.1/18035 57253453 eng M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/7582 71 leaves 4118645 bytes 4125738 bytes application/pdf application/pdf application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Shu, I-hsiang, 1979- Enabling fast flexible planning through incremental temporal reasoning |
| title | Enabling fast flexible planning through incremental temporal reasoning |
| title_full | Enabling fast flexible planning through incremental temporal reasoning |
| title_fullStr | Enabling fast flexible planning through incremental temporal reasoning |
| title_full_unstemmed | Enabling fast flexible planning through incremental temporal reasoning |
| title_short | Enabling fast flexible planning through incremental temporal reasoning |
| title_sort | enabling fast flexible planning through incremental temporal reasoning |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/18035 |
| work_keys_str_mv | AT shuihsiang1979 enablingfastflexibleplanningthroughincrementaltemporalreasoning |