Projekt

Zurück zur Übersicht

Abstraction Heuristics for Planning and Combinatorial Search

Gesuchsteller/in Helmert Malte
Nummer 141021
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.05.2012 - 30.04.2015
Bewilligter Betrag 273'665.70
Alle Daten anzeigen

Keywords (5)

automated planning; abstraction; heuristic search; artificial intelligence; combinatorial search

Lay Summary (Englisch)

Lead
Lay summary

Computers are often required to autonomously decide which actions to take in order to reach a desired goal of their user. Typical examples of this include satellites in space which must decide which of their sensors to use and how to use them in order to gather a maximal amount of interesting scientific data; intelligent manufacturing plants which must decide how to control conveyor belts and factory robots in order to fulfil the given orders as quickly and efficiently as possible; or logistics software which decides how to best route a fleet of vehicles on a road network in order to perform their delivery tasks in a timely and fuel-efficient manner.

All these are examples of planning problems. Automated planning is a traditional research area in artificial intelligence that is concerned with general solutions to planning problems: developing a single planning system that can solve all kinds of planning problems without requiring any reprogramming when applied to a new type of problem.

Most successful automated planning systems are based on the idea of heuristic search: they systematically explore the set of possible plans that could lead towards the desired goal, and this exploration is guided by a heuristic function which gives estimates on how far away any given situation is from the goal. A major research challenge in this context is coming up with useful heuristic functions.

In this project we explore ideas for heuristic functions based on abstraction, which in this context means solving a simpler (smaller) problem than the actual planning problem in order to get insights about how to best solve the actual planning problem. Specificially, we are interested in three aspects of abstraction heuristics:

1. To advance the theory of abstraction heuristics in order to improve our theoretical understanding of their capabilities, limitations and relationship to other approaches to planning.

2. To develop improved abstraction heuristics for general planning problems that allow us to solve more complex planning problems than the current state of the art is capable of.

3. To transfer our newly developed abstraction heuristics to other application areas of heuristic search, such as sequence analysis problems in bioinformatics.

Direktlink auf Lay Summary Letzte Aktualisierung: 21.02.2013

Verantw. Gesuchsteller/in und weitere Gesuchstellende

Mitarbeitende

Publikationen

