Transcript Factored Planning for Controlling a Robotic Arm

CS 440 / ECE 448
Introduction to Artificial Intelligence
Spring 2010
Lecture #14
Instructor: Eyal Amir
Grad TAs: Wen Pu, Yonatan Bisk
Undergrad TAs: Sam Johnson, Nikhil Johri
Today
• Planning and SAT technologies
• Combining planning and motion planning
• Review before midterm
SAT Technologies
• SATLIB
– Library of test problems for SAT solvers
• SAT Live
– http://www.satlive.org/
• DIMACS format for SAT problems
– Standard format for CNF knowledge bases
• Annual conference
– http://www.satisfiability.org/
Planner Technologies
• Many planners
– http://www4.ncsu.edu/~stamant/planningresources.html
• Planning competitions http://www.icapsconference.org/index.php/Main/Competitions
• PDDL (Planning Domain Description Language)
– Standard format for specifying planning problems
• Extensions: parallel actions, actions off varying
duration, non-deterministic actions (actions that
may fail or have different effects than intended).
• Separate: Motion Planning
Factored Planning for Robot Motion
Motivation – AI Planning Only
• Strength of AI planning and description (PDDL)
– Planning with logical constraints in state space
• Weakness of AI planning
– Executing (or actuating) real-world robots
– i.e. How to push a button (key1)?
• If we plan with kinematics constraints,
actkey1
Pre: pushedkey1
Eff: pushedkey1
– Incomplete (require details): In many cases, an action (i.e. push a
button) is not straightforward to incorporate kinematic constraints into
logic states. Moreover, there is no guarantee that there is a path for the
action.
– Ambiguous: there are many ways to interpret an action.
Assumption: executable actions are given.
Example
• Goal: button (key1) is on (lit)
P (c)=1
• Problem: Find a motion+logical plan CSpace key1
that achieves Goal
Pkey1(c)=0
PDDL
actkey1
Pre: pushedkey1onkey1
Eff: pushedkey1onkey1
• We have two different representations
• A graph built by a motion planner (i.e. PRM) in CSpace
• Actions in PDDL (Planning Domain Description Language)
• Two representations share predicates (Pkey1(.) = pushedkey1)
Our Representation (Assumption)
• Assumption: pair of shared predicates (Pi, P’i) are given.
– Pi: CSpace  {0,1} and P’i: State Space of PDDL  {0,1}
CSpace
C1, C2, C3,…,CN-1, CN
Shared Space
State Space of PDDL
P1, P2, …, PM-1, PM
P’1, P’2, …, P’M-1, P’M
Pkey1(c)=1
actkey1
Pre: pushedkey1onkey1
Eff: pushedkey1onkey1
Pkey1(c)=0
CSpace
• In the example
– P1=Pkey1 and P’1= Pushedkey1
S1, S2, S3,…,SK-1, SK
PDDL
Problem Definition
• Given
–
–
–
–
–
A CSpace* for a robot and objects
PDDL (Planning Domain Description Language)
Initial configuration (cinit) in CSpace
Initial/Goal conditions (qinit/qgoal) in PDDL
Predicates† map between PDDL and CSpace
• Goal
– Finding a path from the cinit  qinit to qgoal
• The path is collision free in CSpace
• Each action in the path changes states according to PDDL description.
*CSpace is the set of all the possible configurations.
† A predicate is a function which maps a configuration to a discrete value
Algorithm: Plan with Motion
1. Find a plan (sequence of actions) with the PDDL
•
Using AI planner (e.g. FF, GraphPlan, SATPlan, …)
2. Find a path which passes through the PDDL actions in order
actkey1
Pre: P’iP’jpushedkey1
Eff: P’iP’jpushedkey1
actunkey1
Pre: Pi  Pj
Eff: Pi  Pj
act’key1
actunkey1
act’key2
…
Experimental Setting in Simulation
 Initial: no button is pushed
 Goal: Call (A)dam, (B)en, and
(C)olin
 Constraints encoded in PDDL




Called_A: Push Call after Push A
Called_B: Push Call after Push B
Called_C: Push Call after Push C
Unlock: Push unlock after On key1 and On key2
 Unlock causes Onkey1 and Onkey2
 Lock: Push Call
 Call causes Lock
Result Video
Summary of Technical Today
• SAT solvers technology – can be downloaded from
the web. Many free implementations
• Planning technologies – same
• Combining planning and motion planning: Many
times done in a hierarchy when the AI planning
algorithm requests motions from the lower-level
motion planner
Now…
• Review!
•
•
•
•
•
•
Search
Game playing (2-players, full information)
FOL
FOL Theorem Proving
Propositional reasoning
Planning
Questions Driven
• Appetizer question: how to prove
reachable ( Room 3314, Room 2314)
What axioms are needed?