The planning problem in Artificial Intelligence is about
the decision making performed by intelligent creatures like robots,
humans, or computer programs when trying to achieve some goal.
The most basic form of planning views actions as atomic entities that are
taken one at a time in a sequence (see classical planning.)
When multiple things can be happening at a time, it is necessary to model
the duration and concurrency of actions and events.
Multiple actions can be taken simultaneously, their durations may vary, and
actions and events may have complex interdependencies which determine which
combinations are possible.
This is called temporal planning.
Closely connected to temporal planning are various scheduling problems,
where similarly the duration and interdependencies between different events or tasks
are central. In scheduling the tasks are given, and the core problem to solve is
determining how the tasks can be scheduled, i.e. assigned a starting time,
so that given resource and ordering constraints are satisfied.
Temporal planning involves solving the same scheduling problem, but additionally
the choice of actions/tasks is left open, and they must be selected together with
their scheduling, given a model of the actions and their effects.
References
Cushing, Weld, Kambhampati, Mausam, and Talamadupula,
Evaluating Temporal Planning Domains,
Proceedings of ICAPS, pages 105-112, AAAI Press, 2007.
Rankooh and Ghassem-Sani.
New Encoding Methods for SAT-Based Temporal Planning,
Proceedings of ICAPS, pages 73-81, AAAI Press, 2013.
Models of timed state transition systems
Due to the possibility of multiple concurrent actions, transition systems
cannot be modelled as easily as in classical planning as a (finite) set of states
together with viewing actions as binary relations on the states.
State variables
Similarly to classical planning, the state of the world at a given time point
is represented as the values of state variables. The values can be changed by
actions.
Time-delays in actions
For a full description of what happens at a given time moment the
values of state variables is in general not sufficient. A central feature of
temporal models is that actions and events have effects that span a (potentially
very long) time interval. For this it is necessary to somehow represent,
for every time point,
the things that will happen at later time points.
For example, an action taken at a time point t can have its effects at t
or at later time points.
Resources
Resources represent dependencies between actions. Temporal overlap between two actions
is limited if they need the same resource in conflicting ways. For example, two actions
that both exclusively require the same machine, tool or device cannot take place
at the same time.
The main resource types are the following.
unary resources: A unary resource may be used by at most one action at a time.
n-ary resources: An n-ary resource may be used by at most n actions at a time.
Different actions could use different amounts of the resource. So 2 units and 1 unit
of a 3-ary resource could be used at a time by two actions, and further actions could
not use the resource.
state resources: The resource could be viewed to have multiple states,
and the resource could not be used in different states at the same time, but
the number of actions using the resource in one state would not be limited.
Other modelling languages
A language used in the planning competitions (IPC) is PDDL 2.1. The reasons why
we are not using PDDL is because of a number of limitations.
It is limited to Boolean and real-valued state variables. There is no support
for integer, finite range integer, or multi-valued (enum) variables.
There is no explicit notion of resources, and consequently the representation of
many scheduling problems is clumsy and difficult, and, additionally, conflicts between actions are not directly visible, but must be inferred, sometimes through a complex sequence of inference steps.
An action can only have effects at its starting point and at its ending point.
There is no support for integer time. Many practically occurring problems are
best represented with integer time. The use of real time for these problems induces,
completely unnecessarily, a very large search space of plans/schedules with non-integral
starting points for actions. This has a high performance penalty.
These limitations make PDDL 2.1 and many of the temporal planning benchmark problems
(from the IPC) unrealistic w.r.t. real-world planning problems, many of which have
a strong scheduling flavor. Additionally, the resource mechanism in PDDL 2.1 leads to
inefficient representations in all of the leading formalisms for representing
planning and scheduling problems, including forms of Constraint Programming,
Mixed Integer Linear Programming (MILP), Integer Programming, SAT, SMT.
Other timed modeling languages exist. Good examples are Timed Petri Nets
and Timed Automata. Both are widely used in modeling various distributed
systems, and both can be used also for representing many planning problems.
The reason why we don't condsider them here is that - similarly to PDDL - they have no
explicit support central planning & scheduling concepts such as resources.
Explicit state-space search
Explicit state-space search,
meaning the generation of states reachable from the initial state
one by one,
is the earliest and most straightforward method for solving some of the
most important problems about transition systems, including model-checking
(verification), planning, and others, widely used since at least the 1980s.
For more details of the basic framework, see the notes on classical planning.
A timed state consists of
an assignment of values to state variables, and
a set of clocks, indicating the time remaining for a specific change or event.
The state variables are as in classical planning.
Typically each action is associated with one clock.
The clock is initialized to 0 when the action is taken.
When a clock reaches a specific value, corresponding changes to the state will
take place. For actions this is typically the changes in the state variables that
are later than the action's starting point.
Additionally, the satisfaction of constraints on the use of resources is defined
in terms of the clocks. Specifically, for an action to be possible at a given (timed) state,
its precondition has to be true, and the clocks of actions using the same resources have
to have values that indicate legal use of shared resources.
Given a timed state, two types of changes are possible.
Time can be advanced by a given amount t. This is possible if none
of the active clocks have critical values > c and < c+t. The state variables
retain their old values, but all clocks are advanced from their current value by t.
An action can be taken. This is possible if its precondition and resource constraints
are satisfied. The action's clock is set to 0. If the action has immediate (time 0) effects,
they will change the values of some state variables. Other state variables remain unchanged.
Similarly to classical planning, the timed version of explicit state-space search
is easy to implement, and can be used in connection with well-known state-space
search algorithms, such as breadth-first, informed search algorithms such as A* and
various best-first algorithms as well as stochastic search algorithms.
The basic issues in the implementation of timed state-space search are the same as with explicit state-space search for untimed (asynchronous) systems, with the exception of choosing how much time should be advanced.
All the main techniques for improving explicit state-space search were fully developed
by 1990s, including symmetry and partial order methods, and efficient implementation
technology.
Explicit state-space search methods are understood very well, and implementation
technology is well developed.
However, as it is with asynchronous systems, when the number of states is high,
the applicability of explicit state-space search methods to timed systems is limited
by the necessity to do search one state at a time.
Constraint-Based Search: SAT, SMT, Mixed Integer Linear Programming, Constraint Programming
The constraint-based representations represent a sequence of timed states
corresponding to the time points where time is stopped between consecutive
advance-time operations. We call these time points steps.
For each step the values of all state variables are represented as
propositional variables (Boolean variables) for SAT and also numeric variables for SMT.
MILP and CP framework generally allow representation of Boolean, integer variables and
real variables.
The times associated with steps i can be represented either
explicitly as the absolute times Τi, or
implicitly through the differences Δi between steps i-1 and i.
The delayed effects of an action can be represented either of two ways.
Delays are presented through explicitly represented clocks, which are initialized to 0 when an action
is taken, and which trigger effects when the clock reaches a critical value. Clock increases between steps are expressed with Δi or
Τi-Τi-1.
Constraints to prevent going past a critical clock value are needed.
Alternatively, a given action entails that for (at least) one of the later steps
the time difference to the present step (Τj-Τi)
is the critical value and the effects take place at that step.
J. Carlier, P. Chretienne, and C. Girault, Modelling scheduling problems with timed Petri nets, Advances in Petri Nets 1984, pages 62-82, Springer-Verlag, 1985.
Ji-Ae Shin and Ernest Davis, Processes and continuous change in a SAT-based planner, Artificial Intelligence, 166(1), pages 194-253, 2005. (Introduces SAT-based encodings for planning with timed/hybrid systems as modelled in PDDL 2.1.)
M. Do and S. Kambhampati, Sapa: A multi-objective metric temporal planner, Journal of Artificial Intelligence Research, 20, pages 155-194, 2003.
(A temporal planner based on explicit state-space search.)
A. Horz, On the relation of classical and temporal planning, Proceedings of the Spring Symposium on Foundations of Automated Planning. 1993.
(An early paper on temporal planning, based on the causal link paradigm (partial-order planning.).)
J. Kvarnström, P. Doherty, and P. Haslum, Extending TALplanner with concurrency and resources, In Proceedings of the European Conference on Artificial Intelligence, pages 501-505. 2000.
(An early temporal planner that is based on explicit state-space search.)
Penberthy, J. Scott, and Daniel S. Weld. Temporal planning with continuous change, Proceedings of the National Conference on Artificial Intelligence (AAAI), 1994.
(An early paper on temporal planning, based on the causal link paradigm (partial-order planning.).)
J. Rintanen,
Complexity of concurrent temporal planning,
Proceedings of the 17th International Conference on Automated Planning and Scheduling, pages 280-287, AAAI Press, 2007.
D. E. Smith and D. S. Weld, Temporal planning with mutual exclusion reasoning, In IJCAI (Vol. 99, pp. 326-337), 1999.
(An extension of the Graphplan framework to timed models.)
W. Zuberek, Extended D-timed Petri nets, timeouts, and analysis of communication protocols,Proceedings of the 1985 ACM Annual Conference on the Range of Computing: Mid-80's Perspective, ACM, 1985.
(An early example on the use of temporal models.)