Projekt

Zurück zur Übersicht

Reasoning about Plans and Heuristics for Planning and Combinatorial Search

Gesuchsteller/in Helmert Malte
Nummer 159377
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.2015 - 30.04.2018
Bewilligter Betrag 675'631.00
Alle Daten anzeigen

Keywords (7)

combinatorial search; potential functions; operator-counting constraints; heuristic search; LTL plan constraints; artificial intelligence; automated planning

Lay Summary (Deutsch)

Lead
Handlungsplanung ist ein Bereich der künstlichen Intelligenz, bei dem ein Computersystem selbstständig die nötigen Aktionen zur Erreichung eines gegebenen Ziels finden muss. Um in der immensen Anzahl von Handlungsmöglichkeiten eine Lösung zu finden, werden meist heuristikbasierte Verfahren verwendet. Eine Heuristik ist dabei eine Funktion, die für einen Weltzustand abschätzt, wie aufwändig es ist von dort das Ziel zu erreichen. Im Prinzip kann man eine Heuristik darüber definieren, welche Informationen sie nützt und in welcher Weise sie dies tut, wobei beide Aspekte bisher meist als integrierter Prozess betrachtet wurden. Durch eine entkoppelte Herangehensweise liessen sich jedoch vielfältige Vorteile für die praktische Anwendung und die weitere theoretische Forschung erreichen.
Lay summary

Inhalt und Ziele des Forschungsprojekts

Unser Ziel ist es, eine entkoppelte Herangehensweise an Heuristiken zu etablieren. Dabei soll die einfliessende Information (z.B. über mögliche Aktionsfolgen) deklarativ durch sogenannte Constraints oder mit logikbasierten Formalismen beschrieben werden. Die Verwendung der Information geschieht dann durch allgemeine Schlussfolgerungs- und Optimierungsmethoden, die wir in diesem Projekt entwickeln. Die resultierende Theorie soll dabei bestehende Heuristiken unter einem Dach vereinen.

Wissenschaftlicher und gesellschaftlicher Kontext des Forschungsprojekts

Unser Ansatz ermöglicht es Anwendern vorhandenes Domänenwissen zu verwenden, ohne die Interna von Heuristiken zu kennen. Gut erforschte Methoden erlauben es dann, diese Informationen bestmöglich zu nutzen. Die vereinigende Theorie bestehender Heuristiken ermöglicht es, diese theoretisch fundiert zu vergleichen, ihre wechselseitigen Vorteile zu kombinieren und die Schlussfolgerungsmethoden weiter zu verbessern.

Direktlink auf Lay Summary Letzte Aktualisierung: 22.04.2015

Verantw. Gesuchsteller/in und weitere Gesuchstellende

Mitarbeitende

Verbundene Projekte

Nummer Titel Start Förderungsinstrument
156057 Automated Reformulation and Pruning in Factored State Spaces 01.01.2015 Projektförderung (Abt. I-III)
141021 Abstraction Heuristics for Planning and Combinatorial Search 01.05.2012 Projektförderung (Abt. I-III)

Abstract

Action planning is one of the oldest and one of the central research problems in artificial intelligence. A planning problem arises whenever an intelligent agent (virtual or embodied) needs to decide which activities it must carry out in order to achieve its goals, or as Patrik Haslum put it succinctly: "Planning is the art and practice of thinking before acting."Classical planning, the most widely studied variant of the planning problem with which this project is concerned, can be formalized as finding shortest paths (optimal planning) or any path (satisficing planning) from a given initial state to some goal state in an implicitly given planning task, essentially a directed graph. Planning is hard because these graphs are often enormous in size in practical applications, comprising 10^100 states or more, precluding the application of traditional "blind" graph search methods.The most successful planning algorithms of the last decade fall into the general class of heuristic search methods, usually based on A* or a related search algorithm. In this context, the word heuristic, which carries a wide range of meanings in different areas of computer science, is a very specific technical term: a heuristic is a function whose input is a state s of a planning task and which returns an estimate of the distance from s to a nearest goal state. Heuristics are the heart and soul of planning algorithms based on state-space search. Depending on the accuracy of the heuristic estimates, heuristic search algorithms can range from solving planning tasks blindingly fast to being worse than blind search.Hence, much of the most influential classical planning research in the recent past has been concerned with developing better and better heuristics and furthering our theoretical understanding of existing heuristics. This has led to increasingly more sophisticated approaches. A large amount of human ingenuity has gone into devising today's advanced approaches and developing the underlying theory, especially in the case of optimal planning, where heuristics must satisfy a lower-bound property (be admissible) in order to be safe to use.The central idea of this project is to shift this burden of sophistication and ingenuity away from the human heuristic designer and onto the machines that perform the heuristic search. Equipped with appropriate reasoning algorithms and representations, computers can derive knowledge about planning tasks more quickly, more reliably andin more complex settings than we humans are capable of. A planning researcher or practitioner should be able to focus on which information a planning algorithm ought to exploit, without having to worry about how to exploit it in the best way. In other words, we are suggesting a declarative approach to heuristic search planning that enables planning algorithms to reason about plans and heuristics in powerful and general ways.A key research challenge in this endeavour is identifying an appropriate level of representation at which this declarative information is specified. It should be general enough to capture the concepts that today's state-of-the-art planning algorithms rely on in order to obtain accurate heuristic estimates, yet limited enough to afford efficient reasoning algorithms. In this project, we explore this design space in depth, both theoretically and with an emphasis on efficient practical algorithms.
-