Automated Reformulation and Pruning in Factored State Spaces
Third-party funded project
Project title Automated Reformulation and Pruning in Factored State Spaces
Principal Investigator(s) Helmert, Malte
Project Members Wehrle, Martin
Organisation / Research unit Departement Mathematik und Informatik / Artificial Intelligence (Helmert)
Project Website http://ai.cs.unibas.ch/research/
Project start 01.01.2015
Probable end 31.07.2016
Status Completed
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 10100 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 project 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: 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. to develop general and efficient methods for dominance pruning in transition systems. SPOSSS focused on equivalence pruning, which ignores transition sequences σ that can be shown to have exactly the same overall effect as another sequence τ. We will investigate more general methods that can also detect and exploit situations where σ is strictly less useful than τ. 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. 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.

Keywords pruning techniques, symmetries, automated planning, problem reformulation, artificial intelligence
Financed by Swiss National Science Foundation (SNSF)
Follow-up project of 1380111 Safe Pruning in Optimal State-Space Search

Cooperations ()

  ID Kreditinhaber Kooperationspartner Institution Laufzeit - von Laufzeit - bis
2811774  Helmert, Malte  Hoffmann, Jörg  Universität des Saarlandes  01.05.2012  31.12.2030 
2811778  Helmert, Malte  Fox, Maria  King's College, London  01.11.2012  31.07.2016 
2811782  Helmert, Malte  Domshlak, Carmel  Technion  01.01.2015  31.12.2030 
   

MCSS v5.8 PRO. 1.061 sec, queries - 0.000 sec ©Universität Basel  |  Impressum   |    
22/10/2018