1. Introduction and JUnit
Planning
1
To exhibit intelligent (rather than random or else rigid) behavior, agents must plan.
1
Examples: Plan …
2
… a wedding
… a trip
… a project
… a move
between apartments
between houses
from one business location to another
… a robot’s course of action
Robots, and agents in general, are much more effective if they have a plan rather that following a purely greedy algorithm.
2
Planning: Learning Objectives
Recognize actions applicable in states
Plan forward or backward
Apply to programming
3
By the end of this module, you will be able to observe states as the mode for a plan, distinguish the creation of a plan by beginning with the initial state, or else with a final desired state.
The ideas are applicable to programs, which are a kind of plan.
3
Planning
Introduction
Forward vs. Backward Planning
Heuristics and Plan Graphs
Conclusion
In this section we discover what’s involved in planning.
Example: Outcome
Consider the problem of finding a way to manufacture an item, such as the one shown made from a single flat piece of metal. This is backward planning.
The problem of assembling items (creating molecules, packing a box etc.) is similar.
5
Example: Plan Folding Operations
The figure shows a way to do this. The question is: can this plan be arrived at through an (AI planning) algorithm. The advantages include faster manufacturing, less waste, and labor saving.
6
Example Source
The figure shows an abstract of this particular paper.
7
Planning for Extraterrestrials
8
Planning is also required for the increasing autonomy of vehicles, just as humans exercise as much foresight as they can in operating them. This is especially true of extraterrestrial vehicles, which cannot be controlled in real time.
8
What is a Plan?
9
A sequence of actions.
e.g., to get to NYC
Obtain from action inventory indexed by state.
the initial state
e.g., (agent is) in JP, Boston or agent1 in …. and agent2 in …
…
A plan, formally speaking, is a sequence of actions that accomplish a goal. Each action changes the state of the agent, agents, or system. The set of available actions depends on the state.
9
What is a Plan?
10
A sequence of actions.
e.g., to get to NYC
Obtain from action inventory indexed by state.
the initial state
e.g., (agent is) in JP, Boston or agent1 in …. and agent2 in …
the actions available in a state
the result of applying an action
the goal test
(agent is) in NYC?
A plan, formally speaking, is a sequence of actions that accomplish a goal. Each action changes the state of the agent, agents, or system. The set of available actions depends on the state.
10
States
Source: Russell and Norvig
Each state is represented as a conjunction of “fluents”: ground, functionless atoms.
For example,
Poor ∧ Unknown,
In_JP ∧ Have_car
In general, a state is defined by values of variables. For example, the state “Late for Work” is defined by t > K where t is the variable time to get to work and K is minimum time to get to work without being late. In this example, the variable (t) is continuous.
Russell and Norvig simplify this by considering only a discrete variable (sometimes called state)—that can only take a set of values from a finite set. These values are called fluents, and are given names. An example is
state = {Poor, Unknown}
11
A State Example …
Source: Russell and Norvig
The simplified version of states are often expressed in planning as predicates, such as those in the figure. This is like a variable At, whose values are pairs.
12
Closed World Assumption
13
Anything not provable is assumed to be false.
Example…
In AI, we often choose to make the closed world assumption. Think of it as ultra-science-based: assume that anything unprovbable within a system is actually false within that system.
13
Apply Closed World Assumption
14
Anything not provable is assumed to be false.
Example: Plan a driving vacation between Denver and LA.
If steep roads are en route can’t be established from the given environments,
assume that there are none.
The CWA is by no means foolproof, as the example in the figure suggests.
14
Action Schemas
15
A set of actions may be represented by a single action schema.
…
Source: Russell and Norvig
So far, our discussion of planning has involved simple states (e.g., At(Truck, Melbourne)) and actions. This is addressed with schemas—set of actions.
15
Action Schemas
16
A set of actions may be represented by a single action schema.
Lifts level of reasoning from propositional logic to first-order logic.
For example, …
Source: Russell and Norvig
So far, our discussion of planning has involved simple states (e.g., At(Truck, Melbourne)) and actions. This is addressed with schemas—set of actions.
16
Action Schemas
17
A set of actions may be represented by a single action schema.
Lifts level of reasoning from propositional logic to first-order logic.
For example, an action schema for flying a plane from one location to another:
Action(
Fly(p, from, to),
PRECOND: At(p, from) ∧ Plane(p) ∧ Airport(from) ∧ Airport(to)
EFFECT: ¬At(p, from) ∧ At(p, to)
)
Source: Russell and Norvig
Schemas tell what the effects (the postconditions) are for an action—under what preconditions.
17
Recall a Plan
18
A sequence of actions, given …
the initial state
the actions available in a state
the result of applying an action
the goal test
A plan, formally speaking, is a sequence of actions that accomplish a goal. Each action changes the state of the agent, agents, or system. The set of available actions depends on the state.
18
Plan Example: Spare Tire
19
Source: Russell and Norvig
Schemas
Consider the goal At(Spare, Axle) (the spare tire is installed), given Tire(Flat) (the regular tire is flat) etc. What plan (sequence of schemas) accomplishes this?
We show the beginning of the first schema of such as sequence: Action(PutOn(t, Axle) …
19
Plan Example: Spare Tire
20
Source: Russell and Norvig
The sequence of actions is Remove(Tire, Axle), PutOn(Spare, Axle), LeaveOvernight, and each is defined above with their pre- and postconditions. Notice that we can’t assume any common sense: for example, the logic has to be explicit, in the last Action, that the Spare is not at specific locations—other than the axle.
20
21
(Classical) Blocks World
Source: Russell and Norvig
A simple example shows the principles: such is the purpose of the blocks shown in the figure.
21
22
Blocks World
Source: Russell and Norvig
The figure shows the totality of initial conditions.
22
23
Blocks World
Source: Russell and Norvig
The Action needed to accomplish the goal are instances of Move, as defined in the figure.
23
Plan Example
24
There is cargo at San Francisco, which we want at JFK.
There is cargo at JFK which we want at San Francisco.
We have a plane at San Francisco and one at JFK.
Develop a plan (at the level of load/unload/fly).
WHAT PDDL* INPUT DOES THIS TRANSLATE TO?
* Planning Domain Definition Language
The figure poses a practical planning example. It refers to PDDL (the Planning Domain Definition Language), which Russell and Norvig translate into logic notation as in the figures.
24
PDDL
25
“The Planning Domain Definition Language (PDDL) is an attempt to standardize Artificial Intelligence (AI) planning languages.” (Wikipedia)
Can specify
the initial state
the actions available in a state
the result of applying an action
the goal test
https://github.com/pellierd/pddl4j/wiki/A-tutorial-to-start-with-PDDL
An available action schema
The figure specifies the initial conditions, the goal, and the first action of the plan.
26
The plan is completed in this figure.
27
PDDL (Code) Examples
28
https://github.com/pellierd/pddl4j/wiki/Logistics:-a-simple-running-example
(logistic application)
http://kcl-planning.github.io/ROSPlan//demos/robot_pages/squirrel.html
(demo)
https://github.com/pellierd/pddl4j/wiki/Logistics:-a-simple-running-example
(code but no demo)
The figure lists a PDDL de mo, code base, and (essentially) a marketing example. The syntax of PDDL is rooted in LISP.
28
Planning
Introduction
Forward vs. Backward Planning
Heuristics and Plan Graphs
Conclusion
In this section we compare the two principal poles of planning: forwards from the initial conditions, and backward from the goal.
Forward Planning
30
Source: Russell and Norvig
Start with initial state
In (pure, un-pruned) forward planning, we generate all possible permissible actions until the goal is encountered. A beginning is shown in the figure.
30
Backwards Planning
31
Source: Russell and Norvig
Start with goal state
In backward planning, we begin with the goal, and generate all actions that result in that goal, noting their preconditions, which become a new set of goals on which to (recursively) apply the same process. In principle, this is performed until the given initial conditions are obtained.
31
Cumulative Fulfillment*
1. Start with overall goals OG1, OG2, … , OGn
2. Identify a sufficient sequence of outcomes CG1, CG2, … ,CGn i.e., such that CG1CG2 … CGn OG1OG2 … Ogn
–which …
* Weakest Preconditions and Cumulative Subgoal Fulfillment by Eric J. Braude, Science of Computer Programming Volume 89, Part C, 1 September 2014, Pages 223-234
(Often … CG1 = OG1, CG2 = OG2, …, CGn = Ogn)
A computer program is analogous to a plan. In the Cumulative Goal Fulfillment approach to programming, we fulfill a set of goals (CG1, CG12, … CGn, say) which are at least as strong as the set of postconditions. We write code that fulfills the first goal; then code that fulfills the second, but which maintains the validity of the first etc.).
32
Cumulative Fulfillment*
1. Start with overall goals OG1, OG2, … , OGn
2. Identify a sufficient sequence of outcomes CG1, CG2, … ,CGn i.e., such that CG1CG2 … CGn OG1OG2 … Ogn
–which are cumulative i.e.,
fulfilling CGi maintains CG1CG2 … CGi-1
Example: Towers of Hanoi: CG1 = “??”
Example: Repair flat: CG1 = “??”
* Weakest preconditions and cumulative subgoal fulfillment by Eric J.Braude, Science of Computer Programming Volume 89, Part C, 1 September 2014, Pages 223-234
The property of fulfilling goals while maintaining prior ones is “cumulative.” Cumulative goals are helpful in being specific about the purpose of each block of code.
33
Cumulative Fulfillment*
1. Start with overall goals OG1, OG2, … , OGn
2. Identify a sufficient sequence of outcomes CG1, CG2, … ,CGn i.e., such that CG1CG2 … CGn OG1OG2 … Ogn
–which are cumulative i.e.,
fulfilling CGi maintains CG1CG2 … CGi-1
Example: Towers of Hanoi: CG1 = “Largest on target”
Example: Repair flat: CG1 = “New inner tube on rim”
* Weakest preconditions and cumulative subgoal fulfillment by Eric J.Braude, Science of Computer Programming Volume 89, Part C, 1 September 2014, Pages 223-234
There are techniques for identifying goals, and the code (the actions in planning lingo) that fulfills them. But they are arrived at by practice, and selected from a very wide set of legal programming constructs whereas in planning, the set of actions is very limited, and we can often use heuristics to identify potentially successful ones.
34
15-Puzzle Postcondition(s)
A conjunction of fluents (maybe location_of_1, location_of_2, …
Which selection is useful?
To solve the famous Fifteen Puzzle, for example, what would be a useful cumulative goal for the plan? What fluents or predicates?
35
15-Puzzle Cumulative Goal # 1
Eric J. Braude “Dijkstra’s Counting Arguments, Puzzles, and Cumulative Subgoal Fulfillment”, Computer Science and Education in Computer Science 9/2013 Issue No: 1 pp 41-45 https://www.ceeol.com/search/article-detail?id=465085
A useful fluent to take as a goal:
A useful—and, it turns out—practical goal is to have the required outer ring in its required order. The point here is that there is apparently no limit on how imaginative useful goal fluents and predicates can be.
36
Unsolved … (non-final) Goal: Dad’s Puzzle
37
from the start position shown on the left, slide pieces (without picking them up) to form the end position shown on the right. *
* http://www.cs.brandeis.edu/~storer/JimPuzzles/ZPAGES/zzzQuzzle.html
A more difficult problem is Dad’s Puzzle, shown in the figure. Goal predicates can be identified such as Square One Move From Destination, but not very useful ones.
37
Bridge-Torch Problem
38
Puzzles provide a fertile ground for planning methods. An example is the Bridge-Torch problem in which a group of people, each with their own bridge-crossing time, must cross a bridge at night. The bridge can hold at most two people. A flashlight is necessary for each crossing. There is only one.
38
Bridge-Torch Problem
39
The figure shows a particular instance of the problem. See me for a solution.
39
Planning
Introduction
Forward vs. Backward Planning
Heuristics and Plan Graphs
Conclusion
In this section we consider how to use heuristics to develop a plan.
Heuristics to Prune the Plan Tree
Ignore preconditions
e.g., in 15-puzzle: ignore “must be a blank”
Ignore “delete lists”
remove negative literals from effects
no action undoes progress made by another action
e.g., Take car does not remove bus available
…
Adapted from Russell and Norvig
Viewing the possible courses of action as a tree of actions, the task of finding a good plan amounts to either generating all possible plans—which is typically impractical—or else pruning the tree using heuristics.
The figure lists two heuristics. Ignore preconditions loosens the circumstances of the problem, allowing for more flexibility in finding a plan. For the 15-puzzle, we could ignore the need to move only to a blank position. The idea is to develop a plan with this omission, swapping tiles, and then use the (illegal) result to create a legal plan. The delete lists heuristic is similar in that it ignores ill effects of actions.
In everyday life, we plan like this all the time. For example, in planning a celebrations, we may first ignore preconditions such as venue availability, then use the resulting rough plan as the basis to move forward, modifying it as realistic venue availability is applied.
41
Heuristics to Prune the Tree
Ignore preconditions
e.g., in 15-puzzle: ignore “must be a blank”
Ignore “delete lists”
remove negative literals from effects
no action undoes progress made by another action
e.g., Take car does not remove bus available
Make states more abstract
e.g., Instead of “Cargo at Atlanta Airport”, use “Cargo at Airport”
e.g., Instead of “Place dining table”, use “Sketch dining space”
Decompose goal (artificially?)
e.g., At Waldorf Astoria At a NYC hotel On Park Avenue
Adapted from Russell and Norvig
Abstract states means to replace concrete courses of actions with general ones, e.g., replace Select hotel with Select venue. This makes it easier make progress with the plan. You then flesh out the resulting rough plan. Decompose goal is similar in that it abstracts aspect of a goal as shown in the figure.
42
Plan Graph Example: Have your cake & …
Source: Russell and Norvig
Consider the problem with the initial condition, goal, and allowable actions shown in the figure. We’ll generate a plan—a sequence of actions that, assuming Init, accomplish Goal.
43
Basic Planning Graph Technique
44
Organize as …
Possible fluents
possible actions
new possible fluents
(2) Group actions together that can be taken in any order
To solve the problem, we think in terms of fluent sets that actions transform into new fluent sets. When a set of actions are such as to not affect each other, we note that because it makes matters easier. For example, the actions selectVenue and selectWeddingDress can be grouped.
44
(Exhaustive) Planning Graph
Source: Russell and Norvig
Action
State
Action
State
State
End
Begin
(and)
To include action sequences
(otherwise draw serial planning graph)
End state is a subset of these fluents
The figure shows a framework for carrying this out.
45
Planning Graph
Based on Russell and Norvig
(no action)
A possible action
We then list all possible first actions (A0) i.e., whose preconditions are included in the initial conditions. This would be No action (as we often say, doing nothing is a real choice) and Eat(Cake). No action activates on any precondition; Eat(Cake) is possible only when Have(Cake).
Note that Bake(Cake) is not an option because its precondition is not valid.
46
Planning Graph
Based on Russell and Norvig
1. Have(Cake) and Have(Cake)
can‘t both be true.
(no action)
A mutex (mutually exclusive) relation holds between two actions at a given level if any of the following is true:
• Inconsistent effects
• Interference: one of the effects of one action is the negation of a precondition of the other. For example Eat(Cake) interferes with the persistence of Have(Cake) by negating its precondition.
• …
Now we collect all the possible states resulting from all possible actions, on all applicable precondition sets. The gray arcs at right (mutex’s) denote mutually exclusivity (you can’t have both X and X).
47
Planning Graph
Based on Russell and Norvig
1. Have(Cake) and Have(Cake)
can‘t both be true.
2. Thus, not both of these actions
are possible at the same time
(mutually exclusive–mutex).
(no action)
The process shows that no action and Eat(Cake) cannot be executed in any order here because their effects are not consistent (contain contradictions). Hence the first set of gray arcs (from the left).
In total, there are 2 possible resulting subsets—{Have(Cake), Eaten(Cake)}, from executing no action—and {Have(Cake), Eaten(Cake)}, from executing Eat(Cake). These define the possible states S1
48
Planning Graph
Source: Russell and Norvig
Continue until S unchanged.
A mutex relation holds between two actions at a given level if any of the following is true:
• Inconsistent effects
• Interference: one of the effects of one action is the negation of a precondition of the other. For example, Eat(Cake) interferes with the persistence (no action”) of Have(Cake) by negating its precondition.
• …
We continue the process for the next possible actions. Instead of the preconditions, we consider the (2) possible states S1. This time, the action Bake(Cake) is an option as well.
49
Planning Graph
Source: Russell and Norvig
A mutex relation holds between two actions at a given level if any of:
• Inconsistent effects
• Interference: one of the effects of one action is the negation of a precondition of the other. For example, Eat(Cake) interferes with the persistence of Have(Cake) by negating its precondition.
• Competing needs: one of the preconditions of one action is mutually exclusive with a precondition of the other. For example, Bake(Cake) and Eat(Cake) are mutex because they compete on the value of the Have(Cake) precondition.
Use a Planning Graph
— to extract a plan
— to estimate the number of actions required to get from a state to a goal
Several variations (see p 382 of R&N)
— to assess whether there is a plan that accomplishes desired goals
Source: Russell and Norvig
51
Spare Tire Example
The figure shows the result of installing a spare tire (from Russell and Norvig). The process does not use any heuristics—which are needed because the exponential nature of its growth. However, many planning problems require a manageable number of steps, and may not require pruning.
52
Planning
Introduction
Forward vs. Backward Planning
Heuristics and Plan Graphs
Conclusion
Summary of Planning
Specified by actions applicable in some states
Forward and backward
Serious pruning needed for forward
PDDL facilitates applications
54
/docProps/thumbnail.jpeg