Duality in STRIPS planning
This work addresses a foundational problem in AI planning by providing a theoretical duality that connects forward and backward search, potentially leading to new algorithms and benchmarks, though it is incremental in nature.
The authors introduced a duality mapping for STRIPS planning tasks, proving that swapping initial/goal conditions and action components yields a dual version solvable if and only if the original is, enabling transfer between forward and backward search approaches. Experiments showed dual versions of IPC benchmarks are often difficult for modern planners, presenting a new challenge, but cases where they are easier demonstrate practical utility.
We describe a duality mapping between STRIPS planning tasks. By exchanging the initial and goal conditions, taking their respective complements, and swapping for every action its precondition and delete list, one obtains for every STRIPS task its dual version, which has a solution if and only if the original does. This is proved by showing that the described transformation essentially turns progression (forward search) into regression (backward search) and vice versa. The duality sheds new light on STRIPS planning by allowing a transfer of ideas from one search approach to the other. It can be used to construct new algorithms from old ones, or (equivalently) to obtain new benchmarks from existing ones. Experiments show that the dual versions of IPC benchmarks are in general quite difficult for modern planners. This may be seen as a new challenge. On the other hand, the cases where the dual versions are easier to solve demonstrate that the duality can also be made useful in practice.