Publikation
From Non-Negative to General Operator Cost Partitioning
Pommerening Florian, Helmert Malte, Röger Gabriele, Seipp Jendrik (2015), From Non-Negative to General Operator Cost Partitioning, in Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI 2015), Austin, TX, USA.
Linear Programming for Heuristics in Optimal Planning
Röger Gabriele, Pommerening Florian (2015), Linear Programming for Heuristics in Optimal Planning, in Proceedings of the AAAI-2015 Workshop on Planning, Search, and Optimization.
New Optimization Functions for Potential Heuristics
Seipp Jendrik, Pommerening Florian, Helmert Malte (2015), New Optimization Functions for Potential Heuristics, in Proceedings of the 25th International Conference on Automated Planning and Scheduling (ICAPS 2015), Jerusalem, Israel.
On the Expressive Power of Non-Linear Merge-and-Shrink Representations
Helmert Malte, Röger Gabriele, Sievers Silvan (2015), On the Expressive Power of Non-Linear Merge-and-Shrink Representations, in Proceedings of the 25th International Conference on Automated Planning and Scheduling (ICAPS 2015), Jerusalem, Israel.
Downward pattern refinement for timed automata
Wehrle Martin, Kupferschmid Sebastian (2014), Downward pattern refinement for timed automata, in International Journal on Software Tools for Technology Transfer, 16.
Exploiting the Rubik’s cube 12-edge PDB by combining partial pattern databases and Bloom filters
Sturtevant Nathan R., Felner Ariel, Helmert Malte (2014), Exploiting the Rubik’s cube 12-edge PDB by combining partial pattern databases and Bloom filters, in Proceedings of the Seventh Annual Symposium on Combinatorial Search (SoCS 2014), Prague, Czech Republic.
Merge-and-Shrink Abstraction: A Method for Generating Lower Bounds in Factored State Spaces
Helmert Malte, Haslum Patrik, Hoffmann Jörg, Nissim Raz (2014), Merge-and-Shrink Abstraction: A Method for Generating Lower Bounds in Factored State Spaces, in Journal of the ACM, 61(3), 16:1-16:63.
Abstraction-Based Guided Search for Hybrid Systems
Bogomolov Sergiy, Donzé Alexandre, Frehse Goran, Grosu Radu, Johnson Taylor T., Ladan Hamed, Podelski Andreas, Wehrle Martin (2013), Abstraction-Based Guided Search for Hybrid Systems, in Proceedings of the International SPIN Symposium on Model Checking of Software (SPIN 2013), Stony Brook, New York, USA.
Additive Counterexample-guided Cartesian Abstraction Refinement
Seipp Jendrik, Helmert Malte (2013), Additive Counterexample-guided Cartesian Abstraction Refinement, in AAAI 2013 Late-Breaking Papers, Bellevue, Washington, USA.
Counterexample-Guided Cartesian Abstraction Refinement
Seipp Jendrik, Helmert Malte (2013), Counterexample-Guided Cartesian Abstraction Refinement, in Proceedings of the 23rd International Conference on Automated Planning and Scheduling (ICAPS 2013), Rome, Italy.
Getting the Most Out of Pattern Databases for Classical Planning
Pommerening Florian, Röger Gabriele, Helmert Malte (2013), Getting the Most Out of Pattern Databases for Classical Planning, in Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI 2013), Beijing, China.
Stronger Abstraction Heuristics Through Perimeter Search
Eyerich Patrick, Helmert Malte (2013), Stronger Abstraction Heuristics Through Perimeter Search, in Proceedings of the 23rd International Conference on Automated Planning and Scheduling (ICAPS 2013), Rome, Italy.
Efficient Implementation of Pattern Database Heuristics for Classical Planning
Sievers Silvan, Ortlieb Manuela, Helmert Malte (2012), Efficient Implementation of Pattern Database Heuristics for Classical Planning, in Proceedings of the Fifth Annual Symposium on Combinatorial Search (SoCS 2012), Niagara Falls, Ontario, Canada.
How to Relax a Bisimulation?
Katz Michael, Hoffmann Jörg, Helmert Malte (2012), How to Relax a Bisimulation?, in Proceedings of the 22nd International Conference on Automated Planning and Scheduling (ICAPS 2012), Atibaia, São Paulo, Brazil.
Diverse and Additive Cartesian Abstraction Heuristics
Seipp Jendrik, Helmert Malte, Diverse and Additive Cartesian Abstraction Heuristics, in Proceedings of the 24th International Conference on Automated Planning and Scheduling (ICAPS 2014).
Generalized Label Reduction for Merge-and-Shrink Heuristics
Sievers Silvan, Wehrle Martin, Helmert Malte, Generalized Label Reduction for Merge-and-Shrink Heuristics, in Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence (AAAI 2014), Québec City, Québec, Canada.
Guided Search for Hybrid Systems Based on Coarse-Grained Space Abstractions
Bogomolov Sergiy, Donzé Alexandre, Frehse Goran, Grosu Radu, Johnson Taylor, Ladan Hamed, Podelski Andreas, Wehrle Martin, Guided Search for Hybrid Systems Based on Coarse-Grained Space Abstractions, in International Journal on Software Tools for Technology Transfer.
Heuristics for Cost-Optimal Classical Planning based on Linear Programming
Pommerening Florian, Röger Gabriele, Helmert Malte, Bonet Blai, Heuristics for Cost-Optimal Classical Planning based on Linear Programming, in Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI 2015), Buenos Aires, Argentinien.
Improved Pattern Selection for PDB Heuristics in Classical Planning (Extended Abstract)
Scherrer Sascha, Pommerening Florian, Wehrle Martin, Improved Pattern Selection for PDB Heuristics in Classical Planning (Extended Abstract), in Proceedings of the 8th Annual Symposium on Combinatorial Search (SoCS 2015), Ein Gedi, Israel.
LP-based Heuristics for Cost-optimal Planning
Pommerening Florian, Röger Gabriele, Helmert Malte, Bonet Blai, LP-based Heuristics for Cost-optimal Planning, in Proceedings of the 24th International Conference on Automated Planning and Scheduling (ICAPS 2014), Portsmouth, New Hampshire, USA.

