A brief overview of AI planning

Models of state transition systems

There are several possible representations for state-transition systems. A state-transition system can be represented as an arc-labeled directed multi-graph. Each node of the graph is a state, and the arcs represent actions. An "action" is usually something that can be taken in several states, with the same or different effects. All the arcs corresponding to one action are labeled with the name of the action. There may be more than one action that moves us from state A to state B, and this means that there are more than one arc from A to B (this is why we said that the graph is a multi-graph.)

Succinct representations of transition systems

If there are state variables A : {1,2,3}, B : {0,1} and C : {0,1}, then there are 3*2*2* states 100, 200, 300, 101, 201, 301, 110, 210, 310, 111, 211, and 311.

If the domain of each state variable is finite, and there are finitely many state variables, then the number of states is finite as well.

When states are represented as valuations of state variables, an action can be represented as a procedure or a program for changing the values of the state variables. Below we explain a couple of possibilities how these procedures can be defined.

STRIPS

An action is possible in a state if all the variables in PRECONDITION have the value 1. Taking the action corresponds to executing the following program, consisting of assignment statements only:
a₁ := 1
a₂ := 1
...
a_n := 1
d₁ := 0
d₂ := 0
...
d_m := 0.

In STRIPS planning, a goal is usually expressed as a set of state variables. A state is a goal state if all of the goals have the value 1 in it.

Petri nets

For Petri nets, the state variables are the places. In state-transition nets, each place can hold 0 or more tokens. Essentially, a place is a state variable with the set of natural numbers as its domain. The class of 1-safe Petri nets adds the condition that each place can only hold 0 or 1 tokens. This way each state variable has the domain {0,1}, and there will be only a finite number of states.

Transitions (actions) in Petri nets are described slightly differently. Each transition has a set of predecessor places and a set of successor places. The transition is possible if all predecessor places N have a token (this corresponds to the PRECONDITION in STRIPS). When the transition is fired, all the successor places will receive an additional token.

STRIPS actions can be relatively easily translated into Petri nets with the 1-safety property (see Hickmott et al., IJCAI'07), but there are some small complications because in STRIPS the assignment a₁ := 1 has the same result no matter what the old value of a₁ was, whereas in Petri nets if a₁ is a successor place, the number of tokens is increased by one, and may become something else than 1 if the place already had one or more tokens.

Petri nets in general cannot be translated into STRIPS, because in general there may be any number of tokens in a place, and consequently an infinite number of states. Petri nets with the 1-safety property however can be translated.

1. C. A. Petri, Kommunikation mit Automaten, Institut für instrumentelle Mathematik, Universität Bonn, Schriften des IIM, No. 2, Germany, 1962.
2. Murata, T., Petri nets: properties, analysis and applications, Proceedings of IEEE, 77(3), pp. 541-580, 1989.

PDDL/ADL

The differences of PDDL in comparison to STRIPS are

• The PRECONDITION may be an arbitrary Boolean combination of atomic facts about the state variables. Atomic facts say something about one state variable, for example a=0 or b=1. A precondition could for example be (a=1)∨¬(b=1∧c=0).
• Instead of the unconditional assignments represented by ADD and DELETE, the effects may be conditional. This means that the effects are of the form, IF condition THEN a := v
  where the condition is a Boolean combination of facts. STRIPS corresponds to PDDL with trivial conditions that are always true (the condition is the constant TRUE).
• Goals may be Boolean combinations of atomic facts (formulas).

• there is NO one to one correspondence between the PDDL actions and the STRIPS actions, because several STRIPS actions may be needed for one PDDL action, and
• the set of STRIPS actions may have a size that is exponential in the size of the set of PDDL actions. This is because a PDDL action may need to be reduced to an exponential number of STRIPS actions. For example, a PDDL action with effects

  IF a₁=0 THEN a₁ := 1
  IF a₁=1 THEN a₁ := 0
  
  IF a₂=0 THEN a₂ := 1
  IF a₂=1 THEN a₂ := 0
  
  ...
  
  IF a_n=0 THEN a_n := 1
  IF a_n=1 THEN a_n := 0
  

  corresponds to 2ⁿ STRIPS actions because the effects of the actions are different in 2ⁿ different classes of states, and for each class of state a different STRIPS action is needed.

Representation of actions in the propositional logic

All the above action representations (STRIPS, 1-safe Petri nets, PDDL) can be compactly represented in the propositional logic. Given an action, its logic representation consists of two parts:

1. the precondition formula P (exactly like in PDDL)
2. description of what happens to each state variable, which is a conjunction of formulas, one conjunct for each state variable. Each state variable a_i is represented as an equivalence F(a₁,a₂,...,a_n) ↔ a'_i where F is a Boolean function on the state variables (a formula).

The reduction from 1-safe Petri nets to the propositional logic goes through the STRIPS representation.

For PDDL the functions F may be arbitrarily complex. We don't give a systematic mapping from PDDL to the propositional logic here, although the mapping is straightforward. An action consisting of the precondition d and the conditional effect IF a∧b THEN c is represented by the propositional formula d∧(((a∧b)∨c)↔c'). The formula says that the new value of c will be TRUE if and only if a and b are both true or c was true already.

