COMP0037 Coursework 1

Term 2, 2019

“Path Planning in a Known World”

Investigating Path Planning Algorithms

COMP0037 Assignment 1

Simon Julier (s.julier@ucl.ac.uk), Dan Butters (daniel.butters.16@ucl.ac.uk), Julius Sustarevas

(julius.sustarevas.16@ucl.ac.uk)

Version: 21st January, 2019

Overview

Assignment Release Date: Monday 21st January, 2019

Assignment Submission Date: 23:55 Friday 8th February, 2019

Weighting: 40% of module total

Final Submission Format: each group submits both the source code and a report in PDF format. Both the code and the

report will be placed in a single zip file. The name of the file will be COMP0037_CW1_GROUP_n.zip, where n is the

name of your group.

Assignment Description

In this assignment, you will implement, investigate and optimize a number of discrete different planning algorithms which can

be used by a robot (the stdr simulation robot from lab exercise 2) in a warehouse-like environment. The robot will be given a

known occupancy grid map of the environment. A ROS node (the_boss) sends the robot a sequence of goal cells that the

robot needs to visit in turn. The robot has to plan a path from its current pose to get to the current goal. Both the structure of

the environment and the position of the robot are known perfectly all the time. Both the planner and the robot will collect

information on statistics such as travel distance and travel time. As explained below in the materials section, you will be

provided with reference code which implements some of the basic (and inefficient) path planning algorithms described in the

lectures, as well as a reference (and deliberately inefficient) controller to drive the robot about.

The assignment has two main parts:

1. Implement, investigate the properties of the path planning algorithms. This can be carried out independently of STDR.

2. Embed your path planning algorithms within a full ROS node and use these to drive the robot around. Explore

additional ways to improve the quality of both the path planning and the control of the robot.

The results of both parts of your investigation will be presented in a single report. This will be divided into two parts according to

the assignment above. The rubric gives the allocation of marks within each part separately. The overall mark for this piece of

coursework will be given by taking the weighted contributions of each part separately.

Note the percentages after each heading are the percentage of the overall coursework mark assigned to each section.

Part 1: Investigate Path Planning Algorithms (60%)

Planning Algorithm Investigation (45%):

The goal of this part of the coursework is for you to implement and evaluate a number of path planning algorithms described in

the first four weeks of the lectures. For reference, we provide implementations of the breadth first and depth first planners are

implemented. You should implement your algorithms in a similar way.

Instrument the path planning algorithms to store information on: the number of cells visited by the planner as it computes the

path, the total travel length of the planned path, and the total angle the robot has turned through when driving along that path.

Implement the Greedy Algorithm described in Week 02. The solutions should be sorted in order of Euclidean distance to the

goal. Cells which are closer to the goal should be searched first.

COMP0037 Coursework 1

Term 2, 2019

Implement Dijkstra’s Algorithm described in Week 03.

Implement the A* Algorithm described in Week 04. As noted in the lectures, the heuristic can make a significant difference in

the performance of the algorithm. You should first implement the following heuristics for the cost-to-come function ?"(?):

1. Always 0.

2. A non-negative constant value c.

3. The Euclidean Distance to the goal.

4. The Octile Distance to the goal.

5. The Manhattan Distance to the goal.

Explore the relationship between the choice of heuristic, its admissibility (including changing the weights) and how it changes

the performance of the algorithm. You should use your metrics defined above (cells visited, path length, angle turned) to

support your arguments. You may also derive further illustrative heuristics to further support your arguments. You may use – or

create – any maps of your own, including the ones in comp0037_resources. Any maps developed or used should be

described in your report and included with your provided code.

Challenge Problem (15%):

What do you think is the optimal heuristic out of all possible heuristics (not just the ones listed above) that A* could use? How

do you think A* will behave if you use it? Support your conclusions by implementing and demonstrating the algorithn. Discuss

the feasibility of using this heuristic in practice.

Part 2: Implementation in ROS (40%)

Assess Performance of Path Planners with Simulated Vehicle (25%):

In this part of the coursework, you will explore the relationship between a path, expressed as a set of cells to be visited, and a

robot which needs to drive it. We provide a map and a set of waypoints which represent an idealized set of tasking in an

idealized scenario (this map is loaded by roslaunch comp0037_cw1 factory_scenario.launch and is shown

below in Figure 1). You must use this scenario and set of waypoints in your analysis and discussion. If you wish, you may create

additional scenarios to analyse results and discuss properties. If you do so, please describe these additional maps and provide

