Projekt

Zurück zur Übersicht

Safe Pruning in Optimal State-Space Search

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
Alle Daten anzeigen

Keywords (4)

symmetries, artificial intelligence, partial order reduction, automated planning

Lay Summary (Englisch)

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 finding paths in state spaces: given a current situation A in which there are many different courses of actions we can take, how can we find a sequence of actions that takes us to a desired situation B?

One example problem of this kind is genome rearrangement: what is a minimal sequence of mutations that we would need to apply to the genome of organism X to obtain the genome of organism Y? Answering such questions is an important part of phylogenetics, the study of evolutionary relationships between organisms based on their genetic information.

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 pruning techniques for problems of this kind, i.e. methods that reliably identify and discard unpromising solutions to search problems in order to avoid wasting time on their exploration.

One focus of the project is the detection and exploitation of symmetries, i.e., the identification of groups of states that are in a formal sense equivalent to each other. There is no need to consider more than one state from each group of symmetric states during search, and hence eliminating symmetric states can greatly reduce the search effort in many cases.

The second focus is on partial-order reduction, techniques that determine situations in which the order of achieving certain subproblems does not matter. When this is the case, a search method can restrict attention to only one possible order. As with symmetry elimination, partial-order reduction can greatly reduce the search effort in many cases.

Direktlink auf Lay Summary Letzte Aktualisierung: 21.02.2013

Verantw. Gesuchsteller/in und weitere Gesuchstellende

Mitarbeitende

Publikationen

Publikation
Metis: Arming Fast Downward with Pruning and Incremental Computation
Alkhazraji Yusra, Katz Michael, Mattmüller Robert, Pommerening Florian, Shleyfman Alexander, Wehrle Martin (2014), Metis: Arming Fast Downward with Pruning and Incremental Computation, n/a, n/a.
Heuristics and Symmetries in Classical Planning
Shleyfman Alexander, Katz Michael, Helmert Malte, Sievers Silvan, Wehrle Martin (2015), Heuristics and Symmetries in Classical Planning, in Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence (AAAI 2015), Austin, TX, USAAAAI Press, Palo Alto, CA, USA.
Bounded Intention Planning Revisited
Sievers Silvan, Wehrle Martin, Helmert Malte (2014), Bounded Intention Planning Revisited, in Proceedings of the 21st European Conference on Artificial Intelligence (ECAI 2014), Prague, Czech RepublicIOS Press, 1013 BG Amsterdam, the Netherlands.
The Relative Pruning Power of Strong Stubborn Sets and Expansion Core
Wehrle Martin, Helmert Malte, AlkhazrajiYusra, Mattmüller Robert (2013), The Relative Pruning Power of Strong Stubborn Sets and Expansion Core, in Proceedings of the 23rd International Conference on Automated Planning and Scheduling (ICAPS 2013), Rome, ItalyAAAI Press, Palo Alto, CA, USA.
Under-Approximation Refinement for Classical Planning
Heusner Manuel, Wehrle Martin, Pommerening Florian, Helmert Malte (2014), Under-Approximation Refinement for Classical Planning, in Proceedings of the 24th International Conference on Automated Planning and Scheduling (ICAPS 2014), Portsmouth, NH, USAAAAI Press, Palo Alto, CA, USA.
Efficient Stubborn Sets: Generalized Algorithms and Selection Strategies
Wehrle Martin, Helmert Malte (2014), Efficient Stubborn Sets: Generalized Algorithms and Selection Strategies, in Proceedings of the 24th International Conference on Automated Planning and Scheduling (ICAPS 2014), Portsmouth, NH, USAAAAI Press, Palo Alto, CA, USA.
Reducing GUI Test Suites via Program Slicing
Arlt Stephan, Podelski Andreas, Wehrle Martin (2014), Reducing GUI Test Suites via Program Slicing, in International Symposium on Software Testing and Analysis (ISSTA 2014), San Jose, CA, USAACM, New York, NY, USA.
A Generalization of Sleep Sets Based on Operator Sequence Redundancy
Holte Robert C., Alkhazraji Yusra, Wehrle Martin (2015), A Generalization of Sleep Sets Based on Operator Sequence Redundancy, in Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI 2015), Austin, TX, USAAAAI Press, Palo Alto, CA, USA.

Zusammenarbeit

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

Wissenschaftliche Veranstaltungen

Aktiver Beitrag

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


Auszeichnungen

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

Verbundene Projekte

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)

Abstract

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.