State-space search

Search algorithms

1. well-known uninformed search algorithms like depth-first search, breadth-first search
2. systematic heuristic search algorithms with optimality guarantees, for example A* and its variants like IDA*, WA*
3. systematic heuristic search algorithms without optimality guarantees, for example the standard "best-first" search algorithm which is like A* but ignores the cost-so-far component of the valuation function
4. incomplete unsystematic search algorithms, most notably stochastic search algorithms

References

Symmetry reduction

The standard works on symmetry reduction for state-space search are from early nineties.

References

1. Starke, P. H., Reachability analysis of Petri nets using symmetries, Journal of Mathematical Modelling and Simulation in Systems Analysis, 8(4/5), pp. 293-303, 1991.

Partial-order reduction

Many of the existing partial-order reduction methods address deadlock detection, but there is a simple reduction from the problem of reaching a goal state to the problem of reaching a deadlock state, and therefore these methods are easily applicable to the planning problem, too.

1. Antti Valmari, Stubborn Sets for Reduced State Space Generation, Advances in Petri Nets 1990. 10th International Conference on Applications and Theory of Petri Nets, Bonn, Germany, Lecture Notes in Computer Science 483, pp. 491-515, Springer-Verlag, 1991.

Heuristics

• the original problem instance is simplified, and then the simplified problem instance is solved, or
• the problem instance is unmodified, but the definition of solution is simplified so that it can be efficiently solved. (In many cases the same thing can be achieved in either of these ways, but the latter option seems to be more general.)

• Computing the max-heuristic of Bonet and Geffner for STRIPS proceeds by ignoring all effects x := 0 and retaining all effects x := 1, and then finding a plan for this simplified problem instance.
  The shortest solution(s) to this problem instance will give a lower bound for the plan length for the original instance, and can be used as a heuristic in a heuristic search algorithm such as A* to find shortest plans.
• Another, general method for deriving heuristics is pattern databases (Culberson & Schaeffer, 1998, with application to planning by Edelkamp in 2001). The idea is to relax the original problem instance in alternative ways, by eliminating all state variables except for a small number n of them (with n typically 10 or less, so that the problem becomes almost trivial), and then solving the simplified problem instances optimally. The length of any of these optimal solutions is a lower bound for the length of the shortest plan of the original problem instance.
• generalized abstractions of Dräger et al. (2006), which can be viewed as a generalization of pattern databases that allows abstraction by arbitrary aggregation of states, not only by ignoring some of the state variables (this was called combine-and-abstract by Dräger et al., and planning researchers have renamed this to merge-and-shrink).

• The simplest one, used in connection for pattern databases, is to take the maximum of different heuristics. Since all of the constituent heuristics are lower bounds for the true shortest plan length, their maximum is a lower bound as well.
• There are variations of the "taking the maximum" scheme that try to be more accurate: when two heuristics respectively give lower bounds n and m, and their calculation (e.g. through the max-heuristics or pattern databases) involved completely disjoint sets of actions, then also the sum of the heuristics is still a lower bound for the length of the shortest plan of the original plan. The use of this strategy is more complicated, because it may be difficult to find a partition the original planning problem in a way that the disjointness property can be guaranteed in a useful way.

References

1. B. Bonet and H. Geffner, Planning as Heuristic Search, Artificial Intelligence Journal, 129(1-2), pp. 5-33, 2001.
2. K. Dräger, B. Finkbeiner and A. Podelski, Directed Model Checking with Distance-Preserving Abstractions, in Model Checking Software, LNCS 3925, pages 19-34, 2006.
3. J. C. Culberson and J. Schaeffer, Pattern Databases, Computational Intelligence, 14(4), pp. 318-334, 1998.
4. S. Edelkamp, Planning with Pattern Databases, Proceedings of the 6th European Conference on Planning (ECP-01), to appear.

