Enhancing the Anytime Behaviour of Mixed CSP-Based Planning

Guettier, C. and Yorke-Smith, N. Enhancing the Anytime Behaviour of Mixed CSP-Based Planning. Proceedings of ICAPS'05 Workshop on Planning under Uncertainty for Autonomous Systems. Monterey, CA, June 2005.

Abstract: An algorithm with the anytime property has an approximate solution always available; and the longer the algorithm runs, the better the solution becomes. Anytime solving is important in domains such as aerospace, where time for reasoning is limited and a viable (if suboptimal) course of action must be always available. In this paper we study the anytime behaviour of solving a mixed CSP, an extension of classical CSP that accounts for uncontrollable parameters, using a benchmark problem from aerospace sub-system control. We propose two enhancements to the existing decomposition algorithm: heuristics for selecting the next uncertain environment to decompose, and solving of incrementally larger subproblems. We evaluate these enhancements empirically, showing that a heuristic on uncertainty analogous to `first fail' gives the best performance. We also show that incremental subproblem solving provides effective anytime behaviour, and can be combined with the decomposition heuristics.

An earlier version of this paper appeared at the CP'04 Workshop on Constraint Solving Under Change and Uncertainty.

PDF (405K) | Bibtex entry