Notes on Chapter 10: Classical Planning

chapters 8 and 9 of the textbook are an in-depth discussion of first-order logic

while the use of first-order logic is important and useful in AI, it is quite technical, and since this is a survey course we will skip to be able to spend more time on other topics

  • it is worth noting that the “logical approach” to AI is one of the major streams of AI research, and many AI researchers essentially study logic
  • this logical approach does not yet seem to have hit the “big time” in they way that machine learning and neural nets have, i.e. there are, as of yet, not many practical applications of logic-oriented AI that
    • SAT solvers may be the biggest practical success so far
  • so if you are interested in more of the logical approach to AI, we encourage you to start by reading chapters 8 and 9 of the textbook for your own interest

Planning

planning is one of the classic AI problems

it has been used as the basis for applications like controlling robots and having conversations

a plan is a sequence of actions

an action is a transformation of a state into another state, so a plan can be thought of as a series of transformations of some initial state

we usually specify an initial state and a goal state, and then try to find (a short!) plan that transform the initial state into the goal state

  • in more realistic planning problems, we might not know exactly what initial state we are in!

this “states and actions” model of planning is quite general, and so can be applied to many different kinds of problems

in general, planning is an extremely difficult problem, and planners are usually out-performed by solvers specifically customized for a particular problem

Example Planning Problem: Making Tea

suppose you have a robot that can serve tea

think about what the robot must do to make tea, e.g.:

  • it must put water in the kettle
  • heat the kettle
  • get a cup
  • pour hot water into the cup (after the water is hot enough)
  • get a tea bag
  • leave the tea bag in the water for enough time
  • remove the tea bag
  • add milk
  • add sugar
  • mix the tea
  • serve the tea

there are many, many actions to consider!

and most actions consist of many smaller sub-actions

  • e.g. the action “get a cup” might involve moving to a cupboard, opening the cupboard door, grasping a cup, taking it out of the cupboard, closing the cupboard

and in some situations, exceptional situations might trigger, very long sub-plans

  • e.g. if there is no milk, the robot might need to go to the store, or ask if creme would be an acceptable substitute
  • e.g. if the robot drops the spoon on the floor, then it must pick it up and clean it before continuing

time and sensing is important as well

  • if the kettle is heated for too long, the water might evaporate
  • how long should the robot mix the tea for?
  • is it essential to add the milk before the sugar? would it be okay to add them at the same time, or to add the sugar first?

Example Planning Problem: Getting Dressed

suppose you want to put your socks and shoes on

you have:

  • a left sock
  • a right sock
  • a left shoe
  • a right shoe

one plan for putting these on is:

  • put left sock on left foot
  • put right sock on right foot
  • put left shoe on left foot
  • put right shoe on right foot

another possible plan is:

  • put left sock on left foot
  • put left shoe on left foot
  • put right sock on right foot
  • put right shoe on right foot

for this planning problem, what matters is that the left sock is put on before the left shoe, and the right sock is put on before the right shoe

  • for many actions, the exact order of some actions might not matter
  • plus, it might be possible to do some actions in parallel, e.g. maybe you could somehow hop into both shoes at the same time

note that we made the somewhat unusual choice that there are “left socks” and “right socks”

  • more realistically, we might say we have different socks, sock1 and sock2
  • it doesn’t matter on which foot sock1 and sock2 go, so even more plans are possible
    • i.e. you could swap sock1 and sock2 in any correct plan to get another correct plan

Example Planning Problem: Blocks World

suppose you have three cubical blocks, A, B, and C, and a robot arm that can pick up and move one block at a time

suppose they are initially arranged on a table like this:

    C
  B A     initial state
-------

A and B are on the table, and C is on top of A

suppose that we want to re-arrange them into this state:

 A
 B       goal state
 C
---

furthermore, suppose we re-arrange blocks by picking up one block at a time and moving it to the table, or on top of another block

  • we can only pick up a block if there is nothing on top if it

it’s easy to see that these actions will solve this particular problem:

  • move C to the table
  • move B on top of C
  • move A on top of B

Dialog

a conversation between two people can be thought of as series of actions

  • a conversational action is sometimes called a speech act
  • for example, the command “Fire the torpedoes!” is a speech act, i.e. it is an action that tries to get listeners to shoot torpedoes
  • for example, the assertion “I’m hungry” is a speech act, i.e. it is an action that informs listeners that you are hungry
  • just like regular actions, a speech act can fail
    • e.g. if a captain gives the command “Fire the torpedoes!” and no one actually fires the torpedoes, then we could say the speech act has failed
    • e.g. if you say “I’m hungry”, but the person you’re speaking too doesn’t hear what you said, then the speech act has failed

consider this little conversation:

Customer: Can you tell me where I can find bread?

Employee: It’s in aisle 2.

Customer: Thanks!

here, the customer has the goal of “finding bread”

there are various actions they could do to achieve this goal:

  • walk around the store searching for bread
  • finding a store map that lists where bread is
  • ask someone for help

