Certified Correctness and Guaranteed Performance for Domain-Independent Planning (CCGP-Plan)
Third-party funded project
Project title Certified Correctness and Guaranteed Performance for Domain-Independent Planning (CCGP-Plan)
Principal Investigator(s) Helmert, Malte
Project Members Francès Medina, Guillem
Eriksson, Salomé
Geissmann, Cedric
Seipp, Jendrik
Ferber, Patrick
Organisation / Research unit Departement Mathematik und Informatik / Artificial Intelligence (Helmert)
Project Website https://ai.dmi.unibas.ch/research/
Project start 01.02.2019
Probable end 31.01.2023
Status Active
Abstract

The research area of domain-independent planning is concerned with the following problem: given formal representations of the world an autonomous agent is situated in, of its capabilities, and of its goals, find a plan (a sequence of actions executable by the agent) that achieves the agent's goals, or prove that no such plan exists. We focus on the classical setting, one of the traditional core areas of artificial intelligence (AI). After decades of intensive research, planning algorithms have recently reached a level of maturity that makes them useful for real-world decision-making scenarios. With this increased maturity of planning algorithms, raw performance is no longer automatically the main concern for AI researchers or AI engineers interested in using planning algorithms in the systems they build. Besides efficiency, increasing demands are placed on the reliability of planning algorithms. We identify two ways in which current planning algorithms are brittle, and we suggest ways to improve their reliability. Specifically, we consider the following two challenges:

1. Certified Correctness: As planning is a model-based approach, there are clear notions of correctness: a sound and complete planning algorithm must return a solution if one exists and report unsolvability when no solution exists. An optimal planning algorithm must additionally guarantee that all solutions it returns are of optimal quality. This means that planning algorithms can be incorrect in three ways. They can return solutions that do not actually solve the given problem, falsely claim that a problem is unsolvable, or falsely claim that a solution is optimal (or bounded suboptimal). While the first kind of error can be detected with plan validators, the other two are much more challenging. In critical applications, possible algorithmic errors, implementation bugs, or even malicious programming (for example due to manipulated programs or ulterior motives of the algorithm implementers) are serious concerns. We investigate planning algorithms that always justify their answers in
a way that can be verified independently, automatically, and efficiently.

2. Guaranteed Performance: In many scenarios where a planning algorithm could be used, guaranteeing its correctness is not sufficient. It is also necessary to ensure that in all relevant situations, the algorithm reliably produces a plan within the available computational resources. This is especially true in (common) settings where many similar problems must be solved repeatedly. Current algorithms do not provide performance guarantees, and small differences in the input can make the difference between solutions found within milliseconds, days, or not at all. Due to the PSPACE-completeness of classical planning, there will always be cases where quick solutions are not feasible. However, in many scenarios efficient planning is possible. We propose algorithms that identify such scenarios for individual planning tasks, for planning task structures, and for planning domains.

Financed by Swiss National Science Foundation (SNSF)

Cooperations ()

  ID Kreditinhaber Kooperationspartner Institution Laufzeit - von Laufzeit - bis
3726561  Helmert, Malte  Bonet, Blai  Universidad Simon Bolivar  01.06.2011  31.12.2030 
4500841  Helmert, Malte  Sanner, Scott, Assistant Professor  University of Toronto  01.02.2019  31.01.2023 
4500842  Helmert, Malte  Abdulaziz, Mohammad, Post-Doc  Technical University of Munich  01.02.2019  31.01.2023 
   

MCSS v5.8 PRO. 0.734 sec, queries - 0.000 sec ©Universität Basel  |  Impressum   |    
14/08/2020