COMP0037 Coursework 3 Term 2, 2019
Planning in Uncertain Worlds
COMP0037 Assignment 3
Simon Julier (s.julier@ucl.ac.uk), Dan Butters (daniel.butters.16@ucl.ac.uk), Julius Sustarevas (julius.sustarevas.16@ucl.ac.uk)
Version: 25th March, 2019
Overview
Assignment Release Date: 22nd March 2019
Assignment Submission Date: 23:55 19th April 2019
Weighting: 30% of module total
Final Submission Format: each group submits three things – a single zip file which contains both the source code, and a separate report in PDF format. The name of the zip file will be COMP0037_CW3_GROUP_n.zip, where n is the name of your group. Similarly, the name of the PDF will be COMP0037_CW3_GROUP_n.pdf. Finally, a video will be submitted. We are confirming the upload instructions and will release them shortly.
Assignment Description
In this assignment, you will how uncertainty affects the way the robot plans and moves. It is based on the worked scenario in the lectures, in which there are a number of temporary obstacles which can appear and disappear.
The assignment has three main parts:
1. Written report describing if a robot should re-plan or not. (40%)
2. Demonstrate the performance of your decision threshold in a simple factory like environment using ROS. (40%)
3. A video describing your solution. (20%)
Please note that the video must be submitted and must obey the minimum requirements. Failure to do so means the marks from the first two sections will not be counted. The 20% marks allocated to this task reflect the quality of the video, in particular the quality of the exposition.
COMP0037 Coursework 3 Term 2, 2019
Figure 1: Illustration of the Scenario. (a) A robot plans a path in the factory-like scenario from I to G. The environment includes five different aisles (A to E) that the robot can drive down. The yellow path indicates the planned path. (b) The path down B is sometimes blocked by a temporary obstacle (hatched cells). The robot will detect this when it reaches cell B1. (c) The robot can either wait (not shown) or back up and drive through aisle C. (d) It is also possible for aisle C to be blocked.
Note that the figure is NOT drawn to scale, and no measurements should be taken from it to support your answers.
Consider the situation illustrated in Figure 1 – a robot plans a path from the initial cell 𝐼 to the goal cell 𝐺. Let 𝐿$% be shortest path length between two cells 𝑋 and 𝑌.
The robot can drive down multiple aisles which are denoted by letters. The shortest path has the robot drive down aisle 𝐵 and then cross over to aisle 𝐶. Sometimes aisle 𝐵 can be blocked by a temporary obstacle 𝑂+. The robot only detects if the obstacle is present when it reaches cell 𝐵,. When the robot encounters the obstacle, the number of timesteps the obstacle remains in front of the robot is sampled from a Poisson distribution with mean 𝜆+ .
The robot seeks to find the path with the shortest average path length. The cost of waiting a timestep is 𝐿.. Part 0: Familiarity (Unmarked)
After building the cw3 branch, run:
roslaunch comp0037_cw3 test_obstacler_factory.launch
This will run the factory scenario, using the same waypoints from Part 0 of CW2 (robot mapping the environment). The output is shown in Figure 2. However, the environment now contains a set of obstacles, which are rectangles of different shades of grey in the STDR GUI. (For technical reasons, we could not get the background image in STDR to change, which is why the background will not change.) The obstacles exist with a certain probability. When an obstacle exists, it stops both the laser and the robot. When an obstacle vanishes, the laser will pass through unimpeded and the robot will move. When the robot first encounters the obstacle, the time the obstacle will remain alive is sampled from a Poisson distribution. This is similar to the situation described in the lectures.
COMP0037 Coursework 3 Term 2, 2019
When the robot first detects an obstacle, this obstacle will appear in the map. However, the planning system will only update its occupancy and search grids when it plans a new route. When an obstacle disappears, it also disappears from the mapping system. Note that this is unrealistic – it implies that the robot can tell anywhere at any time that an obstacle has disappeared – but was done to simplify the implementation.
The second test file:
roslaunch comp0037_cw3 test_obstacler_factory_sometimes_obstacles.launch
Demonstrates the same scenario, but with probabilities less than 1 that some obstacles are present.
Figure 2: The application. Note that obstacles (blocks) now appear on the STDR GUl. Note that, unfortunately, these do not dynamically change as obstacles appear and disappear. The mapping system, right, shows currently active obstacles as blocks which appear and disappear in the occupancy grid. Note that, when an obstacle disappears, the robot can pass over where the obstacle was, and the lasers will pass through. Therefore, in this case the robot will (eventually) reach its goal.
Part 1: Develop Static Decision Re-Plan Policy (40%)
Please refer to Figure 1 for the definition of the aisles. For each answer in this part, please write down the equation for the requested value.
Waiting or Replanning When the Obstacle is Always Present (10%):
Suppose the robot has decided to drive down aisle 𝐵 and encounters the temporary obstacle 𝑂+ . What is the minimum mean 𝜆+ for which the robot should replan and not wait for the obstacle?
Aisle Selection at the Start (15%):
Suppose the robot is at 𝐼 and can decide whether it should try to drive down aisle 𝐵, or whether it should just drive directly down aisle 𝐶. What is the minimum mean wait time 𝜆+ at which the robot will decide to drive directly down 𝐶 and not attempt to drive down aisle 𝐵?
The obstacle is not present all of the time. Rather, it is present with probability 𝑝+ and will be absent with probability (1 − 𝑝+ ). Show that if the robot tries to drive down aisle 𝐵, the expected wait time is 𝑝+𝜆+. For a fixed value of 𝜆+, what is the value of 𝑝+ below which the robot will attempt to drive aisle first 𝐵?
Challenge Problem (15%):
COMP0037 Coursework 3 Term 2, 2019
A second obstacle, 𝑂4 , can appear in aisle 𝐶 with probability 𝑝4 . If it appears, the amount of time it lasts is also Poisson- distributed with a different mean wait time 𝜆4 . While at the start, the robot computes that the shortest path from the start to the goal is vial aisle 𝐷. What is the upper bound on the value of the path length of the path going down aisle 𝐷?
Part 2: Implement System in ROS (40%)
The objective here is to implement your decision algorithms in ROS and demonstrate their performance. To compute the cost of the path, use the path distance (not angle) used in CWs 1 and 2. For the wait, use the cost 𝐿. = 2.
For this task there will only be a single start location and a single goal. There is also just a single active obstacle (aisle B). Run the code:
roslaunch comp0037_cw3 part2_drive_factory.launch
In this case, the obstacle is always present in aisle B. The code builds directly upon the reactive planner controller which you developed for CW2. Since this coursework is being released before CW2 has been submitted, the model answer for the reactive controller will be released after the CW2 submission deadline.
Get the Robot to Drive Down Different Aisles (10%):
Complete the implementation of planPathToGoalViaAisle() in src/reactive_planner_controller.py so that, when the robot plans a path, it is possible to control whether this path goes down any of the labelled aisles. Explain your implementation. Demonstrate the performance of your algorithm by showing pictures of the planned routes down different initial aisles.
Hint: Think about multiple destinations work in applications such as Google Maps.
Add Wait or Go Behaviour (15%):
Change the implementation of the reactive planner controller so that, when the robot encounters an obstacle, it can decide to wait until the obstacle clears or will replan down an alternative path. You will need to implement the methods shouldWaitUntilTheObstacleToClear() to make the decision, and waitUntilTheObstacleClears() to implement the robot waiting behavior. Explain your implementation. Show the path cost of waiting versus replanning for a single run of the robot. (You do not need to run the robot multiple times and collect statistics.)
Aisle Selection at the Start (15%):
Suppose the probability that the obstacle is there is 𝑝 = 0.8.
Change the implementation of chooseInitialAisle() to use your logic from Part I to decide if a robot should even attempt to drive a particular aisle. Explain your implementation. Show the path cost of choosing different aisles. The launch file part2_drive_factory_obstacles_sometimes.launch implements this case. (You do not need to run the robot multiple times and collect statistics.)
Part 3: Video Submission (20%)
These instructions are being revised.
Submitting a video is mandatory and must obey the following basic instructions. If you do not do this, then you will receive no marks for this coursework.
Each video will feature all members of the team. They must introduce themselves (on camera). Each member of the team will be responsible for speaking for at least a minute, and no video should run more than five minutes.
In the video, please walk through the solution for each part you attempted for the coursework above. You do not have to provide a presentation, but you should explain each section and your reasoning behind it. Simply reading out the text of the solution is not sufficient.
COMP0037 Coursework 3 Term 2, 2019
Installation
The code is in the branch cw3. 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 cw3
If this was successful, you should see:
Switched to a new branch ‘cw3’
ls -l
-rw-r–r–
-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 1 ucacsjj staff 6 ucacsjj staff 5 ucacsjj staff 5 ucacsjj staff
10 ucacsjj staff 8 ucacsjj staff 8 ucacsjj staff 8 ucacsjj staff 6 ucacsjj staff 5 ucacsjj staff
13 ucacsjj staff
1512 22 Mar
12 22 Mar
192 22 Mar
160 22 Mar
160 22 Mar
320 22 Mar
256 22 Mar
256 22 Mar
256 22 Mar
192 22 Mar
160 22 Mar
416 22 Mar
14:53 LICENSE
14:53 README.md
14:53 comp0037_cw3
14:53 comp0037_example
14:53 comp0037_launch
14:53 comp0037_mapper
14:53 comp0037_obstacler
14:53 comp0037_reactive_planner_controller 14:53 comp0037_resources
14:53 comp0037_the_boss
14:53 comp0037_time_server
14:53 stdr_simulator
You should then be able to do:
cd ../..
catkin_make -DCMAKE_BUILD_TYPE=Release source ./devel/setup.bash
Detailed Description
The software consists of the following packages. Packages in italics are unchanged from CW2.
• comp0037_cw3: 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_launch: Example launch scripts for starting up stdr.
• comp0037_mapper: This has been updated to manage whether obstacles appear or not. It is assumed that the
environment is completely known and the system knowns when an obstacle has disappeared.
• comp0037_obstacler: This node is responsible for causing obstacles to appear and disappear. When an obstacle is first detected by the laser, the system determines if the obstacle is present and, if so, the obstacle will appear for an amount of time drawn from a Poisson distribution.
• comp0037_reactive_planner_controller: This has been extended to introduce the concept that the robot can drive down an aisle and placeholders have been added for waiting.
• 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
a slightly scaled up time (1s simulation = 2s real world time). Scaling it too high can cause everything to become unstable.
• stdr_simulator: This has been updated slightly to handle the obstacles. Also, STDR GUI has been changed so that it leaks memory, instead of crashing, on exit.
COMP0037 Coursework 3 Term 2, 2019
Note the following two have been removed:
• comp0037_cw2: 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 cw3.
• comp0037_explorer: This CW does not require exploration. The package has been removed to reduce the amount of code.
You will be working with just the comp0037_reactive_planner.
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 a single zip file. The name of the zip file will be of the form “Group_XX_CW4.zip”, where XX is the group name. The zip file, when uncompressed, will contain the top-level src directory, 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
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%)
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?
Video criteria to be released shortly.
Submission and Feedback
The deadline for submission is 23:55 19th April 2019. Feedback will be by early May.