Beyond the Frontiers of Timeline-based Planning

Abstract

Any agent, either biological or artificial, understands how to behave in its environment according to its prior knowledge and to its prior experience. The process of deciding which actions to undertake and how to perform them so as to achieve some desired objective is called deliberation. In particular, planning is an abstract and explicit deliberation process that chooses and organizes actions, by anticipating their expected outcomes, with the aim to achieve, as best as possible, some pre-stated objectives called goals. Among the most widespread approaches to automated planning, the classical approach broadly pursues to the following definition of planning: starting from a description of the initial state of the world, a description of the desired goals, and a description of a set of possible actions, the planning problem consists in synthesizing a plan, i.e., a sequence of actions, that is guaranteed, when applied to the initial state, to generate a state, called a goal state, which contains the desired goals.

In order to cope with computational complexity, however, the classical approach to planning introduces some restrictive assumptions. Among them, for example, there is no explicit model of time and concurrency is treated only roughly. Additionally, goals are specified as a set of goal states, therefore, objectives such as states to be avoided and constraints on state trajectories or utility functions are not handled. In order to relax these restrictions, some alternative approaches have been proposed over the years. The timeline-based approach to planning, in particular, represents an effective alternative to classical planning for complex domains requiring the use of both temporal reasoning and scheduling features. This thesis focuses on timeline-based planning, aiming at solving some efficiency issues which inevitably raise as a consequence of the drop out of these restrictions. Regardless of the followed approach, indeed, it turns out that automated planning is a rather complex task from a computational point of view. Furthermore, not all of the approaches proposed in literature can rely on effective heuristics for efficiently tackling the search. This is particularly true in the case of the more recent and hence less investigated timeline-based formulation. Most of the timeline-based planners, in particular, have usually neglected the advantages triggered in classical planning from the use of Graphplan and/or modern heuristic search, namely the capability of reasoning on the whole domain model. This thesis aims at reducing the performance gap between the classical approach at planning and the timeline-based one. Specifically, the overall goal is to improve the efficiency of timeline-based reasoners taking inspiration from techniques applied in more classical approaches to planning. The main contributions of this thesis, therefore, are a) a new formalism for timeline-based planning which overcomes some limitations of the existing ones; b) a set of heuristics, inspired by the classical approach, that improve the performance of the timeline-based approach to planning; c) the introduction of sophisticated techniques like the non-chronological backtracking and the no-good learning, commonly used in other fields such as Constraint Processing, into the search process;d) the reorganization of the existing solver architectures, of a new solver called ORATIO, that allows to push the reasoning process beyond the sole automated planning, winking at emerging fields like, for example, Explainable AI and e) the introduction of a new language for expressing timeline-based planning problems called RIDDLE.