Model-based planning through constraint and causal order decomposition

One of the major challenges in autonomous planning and sequencing is the theoretical complexity of planning problems. Even a simple STRIPS planning problem is PSPACEcomplete, and depending on the expressivity of the planning problem, the complexity of the problem can be EXPTIME-complete or worse. This thesis improves on current approaches to sequencing the engineering operations of a spacecraft or ground-based asset through the explicit use of verifiable models and a decomposition approach to planning. Based on specifications of system behavior, the planner generates control sequences of engineering operations that achieve mission objectives specified by an operator. This work is novel in three ways. First, an innovative "divide-and-conquer" approach is used to assure efficiency and scalability of the planner. The key to the approach is in its combined use of constraint decomposition and causal order decomposition. This technique provides the means to decompose the problem into a set of subproblems and to identify the ordering by which each subproblem should be solved, thus reducing, and possibly eliminating, search. Second, the decomposed planning framework is able to solve complex planning problems with state constraints and temporally extended goals. Such complex system behavior is specified as concurrent, constraint automata (CCA) that provide the expressiveness necessary to model the behavior of the system components and their interactions. The mission objective is described as a desired evolution of goal states called a qualitative state plan (QSP), explicitly capturing the intent of the operators. Finally, the planner generates a partially-ordered plan called a qualitative control plan (QCP) that provides additional execution robustness through temporal flexibility. We demonstrate the decomposed approach to Model-based planning on a scenario based on the ongoing Autonomous Sciencecraft Experiment, onboard EO-1 spacecraft. The EO-1 problem has a large state space with well over 660 quintillion states, 6.6 x 10²⁰.

Department dc:contributor.department

Massachusetts Institute of Technology. Dept. of Aeronautics and Astronautics.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2008

Author dc:creator

• Chung, Seung H. (Seung Hwa), 1975-

Advisor dc:contributor.advisor

• Brian C. Williams.

• Aeronautics and Astronautics.

Statement dc:rights

• 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.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/46555

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/46555