APROPOS 2 : Approximate Probabilistic Planning Out of Stochastic Satisfiability
Stephen M. Majercik · 2002
The probabilistic contingent planner ZANDER (Majercik 2000) operates by converting the planning problem to a stochastic satisfiability problem and solving that problem instead. Although ZANDER can solve some simple standard test problems more efficiently than three alternative approaches to probabilistic planing, ZANDER is currently confined to small problems. We introduce APROPOS 2, a probabilistic contingent planner based on ZANDER that produces an approximate contingent plan and improves that plan as time permits. APROPOS 2 does this by considering the most probable situations facing the agent and constructing a plan, if possible, that succeeds under those circumstances. Given more time, less likely situations are considered and the plan is revised if necessary. In some cases, a plan constructed to address a relatively low percentage of possible situations will succeed for situations not explicitly considered as well, and may return an optimal or near-optimal plan. This means that APROPOS 2 can sometimes find optimal plans faster than ZANDER. And the anytime quality of APROPOS 2 means that suboptimal plans could be efficiently derived in larger time-critical domains where ZANDER might not have time to calculate the optimal plan. We describe some preliminary experimental results and suggest further work needed to bring APROPOS 2 closer to attacking real-world problems.