Title PageComplete RobotComplete RobotProblem Solving - PlanningExamples of TasksExample - Blocks WorldThe Blocks WorldThe Blocks World - DefinitionSussman's AnomalyActionsAction RepresentationSussman's AnomalyAnother Example - ManufacturingExample - Problem and PlanWhy is Planning Hard?Planning StrategiesOne-Way Rocket DomainPlanning with Stack of Goals: IncompletenessPartial Order PlanningPartially Ordered PlanMany Issues To Resolve...Uncertainty in the WorldHandling UncertaintyThe Flat Tire OperatorsA Flat Tire ProblemPossible ContingenciesThe Flat Tire Operators - RevisedGame PlayingRobot Problem SolvingReactive Planning: Finite-State MachinesMulti-Fidelity BehaviorsMulti-Fidelity BehaviorsLow-level Planning - NavigationRRT DiscussionR-RRT - RRT for Robot NavigationR-RRT Storage, Replanning EfficiencySummary - Planning - Action SelectionCMRoboBits:Action Selection: Behaviors, PlanningManuela VelosoScott Lenser15-491November 3, 2003CMRoboBits: PlanningComplete Robot• Perception• Cognition• ActionCMRoboBits: PlanningComplete Robot• Perception– What is it?– All the sensors, vision, world modeling• Cognition– What is it?– Action selection, problem solving– Coordination, learning• Action– What is it?– Motion, manipulation– Sound, speechCMRoboBits: PlanningProblem Solving - PlanningNewell and Simon 1956• Given a problem specified as:– an initial state of the world,– a goal statement to be achieved.• Given the actions available,• Find a solution to the problem, i.e., the actions that can transformthe initial state into a new state of the world where the goalstatement is true.State, Actions, GoalCMRoboBits: PlanningExamples of Tasks• The blocks world• Towers of Hanoi• Chess• 8-puzzle• Puzzles• Artificial domains• Logistics transportation• Manufacturing planning• Vacation planning• .....CMRoboBits: PlanningExample - Blocks WorldACBBCACMRoboBits: PlanningThe Blocks WorldDescription of the domain:• All blocks are labeled and of equal size.• There is an infinite table where any block can be.• The block position on the table does not matter.• There can be at most one block on top of another.• Blocks are moved by an arm.• The arm can hold only block at a time.Problems:• Given an initial set of towers of blocks, find the actions thatachieve some specific block positions.CMRoboBits: PlanningThe Blocks World - Definition• States can be defined as a conjunction of literals.– on(A,B), on(C,table), clear(B), arm-empty,....• Goal statement– A conjunction of literals; a subset of a complete state• Actions– move, pick-up, put-down– We need to represented legal actions at states.CMRoboBits: PlanningSussman’s AnomalyACBBCA• State: on(A,table), on(C,A), on(B,table), arm-empty,clear(C), clear(B)• Goal: on(A,B), on(B,C)CMRoboBits: PlanningActions• Actions - operators – rules – with:– Precondition expression – must be satisfied before theoperator is applied.– Set of effects – describe how the application of the operatorchanges the state.• Precondition expression: propositional, typed first orderpredicate logic, negation, conjunction, disjunction, existentialand universal quantification, and functions.• Effects: add-list and delete-list.• Conditional effects – dependent on condition on the state whenaction takes place.CMRoboBits: PlanningAction Representation(OPERATOR MOVE:preconds?block BLOCK?from OBJECT?to OBJECT(and (clear ?block)(clear ?to)(on ?block ?from)):effectsadd (on ?block ?to)del (on ?block ?from)(if (block-p ?from)add (clear ?from))(if (block-p ?to)del (clear ?to)))CMRoboBits: PlanningSussman’s AnomalyACBBCA• State: on(A,table), on(C,A), on(B,table), arm-empty,clear(C), clear(B)• Goal: on(A,B), on(B,C)• Optimal plan:– MOVE C A table– MOVE B table C– MOVE A table BCMRoboBits: PlanningAnother Example - ManufacturingSPOT-DRILL TWIST-DRILL<drill-bit><part>DRILL PRESSPART DRILL-BITTYPE HIERARCHYPre:Add:<part>: type PARTdrill-spot (<part>, <drill-bit>)<drill-bit>: type SPOT-DRILLDel:Pre:Add:tool-holder-emptytool-holder-empty<drill-bit>: type DRILL-BITput-drill-bit (<drill-bit>)Pre:Add:part-holder-emptyDel: part-holder-empty<part>: type PARTput-part(<part>)Pre:Add:Del:part-holder-empty<part>: type PARTremove-part(<part>)Del:Pre:Add: tool-holder-empty<drill-bit>: type DRILL-BITremove-drill-bit(<drill-bit>) Pre:Add:<drill-bit>: type TWIST-DRILL<part>: type PARTdrill-hole(<part>, <drill-bit>)(holding-tool <drill-bit>)(holding-part <part>)(has-spot <part>)(has-spot <part>)(holding-tool <drill-bit>)(holding-part <part>)(has-hole <part>)(holding-tool <drill-bit>)(holding-tool <drill-bit>)(holding-tool <drill-bit>)(holding-part <drill-bit>)(holding-part <drill-bit>)(holding-part <drill-bit>)CMRoboBits: PlanningExample - Problem and Planpart-holder-emptydrill-holder-emptyInitial State drill-1: type SPOT-DRILLpart-1, part-2 : type PARTdrill-2, drill-3 : type TWIST-DRILLSet of ObjectsGoal Statementhas-hole (part-1)put-part(part-1)put-drill-bit(drill-1)drill-spot(part-1, drill-1)remove-drill-bit(drill-1)put-drill-bit(drill-2)drill-hole(part-1, drill-2)CMRoboBits: PlanningWhy is Planning Hard?Planning involves a complex search:• Alternative operators to achieve a goal• Multiple goals that interact• Solution optimality, quality• Planning efficiency, soundness, completenessCMRoboBits: PlanningPlanning Strategies• Forward chaining – progression– From the initial state,– Apply operators with preconditions true in the state,– Get new states.• Backward-chaining – regression– From the goal state,– Find operators that can add goal,– Set its preconditions as new goals.CMRoboBits: PlanningOne-Way Rocket Domain(OPERATOR LOAD-ROCKET:preconds?roc ROCKET?obj OBJECT?loc LOCATION(and (at ?obj ?loc)(at ?roc ?loc)):effectsadd (inside ?obj ?roc)del (at ?obj ?loc))(OPERATOR UNLOAD-ROCKET:preconds?roc ROCKET?obj OBJECT?loc LOCATION(and (inside ?obj ?roc)(at ?roc ?loc)):effectsadd (at ?obj ?loc)del (inside ?obj ?roc))(OPERATOR MOVE-ROCKET:preconds?roc ROCKET?from-l LOCATION?to-l LOCATION(and (at ?roc ?from-l)(has-fuel ?roc)):effectsadd (at ?roc ?to-l)del (at ?roc ?from-l)del (has-fuel ?roc))CMRoboBits: PlanningPlanning with Stack of Goals:IncompletenessInitial state:(at obj1 locA)(at obj2 locA)(at ROCKET locA)(has-fuel ROCKET)Goal statement:(and(at obj1 locB)(at obj2 locB))Goal Plan(at obj1 locB) (LOAD-ROCKET obj1 locA)(MOVE-ROCKET)(UNLOAD-ROCKET obj1