Transcript CSC 550: Introduction to Planning Fall 2004

CSC 550: Introduction to Planning
Fall 2004
Goals:
1. Defining Planning
2. Early planning systems
3. Types of Planning and their challenges:
- Hierarchical
- Non-Hierarchical,
- Other common approaches
4. Current Projects and challenges
Definition of Planning
• Planning is reasoning about future events in
order to establish a series of actions to
accomplish a goal.
- A common approach to planning is representing a
current state and determining the series of actions
necessary to reach the goal state. (or vice versa)
– Problem solving technique
– Plans are created by searching through a space of possible actions until
the sequence necessary to accomplish the task is discovered.
• Planning is a specific kind of state space search
• Deals with steps and goals that interact
– Initial State and Goal State (Next Slide)- Hallmark example with blocks
Initial State and Goal State
These two diagrams show the initial state and goal state for a simple planning problem. The
purpose of planning is to find a sequence of actions that gets from the initial state to the goal
state, or from the goal state back to the initial state.
Possible Solution: Pickup(c),Table(c), Pickup(b), PlaceOn(c), Pickup(a), PlaceOn(b)
Search in Planning
• Planning involves search through a search
space
– Progression: choose an action whose preconditions
are met until a goal state is reached
• A forward approach, simple algorithm, but can have large
branching factor
– Regression: choose an action that matches an
unachieved subgoal while adding unmet
preconditions to the set of subgoals. Continue until
the set of subgoals is empty.
• A backward approach, goal oriented, tends to be more
efficient
Linear and Non-Linear
• Linear
– Solving one goal at a time with a stack of unachieved goals,
subgoals are solved in the same order as the actions of the plan
to be executed
– Depth-first search
• Non-Linear
– Solving subgoals that are in a set of unachieved goals, can
solve parallel branches of the set of goals arbitrarily.
– Breadth-first search
– Tends to avoid backtracking
– More flexible execution
– Representing plans and search algorithms are more complex
than linear
Definition of Planning, cont.
– Applications in robotics, expert systems,
manufacturing, and natural language
understanding
• Expert System – reasoning about events occurring
over time
• Manufacturing – process control
• Robotics – organization of partial plans in a
solution
• Natural Language – human interactions, goal
oriented
Definition of Planning, cont.
- Potential Benefits of Planning
•
•
•
•
Helps to solve large problems quickly
Find better solutions
Can resolve goal conflicts
Can provide methods for error recovery
– General Limitations
• Complexity of state spaces, must represent the whole
environment, search can become exponentially large
• Frame Problem- being able to represent what changes and
what remains unchanged following an action (by default,
things stay the same, unless you tell it otherwise)
• Inconsistencies between the real world and the program
model, comes back to the complexity issue
Early Planning Systems
1956 – Logic Theorists – Newell, Shaw, and Simon
- One of the first to use heuristics, proved theorems in propositional
calculus, operated by using backward reasoning from the theorem to the
axioms
- limited by its heuristics and certain theorems could not be proven
1957-1969 – GPS – Newell, Shaw, and Simon
- The General Problem Solver, how to solve human intelligence problems,
areas – propositional calculus proofs, puzzles, symbolic integrations, etc.
- Introduced means-end analysis which tried to find the difference between
the current state and goal, then used a table to find an action to minimize
the difference between the two states.
Non-Hierarchical Planners
•
Earliest Method of Planning
– Made no distinction between more and less important plan
elements
– Slowed by getting hung up on less important elements
– Lack of structure led to poor performance with complex problems
– Example: STRIPS
• STanford Research Institute Planning System
• 1971 by Fikes and Nilsson
• Used to run the SHAKEY robot of the 1970’s
– The block example
STRIPS
• Goal states are
maintained on a stack
• If the top goal on the
stack matches the current
state, the goal is removed
from the stack
• Also adds to the goal
stack any sub-goals
found while trying to get
to the goal state
•
Initial State (On(C,A) and
OnTable(B)) and Goal State
(On(C,B) and On(A,C))
STRIPS
This diagram is
an example of
a STRIPS
search graph
with goal
stacks
included. The
goal state is
On(A,C) ^
On(C,B).
STRIPS
STRIPS
• Problems
– Does not always find the optimal solution (Ex: On(A,B) before
On(B,C))
– Some simple problems that cannot be solved: switching the
contents of two registers
– Cannot tell the difference between important information and
details
– No guidelines to tell it what to do first
– Cannot know when it is going down a bad path
– Memory Goal Stack and Start State
• Next slide
Current State State Description
1
CONT(X,A)
Goal Stack
CONT(X,B) ^ CONT(Y,A)
CONT(Y,B)
CONT(Z,0)
2
3
CONT(X,A)
CONT(X,B)
CONT(Y,B)
CONT(Y,A)
CONT(Z,0)
CONT(X,B) ^ CONT(Y,A)
CONT(X,A)
CONT(r,B) ^ CONT(X,t)
CONT(Y,B)
Assign(X,r,t,B)
CONT(Z,0)
CONT(Y,A)
CONT(X,B) ^ CONT(Y,A)
4
CONT(X,B)
CONT(Y,A)
CONT(Y,B)
CONT(X,B) ^ CONT(Y,A)
CONT(Z,0)
At State 3, the program sees the goal CONT(X,B) can be completed. The
problem is the contents of Y are never copied into Z and is lost. At State 4, the
goal cannot be met due to A being lost.
- An example of subgoals that conflict
Hierarchical Planners
• Makes a distinction between more and less important parts of the
plan
– Example: When purchasing a new Jesuit statue, we first need to decide
where to get the funds. It doesn’t make sense to find a good place for it
on campus before you have the money.
– Example: ABSTRIPS – 1974 – Sacerdoti
• Abstract-Based STRIPS
• Like STRIPS but plans in a hierarchy, greatly reduces search space,
and is more efficient at solving large problems
• Certain preconditions are judged as more important than others by
adding weights to those elements
• Finds early recognition of bad paths and gets rid of wasted search
• Uses a hierarchy of abstraction levels
• Solves highest level of abstraction. If that passes, it increases level
of detail
ABSTRIPS
Example: PUSH-THRU-DOOR (bx, dx, rx)
Preconditions: 6 PUSHABLE (bx)
6 IS-A (dx, DOOR)
6 IS-A (rx, ROOM)
2 STATUS (dx, OPEN)
1 NEXT-TO (bx, dx)
1 NEXT-TO (ROBOT, bx)
Each number represents the weight of the
element. We see that the elements with weight 6
are the first elements we need to know in order
to get to the goal state.
Common Approaches
Opportunistic Planning
- Situation-based triggering of new goals, subgoals, and/or partial plans
- Implementation is a bottom-up approach, whereas Hierarchical planners
start with the goal and move down
Resource-Sensitive Planning
- Takes into account the resources available and the cost involved in plans
- Interval Logic, James Allen-1983
- A system which represents actions where timing is important
- Uses time interval relations (before, meets, overlaps, during, etc.)
- Links are made between actions that satisfy interval relations
Conditional and Uncertainty Planning
- Deals with information that is incomplete, devises generic plans that leave
out specifics, details are filled in later
- Emphasis on uncertainty in real world applications
Current Research Focus
• Emphasis on Hierarchical Planning with special
consideration given to:
– Complex Conditions
– Availability of Resources
– Uncertainty
• More practical approaches considering the
complex world that we live in.
- Biggest difficulty is in the representation of complex
states and actions
- Problems also arise as complexity leads to a
sometimes exponentially increased search
Classical Planning Assumptions
•
•
•
•
•
•
Perfect Information
Deterministic Effects
Instantaneous Execution
Solo Agent
No concern over time, cost, resources
Etc.
These assumptions were made early on because complex
tasks were too complex to solve. These assumptions
were used to complete smaller tasks (blocks).
Modern approaches deal with the scaling issue.
Recent Projects
• ASPEN
– Automated Scheduling and Planning ENvironment
–
–
–
–
–
NASA application
Used for mission design
Surface rover planning
Ground antenna utilization
NASA operators send goals to ASPEN, then ASPEN sends commands
to the spacecraft, ASPEN continually receives updates from the
spacecraft and the current plan is updated to reflect the necessary
environmental changes
• PLANET
– Applications: workflow management, intelligent manufacturing, robot
planning, aerospace and airline planning
• EXCULIBUR
– Computer gaming environment
– Pursue their given goals and adapt to new opponents
– Dynamic nature of games, uncertainty
Sources of Information
•
•
•
•
•
•
•
•
•
•
•
Luger, George F., Artificial Intelligence: Structures and Strategies For
Complex Problem Solving, Fourth Edition, Pearson Education Limited 2002.
Nilsson, Nils J. Principles of Artificial Intelligence, Tioga Publishing Co.,
1980.
Shirai, Yoshiaki and Tsujii, Jun-ichi, Artificial Intelligence: Concepts
Techniques, and Applications, Iwanami Shoten, Publishers, Tokyo, 1982.
http://www.cs.washington.edu/ai/#PLAN
http://www.cs.dartmouth.edu/~brd/Teaching/AI/Lectures/Summaries/plannin
g.html
www.cs.bham.ac.uk/~mmk/Teaching/Planning/l6.html
www.cs.umbc.edu/671/fall03/slides/25
http://www-2.cs.cmu.edu/~reids/planning/handouts/ReprSearch.pdf
http://vitalstatistix.nicve.salford.ac.uk/planet2/desc.html
http://www.ai-center.com/projects/excalibur/goals.html
http://www-aig.jpl.nasa.gov/public/planning/projects/current.html