them with the code.

Figure 1: Example output from running roslaunch comp0037_cw1 factory_scenario.launch

COMP0037 Coursework 1

Term 2, 2019

Instrument the planner and controller to record the distance travelled, the total angle turned, and time required for the robot to

drive a path. Make sure that you do not include the time of drawing the graphics in your planning time, because the graphics

update can be rather slow.

Compute the performance of the planner, implemented in move2goal_controller, when completing the task. What do

you notice about this algorithm?

Implement a low-level controller which moves the robot from its current location to a specified position and orientation of the

graph. You may adapt, if you wish, your controller you developed as part of Lab Exercise 02. Note that the interface is a bit

different from that encountered in Lab Exerise 02. The helper class controller_base.py provides interfacing code which

should be of help.

For the different algorithms evaluated in Part 1, assess their performance on robot motion.

Challenge Problem (15%)

How can you improve the controller to increase the speed of the robot as it drives to new waypoints? Implement your proposed

improvements and compare the performance of the robot when driving over different paths. Note that we do not look for any

fixed percentage in improvement. Rather, we would like a description of why and where you have identified the inefficiencies,

and report on how your improvements have improved performance.

Materials Description

All the software provided to support this module is on github. This consist of a catkin workspace which you will initialize and run

on your machine.

Installation

The code is in the branch cw1 available in the original repository URL but in a new branch. The safest approach is to create a new

catkin_ws and run:

cd <your_cw1_catkin_ws>/src

git clone https://github.com/UCL/comp0037.git

git checkout cw1

If this was successful, you should see:

Switched to a new branch 'cw1'

ls -l

-rw-r--r-- 1 sjulier staff 1512 20 Jan 09:15 LICENSE

drwxr-xr-x 7 sjulier staff 224 20 Jan 09:20 comp0037_cw1

drwxr-xr-x 5 sjulier staff 160 20 Jan 09:15 comp0037_example

drwxr-xr-x 5 sjulier staff 160 20 Jan 09:15 comp0037_launch

drwxr-xr-x 8 sjulier staff 256 20 Jan 09:20 comp0037_planner_controller

drwxr-xr-x 5 sjulier staff 160 20 Jan 09:15 comp0037_resources

drwxr-xr-x 5 sjulier staff 160 20 Jan 09:20 comp0037_the_boss

drwxr-xr-x 5 sjulier staff 160 20 Jan 09:20 comp0037_time_server

drwxr-xr-x 13 sjulier staff 416 20 Jan 09:15 stdr_simulator

You should then be able to do:

cd ../..

catkin_make

COMP0037 Coursework 1

Term 2, 2019

source ./devel/setup.bash

The code can be run in two modes: standalone and full ROS.

Running Standalone (Needed for Part 1)

The standalone mode can be used to address the first part of this coursework and does not require STDR to run. Several standard

programs are provided. These can be run from:

rosrun comp0037_planner_controller run_fifo_standalone.py

rosrun comp0037_planner_controller run_lifo_standalone.py

rosrun comp0037_planner_controller minkowski_sum_tester.py

The first two run provided implementations of the fifo (breadth first search) and lifo (depth first search algorithms). The last test,

which uses depth first search, shows how the map obstacles can be expanded to take account of the size of the robot. These calls

load the scripts called run_fifo_standalone.py, run_lifo_standalone.py and minkowski_sum_tester.py

which can be found in the comp0037_planner_controller/scripts directory. The code should be “selfdocumenting”.

However, please ask us any questions.

Running Full ROS (Needed for Part 2)

To run, use:

roslaunch comp0037_cw1 factory_scenario.launch

This will launch all the necessary nodes required, including STDR, an appropriate robot, a suitable map, the boss and the test files.

Once started up, the boss will play through a sequence of waypoints.

In addition, you can run:

roslaunch comp0037_cw1 test_scenario.launch

This creates an empty map with a few predefined waypoints.

Detailed Description

The software consists of the following packages. Those shown in italics are identical to the ones in Lab Exercise 2.

comp0037_cw1: This package contains launch files, which are used to automate starting up ROS nodes, together with

the scenarios (maps + lists of goals).

comp0037_example: This is the move the robot example you encountered in Lab Exercise 02.

comp0037_launcher: Example launch scripts for starting up stdr.

comp0037_planner_controller: This node will be the main focus of your coding efforts. It contains both the path

planner which computes a path, and the controller to drive the robot.

comp0037_resources: These are resources such as simple rooms.

