Problem Set #2 Due: in class Wed, 10/2/02BackgroundProblem 1 – Simple Planning ProblemProblem 2 – Forward State-Space SearchProblem 3 – Using Planning Software for Larger ProblemsProblem 4 – Cleaning Up RoomsProblem 5 – Temporal PlanningProblem 6 – Advanced LectureMassachusetts Institute of Technology16.412J/6.834J Intelligent Embedded SystemsProblem Set #2 Due: in class Wed, 10/2/02 BackgroundThe purpose of this problem set is to develop a grounded understanding ofplanning problems and their solution. This includes understanding of howsuch problems are formulated, of the variety of algorithms that can be usedfor solution, and of the limits of these formulations and algorithms.Problem 1 – Simple Planning Problem Consider the following valve network.FuelRocketMotorV1V2V3V4 V5 V6NONONONCNC NCValves V1 – V6 are pyro valves. Pyro valves are initially in one particularstate (open or closed). An explosive bolt can be fired that switches a pyrovalve to its other state. Thus, an important disadvantage of a pyro valve(with respect to a typical electrically activated on-off valve) is that a pyrovalve can switch states only once. The advantage of using a pyro valve isthat it is extremely reliable. It will stay in its initial state until it is fired.When it is fired, it is guaranteed to switch to the opposite state where it willremain.In the above diagram, valves V1 – V3 are initially open (indicated by NO fornormally open). Firing these closes them. Valves V4 – V6 are initiallyclosed (NC for normally closed). Firing these opens them.Now, consider the following STRIPS formulation of facts and operators forthis problem (refer to Ch. 11 of the Russell and Norvig text for a descriptionof the STRIPS language).Operators:(operator fire-open-1 (params (<vout> Valve) (<vtop> Valve)) (preconds (top-input-to <vtop> <vout>) (normally-closed <vout>) (normally-open <vtop>)) (effects (del normally-closed <vout>) (fired-open <vout>) (del fuel-not-flowing <vout>) (fuel-flowing <vout>)))(operator fire-open-2 (params (<vout> Valve) (<vtop> Valve) (<vbottom> Valve)) (preconds (top-input-to <vtop> <vout>) (bottom-input-to <vbottom> <vout>) (normally-closed <vout>) (fired-closed <vtop>) (fuel-flowing <vbottom>)) (effects (del normally-closed <vout>) (fired-open <vout>) (del fuel-not-flowing <vout>) (fuel-flowing <vout>)))(operator fire-open-3 (params (<vout> Valve) (<vtop> Valve) (<vbottom> Valve)) (preconds (top-input-to <vtop> <vout>) (bottom-input-to <vbottom> <vout>) (normally-closed <vout>) (fired-closed <vtop>) (fuel-not-flowing <vbottom>)) (effects (del normally-closed <vout>) (fired-open <vout>) (del fuel-flowing <vout>) (fuel-not-flowing <vout>)))(operator fire-close-top-1 (params (<vout> Valve) (<vtop> Valve) (<vbottom> Valve)) (preconds (top-input-to <vtop> <vout>) (bottom-input-to <vbottom> <vout>) (normally-open <vtop>) (fired-open <vout>) (fuel-flowing <vbottom>)) (effects (del normally-open <vtop>) (fired-closed <vtop>) (del fuel-not-flowing <vout>) (fuel-flowing <vout>)))(operator fire-close-top-2 (params (<vout> Valve) (<vtop> Valve) (<vbottom> Valve)) (preconds (top-input-to <vtop> <vout>) (bottom-input-to <vbottom> <vout>) (normally-open <vtop>) (fired-open <vout>) (fuel-not-flowing <vbottom>)) (effects (del normally-open <vtop>) (fired-closed <vtop>) (del fuel-flowing <vout>) (fuel-not-flowing <vout>)))(operator assert-fuel-flowing-top (params (<vout> Valve) (<vtop> Valve)) (preconds (top-input-to <vtop> <vout>) (fired-open <vout>) (normally-open <vtop>)) (effects (del fuel-not-flowing <vout>) (fuel-flowing <vout>)))(operator assert-fuel-flowing-bottom (params (<vout> Valve) (<vbottom> Valve)) (preconds (bottom-input-to <vbottom> <vout>) (fired-open <vout>) (fuel-flowing <vbottom>)) (effects (del fuel-not-flowing <vout>) (fuel-flowing <vout>)))(operator assert-fuel-not-flowing (params (<vout> Valve)) (preconds (normally-closed <vout>)) (effects (del fuel-flowing <vout>) (fuel-not-flowing <vout>)))(operator assert-fuel-no-input (params (<vout> Valve) (<vtop> Valve) (<vbottom> Valve)) (preconds (top-input-to <vtop> <vout>) (bottom-input-to <vbottom> <vout>) (fired-closed <vtop>) (fuel-not-flowing <vbottom>)) (effects (del fuel-flowing <vout>) (fuel-not-flowing <vout>)))(operator fire-rocket-motor (params) (preconds (off rocket-motor) (fuel-flowing v6)) (effects (del off rocket-motor) (on rocket-motor)))(operator shut-off-rocket-motor (params) (preconds (on rocket-motor) (fuel-not-flowing v6)) (effects (del on rocket-motor) (off rocket-motor)))(operator assert-motor-fired-one-time (params) (preconds (on rocket-motor) (zero times-motor-fired)) (effects(del zero times-motor-fired) (one times-motor-fired)))(operator assert-motor-stopped-one-time (params) (preconds (off rocket-motor) (one times-motor-fired)) (effects (one times-motor-stopped)))(operator assert-motor-fired-two-times (params) (preconds (on rocket-motor) (one times-motor-fired) (one times-motor-stopped)) (effects (del one times-motor-fired) (two times-motor-fired)))(operator assert-motor-stopped-two-times (params) (preconds (off rocket-motor) (two times-motor-fired)) (effects (two times-motor-stopped)))(operator assert-motor-fired-three-times (params) (preconds (on rocket-motor) (two times-motor-fired) (two times-motor-stopped)) (effects (del two times-motor-fired) (three times-motor-fired)))Facts:(v1 Valve)(v1 Object)(v2 Valve)(v2 Object)(v3 Valve)(v3 Object)(v4 Valve)(v4 Object)(v5 Valve)(v5 Object)(v6 Valve)(v6 Object)(rocket-motor Object)(times-motor-fired Object)(times-motor-stopped Object)(preconds(top-input-to v3 v6) (bottom-input-to v5 v6) (top-input-to v2 v5) (bottom-input-to v4 v5) (top-input-to v1 v4)(normally-open v1) (normally-open v2) (normally-open v3)(normally-closed v4) (normally-closed v5) (normally-closed v6)(off rocket-motor) (zero times-motor-fired))A. Given this configuration, what is the maximum number of times therocket can fire?B. Suppose the goal state is:(effects (two times-motor-fired)) Manually generate a plan that achieves this goal.C. For the goal state specified in B, solve this problem (manually) using thePOP algorithm. Sketch the final partial-order plan using diagrams of thesame form as those used in Ch. 11 of the Russell and Norvig text. Alsoinclude a few of the intermediate partial-order plans.D. For the goal state specified in B, solve this problem (manually) using theGraphplan algorithm. Draw
View Full Document
Unlocking...