How can a computer, with its discrete actions, achieve goals as fast as possible
in the real continuous world? This task requires reasoning about both discrete
abstractions and continuous processes possibly overlapping in time and
interacting in a complex ways. Automated efficient planning in the continuous
world is an interesting and important research area in the intersection of
combinatorial search (guided by modern heuristics), optimal control, and
reasoning about actions. The focus on planning in the continuous world makes it
both challenging and different from other research in the area of model-based
automated planning with deterministic actions.
To realize how ubiquitous is this problem in everyday life think about planning of
cooking, washing, cleaning activities in a kitchen or in a laundry room.
The humans solve these planning problems well even in unfamiliar environments.
Planning is the long-standing problem of selecting and organising future actions to achieve a goal. It has been a focus of AI research for more than half a century and remains a challenging problem, even in the case where the world is assumed to be deterministic, fully observable and only affected by the actions being planned. Significant
progress has been made in finding good heuristics to direct search in this context. However, as that progress makes planning more relevant to real problems, some of its limitations become more apparent. In particular, to be useful for real problems, planning must operate in a world in which actions take time, concurrent activity is possible
(and desirable), and actions affect not only logical facts, but also numeric fluents -- in short, temporal and numeric planning is the variant that offers real value in application. Once planners are expected to reason about physical world models, it is hard to avoid the need to consider processes: physical systems that can be
controlled by actions of the planning agent, but, once started, operate independently of the executive and do so continuously. Examples include managing the flow of fluids while drilling, timing the performance of survey actions from a moving vehicle, coordinating activities with changing pressure regimes in flow systems. balancing load and
battery-charging in electrical systems and interacting with mobile robots. Crucially, planning in these situations involves reasoning about mixed discrete-continuous systems, which remains one of the most challenging problems in optimisation.
The planning problems described above are undecidable
in the general case. For this reason research focuses on developing sound
efficient algorithms that can sometimes solve the practical instances of
the planning problem.
The challenge of reasoning about continuous processes has been considered in several areas of modelling and reasoning, but in this tutorial we propose to focus on its relevance in the context of planning. There are several facets to this challenge: first is to identify motivating examples and then to model them; next is to ensure these
models have an appropriate semantics and finally is to reason about with them in order to construct valid and feasible plans. We will consider contributions to this field from the planning research community, from optimal control and, more briefly, other areas (we do not intend to provide an exhaustive review of the contributions that have
been made to this field).
We will explore some of the heuristics that have been developed to confront this challenge
(and their limitations) and also explore the further challenges that arise when translating
plans for these models into execution and control.
The primary objectives of the tutorial are the following:
introduce expert non-specialists to an AI sub-area,
provide instruction in established but specialized AI methodologies,
emphasize topics with significant industrial impacts: 2-3 scenarios will be mentioned.
In terms of prerequisites, we expect familiarity with declarative modelling
(under the usual determinism and full observability assumptions),
basic knowledge of first order logic, understanding of planning and
heuristic search at the level of an introductory AI course, familiarity with
constrained optimization at the level of an undergraduate calculus course.
We do not expect an expertise in modern planning. No previous knowledge of PDDL
(the Planning Domain Definition Language) is required to attend this tutorial.
The world does not stand still while we act! Our plans have to take into account
the physical processes with which they interact, for better or worse,
weaving action to manage the impact of those processes. We motivate, model
and manage some of the challenges of hybrid discrete-continuous systems.
The area of automated planning is concerned with computing a sequence of
actions that leads from an initial situation to a goal situation.
In the case of automated temporal planning, the task includes also scheduling
the actions so that the goal can be achieved in minimal time. Experimental
studies with ChatGPT and similar LLMs demonstrated they can solve only small
scale planning instances that do not require scheduling. The planning problem is
computationally challenging since it may require searching efficiently over
numerous combinations of actions and their parameters. The most popular approach
to solving the planning problem reduces this problem to heuristic search.
There are a number of domain independent heuristics that can guide search for
a large class of planning domains, not just for a specific application.
This principled approach is interesting thanks to its generality.
However, there are several important conceptual challenges remaining. They
include automated planning in the real world, where action parameters vary over
infinite domains (e.g., fuel, weights, time), and where actions initiate or
terminate continuous processes that can overlap arbitrarily over time. We
discuss how these challenges can be addressed on modelling and algorithmic
levels. In the second part of our tutorial, we explain an approach that formulates
the planning problem in a logical language as a reasoning problem augmented
with symbolic numerical constraints, and delegates numerical constrained
optimization to an external solver.
This tutorial is suitable for graduate students and non-specialists researchers alike.
Derek Long
has been an academic working in Automated Planning for a surprisingly
long time, having been a full professor at two universities, most recently
King's College London since 2011. In 2002, he and colleague Maria Fox proposed
the challenge of planning with time as part of the International Planning
Competition and created the extension to the Planning Domain Description
Language, PDDL, to capture the models they envisaged (in PDDL2.1 and PDDL+).
In 2016, he moved to work mostly in application in industry, determined to see
Automated Planning find real application. His experiences have convinced him
that it is true that real planning problems demand models with time and numbers,
and that processes do, indeed, matter. He still dabbles in an academic life,
although his time is almost entirely consumed by his work in applications of
planning and, more recently, scheduling, to real problems.
Mikhail Soutchanski
is a full professor at the Department of Computer Science
at the Toronto Metropolitan (formerly Ryerson) University. Mikhail's primary
research interest is in the area of reasoning about actions and its application
to automated planning in realistic domains. In particular, he focuses on
temporal planning in the mixed discrete-continuous relational domains where
the discrete actions can initiate or terminate continuous processes subject
to non-linear constraints, and where the objective is to find a plan with
the shortest total duration (the minimum make-span). In addition, he does research
on lifted heuristic planning in the domains where the objects can be created or
destroyed at run time.
