Optimal temporal planning at reactive time scales via dynamic backtracking branch and bound
Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Aeronautics and Astronautics, 2006.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2007
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/37948 |
| _version_ | 1811082061525549056 |
|---|---|
| author | Effinger, Robert T |
| author2 | Brian C. Williams. |
| author_facet | Brian C. Williams. Effinger, Robert T |
| author_sort | Effinger, Robert T |
| collection | MIT |
| description | Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Aeronautics and Astronautics, 2006. |
| first_indexed | 2024-09-23T11:56:57Z |
| format | Thesis |
| id | mit-1721.1/37948 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T11:56:57Z |
| publishDate | 2007 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/379482019-04-11T03:16:27Z Optimal temporal planning at reactive time scales via dynamic backtracking branch and bound Effinger, Robert T Brian C. Williams. Massachusetts Institute of Technology. Dept. of Aeronautics and Astronautics. Massachusetts Institute of Technology. Dept. of Aeronautics and Astronautics. Aeronautics and Astronautics. Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Aeronautics and Astronautics, 2006. Includes bibliographical references (p. 110-115). Autonomous robots are being considered for increasingly capable roles in our society, such as urban search and rescue, automation for assisted living, and lunar habitat construction. To fulfill these roles, teams of autonomous robots will need to cooperate together to accomplish complex mission objectives in uncertain and dynamic environments. In these environments, autonomous robots face a host of new challenges, such as responding robustly to timing uncertainties and perturbations, task and coordination failures, and equipment malfunctions. In order to address these challenges, this thesis advocates a novel planning approach, called temporally-flexible contingent planning. A temporally-flexible contingent plan is a compact encoding of methods for achieving the mission objectives which incorporates robustness through flexible task durations, redundant methods, constraints on when methods are applicable, and preferences between methods. This approach enables robots to adapt to unexpected changes on-the-fly by selecting alternative methods at runtime in order to satisfy as best possible the mission objectives. The drawback to this approach, however, is the computational overhead involved in selecting alternative methods at runtime in response to changes. (cont.) If a robot takes too long to select a new plan, it could fail to achieve its near-term mission objectives and potentially incur damage. To alleviate this problem, and extend the range of applicability of temporally-flexible contingent planning to more demanding real-time systems, this thesis proposes a temporally-flexible contingent plan executive that selects new methods quickly and optimally in response to changes in a robot's health and environment. We enable fast and optimal method selection through two complimentary approaches. First, we frame optimal method selection as a constraint satisfaction problem (CSP) variant, called an Optimal Conditional CSP (OCCSP). Second, we extend fast CSP search algorithms, such as Dynamic Backtracking and Branch-and-Bound Search, to solve OCCSPs. Experiments on an autonomous rover test-bed and on randomly generated plans show that these contributions significantly improve the speed at which robots perform optimal method selection in response to changes in their health status and environment. by Robert T. Effinger, IV. S.M. 2007-07-18T13:14:07Z 2007-07-18T13:14:07Z 2006 2006 Thesis http://hdl.handle.net/1721.1/37948 144580849 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 115 p. application/pdf Massachusetts Institute of Technology |
| spellingShingle | Aeronautics and Astronautics. Effinger, Robert T Optimal temporal planning at reactive time scales via dynamic backtracking branch and bound |
| title | Optimal temporal planning at reactive time scales via dynamic backtracking branch and bound |
| title_full | Optimal temporal planning at reactive time scales via dynamic backtracking branch and bound |
| title_fullStr | Optimal temporal planning at reactive time scales via dynamic backtracking branch and bound |
| title_full_unstemmed | Optimal temporal planning at reactive time scales via dynamic backtracking branch and bound |
| title_short | Optimal temporal planning at reactive time scales via dynamic backtracking branch and bound |
| title_sort | optimal temporal planning at reactive time scales via dynamic backtracking branch and bound |
| topic | Aeronautics and Astronautics. |
| url | http://hdl.handle.net/1721.1/37948 |
| work_keys_str_mv | AT effingerrobertt optimaltemporalplanningatreactivetimescalesviadynamicbacktrackingbranchandbound |