Projekt

Zurück zur Übersicht

Automated Reformulation and Pruning in Factored State Spaces

Gesuchsteller/in Helmert Malte
Nummer 156057
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.01.2015 - 31.07.2016
Bewilligter Betrag 165'367.00
Alle Daten anzeigen

Keywords (5)

pruning techniques; symmetries; automated planning; problem reformulation; artificial intelligence

Lay Summary (Deutsch)

Lead
Viele Probleme in der Informatik und ihren Anwendungen sind von der folgenden Art: gegeben eine Menge von Aktionen, die wir ausführen können, um die aktuelle Situation zu verändern (zusammen mit einer Beschreibung der Auswirkungen jeder Aktion), finde eine Folge von Aktionen, die ein gegebenes Ziel erreicht. Solche Probleme werden als Zustandsraumsuchprobleme bezeichnet.
Lay summary

Beispiele für Zustandsraumsuchprobleme sind Optimierungsprobleme wie das Problem des Handlungsreisenden (Travelling Salesperson Problem), bei dem die kürzeste Rundreise durch eine Menge von Orten bestimmt werden soll, aber auch abstraktere Suchprobleme wie das automatische Finden von Fehlern in Computerprogrammen, das Aufspüren von Sicherheitslücken in Netzwerkprotokollen oder die Planung der Handlungen von intelligenten Agenten.

