Flat Tire ExampleSlide 2Slide 3Slide 4Slide 5SatPlanmore complex planning domainsSlide 8Slide 9Slide 10Slide 11RoboticsFlat Tire Example•init: {tire(flat),tire(spare),at(flat,axle),at(spare,trunk)}•goal: at(spare,axle)•operators:–Remove(obj,loc)•precond: at(obj,loc)•effect: at(obj,loc),at(obj,ground)–PutOn(t,axle)•precond: tire(t),at(t,ground),at(flat,axle)•effect:  at(t,ground), at(flat,axle)–LeaveOvernight•precond:•effect: at(spare,ground), at(spare,trunk), at(spare,axle)at(flat,ground), at(flat,trunk), at(flat,axle)SatPlan•propositionalization–create separate literals for each ground instance of each fluent for each state index•e.g. on_a_b_1 , on_a_b_2 , on_a_b_3, gripper_empty_1, gripper_empty_2...–create propositions for action taken at step t: pickup_a_b_1...•convert axioms in FOL to propositional sentences (one copy for each time index)–possibility axioms: s,a Prec(s)Poss(a,s)•gripper_empty_1clear_a_1 poss_pickup_a_1•gripper_empty_2clear_a_2 poss_pickup_a_2•gripper_empty_1clear_b_1 poss_pickup_b_1–successor axioms: s Poss(a,s)Eff(result(a,s))•poss_pickup_a_1  pickup_a_1 holding_a_2gripper_empty_2–frame axioms: s Flu(s)aCancelingActionsFlu(result(a,s))•on_b_c_1  poss_pickup_a_1 on_b_c_2•use a satisfiability solved like DPLL or WalkSat–query: poss_on_a_b_1? poss_on_a_b_2? poss_on_a_b_3?–the truth values of action propositions in the model tell you the plan•pickup_c_a_1=T, puton_c_table_2=T, pickup_b_table_3=T, puton_b_a_4=Tmore complex planning domains•Plan Abstraction–the idea: simplify problem by temporarily “dropping” easy preconditions•defer solving them till later•make high-level plan, then fill in details–system: ABSTRIPS–example:•make a high-level plan for solving 8-puzzle where you assume you can move pieces without empty space7 2 45 1 68 37 2 45 1 38 6•Hierarchical Task Networks (HTNs)–plan library •a list of standard operating procedures, written out in procedural syntax•ExecuteMissionWithHelicopters: –preconds: haveHelicopters, knowTargetCoordinates– steps: {FlyFlightPlan,Engage,ReturnToBase}–high-level operators vs. low-level operators–expansion, multiple choices of how to achieve subtask–still a problem of sub-goal interactions– system: STEAM• plan monitoring and repair–what if action in step i might fail?–non-deterministic domains (most in real-world)– at each step, check pre-conditions– if expected conditions not satisfied, re-invoke planner•costly to re-plan from scratch•search for modification of existing plan, e.g. re-do previous action or insert steps to get back on track•contingent planning: – a plan with a branch in it– include sensor actions to sense state–algorithm to create such plans to achieve goals•goal regression? •universal planners: generate state-action tables, finite-state machines{pickupA, senseHolding, while not holding do {pickupA,senseHolding}}{swingAx, senseTree, while TreeStanding do {swingAx,senseTree}}enter roomsense lightoff(light)?  flip(switch)next action•plan optimization–use heuristics to search for a plan that minimizes cost of operators, or time...–start by finding any plan that achieves goals, and then apply incremental modifications•related to scheduling–critical path method (CPM) – compute [ES,LS]–resource constraints (e.g. 1 machine to add engine)Robotics•basic approach:–navigation in configuration space – find path from initial configuration to goal configuration–# dimensions = degrees of freedom (parameters that can be controlled, e.g. joint angles)–find path; avoid collisions with