Compact Belief State Representation for Task Planning
This work addresses a bottleneck in task planning under uncertainty, offering an incremental improvement for domains with state uncertainty.
The paper tackles the intractability of belief state representations in probabilistic task planning by introducing a novel representation called AOBS, which uses cartesian product and union operations to achieve more compact scaling than Binary Decision Diagrams in most simulated cases.
Task planning in a probabilistic belief state domains allows generating complex and robust execution policies in those domains affected by state uncertainty. The performance of a task planner relies on the belief state representation. However, current belief state representation becomes easily intractable as the number of variables and execution time grows. To address this problem, we developed a novel belief state representation based on cartesian product and union operations over belief substates. These two operations and single variable assignment nodes form And-Or directed acyclic graph of Belief State (AOBS). We show how to apply actions with probabilistic outcomes and measure the probability of conditions holding over belief state. We evaluated AOBS performance in simulated forward state space exploration. We compared the size of AOBS with the size of Binary Decision Diagrams (BDD) that were previously used to represent belief state. We show that AOBS representation is not only much more compact than a full belief state but it also scales better than BDD for most of the cases.