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
actions 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.
This introductory mini course focuses on logical representation for actions and
temporal continuous processes.
It starts with a brief introduction to situation calculus.
It is expected that the attendees are not familiar with situation calculus and automated planning,
but they have a basic knowledge of first order logic, understand what is informed
search guided by an heuristic (at the level of an undergraduate introductory AI course),
and have basic understanding of constrained optimization problems at
level of introductory undergraduate level course on multivariable calculus.
Several algorithmic and implementation issues will be discussed in the course.
This mini course focuses on the representation of change and on automated planning.
The area of automated AI planning is concerned with computing a sequence of actions
that leads from a given initial situation to a goal situation.
In the case of automated temporal planning, the task also includes scheduling
the actions so that they can be executed at specific moments of time and
the goal can be achieved as soon as possible. The automated temporal planning
problem is computationally challenging, since it may require searching efficiently
over a large number of combinations when the number of action parameters can be large.
One of the promising approaches to automated planning instantiates action
parameters at run-time. This is known as lifted planning. The most popular approach
to solving the temporal planning problem reduces this problem to heuristic search.
There are a number of domain independent heuristics that can guide search
to find a plan for a large class of planning domains, not just for a specific
application. This is an interesting approach since it is general.
However, there are a number of important conceptual challenges for automated planning.
One of the challenges remaning includes planning in the domains with dynamically changing objects,
when objects can be created or destroyed by the plan actions.
Another important challenge includes automated planning in the real world,
where action parameters vary over infinite domains (e.g., fuel, weights, time),
and actions initiate or terminate continuous processes.
Both these challenges can be addressed if the planning problem is formulated
as a reasoning problem over logical language such that the problem specification
can have both finite and infinite models.
Our basic language is the situation calculus. This mini-course covers both the well-known
logical foundations and the recent developments in the situation calculus.
Specifically, the initial part of the tutorial includes logical characterizations
of qualitative change within the situation calculus, and the middle part presents
a recent approach that extends the previous version of the situation calculus
with new representations for reasoning about quantitative change over time.
It turns out that this new version of temporal situation calculus can serve
as a basis for the development of a new domain-independent heuristic planner
that can solve the planning problems in the mixed discrete-continuous domains.
These hybrid domains include not only the usual discrete actions and qualitative
properties, but also continuous processes that can be possibly initiated or
terminated by actions.
The final part of the mini-course includes an overview of the deign prinicples of
a new automated planner and the experimental results collected from running
a tentative implementation of a new planner on selected benchmarks designed
by the planning community for the hybrid domains.
No previous background in the situation calculus or AI planning is required.
However, it is expected that the attendees have basic understanding of heuristic
search and working knowledge of first order logic.
(Lecture 1)
Introduction to reasoning about action. Intuitive ideas for the situation calculus.
Deterministic, primitive, atemporal actions without side-effects.
Frame axioms (axioms about lack of effects for actions), the frame problem: Reiter's solution.
Effect axioms, normal form for effect axioms. Transforming effect axioms for a given fluent
into a single positive effect axiom and a single negative effect axiom for the fluent.
Explanation closure, causal completeness, successor state axioms (SSA).
Basic Action Theories (BATs): preconditions, successor state axioms, initial theory, foundational axioms
for the tree of situations, unique name axioms (UNA). Closed World (CWA) vs Open World Assumption (OWA).
Domain Closure Assumption (DCA) vs open domains with varying objects.
The projection problem as a prerequisite to the planning problem in SC.
The projection and executability problems. Two techniques for solving these problems:
regression (reasoning backwards) and progression (reasoning forward).
The regression operator. The relative satisfiability theorem.
The theorem about reducing the projection problem to entailment of a regressed
formula from an initial theory (together with UNA). Several examples.
(Lecture 2)
Reasoning forward in the situation calculus. Forgetting about a single ground
atom and about multiple ground facts that are no longer true after doing an action.
Application of forgetting to computing direct effects of actions.
Definition of progression using forgetting. Challenges in computing progression.
Local-effect basic action theories: a natural class of action theories.
Computing progression efficiently in local-effect basic action theories.
(Lecture 3)
Automated planning over the situation tree with a domain independent heuristic.
Advantages of deductive planning (based on theorem proving).
The review of the landscape of research on automated planning.
Bounded lifted planning with basic action theories.
A* and greedy best-first search (GBFS) over situation tree to find a plan.
The GraphPlan heuristic with delete relaxation as an example of a domain independent heuristic.
Theorem Proving Lifted Heuristic (TPLH) planner.
Experimental evaluation of TPLH on several well-known planning benchmarks.
(Lecture 4)
The situation tree with a timeline. Instantaneous actions, processes extended in time.
The sequential, temporal situation calculus.
A recent extension: Hybrid Temporal Situation Calculus (HTSC).
Atemporal fluents vs temporal fluents.
Continuous processes initiated or terminated by the last action (event).
Example 1: the bouncing balls. Temporal Change Axioms (TCA) to represent how
temporal numerical fluents continuously change over time in each context.
Deriving State Evolution Axioms. Temporal (sequential) BATs.
Example 2 to illustrate the proposed methodology for representing continuous change.
(Lecture 5)
A lifted planner NEAT based on Hybrid Temporal Situation Calculus.
Automated planning in the mixed discrete-continuous domains.
A new domain independent heuristic based on ideas from optimal control.
Constraint Logic Programming (CLP).
Interface to an external Non-Linear Programming (NLP) solver.
Experimental assessment, and comparison with the other state of the art
planners on the challenging benchmarks with linear or non-linear change.
The linked lecture handouts are available under the
Creative Commons Attribution-NonCommercial-ShareAlike-4.0 International Public License
(CC BY-NC-SA 4.0).
(Optional prerequisite)
Lecture 0:
this handout provides a brief introduction to first order logic.
Lecture 3.
The readers who are not familiar with
Planning Graph-Based Reachability Heuristics
might wish to study first the tutorial provided by Daniel Bryce and Subbarao Kambhampati:
pages 49-55 only in the linked PDF file. Published in AI Magazine, 2007, v.28, N1.
The readers who are not familiar with linear programming, can start with the slides prepared by
Kevin Wayne (Princeton University):
Linear Programming I (1 page up)
or
Linear Programming I (4 pages up).
You can skip the slides related to simplex algorithm.
These are lecture slides to the textbook "Algorithm Design" by Jon Kleinberg and Éva Tardos.