Zustandsraumsuchprobleme sind bekanntermassen schwer zu lösen, da in vielen praktisch wichtigen Beispielen eine astronomisch grosse Zahl an möglichen Situationen (Zuständen) berücksichtigt werden muss. Als Beispiel für diese so genannte Zustandsraumexplosion kann ein Spielzeug dienen: der bekannte Zauberwürfel (Rubik's Cube) kann durch Rotation der Seitenflächen in 43'252'003'274'489'856'000 verschiedene Zustände überführt werden. Diese Möglichkeiten systematisch zu generieren würde auf einem modernen Computer mehrere Tausend Jahre Rechenzeit sowie Speicherplatz im Umfang von Millionen von Festplatten erfordern. Eine solche erschöpfende Suche ist also offensichtlich nicht praktikabel.

Daher werden raffiniertere Techniken als blinde Suche benötigen, um trotz Zustandsraumexplosion anspruchsvolle Suchprobleme lösen zu können. Das ARAP-Projekt (Automated Reformulation and Pruning in Factored State Spaces) erforscht Techniken, die automatisch und effizient Symmetrien und andere Regelmässigkeiten in Zustandsräumen erkennen und diese bei der Problemlösung intelligent ausnutzen, um den Lösungsaufwand zu reduzieren. Mit den gewonnenen Methoden können Computer eine gegebene Problembeschreibung automatisch so umformulieren, dass das Problem leichter gelöst werden kann.

Direktlink auf Lay Summary Letzte Aktualisierung: 22.12.2014

Lay Summary (Englisch)

Lead
Many problems in computer science and its applications are of the following kind: given a set of actions that we can perform to change the current situation (together with a description of what the effect of each action is), find a sequence of actions that takes us from the current situation to one that achieves a certain goal. Such problems are known as state-space search problems.
Lay summary

Examples of state-space search problems include all kinds of optimization problems such as the Travelling Salesperson Problem (find the shortest route that visits a given set of locations), the automatic detection of errors in computer programs or security vulnerabilities in network protocols, or the planning of actions performed by an intelligent agent.

State-space search problems are notoriously difficult to solve due to the astronomically large number of possible situations (states) that must be taken into account. To illustrate this point with a toy example, the well-known Rubik's cube puzzle has 43,252,003,274,489,856,000 possible configurations that can be obtained by rotating its faces. Exploring these possibilities exhaustively on a modern computer would require thousands of years of computation time and millions of hard disks worth of storage. This is clearly not practical.

Therefore, more sophisticated techniques than blind search are needed to tackle this so-called state explosion problem. Project ARAP (Automated Reformulation and Pruning in Factored State Spaces) deals with techniques that automatically and efficiently recognize symmetries and other regularities in search problems and intelligently exploit them when solving problems in order to reduce the search effort. This enables the computer to rephrase given problem definitions in a way that allows it to solve the problem more easily.

Direktlink auf Lay Summary Letzte Aktualisierung: 22.12.2014

Verantw. Gesuchsteller/in und weitere Gesuchstellende

Mitarbeitende

Publikationen

Publikation
Decoupled Strong Stubborn Sets
Gnad Daniel, Wehrle Martin, Hoffmann Jörg (2016), Decoupled Strong Stubborn Sets, in Proceedings of the 25th International Joint Conference on Artificial Intelligence, AAAI Press, Palo Alto, CA, USA.
Graph-Based Factorization of Classical Planning Problems
Wehrle Martin, Sievers Silvan, Helmert Malte (2016), Graph-Based Factorization of Classical Planning Problems, in Proceedings of the 25th International Joint Conference on Artificial Intelligence, AAAI Press, Palo Alto, CA, USA.
Sleep Sets Meet Duplicate Elimination
Alkhazraji Yusra, Wehrle Martin (2016), Sleep Sets Meet Duplicate Elimination, in Proceedings of the 9th Annual Symposium on Combinatorial Search (SoCS 2016), AAAI Press, Palo Alto, CA, USA.
Structural Symmetries for Fully Observable Nondeterministic Planning
Winterer Dominik, Wehrle Martin, Katz Michael (2016), Structural Symmetries for Fully Observable Nondeterministic Planning, in Proceedings of the 25th International Joint Conference on Artificial Intelligence, AAAI Press, Palo Alto, CA, USA.
A Normal Form for Classical Planning Tasks
Pommerening Florian, Helmert Malte (2015), A Normal Form for Classical Planning Tasks, in Proceedings of the 25th International Conference on Automated Planning and Scheduling (ICAPS 2015), AAAI Press, Palo Alto, CA, USA.
An Empirical Case Study on Symmetry Handling in Cost-Optimal Planning as Heuristic Search
Sievers Silvan, Wehrle Martin, Helmert Malte, Katz Michael (2015), An Empirical Case Study on Symmetry Handling in Cost-Optimal Planning as Heuristic Search, in Proceedings of the 38th Annual German Conference on Artificial Intelligence (KI 2015), Springer Verlag, Heidelberg.
Factored Symmetries for Merge-and-Shrink Abstractions
Sievers Silvan, Wehrle Martin, Helmert Malte, Shleyfman Alexander, Katz Michael (2015), Factored Symmetries for Merge-and-Shrink Abstractions, in Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI 2015), AAAI Press, Palo Alto, CA, USA.
Integrating Partial Order Reduction and Symmetry Elimination for Cost-Optimal Classical Planning
Wehrle Martin, Helmert Malte, Shleyfman Alexander, Katz Michael (2015), Integrating Partial Order Reduction and Symmetry Elimination for Cost-Optimal Classical Planning, in Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI 2015), AAAI Press, Palo Alto, CA, USA.
PDDL+ Planning with Hybrid Automata: Foundations of Translating Must Behavior
Bogomolov Sergiy, Magazzeni Daniele, Minopoli Stefano, Wehrle Martin (2015), PDDL+ Planning with Hybrid Automata: Foundations of Translating Must Behavior, in Proceedings of the 25th International Conference on Automated Planning and Scheduling (ICAPS 2015), AAAI Press, Palo Alto, CA, USA.
Stubborn Sets for Fully Observable Nondeterministic Planning
Winterer Dominik, Mattmüller Robert, Wehrle Martin (2015), Stubborn Sets for Fully Observable Nondeterministic Planning, in Proceedings of the ICAPS 2015 Workshop on Model Checking and Automated Planning (MoCHAP), ICAPS 2015, Jerusalem, Israel.

Zusammenarbeit

