MS thesis abstract - Chung, Seung
| Author: | Chung, Seung |
| Degree: | Masters of Science |
| SERC #: | 7-03 |
| File type: | PDF, 760 kB |
 Download file (opens in new window) | |
A Decomposed Symbolic Approach to Reactive Planning
Autonomous systems that operate in uncertain dynamic environments must respond to unanticipated events and goals by reconfiguring themselves in real-time. Reactive planning achieves reconfiguration in real-time by constructing a goal-directed plan (GDP) for all possible events and goals oČine and then executing the GDP online, while monitoring the outcome of each execution step. A GDP, however, is susceptible to an explosion in space that is proportional to the square of the system's state space.
This thesis presents a new reactive plan encoding called a decomposed goal-directed plan (DGDP), which addresses the state space explosion problem by unifying two complementary approaches in the literature: transition-based decomposition and symbolic encoding. The DGDP encoding first uses transition-based decomposition to reduce the overall complexity of the planning problem by dividing the problem into a set of subproblems that may be solved independently, and then combined serially. This decomposition is based on the structure of the system's transition dependency graph (TDG), which captures the transition dependencies among the system components. Next, a GDP for each subproblem is generated using a compact symbolic encoding in terms of Ordered Binary Decision Diagrams (OBDD). Finally, these GDPs are combined into a full plan, the DGDP, based on the transition-based decomposition. This thesis makes two additional contributions to state-of-the-art reactive planning. First, it generalizes the "divide-and-conquer" approach introduced by the Burton reactive planner to systems with interdependent components, where a system with interdependent components is characterized by cycles within its TDG. Second, it generalizes OBDD plan encodings from universal plans, which are conditioned on all possible initial states, to goal-directed plans that are also conditioned on all possible goal states. The new decomposed symbolic reactive planner is empirically validated on representative spacecraft subsystem models.