Zusammenarbeit

Gruppe / Person Land
Formen der Zusammenarbeit
Australian National University & NICTA, Canberra Australien (Ozeanien)
- vertiefter/weiterführender Austausch von Ansätzen, Methoden oder Resultaten
- Publikation
Albert-Ludwigs-Universität Freiburg Deutschland (Europa)
- vertiefter/weiterführender Austausch von Ansätzen, Methoden oder Resultaten
- Publikation
INRIA, Nancy Frankreich (Europa)
- vertiefter/weiterführender Austausch von Ansätzen, Methoden oder Resultaten
- Publikation
- Austausch von Mitarbeitern
Ben-Gurion University of the Negev Israel (Asien)
- vertiefter/weiterführender Austausch von Ansätzen, Methoden oder Resultaten
- Publikation
Universität des Saarlandes Deutschland (Europa)
- vertiefter/weiterführender Austausch von Ansätzen, Methoden oder Resultaten
- Publikation
- Austausch von Mitarbeitern

Wissenschaftliche Veranstaltungen

Aktiver Beitrag

Titel Art des Beitrags Titel des Artikels oder Beitrages Datum Ort Beteiligte Personen
AAAI-2015 Workshop on Planning, Search, and Optimization (PlanSOpt) Vortrag im Rahmen einer Tagung Linear Programming for Heuristics in Optimal Planning 25.01.2015 Austin, Texas, Vereinigte Staaten von Amerika Pommerening Florian;
Twenty-Ninth AAAI Conference on Artificial Intelligence (AAAI 2015) Vortrag im Rahmen einer Tagung From Non-Negative to General Operator Cost Partitioning 25.01.2015 Austin, Texas, Vereinigte Staaten von Amerika Helmert Malte; Seipp Jendrik; Pommerening Florian;
Twenty-Ninth AAAI Conference on Artificial Intelligence (AAAI 2015) Vortrag im Rahmen einer Tagung Automatic Configuration of Sequential Planning Portfolios 25.01.2015 Austin, Texas, Vereinigte Staaten von Amerika Seipp Jendrik; Helmert Malte;
Seventh Annual Symposium on Combinatorial Search (SoCS 2014) Vortrag im Rahmen einer Tagung Exploiting the Rubik's Cube 12-Edge PDB by Combining Partial Pattern Databases and Bloom Filters 15.08.2014 Prag, Tschechische Republik Helmert Malte;
Sixth Workshop on Heuristics and Search for Domain-independent Planning (HSDIP 2014) Vortrag im Rahmen einer Tagung Generalized Label Reduction for Merge-and-Shrink Heuristics 22.06.2014 Portsmouth, New Hampshire, Vereinigte Staaten von Amerika Helmert Malte;
24th International Conference on Automated Planning and Scheduling (ICAPS 2014) Vortrag im Rahmen einer Tagung LP-based Heuristics for Cost-optimal Planning 21.06.2014 Portsmouth, New Hampshire, Vereinigte Staaten von Amerika Pommerening Florian; Helmert Malte;
24th International Conference on Automated Planning and Scheduling (ICAPS 2014) Vortrag im Rahmen einer Tagung Diverse and Additive Cartesian Abstraction Heuristics 21.06.2014 Portsmouth, New Hampshire, Vereinigte Staaten von Amerika Helmert Malte; Seipp Jendrik;
23rd International Joint Conference on Artificial Intelligence (IJCAI 2013) Vortrag im Rahmen einer Tagung Getting the Most Out of Pattern Databases for Classical Planning 03.08.2013 Peking, China Pommerening Florian; Helmert Malte;
Twenty-Seventh AAAI Conference on Artificial Intelligence (AAAI 2013) Poster Additive Counterexample-guided Cartesian Abstraction Refinement 14.07.2013 Bellevue, Washington, Vereinigte Staaten von Amerika Seipp Jendrik; Helmert Malte;
Twenty-Seventh AAAI Conference on Artificial Intelligence (AAAI 2013) Vortrag im Rahmen einer Tagung What's Hot in Planning 14.07.2013 Bellevue, Washington, Vereinigte Staaten von Amerika Helmert Malte;
23rd International Conference on Automated Planning and Scheduling (ICAPS 2013) Vortrag im Rahmen einer Tagung Counterexample-guided Cartesian Abstraction Refinement 10.06.2013 Rom, Italien Helmert Malte; Seipp Jendrik;
Fifth Annual Symposium on Combinatorial Search (SoCS 2012) Poster Efficient Implementation of Pattern Database Heuristics for Classical Planning 19.07.2012 Niagara Falls, Ontario, Kanada Helmert Malte;
22nd International Conference on Automated Planning and Scheduling (ICAPS 2012) Vortrag im Rahmen einer Tagung How to Relax a Bisimulation? 25.06.2012 Atibaia, São Paulo, Brasilien Helmert Malte;


