• Released on: 10/05
• Due on: 10/26 (by 11:59 PM)

There are three objectives for this project:

1. Become familiar with and implement an advanced path planning algorithm.
2. Become familiar with modelling for activity planning.
3. Understand the interplay between path and activity planning.

The code for 16.413 students is being kept on a separate branch of the repo used for the course (so as to not clutter the path of people in 16.410). Run the following commands to switch branches. Remember the default password (needed for sudo) is 'student'.

sudo update_intro_to_autonomy
cd /etc/chef
sudo git checkout 16.413
sudo apt-get update
sudo update_intro_to_autonomy
# This update ^ will probably take a much longer time than normal. If it fails, try it one more time before posting a question.

This project uses the command line heavily and we need to set up a Python virtualenv to use for this project. To do so, run the following commands. Note that the first command has two >s, not one!

echo "source /usr/share/virtualenvwrapper/virtualenvwrapper.sh" >> ~/.bashrc
# Close and then reopen any terminals you have open at this point.
mkvirtualenv --system-site-packages proj1
workon proj1
pip install -r /home/student/jupyter/projects/project1/requirements.txt
# The previous step may take quite a bit of time.
add2virtualenv /home/student/jupyter/projects/project1/py

From now on, any time you open a terminal to work on this project, you need to make sure all the Python libraries are on your path by running:

workon proj1

The project makes use of the following packages:

openjdk7-jre virtualenvwrapper python-gtk2-dev coinor-libcbc-dev coinor-libclp-dev coinor-libcoinutils-dev coinor-libosi-dev coinor-libcgl-dev bison flex nginx

In this project, you are working for a brand new company, Googazon, that is using quadrotors for deliveries. Googazon has a set of warehouses that stock cream and sugar, and a set of customers that want cream and/or sugar for their coffee. Your goal is to make all of the customers happy by delivering them the goods they want. You will do this by modelling the delivery problem for a generative planner and implementing a path planner to route the vehicle between different locations.

You will be using RMPL (reactive model-based programming language) as the modelling language for this project. RMPL is developed by the MERS group at MIT. It is an experimental language still under development, but the subset of the language you will be using for this project has been extensively tested.

First, let's look at how the code in this project is laid out. The project is located in the ~/jupyter/projects/project1/ folder. Most of the python code used is located in the py/ folder. bin/ contains executable scripts used for preprocessing, planning, and executing plans. rmpl/ is where provided RMPL scripts are located. environments/ is where provided environment files are located. submission/ is where you will store files we ask you to generate.

We may need to push out updates during this project. To make that process painless, we ask that you do not modify any existing files, except py/intro_to_autonomy/project1/path_planner.py and requirements.txt. Feel free to add new files as you see fit.

Now let's look at what RMPL files look like. Open the file rmpl/simple.rmpl. You can use a text editor of your choice, the Jupyter environment, or the (new) editor located at http://localhost/rmpl-editor to open the file. RMPL is an object-oriented language with a syntax inspired by Java.

One of the ways RMPL classes are different than Java classes is that every class has an implicit “mode” variable that can take on one of a set of predefined values (think Enums in Java). These values are declared using the value keyword.

Let's first look at how Booleans are represented.

class Boolean {
  value yes;
  value no;
}

This makes a class called Boolean whose mode variable can take on the values “yes” and “no”.

You'll also see a line:

#LOCATION_CLASS

This is a statement to the RMPL preprocessor that results in a class being inserted here called Location with values that match every feature in the environment you are using to preprocess the file (more on that later).

We can see Warehouses are defined by:

class Warehouse {
  Boolean has_sugar;
  Location location;
}

