COMP0037 Coursework 2 Term 2, 2019
“Exploration of Unknown Environments”
COMP0037 Assignment 2
Simon Julier (s.julier@ucl.ac.uk), Dan Butters (daniel.butters.16@ucl.ac.uk), Julius Sustarevas (julius.sustarevas.16@ucl.ac.uk)
Version: 19st February, 2019
Overview
Assignment Release Date: Tuesday 19th February, 2019
Assignment Submission Date: 23:55 Friday 15th March, 2019
Weighting: 30% 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_CW2_GROUP_n.zip, where n is the name of your group.
Assignment Description
In this assignment you will investigate how a mobile robot explores an unknown environment. In particular, we will look at the factory-like environment encountered so far. We assume that the robot operates in two phases. In the first phase, the robot constructs a static model of the environment. This is used in the second phase to carry out a set of tasks. This coursework concentrates on the first phase.
There is an unmarked familiarization phase which is to get you familiar with the code. This coursework has three main parts:
1. You will implement an exploration system which will attempt to explore an environment (although the planning system actually knows ground truth).
2. You will implement a reactive planner to allow the robot to compensate for uncertainty as it completes its mission.
3. You will show how the exploration system and the reactive planning system interact with one another.
As explained below in the materials section, you are provided with reference code which implements some of the techniques in the lecture. These include a mapping system, a (deliberately very inefficient) exploration system, and the hooks to show where reactive planning will be implemented. The code also includes a reference implementation of an A* planner which supports a range of heuristics.
The results of your development will be presented in a single report. This will be divided into two separate parts. The rubric gives the allocation of marks within each part separately. The overall mark for the coursework will be given by taking the weighted contributions of each part separately.
Part 0: Mapping System (Unmarked)
This is a familiarization exercise to get you up and running with the new system. It is also an opportunity for you to finetune the system, and to bring in your code from CW1 and use it if you wish.
Run:
roslaunch comp0037_cw2 mapping_prespecified_waypoints.launch
This will launch the planning and mapping system using a known search map of the environment, and a set of waypoints that the robot will drive to in order to full model the environment. For path planning, the robot uses my implementation of Dijkstra.
COMP0037 Coursework 2 Term 2, 2019
Figure 1: Docker output for familiarization task.
The code will open four windows shown in Figure 1.
1. Planner OG: This is the occupancy grid the planner has available. In this familiarization task, this is exactly the structure of the environment. In later parts, this will not be the “ground truth”.
2. Planner SG: This is the search grid the planner uses. This is created by thresholding the occupancy grid.
3. Mapper Node Occupancy Grid: This is the view of the world the mapping system builds. Initially it is all empty (grey) but will fill in as the robot moves with cells. You will see artefacts on occasion which are caused by things such as numerical
rounding issues and timing mismatches due to networking. These should not cause any substantial difficulty for the
coursework.
4. STDRGUI.
Optional tasks to look at:
1. You should be able to take your A* implementation from CW1 and use it directly in the code. See the file comp0037_reactive_planner_controller/scripts/planner_controller_node.py. The code uses my implementation of Dijkstra.
2. You should be able to look at your robot control strategy and see about moving it over. The main thing to note is that, unlike CW1, for CW2 there are additional API hooks to stop the robot driving if a collision is detected. If you compare the code in comp0037_reactive_planner_controller/src/controller_base.py and comp0037_reactive_planner_controller/src/move2goal_controller.py, you should able to see what changes are needed.
3. Different robot speeds can affect the quality of the mapping. Explore the effect of vehicle drive speed on the quality of map used, and identify a suitable choice. One way to do this would be to use the keyboard-based method to enter robot odometry in comp0037_example. If you choose to do so, note that it has not been modified to account for any changes required to make the mapper run correctly.
Part 1: Implement Frontier-Based Exploration System (60%)
Frontier-Based Planning System (35%):
COMP0037 Coursework 2 Term 2, 2019
The goal of the first part of the coursework is to Implement a frontier-based planning system to guide the robot to fully explore a factory space. The exploration system replaces the boss component by an explorer which dynamically creates the waypoints. The exploration system should keep running until all it has mapped all reachable parts of the map.
In the first part of this coursework, the planner controller actually has full knowledge of the map and so, when presented with a candidate waypoint, it can determine whether the robot can reach that waypoint.
To run the reference system, use the launch file:
roslaunch comp0037_cw2 part_1_exploration_mapping.launch
This includes a (very inefficient) exploration algorithm. Explain how this reference algorithm works. Characterise the performance of the existing exploration system in terms of total distance travelled, total angle turned, total time for completion (use ROS time) and number of waypoints that have to be generated.
Implement your own frontier-based exploration strategy to attempt to improve the speed with which the environment can be explored. Your implementation should include two parts: a method to detect and manage frontiers (based on wavefront detection, fast frontier detection, or another approach that you document and describe), and a method to select waypoints on the frontiers to drive to (use either the closest frontier or largest frontier point heuristic). You should explain what was chosen for each and the justification. Compare the performance of your implementation with the baseline approach.
Challenge Problem (20%+5%):
From a probabilistic perspective, Information Theoretic approaches have the potential to provide the most efficient search strategy by reducing the entropy in the map estimate as quickly as possible. Unfortunately implementing the full method is fairly difficult, and so you will not be required to implement it here. Rather, we ask you to compute the values and compare.
Modify the mapping node so that it computes the entropy of the map roughly once every 5s and saves it to a file.
Plot the curves of how the map entropy changes with the reference exploration algorithm and your frontier-based implementation. Discuss which heuristic appears to be most effective.
For an extra 5%, implement a second frontier selection heuristic and assess its performance as well.
Part 2: Implement Reactive Planner (30%)
Reactive Planner (20%):
The goal is to implement a reactive planner for the robot which uses feedback from the mapping system to validate if the current planned path can be successfully executed and the goal can be reached. If the plan cannot be executed, the planner should be run to create a new path.
For testing, two launch scripts are available to launch the reactive planner:
roslaunch comp0037_cw2 part_2_1_reactive_planner.launch roslaunch comp0037_cw2 part_2_2_reactive_planner.launch
The first sends a set of goals the robot should be able to reach, the second is a single goal the robot cannot reach.
In your report, describe your implementation and illustrate the performance by showing how your robot adapts to unexpected obstacles. You should be able to illustrate two cases. The first is where an obstacle is in a place which is difficult to get to, and the robot has to plan a number of times to be able to get there. The second is where the goal cannot be reached at all (e.g., the goal is within an obstacle).
Reactive planners tend to be very inefficient in their operation, both in terms of planning initially where to move, and the computational costs associated with replanning. Several techniques – including D*-Lite – were discussed during the lectures. Comment on how these could potentially be used to improve the performance of your planner. You do not have to implement the algorithms.
COMP0037 Coursework 2 Term 2, 2019
Challenge Problem (10%):
Many reactive planning systems use a local path planner to try to get around small obstacles. These can use simple heuristics (e.g., turn left and travel a fixed distance before running the full planner). Describe (but do not implement) how you would implement a system in this case.
Part 3: Putting it All Together (10%)
In this part, you will run your exploration algorithm with your reactive planning algorithm and describe the results. Unlike part 1, where the planner had knowledge of the complete map and could validate whether a goal is reachable or not, the system here will only have access to the map which is being built at run time.
roslaunch comp0037_cw2 part_3_reactive_exploration_mapping.launch
Critically discuss the performance of your system using the map. Note that it is not necessary for the final system to be able to map and explore full environment.
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 cw2. The safest approach is to create a new catkin_ws and run:
cd
git clone https://github.com/UCL/comp0037.git cd comp0037
git checkout cw2
If this was successful, you should see:
Switched to a new branch ‘cw2’
ls -l
-rw-r–r–
drwxr-xr-x
drwxr-xr-x
drwxr-xr-x
drwxr-xr-x
drwxr-xr-x
drwxr-xr-x
drwxr-xr-x
drwxr-xr-x
drwxr-xr-x
drwxr-xr-x
1 ucacsjj staff 6 ucacsjj staff 5 ucacsjj staff 8 ucacsjj staff 5 ucacsjj staff
10 ucacsjj staff 8 ucacsjj staff 8 ucacsjj staff 5 ucacsjj staff 5 ucacsjj staff
13 ucacsjj staff
1512 19 Feb 08:19 LICENSE
192 19 Feb 08:20 comp0037_cw2
160 19 Feb 08:20 comp0037_example
256 19 Feb 08:20 comp0037_explorer
160 19 Feb 08:20 comp0037_launch
320 19 Feb 08:20 comp0037_mapper
256 19 Feb 08:20 comp0037_reactive_planner_controller 256 19 Feb 08:20 comp0037_resources
160 19 Feb 08:20 comp0037_the_boss
160 19 Feb 08:20 comp0037_time_server
416 19 Feb 08:19 stdr_simulator
You should then be able to do:
cd ../..
COMP0037 Coursework 2 Term 2, 2019
catkin_make
source ./devel/setup.bash
The code only runs in full ROS mode.
Detailed Description
The software consists of the following packages. Packages in italics are unchanged from coursework 1.
• comp0037_cw2: 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_explorer: This module will be responsible for running the exploration phase of the robot. It will be
responsible for identifying frontiers, planning, etc.
• comp0037_launch: Example launch scripts for starting up stdr.
• comp0037_mapper: This module runs the mapping algorithm which takes odometry and other data and produces
new updated maps of the environment. It issues two types of maps: the full updated occupancy grid, and the delta
occupancy grid, which only contains non-zero entries where the occupancy grid cell values have changed.
• comp0037_reactive_planner_controller: This forms a similar function to the planner controller from course
work 1. However, it has been modified to provide hooks to support real-time feedback.
• comp0037_resources: These are resources such as simple rooms.
• comp0037_the_boss: Sends waypoints for the robot to drive to from a prescribed list.
• 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).
• stdr_simulator: This is a locally modified version of the stdr simulator which fixes a couple of bugs. The speed
limiter has been removed.
Removed packages:
Note the following two have been removed:
• comp0037_cw1: This package contains launch files, which are used to automate starting up ROS nodes, together with the scenarios (maps + lists of goals). It is not needed for cw2.
• comp0037_planner_controller: The reactive planner controller introduces many small changes and trying to maintain full backwards compatibility was too difficult.
You will mainly be working with comp0037_explorer for Part 1, comp0037_reactive_planner_controller for Part 2 and both components together for Part 3.
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. I will be checking the forum as often as I 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 two files – a pdf of the report via Turn-It-In and a zip file. The name of the zip file will be of the form “Group_XX_CW2.zip”, where XX 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.
Marking Guidelines
COMP0037 Coursework 2 Term 2, 2019
All reports will be marked against the marking rubric, which is downloadable from the course’s Moodle page. The mark weighting for each section is as follows:
1. Algorithms Description (30%)
How well are the different algorithms described and contrasted?
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?
3. Format, structure, referencing and clarity of writing (10%)
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?
4. Challenge Problems (20%)
Additional marks for the challenges – 10% on description, 5% on analysis and 5% on performance gains.
Submission and Feedback
The deadline for submission is 23:55 on Friday 15th March, 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, 25th May 2019.