CS7649-Homework 4 Solved

Robot Intelligence: Planning

Problem 1: 

In this problem you will construct a plan graph for a very simple spacecraft control problem.

 
A critical stage of many deep space probe missions is orbital insertion. One of the most ambitious simulation-based autonomy demonstrations to date has been robust mission planning, execution and failure recovery for Saturn Orbital Insertion (SOI). During SOI it is essential that the main engine be commanded reliably under failure. In this problem we consider the problem of automatically planning a control sequence for a simple rocket engine system.  


Consider an extremely simple rocket engine system, shown below. To fire the engine, fuel must flow to it. Fuel flow is controlled by valves V1 and V2, which are pyrotechnic valves, pyro for short. Pyro valves are initially in one particular state (open or closed). An explosive bolt can be fired that switches a pyro valve 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 pyro valve can switch states only once. The advantage of using a pyro valve is that it is extremely reliable; it will stay in its initial state until fired. When the valve is fired, it will switch with high probability to its opposite state, where the valve remains. In the following diagram, valve V1 is initially open (indicated by NO for normally open). Firing V1 closes it. Valve V2 is initially closed (NC for normally closed). Firing V2 opens it.

 
We formulate the problem using the STRIPS plan representation (the STRIPS representation is introduced in the lecture notes and Ch. 11 of AIMA). Our problem is to generate a command sequence that fires the rocket engine, given that initially v2 is closed, v1 is open and the rocket is off. The initial and goal conditions in STRIPS are:

 
Initial Conditions:

(preconds

(closed-v2)

(open-v1)

(off-rocket)) Goal:

(effects

(rocket-fired)

(fuel-flowing))

 
We define the operations of firing pyro valves v1 and v2 through the plan operators fire-v1 and fire-v2, given below. Note that fire-v1 moves v1 from open to closed and can only be executed when v2 is open. Likewise, fire-v2 moves v2 from closed to open, and can only be executed when v1 is open:

 
(OPERATOR fire-v1

(params)

(preconds (open-v2)

(open-v1))

(effects (del open-v1)

(closed-v1)

(del fuel-flowing)

(fuel-not-flowing)))

 
(OPERATOR fire-v2

(params)

(preconds (closed-v2)

(open-v1))

(effects (del closed-v2)

(open-v2)

(del fuel-not-flowing)

(fuel-flowing)))

 
(OPERATOR fire-rocket

          (params)

          (preconds (fuel-flowing)

                    (off-rocket))

          (effects (on-rocket)

                    (rocket-fired))

 
Part A) Draw the plan graph for this problem, beginning with the initial state, and expanding levels until a level appears that contains all goal variables. Ignore mutex relations for now.

 
Part B) Draw a plan graph for this problem that includes mutex relations for both actions and variables. Note that this may require adding layers to the graph, relative to Part A. The last level for this graph must include all goal variables with no mutex relations between any of them.

Problem 2 

Implement* an activity planner that parses in PDDL domain and problem files and returns a solution (i.e., an “activity plan”). When the code you write is placed within a folder on a computer, it should read in two files: A domain file called “domain.pddl” and a problem file called “problem.pddl”. Your code should print the solution as a sequence of actions, which are separated by commas. We will supply you with example domain and problem files. You will be graded in part based upon the success of your code in solving a hold-out problem file for one of the two domains we provide as examples. The plan you return must not only be complete and consistent, it must also be optimal.**


*You do not have to implement this parser from scratch. You may use a python parser (e.g., https://pypi.org/project/pddlpy/) so that you do not have to implement the infrastructure from scratch. Further, you may utilize any online solver that you want (we will update the approved libraries list on Piazza, please ensure your external libraries are on the list or your submission may not be graded). All you must do is make sure that the code you submit parses in the files and returns a complete, consistent, optimal plan. Your code must run as a single file and cannot require that the TAs install files to get it to work – it should be self-contained.

**Optimal here means that it requires the fewest number of “layers” or time steps.
                 

Problem 3: 

Consider a path-planning problem for the room below (with a notional RRT graph partially depicted). All dimensions are in meters. The four corners of the room are

•       (0,0)

•       (10,10)

•       (0,10)

•       (10,0)

The four corners of the obstacle in the middle are:

•       (3,3)

•       (7,7)

•       (3,7)

•       (7,3)

Your robot starts at location (1,1). The goal location is (9,9).  

Implement RRT to find a collision-free path from the start to goal locations. Ignore dynamics (i.e., your robot can turn in any direction with infinite linear and angular acceleration). Specifically,

Steer(𝑥𝑥𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛, 𝑥𝑥𝑛𝑛𝑛𝑛𝑛𝑛𝑟𝑟) can simply create a line segment from 𝑥𝑥𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛 to 𝑥𝑥𝑛𝑛𝑛𝑛𝑛𝑛𝑟𝑟.

The robot, however, cannot go outside of the room, nor can it go through the obstacle. When evaluating

ObstacleFree(𝑥𝑥𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛𝑛, 𝑥𝑥𝑛𝑛𝑛𝑛𝑛𝑛), you need to check to make sure the path does not go through an obstacle!

Run your FOR loop for 𝑁𝑁 = 1,000 iterations.  

Once you have generated your tree, implement any search algorithm to find a path from the start node to the goal and return it per the template.