Gruppe / Person Land
Formen der Zusammenarbeit
Prof. Daniele Magazzeni, AI Planning Group, King's College London Grossbritannien und Nordirland (Europa)
- vertiefter/weiterführender Austausch von Ansätzen, Methoden oder Resultaten
- Publikation
- Austausch von Mitarbeitern
Dr. Michael Katz, Automated Decision Making, IBM Research Haifa Israel (Asien)
- vertiefter/weiterführender Austausch von Ansätzen, Methoden oder Resultaten
- Publikation
- Austausch von Mitarbeitern
Dr. Sergiy Bogomolov, Design and Analysis of Concurrent and Embedded Systems, IST Austria Oesterreich (Europa)
- vertiefter/weiterführender Austausch von Ansätzen, Methoden oder Resultaten
- Publikation
Prof. Jörg Hoffmann, Foundations of Artificial Intelligence Group, Saarland University Deutschland (Europa)
- vertiefter/weiterführender Austausch von Ansätzen, Methoden oder Resultaten
- Publikation
- Austausch von Mitarbeitern
Prof. Carmel Domshlak, Industrial Engineering and Management, Technion Israel (Asien)
- vertiefter/weiterführender Austausch von Ansätzen, Methoden oder Resultaten
- Publikation
Prof. Bernhard Nebel, Foundations of Artificial Intelligence Group, University of 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
25th International Joint Conference on Artificial Intelligence (IJCAI 2016) Poster Graph-Based Factorization of Classical Planning Problems 09.07.2016 New York, NY, Vereinigte Staaten von Amerika Helmert Malte;
Ninth International Symposium on Combinatorial Search (SoCS 2016) Vortrag im Rahmen einer Tagung Sleep Sets Meet Duplicate Elimination 06.07.2016 Tarrytown, NY, Vereinigte Staaten von Amerika Helmert Malte;
29th AAAI Conference on Artificial Intelligence (AAAI 2015) Poster Factored Symmetries for Merge-and-Shrink Abstractions 25.01.2015 Austin, TX, Vereinigte Staaten von Amerika Helmert Malte;


Auszeichnungen

Titel Jahr
Best Paper Award of the Ninth International Symposium on Combinatorial Search (SoCS 2016) for the paper "Sleep Sets Meet Duplicate Elimination" 2016

Verbundene Projekte

Nummer Titel Start Förderungsinstrument
159377 Reasoning about Plans and Heuristics for Planning and Combinatorial Search 01.05.2015 Projektförderung (Abt. I-III)
141021 Abstraction Heuristics for Planning and Combinatorial Search 01.05.2012 Projektförderung (Abt. I-III)
143698 Safe Pruning in Optimal State-Space Search 01.11.2012 Projektförderung (Abt. I-III)

Abstract

Automated planning is the problem of finding a sequence of state transitions (plan) that transforms the initial state of a transition system into a desired goal state or proving that no such plan exists. It is a fundamental problem in artificial intelligence, where it is studied by the planning and scheduling and heuristic search communities. We focus on (domain-independent) classical planning, which is concerned with algorithms that are generally applicable, rather than being tailored towards one particular class of transition systems. Classical planning is challenging due to the state explosion problem: transition systems of interest frequently include 10^100 or more states.The last decades have seen several breakthroughs in the scalability of classical planning algorithms, chiefly through the development of accurate distance estimators for general search methods such as the A* algorithm. However, there is mounting evidence that this line of research is reaching a saturation point, and that further improvements in the scalability of classical planners will have to be reached through other means than better distance estimators.In the project "Safe Pruning in Optimal State-Space Search" (SPOSSS), we targeted this challenge for the case of optimal planning with a focus on partial-order reduction, a method for eliminating redundancies due to transitions that can be interleaved in many ways. This follow-up proposal widens the scope to also include satisficing planning and to a much more general class of pruning and problem transformation methods than partial-order reduction. The objectives of the project are:O1: to advance the theory and practice of symmetry elimination for planning. While previous work on symmetries focused on pruning symmetric states within a search algorithm, we will apply a rigorous theory of symmetry elimination to other aspects of state-space search, such as grounding, invariant synthesis, and the automatic computation of abstractions.O2: to develop general and efficient methods for dominance pruning in transition systems. SPOSSS focused on equivalence pruning, which ignores transition sequences s that can be shown to have exactly the same overall effect as another sequence t. We will investigate more general methods that can also detect and exploit situations where s is strictly less useful than t.O3: to develop soft pruning methods for satisficing planning. Existing pruning methods designed for optimal planning are hampered by the necessity to be absolutely certain that a pruned transition is not useful. Instead of all-or-nothing pruning decisions, soft pruning methods may decide to deprioritize transitions that are very unlikely to be important for reaching a solution but cannot be ruled out completely.O4: to develop problem reformulation methods that automatically enrich the description of a transition system to make it more amenable to the distance estimation techniques used in modern planning algorithms, and to abstract away parts of the system that can be solved without search.
-