Description
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:
Due Date: 8 FEB 2022 at 11:59 PM Eastern
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.
Due Date: 8 FEB 2022 at 11:59 PM Eastern
Submit your work for parts A and B by embedding images of the graph plans into a single PDF, pset4.pdf,
and submitting that PDF to Pset4 – written on Gradescope.
Due Date: 8 FEB 2022 at 11:59 PM Eastern
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.**
Submit your work for this problem by completing the PS4 Python template and submitting it to
gradescope as pset4.py.
*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.
Due Date: 8 FEB 2022 at 11:59 PM Eastern
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.
Submit the following:
• A single python file which implements the provided PS4 template for this algorithm. Please
name the file as pset4.py and submit to Pset4 – coding on Gradescope.
S
G
