Flexible and Scalable Partially Observable Planning with Linear Translations

The problem of on-line planning in partially observable set-tings involves two problems: keeping track of beliefs about the environment and selecting actions for achieving goals. While the two problems are computationally intractable in the worst case, significant progress has been achieved in recent years through the use of suitable reductions. In particular, the state-of-the-art CLG planner is based on a translation that maps deterministic partially observable problems into fully observable non-deterministic ones. The translation, which is quadratic in the number of problem fluents and gets rid of the belief tracking problem, is adequate for most bench-marks, and it is in fact complete for problems that have width 1. The more recent K-replanner uses translations that are lin-ear, one for keeping track of beliefs and the other for select-ing actions using off-the-shelf classical planners. As a result, the K-replanner scales up better but it is not as general. In this work, we combine the benefits of the two approaches – the scope of the CLG planner and the efficiency of the K-replanner. The new planner, called LW1, is based on a trans-lation that is linear but complete for width-1 problems. The scope and scalability of the new planner is evaluated exper-imentally by considering the existing benchmarks and new problems