Definition of Classical Planning

• AI has been defined as the study of rational action
  • Requires planning: a plan of action to achieve goals
• Problem solving agent (chapter 3) finds sequences of actions to get into goal states
  • Deals with atomic representations of states
  • Requires good domain-specific heuristics to perform well
  • This representation is not good for planning!

Definition of Classical Planning

• Another possibility is to use a hybrid propositional logic agent (chapter 7)
• A hybrid propositional logic agent finds plans without domain specific heuristics
  • Uses domain independent heuristics, based on logical structure of the problem
  • Relies on ground (no-variables) propositional inference
  • Might be swamped when there are many actions and states (Wumpus-agent: moving in 4 directions, T time steps, and \(n^2\) current locations)
  • This representation is not good for planning either

Definition of Classical Planning

• Planning researchers use a factored representation
  • A state of the world stated in a collection of variables
  • PDDL: Planning Domain Definition Language
• PDDL to define a search problem
  1. Initial state
  2. Actions available in the state
  3. Result of applying an action
  4. Goal test

Definition of Classical Planning

• States represented as conjunction of fluents
  • Fluents are ground functionless atoms
    • i.e. \(Poor \land Unknown\), state of a hapless agent
    • i.e. \(At(Truck_1, Melbourne) \land At(Truck_2, Sydney)\), state for a package delivery system
  • Uses database semantics
    • Closed-world assumption: fluents that are non mentioned are assumed false
    • Unique names assumption: i.e. \(truck_1\) is different to \(truck_2\)
  • These fluents are not allowed in a state
    • \(At(x,y)\) not allowed (it is non-ground)
    • \(\neg Poor\) not allowed (it is a negation)
    • \(At(Father(Fred), Sydney)\) not allowed (it uses a function symbol)

Definition of Classical Planning

• States represented as conjunction of fluents
  • Representation carefully designed so that it is treated as a
    • Conjunction of fluents, manipulated by logical inference
    • Set of fluents, manipulated with set operations (set semantics sometimes easiear to deal with)

Definition of Classical Planning

• Actions
  • Described by a set of action schemas
  • Implicitly define ACTIONS(\(s\)) and RESULT(\(s,a\))
  • Needed to do a problem-solving search
• The frame problem
  • Any system for action description needs to solve the frame problem
  • Specify what changes and what stays the same as result of an action
  • Classical Planning concentrates on problems where most actions leave most things unchanged
  • PDDL specifies the result of an action in terms of what changes, what remains the same is not mentioned

Definition of Classical Planning

• Action Schema
  • A set of ground (variable-free) actions
  • The schema is a lifted representation
  • Lifted representation: lifts level of reasoning from propositional logic to a restricted subset of first-order logic
• Example of an action schema
  • \(Action(Fly(p,from,to),\)
    • \(PRECOND:At(p,from) \land Plane(p) \land Airport(from) \land Airport(to)\)
    • \(EFFECT: \neg At(p,from) \land At(p,to))\)

Definition of Classical Planning

• Schema
  • Action name
  • List of all variables used in the schema
  • A Precondition
  • An Effect
• \(Action(Fly(P_1, SFO, JFK),\)
  • \(PRECOND: At(P_1,SFO) \land Plane(P_1) \land Airport(SFO) \land Airport(JFK)\)
  • \(EFFECT: \neg At(P_1, SFO) \land At(P_1, JFK))\)

Definition of Classical Planning

• PRECONDITION and EFFECT
• PRECONDITION and EFFECT are conjunctions of literals (positive or negated atomic sentences)
• PRECONDITION
  • Defines the states in which the action can be executed
• EFFECT
  • Defines the result of executing the action
• An action \(a\) can be executed in state \(s\) if \(s\) entails the precondition of \(a\)

Definition of Classical Planning

• Applicable actions
  • An action \(a\) is applicable in state \(s\) if the preconditions are satisfied by \(s\)
  • Finding applicable ground actions
    • When action schema contains variables: i.e. if action \(a\) has \(v\) variables, in a domain with \(k\) unique names of objects
    • Takes \(O(k^v)\) time (worst case) to find the applicable ground actions
      • Substituting unique names of objects in variables and verify if the resulting action is applicable in state \(s\)

Definition of Classical Planning

