Abstract
This paper introduces a framework for exploiting structural symmetries in fully observable nondeterministic (FOND) planning. By generalizing symmetry reduction techniques from classical planning, the authors develop the CLAO algorithm, which operates on a canonical state space. Experimental results on IPC-08 benchmarks demonstrate that CLAO significantly reduces search space and improves task coverage with minimal computational overhead.
Introduction
Fully Observable Nondeterministic (FOND) planning is a critical framework for agents operating in uncertain environments where actions can have multiple outcomes. However, the exponential growth of the state space often renders large-scale problems intractable. This paper addresses this challenge by generalizing symmetry reduction—a technique successful in classical planning—to the FOND domain. The authors introduce the CLAO* algorithm, which leverages structural symmetries to prune the search space, leading to significant performance gains.
Methods
The authors propose a formal framework for structural symmetries in FOND planning. A symmetry must map an operator to another such that all potential outcomes are also mapped symmetrically. To avoid the high cost of finding all symmetries, they employ a greedy approach to map states to a canonical representative.
The CLAO algorithm is a modification of the standard LAO search that operates on a "Canonical Transition System." By searching this reduced space, the algorithm avoids redundant computations. Finally, a policy reconstruction step "unfolds" the canonical policy back into a concrete one for the original problem.
Key Results
Evaluation on IPC-08 FOND benchmarks revealed that symmetries are pervasive, appearing in 535 out of 660 tasks (~81%). The precomputation of these symmetries is highly efficient, typically finishing in under 10 seconds for over 90% of cases.
CLAO solved 24 more tasks than the baseline FD-LAO. Notably, the authors' base implementation, FD-LAO*, itself established a new state-of-the-art by solving 57 more tasks than the previous leading planner, myND. In specific domains like FOREST, symmetry reduction achieved an exponential reduction in the state space visited, resulting in more compact and manageable policies.
Limitations and Future Work
While the greedy canonical mapping is efficient, it is not exhaustive and may miss some symmetries. Future research should explore the synergy between symmetry reduction and other pruning techniques, such as partial order reduction or stubborn sets, to further enhance the efficiency of FOND planning systems.
Summary updated