## Kontakt

Schweizerischer Nationalfonds (SNF)

Wildhainweg 3Postfach

CH-3001 Bern

Tel. +41 31 308 22 22

Fax +41 31 301 30 09

Gesuchsteller/in | Helmert Malte |
---|---|

Nummer | 143698 |

Förderungsinstrument | Projektförderung (Abt. I-III) |

Forschungseinrichtung | Fachbereich Informatik Departement Mathematik und Informatik Universität Basel |

Hochschule | Universität Basel - BS |

Hauptdisziplin | Informatik |

Beginn/Ende | 01.11.2012 - 31.10.2014 |

Bewilligter Betrag | 207'275.00 |

symmetries, artificial intelligence, partial order reduction, automated planning

Lead |
---|

Lay summary |

Many problems in computer science and its applications require searching through a huge number of possible solutions. One particular challenging class of search problems is concerned with One example problem of this kind is In this and many other applications, we are faced with state-space search problems that are far too large to be solved by computers through simple trial-and-error. There is a need for clever search techniques that can quickly zero in on promising solutions while discarding unpromising ones. This project studies One focus of the project is the detection and exploitation of The second focus is on |

Direktlink auf Lay Summary | Letzte Aktualisierung: 21.02.2013 |

Name | Institut |
---|

Name | Institut |
---|

Publikation |
---|

Metis: Arming Fast Downward with Pruning and Incremental Computation |

Heuristics and Symmetries in Classical Planning |

Bounded Intention Planning Revisited |

The Relative Pruning Power of Strong Stubborn Sets and Expansion Core |

Under-Approximation Refinement for Classical Planning |

Efficient Stubborn Sets: Generalized Algorithms and Selection Strategies |

Reducing GUI Test Suites via Program Slicing |

A Generalization of Sleep Sets Based on Operator Sequence Redundancy |

Gruppe / Person | Land |
---|

Felder der Zusammenarbeit |
---|

Technion | Israel (Asien) |

- vertiefter/weiterführender Austausch von Ansätzen, Methoden oder Resultaten - Publikation |

IBM Research Haifa | Israel (Asien) |

- vertiefter/weiterführender Austausch von Ansätzen, Methoden oder Resultaten - Publikation - Austausch von Mitarbeitern |

University of Alberta | Kanada (Nordamerika) |

- vertiefter/weiterführender Austausch von Ansätzen, Methoden oder Resultaten - Publikation - Austausch von Mitarbeitern |

Albert-Ludwigs-Universität Freiburg | Deutschland (Europa) |

- vertiefter/weiterführender Austausch von Ansätzen, Methoden oder Resultaten - Publikation - Forschungsinfrastrukturen - Austausch von Mitarbeitern |

Titel | Art des Beitrags | Titel des Artikels oder Beitrages | Datum | Ort | Beteiligte Personen |
---|

European Conference on Artificial Intelligence | Poster | Bounded Intention Planning Revisited | 18.08.2014 | Prague, Tschechische Republik | Helmert Malte |

24th International Conference on Automated Planning and Scheduling | Vortrag im Rahmen einer Tagung | Efficient Stubborn Sets: Generalized Algorithms and Selection Strategies | 21.06.2014 | Portsmouth, New Hampshire, Vereinigte Staaten von Amerika | Wehrle Martin |

23rd International Conference on Automated Planning and Scheduling | Vortrag im Rahmen einer Tagung | The Relative Pruning Power of Strong Stubborn Sets and Expansion Core | 10.06.2013 | Rome, Italien | Wehrle Martin |

Doctoral Consortium of ICAPS 2013 | Vortrag im Rahmen einer Tagung | Safe Pruning in Optimal State-Space Search | 09.06.2013 | Rom, Italien | Sievers Silvan |

Titel | Jahr |
---|

ICAPS 2013 Best Paper Award for the paper "The Relative Pruning Power of Strong Stubborn Sets and Expansion Core" | 2013 |

Nummer | Titel | Start | Förderungsinstrument |
---|

141021 | Abstraction Heuristics for Planning and Combinatorial Search | 01.05.2012 | Projektförderung (Abt. I-III) |

156057 | Automated Reformulation and Pruning in Factored State Spaces | 01.01.2015 | Projektförderung (Abt. I-III) |

State space search, i.e., search in large, usually implicitly defined transition systems, is one of the foundational techniques in several research areas in computer science and its applications, including automated planning, directed model checking, and many classes of optimization problems. We focus on explicit-state search, where search algorithms consider one state of the transition system at a time, often (but not necessarily) guided by approximate distance information using algorithms such as A*. Moreover, we focus on the optimal setting, where solution algorithms must guarantee that no cheaper solution than the one reported by the algorithm exists. Recent research has shown that in many practical contexts including search domains studied in optimal planning there are fundamental limits to the scalability of classical search algorithms, even under very optimistic assumptions. In this project, we focus on the development of search techniques and state space pruning techniques to extend classical search algorithms to overcome these limitations, by not having to explore search states that are provably redundant.
The above-mentioned scalability issues are due to the fact that as planning tasks grow in size, a combinatorial explosion happens not just for the number of states, but in many cases also for the number of states that are part of optimal solutions, which all need to be considered as possible alternatives by a standard search algorithm in order to prove optimality of the solution. However, in many cases these potential solutions are not interestingly different; for example, they might vary only in the order in which certain independent subgoals are achieved, and a deeper analysis would reveal that all possible orderings are in a formal sense equivalent.
There are two lines of research, originating from the model checking community, that attempt to address this problem by pruning redundant parts of the state space: partial order reduction and symmetry elimination. While a significant body of work on both approaches exists both in planning and in model checking, we believe that this line of research is not yet sufficiently developed and warrants further investigation. In particular, most of the work on partial order reduction in planning has been developed in isolation without sufficient comparison to other approaches. Moreover, several of the key papers that apply partial order reduction to planning and related problems are theoretically flawed, claiming to be complete and/or optimality-preserving when in fact they are not. It is perhaps telling that none of the recent winners or runners-up of the International Planning Competitions (IPC) made use of partial order reduction or symmetry elimination techniques.
In this project, we investigate sound and complete state space pruning techniques for planning based on partial order reduction and symmetry elimination. The overall goals are to better understand the existing state space pruning approaches in the literature and how they are related to each other, to develop new techniques for state space pruning based on the better understanding obtained, and to apply partial order reduction and symmetry elimination to new algorithmic problems where they have not been considered before such as grounding of operators and the computation of invariants.

Schweizerischer Nationalfonds (SNF)

Wildhainweg 3Postfach

CH-3001 Bern

Tel. +41 31 308 22 22

Fax +41 31 301 30 09

Gesuche eingeben und verwalten

E-Mail eintragen und Sie erhalten regelmässig den SNF-Newsletter

© SNF 2016