89-685: Introduction to Robotics

Fall 2016: Assignment 2

Due at 23:59:59, Tuesday, January 24th, 2017.


The goal of this assignment is to create a simple navigation planner for the robot.
Your program will be given a starting location and a goal location, and should generate the series of locations the robot needs to go through in order to reach the goal location from the starting location, using the shortest path connecting them.

Input Parameters

The launch file of your program should include the following parameters (the values are given here as an example):
<arg name="map_file" default="$(find turtlebot_gazebo)/maps/playground.yaml" />
<param name="starting_location" value="0,0" />
<param name="goal_location" value="2,-1.5" />
<param name="robot_size" value="0.35" />
<param name="map_resolution" value="0.05" />
A sample launch file can be found here.


  1. Load the given map file into memory (using map_server).
  2. Convert the map into an occupancy grid, in which each cell is 0 (free) or 1 (occupied).
  3. Inflate the obstacles in the grid according to the robot size and the map resolution.
  4. Build a graph, in which each node represents a cell in the grid and the edges connect adjacent cells in the grid.
  5. Run A* algorithm on the graph in order to compute the shortest path from the starting location to the goal location.
  6. Print the path (i.e., the series of grid cells the robot needs to go through) to an output file named navigation_plan.txt.

If there is no valid path from the starting location of the robot to its goal location (e.g., the goal location is outside the map boundaries), you should print a suitable error message and exit.

Note: In this assignment you don't need to move the robot, thus you don't actually need to run the Gazebo simulator. In the next assignment you will make the robot move along the planned path.

The Rules

  1. Make sure that your code is well organized and documented.
  2. All parameter values should be configurable.
  3. You should do this lab on your own. All the work you turn in should be yours, and not done in collaboration with anyone else. If you use any external sources of inspiration, other than ros.org, then let us know in README file.

What to Hand In

You should hand in everything that someone else needs to run your code. For this assignment, that means your source code, manifest file, CMakeFiles.txt (if you're using C++), and launch files. You should not hand in executable files, or any other files that can be regenerated.

Your code should be easy to run. After getting a copy of your code, running

catkin-make --pkg navigation_planner
roslaunch navigation_planner navigation_planner.launch
should be sufficient to execute your planner and generate a navigation plan.

You should also hand in a sample navigation_plan file from one of your test runs.

Finally, zip all the necessary files and submit the zip file to ros.exercises@gmail.com.

Good luck!