APROPOS2: Approximate Probabilistic Planning out of Stochastic Satisfiability

Contents

The probabilistic contingent planner ZANDER 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 APROPOS2, 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 APROPOS2 can sometimes find optimal plans faster than ZANDER. And the anytime quality of APROPOS2 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 APROPOS2 closer to attacking real-world problems.