in the conversation, the person has chosen to try the “ask for help” action

  • for this action to succeed, a few things must be true as a pre-condition, e.g.:
    • they must be near an employee and speak loudly and clearly enough in English
    • they assume that the employee knows where the bread is, and they assume that the employee recognizes this and so realizes the question is in fact a request for the location of the bread — not a request to be told whether or not the employee knows where the bread is
      • i.e. the customer does not expect the employee to answer “Yes, I do know where you can find it?”
  • the employee responds with an assertion, i.e. they assert the location of the bread
  • the customer then says “thanks”, which indicates to the employee that they appreciate the help, are satisfied with their answer, and that the dialog is over
  • so we could say the customer performed a 2-action plan:
    • action 1: request location of bread
    • action 2: say thank you

if we wanted to create an agent that could participate in conversations, then we could think of it as a planning problem where speech actions must be put in the right order

Blocks World in More Detail

suppose you have three cubical blocks, A, B, and C, and a robot arm that can pick up and move one block at a time

suppose the blocks are arranged on a table like this:

    C
  B A     initial state
-------

A and B are on the table, and C is on top of A

suppose that we want to re-arrange them into this state:

 A
 B       goal state
 C
---

to write programs that can solve planning problems, we need a precise representation of states and actions

logic is often used to represent states, e.g. we could use these predicates:

  • Block(x) means object x is a block
  • On(x, y) means object x is on top of object y
  • Clear(x) means there is nothing on top of object x

we can model the initial state like this:

     C
   B A       initial state
 -------

  On(B, Table) & On(A, Table) & On(C, A)
& Clear(B) & Clear(C)
& Block(A) & Block(B) & Block(C)

clear(x) is a bit unusual, but is used because most planning languages (such as the one used in the textbook) don’t support quantifiers in state descriptions

  • i.e. if we had quantifiers we could say there is nothing on top of B with the sentence (for all blocks x).!on(x,B)
  • but out planning language doesn’t have quantifiers like “for all”, so we instead use clear(B) to explicitly indicate that B can be picked up or have another block placed on top of it

now lets consider actions

an action transforms a state, so we need to know at least two things for every action:

  • whether or not the action can be applied to a given state; this the action’s pre-condition
  • how the state changes after the action is applied; this is action’s effect

for example:

Move(b, x, y)
  Pre-condition: On(b,x) & Clear(b) & Clear(y)
         Effect: On(b,y) & Clear(x) & !On(b,x) & !Clear(y)

this is an action schema, i.e. a template that describes all possible move actions

  • it is a schema because b, x, and y are variables, and need to be filled in by actual block names

  • for instance, in a blocks world with 3 blocks, there are, at most, 3*2*1=6 move actions involving just blocks:

    Move(A, B, C)
Move(A, C, B)
Move(B, A, C)
Move(B, C, A)
Move(C, A, B)
Move(C, B, A)

Move(b, x, y) moves block b from x to y, and it’s pre-condition can be written in English like this:

  • b must clear so that b can be picked up
  • y must be clear so that b can be placed on top of it
  • b must start on top of x

the effect of Move(b, x, y) is:

  • b is on top of y
  • y is no longer clear (because b has been put on it)
  • x is clear (because b has been moved from on top of it)
  • b is no longer on top of x

the table presents a bit of a problem

  • Move(B, Table, C) has the effect Clear(Table); this is okay if by Clear(Table) we mean it’s possible to place a block on the table
  • Move(C, A, Table) has the effect !Clear(Table); but the table should always have space for a block, so that cannot happen

the usual solution to this is to add a second action schema for moving a block to the table:

MoveToTable(b, x)
   Pre-condition: On(b, x) & Clear(b)
          Effect: On(b, Table) & Clear(x) & !On(b, x)

again this is an action schema: filling in b and x with block names from our 3-block world results in 3*2=6 actions

blocks world is an interesting problem because it is relatively simple, and general-purpose planners (without heuristics specific to blocks world) can have trouble finding short plans

Propositional Planning

in practice, many planners use propositions instead of full-blown predicate logic to describe actions and states

in propositional planning, states can be thought of as a set of variables (representing things known to be true), with the understanding that a variable that does not appear in a state is false

  • i.e. states list only true facts; any facts not listed are assumed to be false

action schemas can then be simplified like this:

SomeAction
  Pre-condition: a,b,c
       Add list: e,f
    Delete list: a,b

SomeAction can be applied to any state that has {a,b,c} as a subset

  • for example, consider the state s={a,b,c,d}
  • SomeAction can be applied to it because {a,b,c} is a subset of s
  • when SomeAction is applied to s, a copy of s is made, but {a,b} is removed and {e,f} is added; i.e. the copy is s - {a,b} union {e,f}

in general, we have this equation for applying an action a to some state s:

Result(a, s) = (s - Del(a) U Add(a))

Del(a) is the delete list for action a, and Add(a) is the add list for a

this shows us how to go forward from one state to another by applying an action

Planners: Forward Planners

a forward planner, or progression planner starts at the initial state, and applies actions in an effort to find a path to the goal state

