Replanning in Domains with Partial Information and Sensing Actions
Guy Shani and Ronen Brafman
Replanning via determinization is a recent, popular approach for online planning in MDPs. In this paper we adapt this idea to classical, non-stochastic domains with partial information and sensing actions. At each step we generate a candidate plan which solves a classical planning problem induced by the original problem. We execute this plan as long as it is safe to do so. When this is no longer the case, we replan. The classical planning problem we generate is based on the translation approach introduced by T0, in which the classical state captures the knowledge state of the agent. However, this latter method introduces non-determinism when applied to sensing actions, and can generate very large classical problem instances. We overcome these problems by using state sampling. State sampling is used to reduce the uncertainty about the initial state and to determinize the outcome of sensing actions. Our planner also introduces a new lazy, history-based method for querying the belief state. The resulting planner is competitive with the state-of-the-art contingent planner CLG, and reaches the goal state much faster in almost all domains tested.