Planning by SAT and constraint-satisfaction

SAT methods are less prone to excessive memory consumption than BDDs. Unlike state-space search, their memory consumption is not linear in the number of visited (stored) states, and they can be implemented with a memory consumption that is linear in the length of a plan or transition sequence (as opposed to the in general exponential memory consumption of explicit state-space search.) However, the currently leading algorithms for the SAT problem gain much of their efficiency by consuming more memory than the theoretical optimal algorithms.

All the main improvements to state-space search (symmetry reduction, partial-order reduction, heuristics) have counterparts in the SAT setting, in the form of symmetry-breaking constraints, parallel or partially-ordered plans, and SAT-solvers with planning-specific heuristics. We will not be discussing these in more detail here.

SAT algorithms

References

1. D. Mitchell, A SAT Solver Primer, EATCS Bulletin, 85, pp. 112-133, February 2005.
2. P. Beame, H. Kautz, and A. Sabharwal, Towards Understanding and Harnessing the Potential of Clause Learning, Journal of AI Research, 22, pp. 319-351, 2004.

Reduction to the SAT problem

The idea is to have formulas P_T (where T is a positive integer) such that P_T is satisfiable if and only if there is a plan with a horizon 0,1,...,T. Depending on the definition of plans, at each time point 0,1,...,T-1 there may be one or more actions.

The formulas P_T can be constructed from the logic representation of actions we described earlier. Instead of using the propositional variables A∪A' where A = { a₁,..., a_n } and A' = { a'₁,..., a'_n } for the values of the state variables in the current and in the next time point, we have the propositional variables A@i = { a₁@i,..., a_n@i } for different time points 0≤i≤T.

Given a formula F for some action expressed in terms of the variables in A∪A', we obtain F@i by replacing all these variables by a₁@i,..., a_n@i,a₁@(i+1),..., a_n@(i+1).

When we have formulas F₁,...,F_n representing n different actions, we can represent the transition relation between states at time i as the formula R@i = F₁@i∨F₂@i∨...∨F_n@i.

Now a sequence of T actions can be represented as R@0∧R@1∧...∧R@(T-1).

Finally,finding a plan (of length T) from any state satisfying a formula I to any state satisfying formula G can be expressed as the formula P_T = I@0∧R@0∧R@1∧...∧R@(T-1)∧G@T, where I@0 and G@T are obtained from I and G by replacing each state variable a in these formulas respectively by a@0 and a@T.

The time it takes to test the satisfiability of the formulas P_T strongly depends on the number of propositional variables in the formulas, which, for a given planning problem, is determined by the parameter T. Most works that improve the efficiency of the satisfiability tests do this by decreasing T by allowing more than one action at each time point. See the references for more details.

References

1. H. Kautz and B. Selman, Pushing the envelope: planning, propositional logic, and stochastic search, AAAI'96, pp. 1194-1201, AAAI Press, 1996.
2. J. Rintanen, K. Heljanko and I. Niemelä, Planning as Satisfiability: parallel plans and algorithms for plan search, Artificial Intelligence, 170(12-13), pages 1031-1080, 2006.
3. J. Rintanen. Planning as satisfiability: heuristics, Artificial Intelligence Journal, 2012.
4. J. Rintanen, Planning and SAT, in A. Biere, H. van Maaren, M. Heule and Toby Walsh, Eds., Handbook of Satisfiability, pp. 483-504, IOS Press, 2009.
5. J. Rintanen. Planning with SAT, admissible heuristics and A*. In Proceedings of the International Joint Conference on Artificial Intelligence, AAAI Press, pages 2015-2020, 2011. (© 2011 American Association for Artificial Intelligence. AAAI)

  I@0
  I@0∧R@0
  I@0∧R@0∧R@1
  I@0∧R@0∧R@1∧R@2

  I
  (∃A.(I∧R))[A'/A]
  (∃A.(((∃A.(I∧R))[A'/A])∧R))[A'/A]
  (∃A.((∃A.(((∃A.(I∧R))[A'/A])∧R))[A'/A])∧R)[A'/A]

states[0] := I;
t := 0;
while states[t]∧G is unsatisfiable do
 t := t+1;
 states[t] := (∃A.(states[t-1]∧R))[A'/A];
end while

goal := any valuation that satisfies state[t]∧G;
while goals does not satisfy I do
  i := any action index i such that states[t]∧Fi↓(goal[A/A']) is satisfiable;
  output action i;
  goal := any valuation (on A) that satisfies states[t]∧Fi↓(goal[A/A']);
end while