• Applicable actions, through propositionalization
• Schemas can be Propositionalized
  • Replace each action schema with a set of ground actions
  • We then use a propositional solver (i.e. SATPlan) to find a solution
  • Impractical when \(v\) and \(k\) are large

Definition of Classical Planning

• RESULT
• The result of executing an action \(a\) in state \(s\) is defined a a state \(s'\)
  • The set of fluents in \(s\) but \(\dots\)
    • But removing those that appear as negative literals in the EFFECT of the action
      • Delete list or DEL(a)
    • Adding those that appear as positive literals in the EFFECT of the action
      • Add list or ADD(a)
  • \(RESULT(s,a) = (s - DEL(a)) \cup ADD(a)\)
• With \(Fly(P_1, SFO,JFK)\) we would remove \(At(P_1,SFO)\) and add \(At(P_1,JFK)\)
  • Any variable in the effect must appear in the precondition
    • All variables will be bound and \(RESULT(s,a)\) will have only ground atoms

Definition of Classical Planning

• Time in PDDL
• In PDDL times and states are implicit in the action schemas
  • Precondition always refers to time \(t\)
  • Effect refers to time \(t +1\)

Definition of Classical Planning

• Defining an Initial state and a Goal
• Initial state is a conjunction of ground atoms
• Goal is as a precondition
  • A conjunction of literals (positive or negative), may contain varialbes: \(At(p, SFO) \land Plane(p)\) (have any plane at SFO)
  • Variables treated as existentially quantified
• Planning as a Search problem
  • Find a sequence of actions that end in a state \(s\) that entails the goal

Example: Air Cargo Transport

Example: Air Cargo Transport

• Problem involves loading and unloading cargo and flying it from place to place
• Three actions: Load, Unload, Fly
• Actions affect two predicates:
  • In(c,p): cargo \(c\) is in plane \(p\)
  • At(x,a): object \(x\) (plane or cargo) is at airport \(a\)
  • When a plane flies from one airport to another all cargo inside moves with it
  • In FOL we could use quantifiers (i.e. \(\forall\)), but PDDL doesn’t have \(\forall\)
    • A piece of cargo ceases to be \(At\) a place when it is \(In\) a plane
    • A piece of cargo becomes \(At\) the new airport when it is unloaded

Example: Air Cargo Transport

• A plan solution to the problem
  • \([Load(C_1, P_1, SFO), Fly(P_1,SFO,JFK), Unload(C_1,P_1,JFK)\),
  • \(Load(C_2,P_2,JFK), Fly(P_2,JFK,SFO), Unload(C_2,P_2,SFO)].\)
• Spurious actions: \(Fly(P_1, JFK, JFK)\)
  • Contradictory effects: \(At(P_1,JFK) \land \neg At(P_1,JFK)\)
  • We may add a precondition: i.e. the from and to airports must be different

Example: The Spare Tire Problem

• Problem of changing a flat tire
  • Goal: properly get and mount the spare tire onto the car’s axle
  • Initial state: flat tire on the axle and a good spare tire in the trunk
  • This example keeps it simple: no sticky lug nuts nor other complications
  • Assumptions:
    1. Car is parked in a bad neighborhood
    2. Leaving car unattended overnight may make the tires disappear

Example: The Spare Tire Problem

• Problem of changing a flat tire
  • Only four actions
    1. Remove spare from trunk
    2. Remove flat tire from axle
    3. Put spare on axle
    4. Leave car unattended overnight
  • A solution
    • \([Remove(Flat,Axle), Remove(Spare,Trunk), PutOn(Spare,Axle)]\).

Example: The Spare Tire Problem

Example: The Blocks World

• Famous planning domain
• A set of cube-shaped blocks sitting on a table
• Blocks can be stacked, only one block can fit directly on top of another
• Robot arm picks up a block and moves it to another position
  • On the table or on top of another block
  • Arm can pick only one object at a time (can’t pick an object that has another one on it)

Example: The Blocks World

• Goal: build one or more stacks of blocks, specifying which blocks are on top of what other blocks
  • i.e. Get block \(A\) on \(B\) and \(B\) on \(C\)
  • \(On(b,x)\) means that block \(b\) is on \(x\), where \(x\) can be another block or the table
  • \(Move(b,x,y)\) is the action of moving block \(b\) from the top of \(x\) to the top of \(y\) if \(b\) and \(y\) are clear
    • After the move, \(b\) is still clear but \(y\) is not
    • \(Action(Move(b,x,y)\),
      • PRECOND: \(On(b,x) \land Clear(b) \land Clear(y)\),
      • EFFECT: \(On(b,y) \land Clear(x) \land \neg On(b,x) \land \neg Clear(y))\).
    • Doesn’t mantain the Clear property when \(x\) or \(y\) is the table
      • The table should not become clear: \(Clear(table)\)
    • Fixing the problem
    • \(Action(MoveToTable(b,x)\),
      • PRECOND: \(On(b,x) \land Clear(b)\),
      • EFFECT: \(On(b, Table) \land Clear(x) \land \neg On(b,x))\).

Example: The Blocks World

Example: The Blocks World

Complexity of Classical Planning

• PlanSAT: Question of whether there exists any plan that solves a planning problem.
• Bounded PlanSAT: Asks whether there is a solution of length \(k\) or less, can be used to find an optimal plan
• Both decision problems are decidable for classical planning
  • If we add function symbols to the language
    • Number of states becomes infinite
    • PlanSAT becomes semidecidable
      • An algorithm that will terminate with the correct answer for any solvable problem exists, but may not terminate on unsolvable problems
    • Bounded PlanSAT is still decidable when we add function symbols
• Complexity of PlanSAT and Bounded PlanSAT is in class PSPACE, larger and more difficult than NP

Algorithms for Planning as State-Space Search

• Forward (progression) state-space search
  • We use heuristic search algorithms (chapter 3) or local search algorithm (chapter 4)
    • We keep track of actions used to reach the goal state
    • We choose action from those that are applicable
    • Need accurate heuristic
  • 1961 until 1998, assumed that forward state-space search was too inefficient to be practical
    • Forward search prone to exploring irrelevant actions
      • i.e. buying a book by ISBN (10 digits number), search through 10 billion ground actions, enumerating too many ISBN’s to reach the goal state
    • Planning problems often have large state spaces
      • i.e. Air cargo problem with 10 airports, 5 planes and 20 pieces of cargo per airport
      • Goal: moving cargo from airport A to airport B
      • Average branching factor is huge: 50 planes can fly to 9 other airports, each of 200 packages can be unloaded or loaded
      • Minimum of 450 actions per state (all packages at airports with no planes)
      • Maximum of 10,450 (all packages and planes at the same airport)
      • Search graph with around 2000 possible actions per state: depth of solution has about \(2000^{41}\) nodes

Algorithms for Planning as State-Space Search

• Backward (regression) relevant-states search
  • Start at the goal
  • Apply the actions backward until we find a sequence of steps that reaches the initial state
  • Called relevant-states
    • Only consider actions relevant to the goal (or current state)
    • There is a set of relavant states to consider at each state (not only one)
  • \(n\) ground fluents in a domain \(\rightarrow\) \(2^n\) ground states (each fluent can be true or false), there are \(3^n\) descriptions of sets of goal states (each fluent can be positive, negative or not mentioned)
  • Works when we are able to compute the predecessors of a state or set of states
    • 8 queens?, it is difficult, describe states one move from the goal
  • PDDL used to regress a goal description through an action
    • Given ground goal \(g\) and ground action \(a\), regression from \(g\) over \(a\) gives state description \(g'\) with positive and negative literals given by:
    • POS(\(g'\)) = (POS(\(g\)) - ADD(\(a\))) \(\cup\) POS(\(Precond(a)\)).
    • NEG(\(g'\)) = (NEG(\(g\)) - DEL(\(a\))) \(\cup\) NEG(\(Precond(a)\)).
  • We choose actions from those that are relevant, that could be the last step in a plan leading up to the current goal state

Algorithms for Planning as State-Space Search

• Heuristics for planning
  • \(h(s)\) estimates distance from a state \(s\) to the goal
  • If we find an admissible heuristic (one that doesn’t overestimate), we can use \(A^*\)
    • In order to find optimal solutions
    • To define an admissible heuristic we could relax the problem (define a problem easier to solve)
  • Important to make forward or backward search efficient
• Search problem as a graph
  • Nodes are states and edges are actions
  • Problem is to find a path from initial state to a goal state
  • Two ways to relax the problem
    • Adding edges to the graph, makes it easier to find a path to the goal
    • Grouping multiple nodes together, abstraction of the state space with fewer states, easier to search

Algorithms for Planning as State-Space Search

• Heuristics for planning
• Ignore Preconditions Heuristic - adds edges to the graph
  • Drops all preconditions from actions
  • Every action becomes applicable in every state
  • Any single goal fluent can be achieved in one step (if there is an applicable action)
  • For many problems we find heuristics by
    • Relax the actions (remove all preconditions and all effects except those that are literals in the goal)
    • Count the number of actions required such that the union of those actions’ effects satisfies the goal
      • Instance of the set-cover problem
      • NP-hard
      • Greedy algorithm runs in \(\log n\)
      • Loses guarantee of admissibility
• Possible to ignore only selected preconditions of actions
  • Sliding-block puzzle
  • Planning problem involving tiles with a single schema Slide:
    • \(Action(Slide(t, s_1, s_2)\),
      • PRECOND: \(On(t,s_1) \land Tile(t) \land Blank(s_2) \land Adjacent(s_1, s_2)\)
      • EFFECT: \(On(t,s_2) \land Blank(s_1) \land \neg On(t,s_1) \land \neg Blank(s_2))\)
  • Removing preconditions \(Blank(s_2) \land Adjacent(s_1, s_2)\)
    • Any tile can move in one action to any space
    • We get the number-of-misplaced-tiles heuristic
  • Removing \(Blank(s_2)\), we get the Manhattan-distance heuristic

Algorithms for Planning as State-Space Search

• Heuristics for planning
• State Abstraction - grouping nodes
  • Relaxed problems simplified but still expensive to solve
  • Many planning problems have too many states (i.e. \(10^{100}\))
    • Relaxing the actions does not reduce the number of states
    • Now we work in relaxations to decrease the number of states
    • Form a state abstraction
      • A many-to-one mapping from the ground representation to the abstract representation
  • Forms of abstraction
    • Ignore some fluents
      • In the cargo problem:
        • 10 airports, 50 planes, 200 pieces of cargo
        • Each plane can be at one of 10 airports, each package can be uploaded into a plane or unloaded at an airport
        • There are \(50^{10} \times 200^{50+10} \approx 10^{155}\) states
      • Particular cargo problem instance:
        • All packages are in 5 airports
        • All packages at given airport have the same destination
        • A useful abstraction
          • Drop all the \(At\) fluents except those involving a plane and one package at each of the 5 airports
          • There are \(5^{10} \times 5^{5+10} \approx 10^{17}\) states

Algorithms for Planning as State-Space Search

• Heuristics for planning
  • When defining heuristics
    • A key idea is decomposition:
      • Divide the problem into parts
      • Solve each part independently
      • Combine the parts
    • We make the subgoal independence assumption
      • The cost of solving a conjunction of subgoals is approximated by the sum of the costs of solving each subgoal independently
      • This assumption can be:
        • Optimistic: there are negative interactions between subplans
        • Pesimistic (therefore inadmissible): when subplans contain redundant actions
          • i.e. two actions that could be replaced by a single action in the merged plan

Planning Graphs

• All previous heuristics suffer from inaccuracies
• Data structure called a Planning Graph can be used to get better heuristic estimates
  • We can search for a solution over space formed by planning graph using algorithm GRAPHPLAN
• Planning problem
  • Asks if we can reach a goal from the inital state
  • We can construct a tree of all possible actions from initial state to successor states, and their successors, and so on
  • With this tree we could answer the planning question
    • Can we reach state G from state \(S_0\)
    • Just by looking into the tree
    • But the tree size is exponential and this approach is impractical
  • A planning graph is a polynomial-size approximation to the tree and can be quickly constructed
    • Can’t answer definitively if \(G\) is reachable from \(S_0\)
    • But it can estimate how many steps it takes to reach \(G\)
    • Always correct when it finds that the goal is unreachable
    • Never overstimates the number of steps, it is an admissible heuristic

Planning Graphs

• Planning problem
  • Planning Graph
    • Directed graph organized into levels
      • First level \(S_0\) for initial state
        • Nodes representing each fluent that holds in \(S_0\)
      • Level \(A_0\)
        • Nodes for each ground action that might be applicable in \(S_0\)
    • Alternates levels \(S_i\) followed by \(A_i\)
      • Until we reach a termination condition
    • \(S_i\) contains all literals that could hold at time \(i\) depending on actions executed at previous time steps
      • If \(P\) or \(\neg P\) could hold, both will be in \(S_i\)
    • \(A_i\) (roughly speaking) contains all actions that could have their preconditions satisfied at time \(i\)
      • Roughly speaking because planning graph records only resticted subset of possible negative interactions among actions
      • A literal might show up at level \(S_j\) when it could not be true until a later level (if at all)
        • A literal will never show up too late
    • Planning graphs only work for propositional planning problems
      • Those with no variables
      • Straightforward to propositionalize a set of action schemas
    • Although problem description grows, planning graphs are effective tools in practice

Planning Graphs

• The have cake and eat cake too problem

Planning Graphs

• Planning graph for the have cake and eat cake too problem
  • Actions at level \(A_i\) connected to preconditions at \(S_i\) and its effects at \(S_{i+1}\)
  • A literal appears because an action caused it
  • A literal can persist if no action negates it
    • Represented by a persistence action ( a no-op)
    • Example shows
      • 1 real action: \(Eat(Cake)\)
      • 2 persistence actions drawn as small square boxes
  • Level \(A_0\) has all actions that could occur in state \(S_0\)
    • It also records conflicts between actions that would prevent them from occurring together
      • Grey lines show mutual exclusion or mutex links
      • i.e. \(Eat(Cake)\) is mutually exclusive with persistenc of either \(Have(Cake)\) or \(\neg Eaten(Cake)\)
  • Level \(S_1\) contains literal that could result from picking a subset of actions in \(A_0\)
    • Also shows mutex links (for literals that cannot appear together)
      • i.e. \(Have(Cake)\) and \(Eaten(Cake)\)
    • \(S_1\) represents a belief state, a set of possible states
  • Levels \(S_i\) and \(A_i\) alternate until two consecutive levels are equal
    • Until the graph has leveled off
    • Graph in figure levels off at \(S_2\)

Planning Graphs

Planning Graphs

• Planning Graphs for Heuristic Estimation
  • Planning graph is a rich source of information about the problem
  • If goal literal doesn’t appear in final level of the graph
    • The problem is unsolvable
• Level Cost Heuristic
  • The cost of achieving any goal literal \(g_i\) from an initial state \(s\)
    • The level in which \(g_i\) first appears in the planning graph from initial state \(s\)
    • This estimate is admissible but might sometimes be innacurate
      • Because of the several actions at each level that are allowed
• Serial Planning Graph
  • Only one action can actually occur at any given time step
  • Achieves this by using mutex links between every pair of nonpersistence action
  • Better estimates than with level cost heuristic

Planning Graphs

• Planning Graphs for Heuristic Estimation
  • Heuristics to estimate the cost of a conjunction of goals
• Max-level heuristic
  • Applies maximum level cost of any of the goals
  • Admissible but might not be accurate
• Level-sum heuristic
  • Returns the sum of level costs of the goals
  • Can be inadmissible but in practice, it works well
    • For problems that are largely decomposable
• Set-level
  • Finds the level at which all literals in conjuctive goal appear in the planning graph
    • None of them being mutually exclusive (no mutex links between them)
  • It is admissible
  • Works very well on tasks with interaction among plans
  • Ignores interactions among three or more literals

Planning Graphs

• The GRAPHPLAN Algorithm
  • To extract a plan from the planning graph
  • Repeatedly adds a level to a planning graph with EXPAND-GRAPH
  • When goals show up as non-mutex, GRAPHPLAN calls EXTRACT-SOLUTION
    • Looking for a plan that solves the problem
    • If it fails, it expands another level and tries again
    • If no reason to continue, it terminates

Planning Graphs

• International Planning Competition
  • Top performing systems

Other Classical Planning Approaches

• Most popular approaches for fully automated planning
  • Translating to a Boolean satisfiability (SAT) problem
  • Forward state-space search with carefully crafted heuristics
  • Search using a planning graph
• Other approaches
  • Planning as first-order logical deduction: Situation calculus
  • Planning as constraint satisfaction
  • Planning as refinement of partially ordered plans