This chapter is the deck M10 — Planning for Intelligent Agents, the closing act of the logic–reasoning–planning arc that Chapters 8 and 9 opened. Chapter 9 ended with reasoning about actions and promised exactly this: keep the search machinery, change the object — from proofs to plans. M10 delivers that promise: plans are searched, proven, ordered, refined and evaluated, and every technique is a variation on the search theme the previous chapters established. The deck is also the last Module 1 lecture before the tool-and-artefact turn of Chapter 11 and the Jade case study of Chapter 12. One connective detail worth keeping in mind: the deck repeatedly references Jason adopting a sort of hierarchical planning — a preview of the AgentSpeak(L) material that follows this segment.
The deck opens by describing what it means for an agent to plan. Rational agents are provided with a goal — typically expressed as a state of the world (or a set of states) that is considered desirable: for a student, a state of the world where good marks are obtained in every exam. In order to achieve its goal, the agent can exploit:
Then comes the definition of automatic planning: given the state of the world where the agent lives, given the set of actions (currently) available to the agent, and given the goal to achieve by the agent, planning means to devise a plan — where a plan is a (partially or totally ordered) set of actions aimed at achieving a goal. Two things in this definition deserve emphasis. First, the plan is not required to be a linear sequence: ordering is something the plan carries, possibly only partially. Second, planning starts from three inputs that all have to be represented — which is why section 5 will spend so much time on representation.
The deck positions planning inside the course’s conceptual map with two characterisations.
In some sense, planning is a normal AI problem — a search problem. Yet a dynamic environment can change the search space — even during search, and actions themselves, too. So basically, planning is unlike the usual AI search problem — in its generality, at least. Chapter 9’s search spaces were static; a planner’s may not be.
Planning can also be seen as the synthesis of algorithms: a problem to solve, actions to face it, and a workflow to be synthesised to solve the problem. Under simple assumptions, planning is a sort of synthesis of algorithms. Yet input–output, functional problem representation does not fit planning well in dynamic environments, where actions could work concurrently and interfere with each other — as in cyber-physical systems (CPS).
The deck then runs the question do we need planning? at three levels, each time softening the answer:
And the overall answer, which is the one the deck wants you to keep:
Whereas planning might not be strictly required by the needs of systems science or engineering, it could be clearly useful in many application scenarios — even practically necessary. Where planning might be required is in those cases where prominent requirements for (intelligent) systems are observability, accountability, and explainability — so, whenever reasons behind actions are required to be a priori known for any system with some responsibility — in particular within socio-technical systems (STS), where humans need to understand what is going on to effectively participate in the system activity.
This is the planning-specific echo of a theme running through the whole course: the more responsibility a system carries, the more its reasons must be explicit — and explicit reasons are what plans are.
The deck’s running example is mundane and perfect. Goal: go to Cesena and meet the class. State of the world: I am at home; I am sleepy. A first plan:
The example is not decorative: it introduces three notions that structure the whole chapter. Relevance forces the planner to decide what matters in a state; ordering distinguishes necessary constraints from free choices; and the grain of actions opens the question of hierarchical decomposition — section 18’s topic. Also note the pre-condition hidden inside “drive the car”: the sleepy driver is a feasibility pre-condition waiting to be violated.
The deck now gives the chapter’s central definition:
An automatic planner is a (component of an) intelligent agent working in a given application domain, which, given a representation of the initial state of the world, a representation of the goal, and a formal representation of the actions available, dynamically synthesises the plan of actions required to achieve the goal.
And immediately a question: what is autonomy to an automatic planner defined like that? The deck’s rough answer is a pair of aphorisms worth memorising:
Having a plan depends on intelligence; executing a plan depends on autonomy.
Notice the division of labour this sets up for the rest of the course: the planner is the intelligent component that synthesises; the agent’s autonomy is what makes the plan executable — and later chapters (Jason, Jade) will make exactly that split concrete.
Planning cannot begin until its three inputs are represented. The deck devotes three slides to the three representations, and each one carries a decision that will matter later.
Representing the environment means providing the planner with the model of the environment where the agent works. The typical approach is declarative: a conjunction of formulae representing everything known about the world. Which formalism? There is a trade-off between language expressiveness and computational efficiency — the same trade-off Chapter 8 met between logic and computation.
Then observability. The environment is sometimes observable only in a partial way, and not exactly: some aspects may be out of the reach of the agent, for intrinsic features of the environment itself or for the agent’s limitations in observation and interpretation — e.g., only limited portions of the environment are available for perception; perception is subject to noise, inaccuracy, imprecision; the domain may be in practice too vast for a complete representation; the dynamics of the environment could be too fast for the consistency of the agent’s perception and representation to keep up.
The example formula is isbn(booktitle,1234) ∧ price(36.00,1234) ∧ available(amazon,1234). And the question: what about the unrepresented aspects — are they false, or unknown? The answer introduces a term the deck insists on:
What we know as the closed world assumption is more often referred to as database semantics in planning [Russell and Norvig, 2022a]: formulae not explicitly represented are to be considered as false — which basically leads to the frame problem. So, CWA is just an option.
This is the same CWA that Chapter 8 met in Prolog’s negation as failure; here it reappears as a representational choice with a price tag attached (the frame problem, section 10).
The goal is represented typically the same way as the world, since a goal is a specific (desirable) state of the world. But the formalism of choice should include a notion of entailment, so that the achievement of the goal is not checked just by set inclusion — E ⊇ G — but more expressively as a logical entailment — E |= G. Chapter 8’s S |= φ is doing the work behind the scenes.
E |= FP. Post-conditions are the expected effects (EE) of the actions on the world. FP and EE are the same as FP and RE (rational effects) for communicative actions in FIPA ACL [FIPA ACL, 2002] — a bridge to the Jade chapter, where FIPA ACL messages reappear.Declarative conjunction of formulae; observability is partial and inexact; unrepresented formulae are false under closed-world / database semantics — an option, not a law, and one that leads to the frame problem.
A desirable state of the world, in the same formalism as the world; achievement checked as entailment E |= G, not mere set inclusion E ⊇ G.
Intensive schemes with variables, instantiated to ground actions; each action carries feasibility pre-conditions (FP) and expected effects (EE); the FP/EE pair mirrors FIPA ACL’s FP/RE for communicative actions.
The classic planning domain appears here with its two symmetric operators [Sacerdoti, 1977]:
stack(X, Y) — FP: holding(X) ∧ clear(Y); EE: handempty ∧ clear(X) ∧ on(X, Y).unstack(X, Y) — FP: handempty ∧ clear(X) ∧ on(X, Y); EE: holding(X) ∧ clear(Y).The deck adds a remark that is easy to miss: stack/2 and unstack/2 are both conceptually and technically symmetric — they could potentially be used for a sort of physical backtracking. This, however, is not so common for real-world actions: thermodynamics (section 7) is the reason.
Before any technique, the deck lists the four properties that separate benign planning problems from hard ones:
The first great divide in planning techniques is temporal. In off-line planning, the plan is produced completely before execution begins, against a snapshot of the current state of the world taken at the beginning of the planning activity. Everything is decided in advance; execution is just the plan’s enactment.
At the other extreme, on-line algorithms [Karp, 1992] do not require complete input to start; instead they process input piecemeal and proceed with computation without complete information. On-line (reactive) planning inherits this: it can start planning with only partial information on the environment available — it does not require complete initial information on the world, nor, at any time — so it can deal with dynamic and partially-available environments. As a result, planning and execution are constantly alternated, with sensing typically occurring at every step, even during execution.
The two words that will recur in the rest of the chapter: classical planning is traditionally off-line; the moment the environment stops being static, planning becomes a loop that interleaves with acting.
Classical planning [Russell and Norvig, 2022b] is defined by four assumptions, and the deck states them as a checklist:
In other terms, classical planning considers only environments that are fully observable, deterministic, finite, static — change happens only when the agent acts — and discrete — in time, action, objects, and effects. Definitely strong assumptions. And one consequence the deck draws immediately: traditionally, classical planning is off-line planning. The rest of the chapter can be read as a sequence of relaxations of these four assumptions.
The first classical technique is the one closest to Chapter 9: deductive planning uses logic to represent states, actions, and goals, and the plan is generated as a proof [Green, 1969; Kowalski, 1979]. The classical formulation is the situation calculus [McCarthy, 1963, 1968]:
The Block World example: on(b,a,s) and ontable(c,s) are two fluents holding in situation s, and the situation is on(b,a,s) ∧ ontable(c,s) ∧ ontable(a,s) ∧ clear(b,s) ∧ clear(c,s). The action of putting a block on the table:
on(X,Y,S) ∧ clear(X,S) →
ontable(X, do(putOnTable(X), S)) ∧
clear(Y, do(putOnTable(X), S))Pros: a plan can be built by deduction as a goal demonstration; first-order logic allows for high expressiveness. Problem: every action has to specify the fluents that change as well as those that are not affected; when situations go beyond the level of examples, knowledge is too much to be handled like that — the knowledge representation problem becomes intractable, even though we specify frame axioms. This is the frame problem — Chapter 9 announced it, and here it lands as the decisive obstacle that pushed planning away from pure deduction.
Kowalski’s formulation [Kowalski, 1979] makes the machinery explicit as predicates: holds(F,S) means that formula F is true in state S; holds(F,A) that F is true after action A; poss(S) that state S is actually reachable; pact(A,S) that action A can be executed in state S. The meta-axiom: poss(S) and pact(A,S) implies poss(do(A,S)).
And here is the deck’s Prolog translation — the moment Chapter 8’s machinery becomes a planner. Initial state: poss(s0), holds(on(a,d),s0), holds(on(b,e),s0), holds(on(c,f),s0), plus clear(a), clear(b), clear(c), clear(g). Action move(X,Y,Z) represents motion of block X from Y to Z, with expected effects, feasibility pre-conditions, and the frame axiom — the explicit statement of what does not change:
% expected effects
holds(clear(Y), do(move(X,Y,Z), S)).
% feasibility pre-conditions
pact(move(X,Y,Z), S) :-
holds(clear(X), S), holds(clear(Z), S),
holds(on(X,Y), S), X \= Z.
% frame axiom: everything else stays
holds(F, do(move(X,Y,Z), S)) :-
holds(F, S), F \= clear(Z), F \= on(X,Y).
% goal: a state where a is on b and b is on g
?- poss(S), holds(on(a,b), S), holds(on(b,g), S).The expected result: S = do(move(a,d,b), do(move(b,e,g), s0)) — the query returns a term that is the plan. That is deductive planning in one line: the plan is the proof term of the goal’s entailment. The price, again, is the frame axiom: every fluent, every action, every exception must be spelled out.
State-based planning sets itself a precise goal: getting rid of the frame problem. The solution is the closed-world assumption applied as a computational convention: all relations not given explicitly in a state description are assumed to be false, and relations stay valid if not explicitly deleted. Then operator effects can be calculated with simple set operations. The canonical language is STRIPS [Fikes and Nilsson, 1971] — the STanford Research Institute Problem Solver — a very restricted subset of first-order logic: basically Datalog, i.e., Prolog with no functors.
on(B,C), clear(A), clear(B), ontable(A), ontable(C);on(A,B), on(B,C);put(?x, ?y): PRE ontable(?x), clear(?x), clear(?y); ADD on(?x, ?y); DEL ontable(?x), clear(?y).Operator application moves from one state to the next, in two steps: (1) instantiate an operator with respect to the current state Si — from operator to (ground) action o; (2) calculate the successor state with set operations: if PRE(o) ⊂ Si, then Si+1 = Si \ DEL(o) ∪ ADD(o). The deck’s worked example:
put(?x, ?y) with {?x←A, ?y←B} → action o = put(A,B);The deck closes the STRIPS language section with the full Blocks World operator set: put(?x,?y) from the table, put(?x,?y) from another block, and puttable(?x) — each a PRE/ADD/DEL triple.
put(?x, ?y) % from the table
PRE: {ontable(?x), clear(?x), clear(?y)}
ADD: {on(?x, ?y)}
DEL: {ontable(?x), clear(?y)}
put(?x, ?y) % from another block
PRE: {on(?x, ?z), clear(?x), clear(?y)}
ADD: {on(?x, ?y), clear(?z)}
DEL: {on(?x, ?z), clear(?y)}
puttable(?x)
PRE: {clear(?x), on(?x, ?y)}
ADD: {ontable(?x), clear(?y)}
DEL: {on(?x, ?y)}With the language fixed, planning becomes search. A planning formalism must provide: (1) a language to represent states, goals and actions — the STRIPS language, or its extension PDDL (section 22); a planning problem is then P = (I, G, O) with an initial state I, a set of goals G, and a set of operators O; and (2) an algorithm for constructing a sequence of actions that transforms an initial state into a goal state. Operator application is a single planning step; planning is search for a sequence of action applications that transforms the initial state into a goal state.
Then the complexity warning, in two quotes the deck preserves:
The toy problems typical of classical literature present challenges which are different from those arising in more realistic application domains. Real-sized planning domains are affected by combinatorial complexity of different nature, and for this reason a large part of early and current research efforts focus on search control techniques. [Cesta and Milani, 2006]
I present several computational complexity results for propositional STRIPS planning. … These results in combination with previous analyses are not encouraging for domain-independent planning. [Bylander, 1994]
States grow exponentially — typically depth-first strategies are used — and the escape hatch is exactly the one Chapter 9 found for theorem proving: search control techniques, i.e., knowledge and heuristics to prune the space.
The first search-direction dichotomy. Progression planning is forward search: start with state S as the initial state; repeatedly construct successor states by applying actions to the current state S; eliminate cycles; if a dead end is reached, backtrack; until a goal state is reached, or no new states can be generated (for finite domains).
Regression planning is backward search: start with state S as a (partial) goal state; repeatedly construct successor states by backward applying actions to the current state S; eliminate cycles; backtrack at dead ends; until the initial state is reached, or no new states can be generated. The deck’s remark: e.g., STRIPS is regressive — the classic algorithm works from the goal back toward the initial state. The plan is then read as the path from the initial state (the leaf) to the root (the goal state).
Linear planning’s basic idea: work on one goal until completely solved before moving on to the next goal. The basic mechanism is a goal stack. Implications: no interleaving of goal achievement, and efficient search when goals do not interfere with each other (much).
Its engine is means-ends analysis: search only the relevant aspects of the problem, based on what means (operators) are available to achieve the desired ends (goal). Mechanically: find the difference between goal and current state; find an operator to reduce that difference; perform means-ends analysis on the new subgoals.
The General Problem Solver (GPS) [Newell et al., 1959] introduces means-ends analysis, and implements linear planning using recursive procedure calls as the goal-stack mechanism. Its algorithm is the chapter’s first planner pseudocode:
GPS(initial-state, goals):
if goals ⊆ initial-state then return (initial-state, [])
choose a difference d between initial-state and goals
choose an operator o to reduce the difference d
if no applicable operators, then return (∅, [])
(state, plan) = GPS(initial-state, preconditions(o))
if state ≠ ∅ then
(state, rest-plan) = GPS(apply(o, state), goals)
plan = [plan; o; rest-plan]
return (state, plan)Then the historical comparison: STRIPS vs. GPS — STRIPS is based on the same idea as GPS, but it solved the frame problem, introduced operator representation, made the notions of difference, subgoals, and operator application operational, and dealt (somewhat) with plan execution and learning.
Before exposing linear planning’s weakness, the deck defines the evaluation vocabulary for all planning algorithms:
Linear planning’s balance sheet: benefits — reduced search space (goals solved one at a time), good if goals are (mostly) independent, soundness; drawbacks — possible suboptimal solutions (one goal at a time may lead to poor goal ordering; goal interference / interaction) and incompleteness. The incompleteness is demonstrated with the chapter’s counter-example:
Operations: load(Obj, Plane, Loc), unload(Obj, Plane, Loc), fly(Plane, From, To) — where flying consumes fuel: DEL includes haveFuel(Plane). Initial state: {at(obj1, locA), at(obj2, locA), at(b747, locA), haveFuel(b747)}. Goal: {at(obj1, locB), at(obj2, locB)}.
at(obj1, locB) first, with plan [load(obj1, b747, locA); fly(b747, locA, locB); unload(obj1, b747, locB)]: final state {at(obj1, locB), at(obj2, locA), at(b747, locB)} — but subgoal at(obj2, locB) cannot be achieved, because there is no haveFuel(b747) for fly(b747, locB, locA).at(obj2, locB) first: the symmetric failure — at(obj1, locB) becomes unreachable.The problem: linear planning solves one subgoal at a time, and here STRIPS cannot achieve the two subgoals jointly. The UPS World problem is unsolvable in STRIPS — even though a perfectly good plan exists ([load(obj1); load(obj2); fly; unload(obj1); unload(obj2)] — the one the fuel makes impossible to reach by linear decomposition). The lesson: ordering goals greedily is a lossy commitment.
The escape from the UPS trap is to stop forcing an order. The deck quotes Sacerdoti’s founding paper [Sacerdoti, 1975]:
We usually think of plans as linear sequences of actions. This is because plans are usually executed one step at a time. But plans themselves are not constrained by limitations of linearity. This paper describes a new information structure, called the procedural net, that represents a plan as a partial ordering of actions with respect to time. By avoiding premature commitments to a particular order for achieving subgoals, a problem-solving system using this representation can deal easily and directly with problems that are otherwise very difficult to solve.
And the deck adds its own historical gloss: the sequential nature of computing at the time automatic planning was first faced as an AI problem might have led to linear solutions as the first and most natural approach to planning.
The deck then runs the Non-Linear FedEx World trace, where the same UPS-style problem (two objects, one plane, one unit of fuel) is solved in 12 steps by keeping a goal set, an evolving state, and a stack of chosen operators — interleaving the achievement of at(obj1,locB) and at(obj2,locB) so that both objects are loaded before the plane flies. The plan emerges as [load(obj2); load(obj1); fly; unload(obj1); unload(obj2)] — exactly the plan linear planning could not reach.
The deck’s closing quote on non-linear planners [Bundy and Wallen, 1984] plus its attribution [Ghallab et al., 2004]:
Non-linear planners are able to maintain the emerging plan as a partially-ordered network of actions. Unnecessary ordering (or linearisation) of the actions is avoided. Only when there are conflicts between parallel branches of the plan (such as the inability to determine the answer to a query) is an ordering imposed. The first such system was Sacerdoti’s NOAH. … The shift from state-space to plan-space planning is usually attributed to Sacerdoti, who developed a planner called NOAH.
The shift from state-space to plan-space planning [Ghallab et al., 2004] changes the search space itself:
The difference is not only the search space but the definition of a solution plan: plan-space planning uses a more general plan structure than a sequence of actions, where planning is considered as two separate operations — the choice of actions and the ordering of the chosen actions. A plan is a set of planning operators together with ordering constraints and (variable) binding constraints, and it may not correspond to a sequence of actions at all.
The intuitive algorithm:
while < plan not terminated >
select action N in the current plan with pre-condition C non satisfied
select action S whose expected effects include C
add to the plan:
S < N (ordering constraint)
if S does not belong to the current plan, add:
Start < S < Stop (ordering constraint)
S →C < N (causal link)
solve possible conflicts between causal linksThreats: POP switches between precondition-satisfaction steps and conflict-resolution steps. A threat is a conflict on causal links: A3 threatens A1 →C A2 if ¬C is an expected effect of A3 and no ordering constraint forces A3 before A1 or after A2. Possible solutions: impose ordering — A3 < A1 (demotion) or A2 < A3 (promotion). But promotion and demotion alone are not enough to make POP complete [Chapman, 1987].
The completion comes from the Modal Truth Criterion (MTC) [Chapman, 1987], five plan-refinement methods: establishment — satisfying preconditions with a new action, a new ordering constraint, a new variable assignment; promotion and demotion; white knight declobbering — insert A2 (the white knight) between A1 and A3 when A1 threatens A3’s precondition C, with C an effect of A2; and separation sets — non-codesignation constraints between variables (such as X ≠ Y) to prevent unifications that could threaten a causal link. MTC makes POP complete [Chapman, 1987] — possibly too (NP-)complete [Ghallab et al., 2004].
Finally, when is a partial plan a solution? A plan is consistent when there are no cycles in the ordering and no causal-link conflicts; it is a solution when it is consistent and no preconditions are left unsatisfied — then it is no longer a partial plan. And a linearisation of a partially-ordered plan is a totally-ordered plan that contains all its actions and satisfies all its constraints — every partial plan potentially generates multiple linearisations, and a sequential executor would need to pick one, possibly under external conditions that make some preferable to others.
Since the start of AI, hierarchical problem solving has been used as a method to reduce the computational cost of planning. The idea: distinguish between goals and actions of different degrees of relevance, and solve the most important problems first. Its main advantage derives from the fact that emphasising certain activities while temporarily ignoring others makes it possible to obtain a much smaller search space in which to find a plan.
The intuitive example [Yang, 1997]: suppose in the household domain we want to paint the ceiling white. Initially the number of conditions to consider may be overwhelming — availability of supplies, suppliers for equipment and tools, the position of the agent, the ladder, the state of the ceiling. But we could obtain a more manageable search space by first concentrating on whether we have the paint, the ladder, and a brush. The process repeats until a full-blown plan is finally found.
And the historical roll call: GPS, ABSTRIPS, LAWLY, NOAH, NONLIN, MOLGEN, SOAR, SIPE, AbTweak. Plus the remark that matters for the rest of the course: BDI agent frameworks such as Jason adopt a sort of hierarchical planning — plans with pre-conditions and expected effects, decomposed and expanded at need — which is precisely the AgentSpeak(L) material in the chapters following this segment.
When classical planning appeared to be stalled — for expressiveness as well as for complexity reasons — “neo-classical” techniques led to a revival of research on classical planning problems. New search spaces and algorithms allowed directly (or indirectly, through improvement of classical techniques) a significant increase in the size of classical problems that could be solved.
The main difference between classical and neo-classical techniques: in classical planning, every node of the search space is a partial plan — a sequence of actions in the state space, or a partially-ordered set of actions in the plan space — and any solution reachable from that node contains all the actions of this partial plan. In neo-classical planning, every node of the search space can be viewed as a set of several partial plans; this set is either explicit or implicit in the data structures that make a search node, but it is evident in the fact that not every action in a node appears in a solution plan reachable from that node.
Three main techniques: planning-graph techniques, based on a powerful reachability structure called a planning graph; propositional satisfiability techniques — encode a planning problem into a SAT problem and rely on efficient SAT procedures (Chapter 9’s SAT solvers return as planning engines!), including complete methods based on the Davis–Putnam procedure and pseudorandom local search methods; and constraint satisfaction techniques — encode planning into a CSP, with filtering and constraint propagation. State-based approaches currently dominate the field: Graphplan [Blum and Furst, 1997] and Satplan [Kautz and Selman, 1992]. Special aspects move beyond classical planning: temporal/resource constraints, and planning under uncertainty — conformant planning, where a conformant plan is a sequence of actions guaranteed to achieve the goal regardless of the uncertainty in the initial condition and in the nondeterministic effects of actions.
Graphplan [Blum and Furst, 1997] creates a planning graph while planning — a graph that can be built for each problem in polynomial time. It inserts the time dimension into the plan construction process; it is a correct and complete planner; it works under the closed world assumption, off-line; it performs conformant planning; and it returns either the shortest possible plan or an inconsistency. If a valid plan exists, it is a subgraph of the planning graph. Conceptually, it inherits from linear planners the early-commitment feature (“action A is executed at time step 2”) and from non-linear partial-order planners the ability to create partially-ordered sets of actions — it generates parallel plans.
You want to prepare dinner as a surprise for your sweetheart, who is asleep. Initial conditions: (and (garbage) (cleanHands) (quiet)). Goal: (and (dinner) (present) (not (garbage))). Actions: cook (precondition cleanHands; effect dinner), wrap (precondition quiet; effect present), carry (no precondition; effect (and (not garbage) (not cleanHands))), dolly (no precondition; effect (and (not garbage) (not quiet))). The planning graph grows levels of propositions and actions with mutex relations, and the backward search extracts a parallel plan — e.g., cook and wrap in parallel, then carry — while the mutex relations (carry vs. wrap, via quiet) drive the search.
Automated planning and scheduling (P&S) [Ghallab et al., 2004; Cesta and Milani, 2006] is the area of AI dealing with models and techniques for synthesising and maintaining plans of actions, strategies of execution, and resource allocation policies which allow us to realise complex tasks. More precisely:
Scheduling addresses the problem of how to perform a given set of actions using a limited number of resources in a limited amount of time. A resource is an entity that one needs to borrow or consume (a tool, a machine, or energy) in order to perform an action; an action may have the choice between several alternate resources, and a resource may be shared between several actions. The main decision variables: which resources should be allocated to the action, and when to perform it. A solution schedule must meet constraints — deadlines, ordering of actions, type and amount of resources required, availability of resources — and usually there is an optimisation requirement: e.g., achieving all actions as early as possible, or using the least costly resources.
A machine is a resource of unit capacity that is either available or not available at some time point. A job j is a partially-ordered set of one or several actions — like a plan, a job is partially ordered and its resources are left uninstantiated. In a machine scheduling problem we are given n jobs and m machines; a schedule specifies a machine i for each action of a job and a time interval during which that machine processes that action. A machine cannot process two actions at the same time, and a job cannot be processed by two machines at once — in other words, two time intervals corresponding to the same machine or to the same job should not overlap.
The deck’s example: a job-shop problem with three machines m1, m2, m3 and five jobs — e.g., j1: ⟨m2(3), m1(3), m3(6)⟩, i.e., first action on m2 for 3 time units, then m1 for 3, then m3 for 6; j4 needs four actions, m2(4), m3(6), m1(7), m2(4) — note it revisits a machine. The solution is drawn as a Gantt-like schedule where each bar denotes which machine is allocated to which job and when.
Classical planning relies on restrictive assumptions, which the deck reformulates: determinism — each action, if applicable in a state, brings to a single new state; full observability — the controller has complete knowledge about the current state, observations result in a single state; reachability goals — goals are sets of states, the objective is a plan that leads to one of them. As a consequence, plans are sequences of actions and feedback from observations is not necessary. What if we relax those assumptions?
Relaxation happens along four dimensions of uncertainty: nondeterminism, probabilities, partial observability, extended goals. The deck presents two approaches.
Planning based on MDPs [Ghallab et al., 2004] deals with nondeterminism, probabilities, partial observability, and extended goals; its key idea is to represent the planning problem as an optimisation problem, and it has shown some practical applicability to real-world domains — e.g., guiding people with dementia through activities of daily living [Boger et al., 2006]. Conventions:
Planning by model checking [Ghallab et al., 2004] deals with nondeterminism, partial observability, and extended goals; its key idea is to solve planning problems model-theoretically — Chapter 9’s model checking returns as a planning engine. It has great potential to deal with uncertainty in a general, well-founded, and practical way — in principle good for all applications where uncertainty is critical and non-nominal behaviours are relevant, such as safety-critical applications, and promising where models cannot avoid uncertainty — e.g., planning for web services. Conventions:
The deck’s closing move is methodological: no planning technique is the best in any case and application domain — different (sorts of) domains require different techniques for automatic planning to be effective. Given the number and diversity of planning techniques, comparative evaluation is mandatory to select the best approach available. Complexity measures can mostly hint at how techniques will behave on general classes of problems, yet this is too far from the specificity of most application domains to be really of help in practice. How can we lay the foundations for a widely-applicable and practically-useful comparative evaluation? Standard + competition.
The Planning Domain Definition Language (PDDL) [Ghalla et al., 1998] aims at providing the AI planning community with a standard reference language. Adopting a common formalism fosters far greater reuse of research, allows more direct comparison of systems and approaches, and therefore supports faster progress in the field [Fox and Long, 2002]. A common formalism is a compromise between expressive power (driven by potential applications) and the progress of basic research (encouraging development from well-understood foundations), and its role as a communication medium demands a clear semantics.
Components of a PDDL planning task: objects (things of interest in the world), predicates (properties of objects, true or false), initial state, goal specification, actions/operators (ways of changing the state of the world). Planning tasks are separated into two files: a domain file (predicates and actions) and a problem file (objects, initial state, goal specification).
A robot can move between two rooms and pick up or drop balls with either of its two arms; initially all balls and the robot are in the first room; we want the balls in the second room. Objects: the two rooms, four balls, two robot arms. Predicates: ROOM, BALL, GRIPPER, at-robby, at-ball, free, carry.
; ---- domain file ----
(define (domain gripper)
(:predicates (ROOM ?x) (BALL ?x) (GRIPPER ?x)
(at-robby ?x) (at-ball ?x ?y) (free ?x)
(carry ?x ?y))
(:action move :parameters (?x ?y)
:precondition (and (ROOM ?x) (ROOM ?y) (at-robby ?x))
:effect (and (at-robby ?y) (not (at-robby ?x))))
(:action pick-up :parameters (?x ?y ?z)
:precondition (and (BALL ?x) (ROOM ?y) (GRIPPER ?z)
(at-ball ?x ?y) (at-robby ?y) (free ?z))
:effect (and (carry ?z ?x)
(not (at-ball ?x ?y)) (not (free ?z))))
(:action drop :parameters (?x ?y ?z)
:precondition (and (BALL ?x) (ROOM ?y) (GRIPPER ?z)
(carry ?z ?x) (at-robby ?y))
:effect (and (at-ball ?x ?y) (free ?z) (not (carry ?z ?x)))))
; ---- problem file ----
(define (problem four-balls)
(:domain gripper)
(:objects rooma roomb ; rooms
ball1 ball2 ball3 ball4 ; balls
left right) ; robot arms / grippers
(:init (ROOM rooma) (ROOM roomb)
(BALL ball1) (BALL ball2) (BALL ball3) (BALL ball4)
(GRIPPER left) (GRIPPER right) (free left) (free right)
(at-robby rooma)
(at-ball ball1 rooma) (at-ball ball2 rooma)
(at-ball ball3 rooma) (at-ball ball4 rooma))
(:goal (and (at-ball ball1 roomb) (at-ball ball2 roomb)
(at-ball ball3 roomb) (at-ball ball4 roomb))))The diversity of approaches, the heterogeneity of application domains, and the hugely-varying performances of planning techniques make it difficult to assess comparative performance; even scientific literature’s tests and evaluations cannot really bring effective results here. This is why competitions are organised regularly. ICAPS — the International Conference on Automated Planning and Scheduling — is the most important series of conferences in the area; since 1998 it regularly organises ICAPS Competitions, typically with different tracks or themes. Competitions have not only enabled meaningful comparison, but have actually sparked constant and significant progress in planning techniques and technologies; the availability of a de facto standard language such as PDDL makes it possible to organise fair and open competitions, and to focus on comparing planning algorithms.
And RoboCup — an international scientific initiative established in 1997 with the original mission to field a team of robots capable of winning against the human soccer (football) World Cup champions by 2050, since evolved into many leagues with different robots and rules. Even though RoboCup does not specifically focus on planning, the ability to plan in a dynamically-evolving situation — and to plan as a team — is often crucial to the success of its teams. So on the one hand, RoboCup is also a planning competition; on the other, some RoboCup challenges have already been part of ICAPS competitions.
Read the whole chapter as one argument: planning is search (section 2), but over representations that decide what can be said (section 5), under assumptions that decide how hard it is (section 9), with the frame problem as the pivot that moved planning from deduction to state-based set operations (sections 10–11). Linear planning is fast but incomplete (section 15); non-linear and plan-space planning buy completeness with search space (sections 16–17); hierarchical planning buys tractability with abstraction (section 18); Graphplan buys speed with a reachability structure (section 19); time, resources and uncertainty buy realism (sections 20–21); and PDDL plus competitions buy comparability (section 22). Every step is a deal on the same currency: search.
Rational agents are provided with a goal, typically expressed as a state of the world (or a set of states) considered desirable. To achieve its goal, the agent can exploit its repertoire of actions, other agents in the MAS (society), and the resources available in the MAS environment. Automatic planning means devising a plan: a (partially or totally ordered) set of actions aimed at achieving a goal, given the state of the world, the set of actions currently available, and the goal.
In some sense planning is a normal AI search problem. Yet a dynamic environment can change the search space — even during search — and actions themselves, too. So basically, planning is unlike the usual AI search problem, in its generality at least. Planning can also be seen as synthesis of algorithms: under simple assumptions, a sort of synthesis; but functional input–output problem representation does not fit planning in dynamic environments where actions could work concurrently and interfere — as in CPS.
Agents set their own course of action and may not reason in terms of goals (e.g., Jade agents may select a pre-defined course of action). Intelligent agents could exploit proactiveness for situation recognition without a planning phase, but pre-defining all procedural knowledge becomes impossible as complexity grows, and intelligence is particularly useful in highly-unpredictable environments. Autonomous systems may deal with unpredictability without planning (e.g., self-organising systems). Overall: planning may not be strictly required, but it is clearly useful — even practically necessary — where observability, accountability and explainability are prominent requirements, in particular within socio-technical systems.
An automatic planner is a (component of an) intelligent agent working in a given application domain which, given a representation of the initial state of the world, a representation of the goal, and a formal representation of the actions available, dynamically synthesises the plan of actions required to achieve the goal. Having a plan depends on intelligence; executing a plan depends on autonomy.
Declaratively, as a conjunction of formulae representing everything known about the world; the formalism choice is a trade-off between language expressiveness and computational efficiency. Observability may be partial and inexact. The closed world assumption — more often referred to as database semantics in planning [Russell and Norvig, 2022a] — treats formulae not explicitly represented as false, which basically leads to the frame problem; CWA is just an option.
Goals typically use the same representation as the world, and the formalism should include entailment so achievement is checked as E |= G, not just E ⊇ G. Actions are described intensively as schemes with variables, instantiated to ground actions, and equipped with feasibility pre-conditions (FP), to be satisfied for executability (E |= FP), and expected effects (EE). FP and EE are the same as FP and RE (rational effects) for communicative actions in FIPA ACL.
stack(X,Y): FP holding(X) ∧ clear(Y); EE handempty ∧ clear(X) ∧ on(X,Y). unstack(X,Y): FP handempty ∧ clear(X) ∧ on(X,Y); EE holding(X) ∧ clear(Y). They are conceptually and technically symmetric — potentially usable for physical backtracking, though uncommon for real-world actions.
Soundness and completeness (if a rational plan exists the planner finds it; generated plans rationally lead to the goal); decomposability of the problem (into non-interfering subproblems/subplans); reversibility of actions (reversible actions can be backtracked; reversibility is the exception in the physical world); (non-)determinism of effects (real-world environments tend to non-deterministic effects, so actual effects must constantly be verified against the EE).
In off-line planning, the plan is produced completely before execution begins, against a snapshot of the current state. Reactive planning uses on-line algorithms [Karp, 1992]: they do not require complete input, process it piecemeal, and proceed without complete information; planning and execution are constantly alternated, with sensing typically at every step, even during execution — suited to dynamic and partially-available environments.
Atomic time (actions have no duration; instantaneous effects); determinism (once FP are met, execution always brings about EE); complete initial knowledge (everything relevant is known a priori); no disruption (the only cause of disruption is the execution of the planned actions). Equivalently: environments that are fully observable, deterministic, finite, static, and discrete. Classical planning is traditionally off-line planning.
Deductive planning uses logic to represent states, actions and goals, and generates the plan as a proof [Green, 1969; Kowalski, 1979], classically in the situation calculus [McCarthy, 1963, 1968] with situations, fluents and actions. Pros: plan built by deduction as a goal demonstration; high FOL expressiveness. Problem: every action must specify the fluents that change and those not affected; beyond examples, the knowledge representation problem becomes intractable even with frame axioms — this is the frame problem.
Kowalski’s formulation: holds(F,S) (F true in state S), poss(S) (S reachable), pact(A,S) (A executable in S), with meta-axiom poss(S) and pact(A,S) implies poss(do(A,S)). The Prolog example states the initial situation as poss(s0) plus holds/2 fluents, defines action move(X,Y,Z) with EE, FP (pact), and a frame axiom (holds(F, do(move(...), S)) :- holds(F,S), F \= clear(Z), F \= on(X,Y)), then asks ?- poss(S), holds(on(a,b),S), holds(on(b,g),S). The answer S = do(move(a,d,b), do(move(b,e,g), s0)) is the plan.
STRIPS [Fikes and Nilsson, 1971] is a very restricted subset of FOL — basically Datalog, Prolog with no functors. States are sets (conjunctions) of positive literals; goals are conjunctions of literals; operator schemes carry PRE (FP) and ADD-DEL (EE). Application: (1) instantiate an operator w.r.t. the current state Si to a ground action o; (2) if PRE(o) ⊂ Si, compute Si+1 = Si \ DEL(o) ∪ ADD(o). The worked example: put(A,B) on S0 = {ontable(A), clear(A), ontable(C), on(B,C), clear(B)} yields S1 = {ontable(C), on(B,C), on(A,B), clear(A)}, achieving the goal.
Progression is forward search: start from the initial state, construct successor states by applying actions, eliminate cycles, backtrack at dead ends, until a goal state is reached or no new states can be generated. Regression is backward search: start from a (partial) goal state, construct successor states by backward applying actions, until the initial state is reached. STRIPS is regressive.
Means-ends analysis searches only relevant aspects of the problem, based on what means (operators) are available to achieve the desired ends (goal): find the difference between goal and current state, find an operator to reduce it, and perform means-ends analysis on the new subgoals. GPS [Newell et al., 1959] introduced means-ends analysis, implementing linear planning with recursive procedure calls as the goal-stack mechanism. STRIPS is based on the same idea but solved the frame problem, introduced operator representation, and made difference, subgoals and operator application operational.
Soundness: all solutions found are legal plans — all preconditions and goals satisfied, no constraints (temporal, variable binding) violated. Completeness: a solution can be found in the search space whenever one actually exists. Strict completeness: all solutions are included in the search space. Optimality: the order in which solutions are found is consistent with some measure of plan quality.
The UPS World has load/unload/fly operators, where fly deletes haveFuel. With initial {at(obj1,locA), at(obj2,locA), at(b747,locA), haveFuel(b747)} and goal {at(obj1,locB), at(obj2,locB)}, achieving either subgoal first consumes the fuel, leaving the other object unreachable. Linear planning solves one subgoal at a time, so STRIPS cannot achieve the two subgoals jointly — the problem is unsolvable in STRIPS even though a valid interleaved plan exists.
Non-linear planning represents a plan as a partial ordering of actions [Sacerdoti, 1975] — a procedural net — avoiding premature commitments to a particular subgoal order. Basic idea: use a goal set instead of a goal stack, include all possible subgoal orderings in the search space, and handle goal interactions by interleaving. It can be sound and complete, and may be optimal w.r.t. plan length, at the cost of a larger search space and more bookkeeping. The first such system was Sacerdoti’s NOAH.
State-space planning searches for a path in the graph of a state-transition system: nodes are states, arcs are actions, a plan is a sequence of actions. Plan-space planning searches a graph whose nodes are partially-specified plans and whose arcs are plan-refinement operations; it follows the least-commitment principle (add only strictly-needed constraints), starts from the empty plan, and aims at a solution plan. A plan is a set of operators plus ordering and binding constraints, and may not correspond to a sequence of actions.
A threat is a conflict on causal links: A3 threatens A1 →C A2 if ¬C is an expected effect of A3 and no ordering constraint forces A3 before A1 or after A2. Solutions: demotion (A3 < A1) or promotion (A2 < A3). Promotion and demotion alone do not make POP complete; the Modal Truth Criterion adds establishment, white knight declobbering and separation sets, making POP complete [Chapman, 1987].
Hierarchical planning distinguishes goals and actions of different degrees of relevance and solves the most important problems first, obtaining a much smaller search space. Actions are macro-operators expanded either by generating goals for lower-level planning or by expanding pre-compiled plans (domain-specific procedural knowledge). Substitution conditions: the effect X of macro-action A must be an effect of some action of P, X protected until the end, every precondition of P enforced by P or a precondition of A, and no causal links violated. Examples: GPS, ABSTRIPS, NOAH, NONLIN, MOLGEN, SOAR, SIPE, AbTweak; BDI frameworks such as Jason adopt a sort of hierarchical planning.
In classical planning every search node is a partial plan (a sequence or a partially-ordered set), and every solution reachable from it contains all its actions. In neo-classical planning every node can be viewed as a set of several partial plans, and not every action in a node appears in a solution reachable from it. The three techniques: planning-graph techniques (Graphplan), propositional satisfiability techniques (Satplan), and constraint satisfaction techniques. Graphplan builds a levelled planning graph in polynomial time, uses mutex relations, works under CWA, and returns the shortest plan or an inconsistency.
A planning graph is a directed, levelled graph with proposition levels and action levels alternating: P1 A1 P2 A2 …. Edges are precondition (P → A), add (A → P), delete (A → P). Level P1 holds all literals of the initial state; actions enter level Ai if all their preconditions are in Pi; preconditions enter Pi if they are effects of actions in Ai−1 (including no-ops, which solve the frame problem). Exclusion (mutex) relations among incompatible propositions and actions reduce the graph size. Graphplan grows the graph until all goals are reachable and non-mutex, then searches backward for a valid plan, adding levels and retrying if none is found.
Planning and scheduling are closely related; in a simple decomposition, planning is upstream: causal reasoning to find the set of actions needed to achieve the goal (what to do). Scheduling concentrates on time and resource allocation for that set of actions (when and how to do it), respecting capacity, precedence and duration constraints, usually optimising a cost criterion. A plan output is a structured, partially ordered set of actions without resources or a precise schedule; a scheduled plan is synthesised in two steps.
In multiple-stage machine scheduling, each job has several actions requiring particular machines. Flow-shop: each job has exactly m actions, action aji processed by machine i, in the order 1, 2, …, m. Open-shop: similar, but the m actions can be processed in any order. Job-shop: the general case, where each job has a number of actions with specific machine requirements and processing order. Constraints may add deadlines, release dates, setup times and precedence constraints; criteria include makespan, maximum tardiness, weighted completion time, weighted tardiness.
As an optimisation problem: the domain is a stochastic system (nondeterministic state-transition system with probabilities); goals are utility functions over states/actions, possibly over entire execution paths; plans are policies mapping states to actions, yielding conditional and iterative behaviours; the planning problem is to maximise the utility function. Partial observability is handled via belief states (probability distributions over states), reformulating planning as full-observability planning in belief-state space, with policies mapping belief states to actions.
Planning domains are non-deterministic state-transition systems; temporal logic formulas express reachability goals and temporal goals on entire execution paths. Given a state-transition system and a temporal formula, planning generates plans that control the evolution so all behaviours make the formula true; plan validation is a model-checking problem. Symbolic techniques represent sets of states as propositional formulas and search by logical transformations, using ordered binary decision diagrams (BDD).
PDDL is the Planning Domain Definition Language [Ghalla et al., 1998], a standard reference language for the AI planning community fostering reuse and direct comparison, with a clear semantics [Fox and Long, 2002]. A planning task has objects, predicates, initial state, goal specification and actions/operators, organised in two files: a domain file (predicates, actions) and a problem file (objects, initial state, goal specification). The Gripper task with four balls is the deck’s example.
Because no planning technique is best in every case and domain, and complexity measures are too coarse for practice, comparative evaluation is mandatory: standard (PDDL) + competition. ICAPS — the International Conference on Automated Planning and Scheduling — organises ICAPS Competitions since 1998 with different tracks, sparking constant progress. RoboCup is also, on the one hand, a planning competition: planning in dynamically-evolving situations and as a team is crucial to its teams, and some RoboCup challenges have been part of ICAPS competitions.