Safe Pruning in Optimal State-Space Search
Third-party funded project
Project title Safe Pruning in Optimal State-Space Search
Principal Investigator(s) Helmert, Malte
Project Members Sievers, Silvan
Wehrle, Martin
Organisation / Research unit Departement Mathematik und Informatik / Artificial Intelligence (Helmert)
Project Website
Project start 01.11.2012
Probable end 31.10.2014
Status Completed

This project investigates pruning techniques in optimal state space planning. In particular, we consider techniques based on partial order reduction and symmetry reduction.

Partial order reduction has been originally proposed in the area of computer aided verification. The basic idea is to tackle the state explosion problem by avoiding a blow-up that is induced by independent actions. Recent results have shown that such techniques can be powerful in the area of automated planning as well. In SPOSSS, we investigate partial order reduction techniques for computer aided verification and for planning both theoretically and practically.

Similar to partial order reduction, techniques based on symmetry reduction have been originally proposed in the area of computer aided verification. In contrast to partial order reduction which exploits symmetric action sequences, techniques based on symmetry reduction compute a quotient structure of the state space, where symmetrical states are considered equivalent. In SPOSSS, we investigate symmetry reduction techniques and their applications to planning.

Financed by Swiss National Science Foundation (SNSF)

Cooperations ()

  ID Kreditinhaber Kooperationspartner Institution Laufzeit - von Laufzeit - bis
2811778  Helmert, Malte  Fox, Maria  King's College, London  01.11.2012  31.07.2016 
2811779  Helmert, Malte  Rosenschein, Jeffrey  The Hebrew University of Jerusalem  01.11.2012  31.10.2014 
2811780  Helmert, Malte  Podelski, Andreas  Albert-Ludwigs-Universität Freiburg  01.11.2012  31.01.2017 

MCSS v5.8 PRO. 0.342 sec, queries - 0.000 sec ©Universität Basel  |  Impressum   |