The project assignment should be solved individually. Each student should have his/her own solution and be prepared to explain and motivate any part of it. Please refer to the code of honor for more information.
Planning a path from one point of the environment to the other while avoiding collisions with the obstacles is a complicated problem. As the number of degrees of freedom increases, the problem soon becomes very hard to solve. As computing power becomes available, probabilistic methods are being used more and more often to tackle these problems.
This project deals with a method for path planning known as Probabilistic Road Maps. The basic idea with probabilistic road maps is to randomly select a set of nodes/points in the environment that are free from collision, and try to connect them with straight lines that are also free from collisions. A solution to the problem might then be found by estimating a path through the graph from the start point to the end point.
One of the key components in such an algorithm is the ability to check for collisions with the environment. This project assignment is about implementing a world model that allows the path planning algorithm to query if a certain point in space is free from obstacles.
For more in detailed information about planning, have a look at Steve LaValle's book on Planning Algorithms that is available online.
You are given a number of files packed into a zip-file. On a Linux/Unix system you unpack this file with the command unzip prm-files.zip which will give you a directory called prm-files with the following files
$ ls prm-files
AStarNode.cc PRM.cc SingleCircleWorld.cc
AStarNode.hh PRM.hh SingleCircleWorld.hh
plan_problem1.png PRMNode.cc solvePlanningProblem.cc
plan_problem2.png PRMNode.hh World.cc
plan_problem3.png problem1.txt World.hh
plan_singlecircle.png problem2.txt
Position.cc problem3.txt
Position.hh README
The .cc and .hh files are the source files that you are given as a start for this project. Study them so that you understand what they do. Briefly, the solvePlanningProblem.cc file is the application, PRM.hh[cc] implements a simple version of the probabilistic road map method and World.hh[cc] is an abstract base class which you are supposed to inherit from and implement something that can read a problem specification file on the format below.
Problem Specification File
The world is defined in a specification file that gives the start and goal for the path as well as the obstacles. An example of such a file is:
START_AND_GOAL 0.5 0.5 9 9
CIRCLE 0 0 0.5
CIRCLE 1 1 0.3
CIRCLE 1 2 0.3
CIRCLE 2 2 0.3
CIRCLE 4 4 1
CIRCLE 4 7 1.5
CIRCLE 7 5.5 1.5
CIRCLE 10 10 0.5
RECTANGLE 1 3 1 1 0
Each obstacle is define usina a separate line in the file. The format for the circle and rectangle is:
CIRCLE centerX centerY radius
RECTANGLE centerX centerY width height angle
where units are meters and radians.
The first thing you should do is run the code that has been provided. It contains a very simple World implementation that contains a single circle with a fixed position. Compile the code and run:
./solvePlanningProblem
The program will output some information about the setting, like the start and goal position, number of nodes, etc. To see what options are available run:
./solvePlanningProblem -h
You can look at the result of planning with the automatically generated Matlab program dispPRM.m. Just open Matlab and run the program and you will see a plot containing the nodes and path (if it was found). An example of such plot can be found below:
As stated above you are to implement a subclass of World that is able to read a problem specification file, answer collision queries and output information in the Matlab format. When you finish implementation of your code, modify the solvePlanningProblem.cc file slightly to make it use your code. This is done by expanding the if-statement where the World object is created.
if (worldModel == "SingleCircleWorld") {
world = new SingleCircleWorld;
// By adding to this if-statement you can easily make the program
// create an instance of your own class
} else {
std::cerr << "worldModel \"" << worldModel << "\" is unknown,"
<< "specify a correct model with -w option or leave out"
<< std::endl;
return -1;
}
You should then be able to select your new world model with the -w option on the command line.
To fulfill the requirements for this project you have to
- Understand how the provided code works (This would normally not be necessary as the beauty of object oriented programming is that all you really have to understand is the interface of the class World. However, since this is a course, you should practice understanding code written by someone else.)
- Implement a base class for an obstacle and provide it with an appropriate interface
- Implement sub-classes of your base class from above that match the obstacle types in this project
- Implement a sub-class of World that aggregates obstacles and makes use of object oriented design so that it does not need to differentiate different obstacles when it prints them to file and checks for collisions.
- The design can be summarised in the following figure
Your program should be able to
- Read a problem specification file (test with problem1.txt - problem3.txt using -p option). To do this your world file needs to be able to read problem files.
- Answer collision queries so that a correct solution is found for problem1.txt - problem3.txt
- Output Matlab display code so that the obstacle map can be displayed in Matlab
NOTE: No changes are supposed to be made to the provided code except for solvePlanningProblem.cc which needs to be modified to add you world.
The following three images show an example of how the generated path could look for problem1-3 respectively:
Good Luck!
