Planning to plan under uncertainty: An architecture for reactive meta-planning

This dissertation introduces and evaluates a new approach to reasoning about uncertainty in planning systems. Current planning paradigms reduce the planning horizon as uncertainty increases; even to the point where there is no planning ahead in highly uncertain environments: reactive planning. This dissertation posits that more can be obtained from planning ahead than just a plan. In particular, the exercise of planning allows an agent to learn about characteristics of a planning problem that are useful for planning or re-planning in similar situations. One potential use of pre-planning is to train the planner to recognize problem appropriate strategies using a 5 step process: (1) generate plans for problems that are likely to arise, (2) simulate plan execution, (3) reason at the meta-level to discover relationships between the planning strategy, problem characteristics, and results, (4) record these relationships, and (5) map those characteristics during subsequent planning to select a planning strategy reactively in an attempt to optimize plan performance. This approach is called Reactive Meta-Planning (RMP). An architecture is presented to support RMP planning, execution simulation, and meta-planning. A testbed instance of the RMP architecture was implemented in an air tasking order domain. Planning strategies in this domain are defined as a priority order of asset allocation based on asset characteristics. A series of experiments was conducted that varied problem attributes, planning strategies, execution environment uncertainties, and prediction algorithms. Pre-planning results were used to determine which single strategy yielded the best average performance over all training problems: the baseline strategy. When subsequently planning for similar problems, the problem characteristics were used to predict which strategy would produce the best results. RMP successfully identified robust baseline strategies (i.e., problem appropriate strategy for the class of problems). A combination of inaccurate predictors and robust baselines limited the ability to select problem appropriate strategies for individual problems. This suggests that identifying appropriate characteristics of the planning problem and employing a good classifier (predictor) are critical to successful application of the RMP approach.