[Zurück]

M. Suda:
"Duality in STRIPS planning";
Vortrag: 8th Workshop on Heuristics and Search for Domain-independent Planning (HSDIP), London; 13.06.2016; in: "8th Workshop on Heuristics and Search for Domain-independent Planning (HSDIP), London, UK, June 13, 2016, Proceedings", (2016), S. 21 - 27.

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.

STRIPS, regression, progression, duality

http://publik.tuwien.ac.at/files/publik_255028.pdf