Publication Details

Enhancing the Anytime Behaviour of Mixed CSP-Based Planning

by Guettier, C. and Yorke-Smith, N

in Proceedings of ICAPS’05 Workshop on Planning under Uncertainty for Autonomous Systems pp. 29-38,

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 planning 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 anytime solving of a planning problem under uncertainty that arises from online aerospace sub-system control. We examine an existing constraint model-based approach of the problem as a mixed constraint satisfaction problem (mixed CSP), an extension of classical CSP that accounts for uncontrollable parameters. We propose two enhancements to the existing decomposition algorithm: heuristics for selecting the next uncertain environment to decompose, and solving for incrementally longer planning horizons. We evaluate these enhancements empirically, showing that a heuristic on uncertainty analogous to `first fail’ gives the best performance, improving the anytime behaviour w.r.t. robustness to uncertainty. Further, we show that incremental horizon planning provides effective anytime behaviour w.r.t. plan executability, and that it can be combined with the decomposition heuristics.

Electronic Copies

Adobe PDF

BibTeX

EndNote

AIC Personnel

	Name	Title	E-mail
	Yorke-Smith, Neil	Computer Scientist