Causal Belief Decomposition for Planning with Sensing: Completeness Results and Practical Approximation
This work addresses computational efficiency challenges in AI planning systems for domains with high uncertainty, though it builds incrementally on existing width-based methods.
The authors tackled the intractable belief tracking problem in planning with sensing by introducing a new decomposition scheme with improved space complexity (exponential in causal width rather than problem width) and a fast approximation algorithm. Their approach achieved state-of-the-art real-time performance in domains like Minesweeper, Battleship, and Wumpus.
Belief tracking is a basic problem in planning with sensing. While the problem is intractable, it has been recently shown that for both deterministic and non-deterministic systems expressed in compact form, it can be done in time and space that are exponential in the problem width. The width measures the maximum number of state variables that are all relevant to a given precondition or goal. In this work, we extend this result both theoretically and practically. First, we introduce an alternative decomposition scheme and algorithm with the same time complexity but different completeness guarantees, whose space complexity is much smaller: exponential in the causal width of the problem that measures the number of state variables that are causally relevant to a given precondition, goal, or observable. Second, we introduce a fast, meaningful, and powerful approximation that trades completeness by speed, and is both time and space exponential in the problem causal width. It is then shown empirically that the algorithm combined with simple heuristics yields state-of-the-art real-time performance in domains with high widths but low causal widths such as Minesweeper, Battleship, and Wumpus.