COMP 424 – Artificial Intelligence Planning
Instructor: Jackie CK Cheung and Readings: R&N Ch 10
Copyright By PowCoder代写 加微信 powcoder
What is planning?
• A plan is a collection of actions for performing some task. e.g., assembling a new IKEA desk
• Use a subset of FOL to describe the problem
• What actions are we allowed to take? (put two pieces together,
tighten a screw, …)
• When are we allowed to take them? (box must be opened, piece A
and piece B must already be assembled, …)
• What is the initial state? (all the pieces are in the box)
• What is the goal state? (furniture is assembled)
Applications
Pictures from: http://www.stanford.edu/class/cs227/Lectures/lec16.pdf 4
NASA’s Deep Space 1 (1998)
• Launched in Oct. 1998 to test technologies and perform flybys of asteroid Braille and Comet Borrelly.
• Autonav system used for autonomous navigation and finding imaging targets.
• Remote Agent system used to perform automatic fault detection and self-repair.
• First spacecraft to be controlled by AI system without human intervention!
www.jpl.nasa.gov
Planning as search
• Planning problem is described like a search problem (states, operators, goals), but the problem representation is a lot more structured
States are atomic
States and goals are logical sentences
Actions are atomic
Actions are described in logic by preconditions and outcomes
Shakey: “The first electronic person”
• Designed in 1966, at the Stanford Research Institute
• Able to plan and execute simple tasks related to navigation and object manipulation
• Needed a language in which to express planning tasks
• The STRIPS language
http://www.ai.sri.com/shakey/
Let’s Help Shakey Plan to Move
• How can Shakey move from point A to point B?
• It must be in point A.
• Nothing must be impeding Shakey.
• Point B must be clear.
• What happens after Shakey moves from point A to point B?
• Point A is now clear.
• Point B is no longer clear.
• Shakey is now in point B.
• Let’s do all this more formally!
STRIPS (Stanford Research Institute Planning System)
• Domain: set of typed objects represented as propositions.
• States: represented as first-order predicates over objects. Closed-world assumption:
– everything not stated is false
– only objects in the world are the ones defined.
• Operators: defined in terms of:
• Preconditions: when can the action be applied?
• Effects: what happens after the action?
(No explicit description of how the action should be executed.)
STRIPS* representations
• States are represented as conjunctions of predicates: In(robot, room) ∧ Closed(door) ∧ …
• Goals are represented as conjunctions of predicates: In(robot, r) ∧ In(Charger, r)
• Operators:
• Name: Go(x, y)
• Preconditions are represented as conjunctions:
At(robot, x) ∧ Path(x, y)
• Postconditions are represented as conjunctions:
At(robot, y) ∧ ¬At(robot, x)
• Variables (e.g. x, y, r) are typed; they can only be instantiated
with objects of correct type.
*R&N uses a very similar representation called PDDL
STRIPS operator representation
• An action schema defines the following for an operator: • {Name,Preconditions,Effects}
• Preconditions are conjunctions of positive literals
• Effects/Postconditions are represented in terms of:
• Add-list: list of propositions that become true after the action.
• Delete-list: list of propositions that become false after the action.
• e.g. At(robot, y) ∧ ¬At(robot, x)
Add the positive literals Delete the negative literals
Semantics of an Action
• If the precondition is false in a world state:
• the action does not change anything (since it cannot be applied).
• If the precondition is true:
• Delete the items on the Delete-list.
• Add the items on the Add-list.
Order of operations is important here!
• This is a very restricted language, which means we can do efficient inference.
Example: Move action
• Move(object, from, to)
• Preconditions:
• At(object, from), Clear(to), Clear(object)
• There are implicit conjunctions here.
• Effects:
• Delete-list: At(object, from), Clear(to)
• Add-list: At(object, to), Clear(from)
• In logical form: At(object, to) ∧ Clear(from) ∧ ¬ At(object, from) ∧ ¬ Clear(to)
Welcome to the Blocks World!
Initial state
Goal state
Initial state = On(A,table) ∧ On(B,table) ∧ On(C,table) ∧ Clear(A) ∧ Clear(B) ∧ Clear(C)
Goal state = On(A,B) ∧ On (B,C)
Exercise: Fill in the preconditions and effects of these actions
Action = Move(b,x,y) Precondition = Effect =
Move b from x to y, where y is not the table.
Action = MoveToTable(b,x) Preconditions =
Move b from x to the table.
Welcome to the Blocks World!
Initial state
Goal state
Initial state = On(A,table) ∧ On(B,table) ∧ On(C,table) ∧ Clear(A) ∧ Clear(B) ∧ Clear(C)
Goal state = On(A,B) ∧ On (B,C)
Action = Move(b,x,y)
Precondition = On(b,x) ∧ Clear(b) ∧ Clear(y) Effect = On(b,y) ∧ Clear(x) ∧ ¬On(b,x) ∧ ¬Clear(y)
Action = MoveToTable(b,x)
Preconditions = On(b,x) ∧ Clear(b)
Effect = On(b,table) ∧ Clear(x) ∧ ¬On(b,x)
STRIPS state transitions
Write out a plan that actually achieves the goal state
Pros and cons of STRIPS?
• Since it is restricted, inference can be done efficiently.
• All operators can be viewed as simple deletions and additions of propositions to the knowledge base.
• Assumes that a small number of propositions will change for each action (otherwise operators are hard to write down, and reasoning becomes expensive.)
• Limited language (preconditions and effects are expressed as conjunctions), so not applicable to all domains of interest.
Two basic approaches to planning
1. State-space planning works at the level of states and operators.
• Finding a plan is formulated as a search through state space for a path from the start state to the goal state(s).
• Most similar to constructive search.
2. Plan-space planning works at the level of plans.
• Partial order planning – read R&N 10.4.4
Progression (forward) planning
Starting from the initial state, do:
1. Determine all operators that are applicable in the start state by examining preconditions.
2. Ground the operators, by replacing any variables with constants.
3. Choose an operator to apply.
4. Determine the new content of the knowledge base, based on the operator description (apply the effects from the add- and delete lists).
Repeat until goal state is reached.
Example: Supermarket domain
• We’re at home, but we need to buy milk, bananas, and a cordless drill (don’t ask).
Example: Supermarket domain
• In the start state we have At(Home), which allows us to apply operators of the type Go(x,y).
• The operator can be instantiated as Go(Home, HardwareStore), Go(Home, GroceryStore), Go(Home, School), …
• If we choose to apply Go(Home, HardwareStore), we will delete from the KB At(Home) and add At(HardwareStore).
• The new proposition enables new actions, e.g. Buy
• Note that now there are a lot of possible operators to consider!
Regression planning
• Pick actions that satisfy (some of) the goal propositions.
• Make a new goal, containing the preconditions of these
actions, as well as any unsolved goal propositions.
• Repeat until the goal set is satisfied by the start state.
Example: Supermarket domain
• In the goal state we have At(Home) ∧ Have(Milk) ∧ Have(Bananas) ∧ Have(Drill)
• The action Buy(Milk) would allow us to achieve Have(Milk).
• To apply this action we need to have the precondition At(GroceryStore), so we add it to the set of propositions we want to achieve.
• Similarly, we want to achieve At(HardwareStore).
Note that in this case, the order in which we try to achieve these propositions matters!
State-space planning
• Progressive planners reason from the start state, trying to find the operators that can be applied. (-> match preconditions)
• Analogy: forward search!
• Regression planners reason from the goal state, trying to find the actions that will lead to the goal. (-> match effects)
• Analogy: Backward search!
In both cases, the planners work with sets of states, instead of using individual states as in straightforward search.
Analysis of STRIPS planning
• STRIPS planning is SOUND.
• Only legal plans will be found.
• STRIPS planning is NOT COMPLETE.
• Once a subgoal ordering is selected, no backtracking is allowed.
• STRIPS planning is NOT OPTIMAL.
• No guarantee of finding shortest possible plan.
• STRIPS planning is EXPENSIVE. Typically NP-hard or worse.
Some state-of-the-art classical planners
• SATPlan: Planning as satisfiability (Kautz & Selman, 1996)
• Heuristic-search planning (Bonet & Geffner, 1998)
• GraphPlan (Blum & Furst, 1995)
• Fast Forward planning (Hoffman & Nebel, 2001)
• Use hill-climbing to get near a good solution, then best-first-search.
• Hierarchical task network planning
• Decompose complex planning problem into a hierarchy of smaller
planning tasks. • Many more!
Planning as logic
• Planning is very much like searching over sets of states, but the problem representation is more structured.
Key idea: describe states and actions in propositional logic and use forward/backward chaining to find a plan.
Planning as satisfiability: SatPlan
• Introduced by Kautz and Selman, 1990s, very successful method over the years.
• Take a description of a planning problem and generate all possible literals at all time slices.
• Generate a humongous SAT problem.
• Use a state-of-the-art SAT solver (e.g WalkSAT) to get a
• Randomized SAT solvers can be used as well.
Analysis of SatPlan
• Optimality: Yes! (Assuming exact SAT solution.) • Completeness: Yes!
• Complexity:
• Clearly NP-hard (as it can be seen as SAT in finite-length plan
• But actually worse (PSPACE) if we let plan duration vary.
Heuristic-search planning
• Don’t want domain-specific heuristics.
• Define heuristics based on planning problem itself.
• Can we derive an admissible heuristic for search in planning domains?
• Technique we’ve seen before: solve relaxed problem!
• Solving the problem becomes much easier in the relaxed case; number of steps to goal in this heuristic can be used as part of A* search
• Historical note: A* search came from the same research project responsible for STRIPS and Shakey!
Two Heuristics
Ignore Preconditions
• Assume that we can also apply an operator
e.g., you can always move to point B, no matter where you are
Ignore Delete lists (in Effects)
• Assumes that when something is achieved, it stays achieved.
• Solve this relaxed version and use this as the heuristic.
Image from: http://icaps09.uom.gr/tutorials/tut1.pdf 31
Problems in the real world
• Incomplete information
• Unknown predications, e.g., Intact(Spare)
• Disjunctive effects, e.g. Inflate(x) causes Inflated(x) according to the KB, but in reality it actually causes Inflated(x) v SlowHiss(x) v Burst(x) v BrokenPump v …
• Incorrect information
• Current state it incorrect, e.g., spare NOT intact.
• Unanticipated outcomes (missing / incorrect postconditions) of operators, that lead to failure.
• Qualification problem
• Can never finish listing all the required preconditions and possible conditional outcomes of actions.
The real world: Some solutions
• Conditional (contingency) planning:
• Plans include observation actions which obtain information.
• Sub-plans are created for each contingency (each possible outcome of the observation actions).
E.g. Check the tire. If it is intact, then we’re ok, otherwise there are several possible solutions: Inflate, Call-CAA, …
• Expensive because it plans for many unlikely cases.
• Monitoring / Replanning:
• Assume normal states, outcomes.
• Check progress during execution, replan if necessary.
In general, some monitoring / replanning is highly useful.
Handling Uncertainty
• The main theme after the midterm!
• Next week:
• Review and midterm – no new material!
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com