  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.
