Optimal Limited Contingency Planning
This addresses the need for simpler, verifiable plans in domains like safety-critical systems or human-understandable decision-making, though it appears incremental as it builds on existing POMDP frameworks.
The paper tackles the problem of finding optimal plans with a limited number of branches for applications requiring simplicity or verification, presenting an any-time algorithm for optimal k-contingency planning (OKP) that is the first optimal method not based on explicit enumeration, with experimental results on simple test cases.
For a given problem, the optimal Markov policy can be considerred as a conditional or contingent plan containing a (potentially large) number of branches. Unfortunately, there are applications where it is desirable to strictly limit the number of decision points and branches in a plan. For example, it may be that plans must later undergo more detailed simulation to verify correctness and safety, or that they must be simple enough to be understood and analyzed by humans. As a result, it may be necessary to limit consideration to plans with only a small number of branches. This raises the question of how one goes about finding optimal plans containing only a limited number of branches. In this paper, we present an any-time algorithm for optimal k-contingency planning (OKP). It is the first optimal algorithm for limited contingency planning that is not an explicit enumeration of possible contingent plans. By modelling the problem as a Partially Observable Markov Decision Process, it implements the Bellman optimality principle and prunes the solution space. We present experimental results of applying this algorithm to some simple test cases.