Selber organisiert

Titel Datum Ort
Sixth Annual Symposium on Combinatorial Search (SoCS 2013) 11.07.2013 Leavenworth, Washington, USA, Vereinigte Staaten von Amerika

Auszeichnungen

Titel Jahr
AAAI 2015 Best Paper Award 2015
ICAPS 2014 Outstanding Paper Award 2014
Runner-Up for the AAAI 2014 Outstanding Paper Award 2014

Verbundene Projekte

Nummer Titel Start Förderungsinstrument
156057 Automated Reformulation and Pruning in Factored State Spaces 01.01.2015 Projektförderung (Abt. I-III)
143698 Safe Pruning in Optimal State-Space Search 01.11.2012 Projektförderung (Abt. I-III)
159377 Reasoning about Plans and Heuristics for Planning and Combinatorial Search 01.05.2015 Projektförderung (Abt. I-III)

Abstract

Automated planning is one of the traditional and central researchareas in artificial intelligence. In this context, planning means thatan agent reasons over its possible courses of action in order to findout which activities it needs to carry out in order to reach itsgoals. For many applications of planning, it is desirable to producenot just any plan, but one that minimizes some cost metric, a problemcalled optimal planning. The most successful optimal planningalgorithms of the last decade fall into the general class of heuristicsearch methods, typically using A* or a similar search algorithm.A heuristic function, or heuristic for short, is a function thatestimates how far away the planning agent is from its goal. Moreformally, a heuristic maps states s of the task to be solved tonumerical estimates of the minimal cost of reaching the goal from s.For a heuristic search algorithm such as A* to be efficient, it mustbe supplied with a heuristic that is reasonably quickly computable aswell as accurate (i.e., it should provide estimates that are close tothe actual cost). To provide optimality guarantees, the heuristic mustalso be admissible, i.e., never overestimate the true cost.Abstraction heuristics, such as pattern database heuristics andmerge-and-shrink heuristics, have been a very successful class ofadmissible heuristics for optimal planning and related searchproblems. An abstraction heuristic maps states from the actual(concrete) state space of the planning task into a smaller space (theabstract state space) in a homomorphic manner, i.e., preserving statetransitions and goal states. The cost to reach the goal in theabstract space then serves as a cost estimate for the concrete space.Abstraction heuristics have been a subject of intense study in theplanning literature in recent years, leading to several keybreakthroughs both for practical algorithms and in the theoreticalunderstanding of such heuristics. The latter theoretical studies inparticular have shown that state-of-the-art abstraction heuristics,despite their significant successes, do not realize the power of thegeneral approach to its full potential.The research we propose here aims at reducing this gap betweenpractical performance and theoretical promises. Specifically, wepursue three objectives:O1. To advance the theory of abstraction heuristics in order toimprove our theoretical understanding of their capabilities, theirlimitations, and their relationship to other commonly used approachesfor deriving admissible heuristics.O2. To develop improved abstraction heuristics for optimal planning,hence raising the state of the art for optimal planning systems.O3. To transfer the new insights on abstraction heuristics toapplications of optimal search outside of automated planning, in orderto advance the state of the art in these areas.
-