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.