Unavoidable deadends in deterministic partially observable contingent planning

Abstract Traditionally, a contingent plan, branching on the observations an agent obtains throughout plan execution, must reach a goal state from every possible initial state. However, in many real world problems, no such plan exists. Yet, there are plans that reach the goal from some initial states only. From the other initial states, they eventually reach a deadend—a state from which the goal can not be achieved. Deadends that cannot be avoided by resorting to a different plan, are called unavoidable deadends. In this paper we study planning with unavoidable deadends in belief space. We distinguish between two types of such deadends, and adapt offline and online contingent planners to identify and handle unavoidable deadends, using two approaches—an active approach that begins by distinguishing between the solvable and deadend states, and a lazy approach, that plans to achieve the goal, identifying deadends as they occur. We empirically analyze how each approach performs in different cases.

Authors

• Lera Shtutland
• Dorin Shmaryahu
• Guy Shani MSAI, Microsoft & Ben Gurion University of the Negev

Keywords

• Deadends
• Contingent planning
• Partial observability
• Belief space