until about the year 2000, forward planning was thought to be too inefficient to be practical

some apparent problems with forward planning are:

  • how can you choose what action to apply to a state when there are, say, thousands of actions to choose from?
    • e.g. the textbook gives the example of buying a book online using the action scheme Buy(isbn), where isbn is an ISBN number for a book
    • an ISBN has at least 10 digits, so a planner would have to essentially enumerate all 10 billion ISBN numbers to choose among Buy(isbn) actions
  • the search spaces can be huge for even problems that don’t seem that big
    • e.g. the textbook gives the problem 10 airports, where each airport has 5 planes and 20 pieces of cargo
    • the problem is to move all the cargo at airport A to airport B
    • the solution is easy: put all 20 pieces of cargo into a plane at A, and fly it to B, and unload all the cargo (for a total of 41 actions)
    • the difficulty is that the branching factor is very large, i.e. there are 50 planes in total that can fly to 9 different airports, and 200 pieces of cargo that can be loaded or unloaded
      • between 450 and 10450 actions per state!
      • if we assume 2000 actions per state on average, then the obvious 41 move solution is in a search tree with \(2000^{41}\) nodes

surprisingly, forward planning’s fortunes changed in the early 2000s — we’ll say more about them below

Planners: Backward Planners

a backward planner, or regression planner, starts at the goal state, and works backwards from that to try to find a path to the state

for many decades, backwards planners were thought to be inherently more efficient than forward planners because they only consider actions that are relevant to the goal

considering only relevant actions usually results in a smaller branching factor

however, it does require that you apply actions “in reverse”, which results in having to deal with sets of states instead of individual states (as in forward planning)

Planning Heuristics

it appears now that the best forward planners are more efficient than the best backwards planners

the essential reason is that very good general-purpose, and problem-specific, heuristics have been found for forward planners, but similarly good heuristics have not been found for backwards planners

for example, one good general-purpose forward planning heuristic is to ignore pre-conditions of actions: this gives a relaxed version of the planning problem that is still hard to solve, but for which pretty good approximation algorithms exist

another useful technique is to create a so-called planning graph, which can give good estimates of how many actions might be needed to reach a goal

  • if you are curious, see the textbook for details on how to create planning graphs, and how a planning graph can be used to make a complete planner knowns as GraphPlan

Planners: SATPlan

another efficient approach to basic planning is to convert a planning problem into a SAT problem, and then to use a SAT solver to find a solution

the trick here is to come up with a propositional encoding of a planning problem

  • if you are curious, section 10.4.1 of the textbook outlines how to do this conversion: it has many steps, but it is fairly straightforward

Planners: Partial Order Planners

before the success of forward planners, many AI researchers thought partial order planners might be a good approach to planning

partial order planners don’t require all actions to be executed in a particular order: for some actions the order might not matter

  • e.g. if you have to put on your socks, it doesn’t matter if you put the left one on first, or the right one on first

a partial order plan is a set of actions plus a set of constraints on those actions of the form Before(a_i, a_j) (which means action a_i occurs before action a_j)

partial order planners search through plan space, instead of state space

  • i.e. the nodes of the search tree for a partial order planner contain plans instead of descriptions of search spaces

a partial-order planner starts with the empty plan, and then tries inserting actions in a way that corrects some flaw in the current plan

  • a flaw is anything keeps the plan from being true
  • the order in which flaws are addressed are important, and so backtracking might be necessary

partial-order planners have not seen the same success as total-order order planners

  • it seems that this is largely due to the difficulty of finding good heuristics for partial order planners

And More …

forward planners are fast, but not really fast and efficient enough to be very useful in practice

so planning is still a research topic; new planners and techniques are being proposed all the time

also, here we only discussed the simplest sort of planning problems

real-life planning problems introduce other complexities, such as:

  • resource constraints, e.g.
    • the plan you create might not be allowed to over-use some action, e.g. perhaps a robot arm can only be moved three times in a row before it over-heats and must rest
    • you might have to figure out a plan in a limited amount of time, i.e. the planner itself has a time constraint on how long it can run for
  • domains might be non-deterministic, i.e. some actions might have random effects and so you can’t be sure what state you are in after they are applied
    • imagine a robot that rolls dice
    • imagine a robot that turns its wheels to drive forwards but the wheels slip and so it doesn’t actually move
  • multi-agent planning occurs when you have more than one agent that can participate in the plan; the agents must coordinate their actions to solve problems
    • note that multi-agent planning could involve just two agents, e.g. in dialog, or hundreds or thousands of agents working together (like a swarm of insects or flock of birds)

finally, we note one other interesting problem related to planning: plan recognition

imagine you are watching an agent perform some actions: can you determine from the actions alone what plan, if any, the agent is following?

if you can figure out what plan an agent is following, then you might be able to predict what they are going to do (and then help them out)

  • e.g. imagine your Google Home watches you cooking in the kitchen, and from your actions comes to believe that you are trying to cook spaghetti; it might suggest a good recipe, or tell you that you are missing certain ingredients, etc.