Robert P. Goldman, David J. Musliner, Kurt D. Krebsbach, Mark S. Boddy
This paper describes Dynamic Abstraction Planning (DAP), an abstraction planning technique that improves the efficiency of state-enumeration planners for real-time embedded systems such as CIRCA. Abstraction is used to remove detail from the state representation, reducing both the size of the state space that must be explored to produce a plan and the size of the resulting plan. The intuition behind this approach is simple: in some situations, certain world features are important, while in other situations those same features are not important. By automatically selecting the appropriate level of abstraction at each step during the planning process, DAP can significantly reduce the size of the search space. Furthermore, the planning process can supply initial plans that preserve safety but might, on further refinement, do a better job of goal achievement. DAP can also terminate with an executable abstract plan, which may be much smaller than the corresponding plan expanded to precisely-defined states. Preliminary results show dramatic improvements in planning speed and scalability.