stdr: This is a modified version of the stdr simulator. It fixes a number of bugs in the global release. Unfortunately stdr

is not supported anymore, and so we could not get these bug fixes pushed into the main code.

comp0037_the_boss: This node produces the set of waypoints the robot drives to. It waits to receive a message to

confirm that the robot has reached its goal. Rather than use the strings produced in Lab Exercise 02, it uses formatted

ROS messages.

comp0037_time_server: This can be used to “speed up” and “slow down” the simulation time. By default it runs

at real time (1s simulation = 1s real world time). Note that speeding up by more than a factor of 2 can render the

simulation unstable.

You will mostly work with comp0037_planner_controller.

COMP0037 Coursework 1

Term 2, 2019

The launch for the ROS node is scripts/planner_controller_node.py. The way it works is as follows. It waits until

it receives a request to go to a goal. The planner is called to plan a path, and the controller is then invoked to drive the robot to

that goal.

Planning:

cell.py: Contains the description of the cells and their states.

occupancy_grid.py: This is the raw input map. It basically consists of a big array of integers which either have the

value 0 (for clear) or 1 (for occupied).

search_grid.py: This contains an encoding of the graph for search. It consists of a 2D array the same size as the

occupancy_grid. Each element is a cell and can be dead, alive, etc.

planned_path.py: This contains the class which represents the planned path. This consists of the chain of cells,

together with costs.

planner_base.py: This is the base class for the planner. It actually mostly contains stuff for drawing the 2D grid cell

map, and you shouldn’t have to look at it.

general_forward_search_algorithm.py: This includes the implementation of the general forward based

search presented in the lectures. You should not have to change this.

cell_based_forward_search.py: This provides the logic for how the robot state is predicted forwards.

lifo_planner.py: This contains the methods just to implement depth first search.

fifo_planner.py: This contains just the code needed to implement breadth first search.

When you implement your own algorithms, you should only have to create your own classes similar to lifo_planner and

fifo_planner. You should not have to change any other code.

Control:

controller_base.py: This handles the code for taking in odometry from STDR, turning it into a pose that’s

available, and driving the robot from waypoint to waypoint in a path

move2goal_controller.py: This is a simple reference path planner I implemented which is the reference

solution to Lab Exercise 02.

To implement your own controller you should be able to replace the move2goal_controller. You should not have to

change any other code.

Getting Help

You are encouraged to use the assignment discussion forum to help when you get stuck. Please check the forum regularly and try

and answer each other’s questions. Notifications should now be set up, and we will be checking the forum as often as we can and

will be answering any questions that have remained unanswered. Please note that if you have questions about coursework, please

post them to the forum directly rather than emailing me. The reason is that all students will be able to see the reply.

Submission Format and Structure

Each group will submit a single zip file. The name of the zip file will be of the form “COMP0037_CW1_GROUP_n.zip”, where n is

the group name. The zip file, when uncompressed, will contain your catkin_ws/src (including all the nodes described

above), together with a report in pdf format. The code will not be marked independently, however, the code may be tested to

ensure that it works correctly and supports the results presented in the report.

A reference zip file will be provided to show the desired format structure.

Please note that, if you do not conform to the submission guideline, a 10% penalty on your overall mark for the coursework

will be imposed.

Marking Guidelines

Each subsection of this report shows the marks allocated to it. Within each subsection, we use the following weighting scheme:

1. Algorithm or Idea Description (30%)

COMP0037 Coursework 1

Term 2, 2019

How well are the different algorithms or ideas described and discussed? For example, how thoroughly are the strengths

and weakness of different algorithms presented?

2. Implementation, Analysis and Presentation of Results (40%)

How thorough is the analysis and discussion of the results? How well do they compare between the different algorithms

and with properties of those algorithms? Are the algorithms well-supported by quantitative evidence? For example, do

the theoretical benefits identified in the algorithm description actually lead to similar benefits in results?

3. Format, structure, referencing and clarity of writing (30%)

Is your report well laid out and does the write-up follow a clear structure? Have you included any references to show

background research/reading? Is your writing free from spelling, punctuation, and grammatical errors?

Submission and Feedback

The deadline for submission is 23:55 on Friday 8th February, 2019. As explained above,

please submit a single zip file per group. Please pay attention to both the requested file name and the file structure. The reports

will be marked and feedback will be provided by Friday, 1st March 2019.

因为专业，所以值得信赖。如有需要，请加QQ：99515681 或邮箱： 

微信：codinghelp