Meaning that every Warehouse can have sugar (or not) and has a location (it's located at one of the features in the environment). Customers are similar.

Next, we turn to Quadrotors. We can see that the Quadrotor state is currently defined by three things.

Boolean flying;
Location location;
Boolean has_sugar;

Additionally, a Quadrotor has “primitive methods” defined on it. Primitive methods are actions that are directly executable by the hardware being modelled. In this project, only the Quadrotor class should have primitive methods defined. Primitive methods may take arguments, have preconditions, and have effects that should be modelled so that the planner knows what will happen when that method is executed by the hardware. Let's look at pickup_sugar

primitive method pickup_sugar(Warehouse w)
  flying == no
  && w.location == location
  && w.has_sugar == yes
  => has_sugar == yes;

This primitive method is called pickup_sugar. It takes a Warehouse as an argument. It has three preconditions:

1. The quadrotor must not be in the air (technically, the mode variable of the flying field must have the value no).
2. The quadrotor must be located at the warehouse w (technically, the mode variable of w's location field must have the same value as the mode variable as the quadrotor's location field).
3. The warehouse must contain sugar (technically, the mode variable of w's has_sugar field must have the value yes).

It has one effect:

1. The quadrotor now has sugar (technically, the mode variable of the quadrotor's has_sugar field is set to yes).

We are modelling the warehouses as having an infinite supply of sugar.

You'll notice that there are no primitive methods that allow the quadrotor to change locations. That is where the line:

#MOTION_PRIMITIVE(location, fly, flying==yes)

comes in. When run through the preprocessor, this expands into primitive methods for every pair of locations that are traversable.

Next in the RMPL file is the definition of the Main class. This class is responsible for specifying the initial state and goal states for the planner. You'll see that initially, there is one quadrotor, one Warehouse, and two Customers.

Quadrotor 1;
Warehose warehouse1;
Customer customer1;
Customer customer2;

You'll then see that Main's constructor sets the initial state of the world. For instance:

q.location = w1;
q.flying = no;
q.has_sugar = no;

states that the quadrotor is at feature w1 (the same as the warehouse), it is not flying, and it has no sugar).

Last, you'll see the following:

method run() {
  sequence {
    parallel {
      (customer1.wants_sugar == no);
      (customer2.wants_sugar == no);
    }
    (q.location == w1 && q.flying == no);
  }
}

The run() method tells the planner what you want accomplished. It is the planner's job to determine how to accomplish the goals. This says that you want the planner to come up with a series of actions that gets rid of the customer's desire for sugar (the parallel says you don't care the order) and then results in the quadrotor back at the warehouse and landed (the sequence says to quadrotor should return only after the customers are served).

1. Inheritance is not allowed in this version of RMPL.
2. Try to not to use variable names that are the same as a feature from your environment file. This can confuse the planner as the variable will shadow the feature name wherever the variable is accessible.
3. c and u are reserved keywords (for features you won't use in this project). Do not name any variables or values c or u.

Before the planner can use the RMPL file to plan, it first needs to be preprocessed. This step takes information from the environment (feature names and locations) and embeds it the RMPL file. Open a terminal and (after running workon proj1!) run the following commands:

cd ~/jupyter/projects/project1
bin/preprocess-rmpl rmpl/simple.rmpl environments/no-obstacles.yaml StraightLinePathPlanner /tmp/out.rmpl /tmp/paths.txt

This will invoke the RMPL preprocess on the rmpl/simple.rmpl file with the environments/no-obstacles.yaml environment file using the StraightLinePathPlanner. The preprocessed RMPL file will be saved to /tmp/out.rmpl and the computed paths will be output to tmp/paths.txt (so they don't need to be recomputed when the plan is executed).

You should open the /tmp/out.rmpl file and look at the fly primitive methods on the quadrotor class, as well as the Location class.

Now that the RMPL file has been preprocessed, it can be given to the planner. To execute the plan run the command:

bin/plan /tmp/out.rmpl /tmp/plan.tpn

This will take the preprocessed RMPL file and generate a plan for it. The plan is stored as a TPN (Temporal Plan Network) at /tmp/plan.tpn. If you are curious and want to see a graphical representation of the plan, you can use the TPN viewer available at http://localhost/tpn-viewer in the virtual machine. Note that there is some extra cruft in the plan as a result of the planner adding some things for bookkeeping.

bin/plan also takes an optional third argument, the amount of time to wait before timing out, in seconds.

Last, the plan can finally be executed. To execute the plan, run the command:

bin/execute /tmp/plan.tpn environments/no-obstacles.yaml w1 /tmp/paths.txt --speed 5

The w1 is the name of the feature the vehicle starts at in the simulation.

This will show a graph of the quadrotor moving around in the world, and print to the terminal the actions it is taking as it executes them. Note that there's a very good chance the plan generated by the planner is suboptimal. That is OK for this project (we are using the first result from a suboptimal planner, so the results can be comically suboptimal at times).

Now that you have been introduced to the elements of this project, here are your tasks.

Your first task is to implement a more sophisticated path planner than you have for the previous exercises. We are leaving the choice of path planner open-ended so that you may choose your own definition of what “more sophisticated” means to you, based on your personal interests. Before beginning to implement it, be sure to get approval from the course staff (post a private question on Piazza). Some recommendations to consider are:

• RRT*
• Informed RRT*
• Probabilistic Roadmaps
• A risk-aware path planner
• Any of the above with more complex vehicle dynamics (i.e., a truck or airplane instead of a quadrotor).

Once you have chosen and gotten approval, implement your path planner in the file py/intro_to_autonomy/project1/path_planner.py. To use it during the preprocessing step, simply replace StraightLinePathPlanner with the name of the class you implement.

If you find you need any additional python libraries, add them to the requirements.txt file and install them by running pip install -r requirements.txt. While you are free to use any thrid-party libraries, it is expected that you still implement the path planner and not just call an existing path planner.

If you find you need any additional system libraries, feel free to install them, but record them in the file submission/added-system-libraries.txt

You should use the StraightLinePathPlanner as a model when writing your path planner. Additionally, the environment you are given is the same environment object use in the psets, with the modification that in addition to obstacles there are also “features”.

After implementing your path planner, test it on the environments environments/part1-{simple,bugtrap,cluttered}.yaml. Save PNGs of the executed plans to submission/part1-{simple,bugtrap,cluttered}.png.

Last, describe your path planner implementation in the file submission/part1.txt. Be sure to describe what path planner you chose, which resources you used to understand your path planner, any changes you made beyond the standard algorithm, what values you chose for any tunable parameters (and why you chose them), and any issues you had while implementing or running your path planner.

For this part, you will generate your own environment files with more warehouses and customers, then modify the RMPL file to reflect this.

Generate two environment files. One should be of moderate difficulty (~80 obstacles) and one of hard difficulty (+300 obstacles). To each of these, add enough features for 2-4 warehouses and 6-10 customers.

Save these environments to submission/part2-{moderate,hard}.yaml.

Now, modify the provided RMPL file to match the number of customers and warehouses you chose in each environment. Save these files as submission/part2-{moderate,hard}.rmpl.

Save PNGs of the executed plan in each of these environments to submission/part2-{moderate,hard}.png.

In this part, we will add diversity to the customer requests.

Using the same environments from Part 2, save RMPL files to submission/part3-{moderate,hard}.rmpl that model the following:

• Quadrotors can carry nothing, one sugar, one cream, or one cream and one sugar.
• Warehouses can supply sugar and/or cream.
• Customers can want sugar and/or cream.

Hint: you should add new primitive methods for picking up and delivering cream.

Save PNGs of the executed plan with each of these environments/RMPL scripts to submission/part3-{moderate,hard}.png.

In this part, you will do a little bit of advanced modelling in RMPL, using only the hard environment.

Save an RMPL file to submission/part4-hard.rmpl that allows quadrotors to carry up to two objects, i.e. nothing, one sugar, one sugar and one cream, two sugars, two creams, or one cream.

Hint: you may need to add more pickup and deliver methods. Add anything you need so long as they start with pickup_ and deliver_.

Save a PNG of the executed plan to submission/part4-hard.png.

Put answers to each of these questions in the file submission/part5.txt.

1. It was stated earlier that the underlying planner being used is suboptimal. What are some metrics you think Googazon could use when describing the optimality of plans? Choose two of your previous runs from previous parts and discuss how you think the plan would change if the metrics you suggest we used to come up with an optimal plan.
2. In this project we blended path and activity planning by taking an approach commonly used in the research community: compute a path for every pair of locations, embed that information into the file describing the problem, execute the planner, then use the cached plans at execution time. Discuss some pros and cons of this approach. Is there any other approach you would suggest? What would be its pros and cons?
3. We will probably not get to it this semester, but there exist planners that can also reason about time. This would allow you to specify things like “customer 1 must be served within 5 minutes” or “customer 2 is not available until 2 minutes have passed.” Re answer the previous question in the context of these planners. Also consider that in the real world, travel times may not be known exactly due to things like weather or equipment degradation.

In the file submission/feedback.txt please put any feedback you have concerning this project. What was good, bad, or ugly? Anything we should change for next year's class? Anything we should definitely keep the same?

Run the following command and upload the file at /home/student/jupyter/projects/project1-submission.tar.gz to Stellar.

bin/prepare-submission

Remember that you can post questions in our Piazza Forum. Please do not post answers to the problems, though.