Causal Belief Decomposition for Planning with Sensing: Completeness
  Results and Practical Approximation
  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.
