Replanning in Domains with Partial Information and Sensing Actions
  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, presenting a new planner:
SDR (Sample, Determinize, Replan). At each step we generate a solution plan to
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-based approach for conformant planning introduced by Palacios and
Geffner. The state of the classical planning problem generated in this approach
captures the belief state of the agent in the original problem. Unfortunately,
when this method is applied to planning problems with sensing, it yields a
non-deterministic planning problem that is typically very large. Our main
contribution is the introduction of state sampling techniques for overcoming
these two problems. In addition, we introduce a novel, lazy, regression-based
method for querying the agents belief state during run-time. We provide a
comprehensive experimental evaluation of the planner, showing that it scales
better than the state-of-the-art CLG planner on existing benchmark problems,
but also highlighting its weaknesses with new domains. We also discuss its
theoretical guarantees.
