Unavoidable deadends in deterministic partially observable contingent planning

• Published in: Autonomous agents and multi-agent systems 2023-06, Vol.37 (1), Article 3
• Main Authors: Shtutland, Lera, Shmaryahu, Dorin, Brafman, Ronen I., Shani, Guy
• Format: Article
• Language: English
• Subjects: Artificial Intelligence; Computer Science; Computer Systems Organization and Communication Networks; Software Engineering/Programming and Operating Systems; User Interfaces and Human Computer Interaction
• ISSN: 1387-2532; 1573-7454
• DOI: 10.1007/s10458-022-09570-w

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.