A brief overview of temporal planning Jussi Rintanen

A brief overview of temporal planning in AI

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

  1. Cushing, Weld, Kambhampati, Mausam, and Talamadupula, Evaluating Temporal Planning Domains, Proceedings of ICAPS, pages 105-112, AAAI Press, 2007.
  2. 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.
  1. unary resources: A unary resource may be used by at most one action at a time.
  2. 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.
  3. 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.
  1. It is limited to Boolean and real-valued state variables. There is no support for integer, finite range integer, or multi-valued (enum) variables.
  2. 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.
  3. An action can only have effects at its starting point and at its ending point.
  4. 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

  1. an assignment of values to state variables, and
  2. 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.

  1. 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.
  2. 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

The delayed effects of an action can be represented either of two ways. Frame axioms (representing all possible justifications for changes between consecutive steps) are analogous to the classical planning case. See Temporal Planning by SAT Modulo Theories (SMT).

References

  1. 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.
  2. 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.)
  3. 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.)
  4. 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.).)
  5. 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.)
  6. 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.).)
  7. J. Rintanen. Discretization of temporal models with application to planning with SMT. In Proceedings of the AAAI Conference on Artificial Intelligence, AAAI Press, pages 3349-3355, 2015.
  8. J. Rintanen. Constraint-based algorithm for computing temporal invariants. In Proceedings of the European Conference on Logic in Artificial Intelligence, Lecture Notes in Computer Science 8761, Springer-Verlag, 2014.
  9. J. Rintanen, Complexity of concurrent temporal planning, Proceedings of the 17th International Conference on Automated Planning and Scheduling, pages 280-287, AAAI Press, 2007.
  10. 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.)
  11. 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.)

Jussi Rintanen