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)
Overview
Assignment Release Date: 22nd March 2019
Version: 6th April, 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, a separate report in PDF format and a video file. 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 with the name COMP0037_CW3_GROUP_n.[ext]. You may use a variety of video formats, but the video must be playable by VLC.
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.
The video should provide an explanation for each task in turn. Therefore, the mark breakdown for the first two parts shows, for each task in turn, the mark allocation for the report and the video.
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 𝑌. For example, the route shown in Figure 1c has the path length
𝐿() =𝐿(+, +𝐿+,., +𝐿.,. +𝐿.).
Please note that the figure is NOT drawn to scale, and no measurements should be taken from it to support your answers.
The robot can drive down multiple aisles which are denoted by letters. By “driving down aisle 𝑋”, we mean that the robot starts at the intial cell 𝐼, drives to the right until it reaches aisle 𝑋 and then turns left to drive up the map.
The shortest path has the robot drive down aisle 𝐵 and then cross over to aisle 𝐶 as shown in Figure 1a. Sometimes aisle 𝐵 can be blocked by a temporary obstacle 𝑂+. The robot only detects if the obstacle is present when it reaches cell 𝐵2. 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 𝐿4. Part 0: Familiarity (Unmarked)
After building the cw3 branch, run:
roslaunch comp0037_cw3 test_obstacler_factory.launch
COMP0037 Coursework 3 Term 2, 2019
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.
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. As a result, if you launch the scenario multiple times, sometimes the obstacles will exist, and sometimes they will not.
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% Report; 11% Video)
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% Report; 4% Video):
Suppose the robot has decided to drive down aisle 𝐵 and encounters the temporary obstacle 𝑂+ . Given that this is the only obstacle in the warehouse, what is the minimum mean 𝜆+ for which the robot should replan and not wait for the obstacle?
Aisle Selection at the Start (15% Report; 3% Video):
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 𝐵? Again, assume that there can at most be the single obstacle 𝑂+.
COMP0037 Coursework 3 Term 2, 2019
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%; 4% Video):
Suppose a second obstacle, 𝑂. , can appear in aisle 𝐶 with probability 𝑝. . If it appears, the amount of time it lasts is also Poisson- distributed with a different mean wait time 𝜆. . 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% Report; 9% Video)
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 𝐿4 = 2.
For this task there is 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% Report; 3% Video):
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% Report; 3% Video):
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. Using the values you have determined and your equation from Part 1, compute the minimum value of 𝜆+ which will cause the robot to move if it encounters an obstacle.
(You do not need to run the robot multiple times and collect statistics.)
Aisle Selection at the Start (15% Report; 3% Video):
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. Using the values you have determined and your equation from Part 1, compute the minimum value of 𝜆+ which will cause the robot to go directly down aisle 𝐶.
The launch file part2_drive_factory_obstacles_sometimes.launch implements this case. From your (You do not need to run the robot multiple times and collect statistics.)
COMP0037 Coursework 3 Term 2, 2019
Part 3: Video Submission (20% Total; Marks distributed according to the explanation of parts above)
Submitting a video is mandatory and must obey the following instructions. If you do not do this, then you will receive no marks for this coursework.
In your video, you will discuss your solution for each part you attempted for the coursework above. Each video will feature all the members of the team. Each member of the team will be expected to speak for at least a minute, and the overall video should run between 3 and 10 minutes. (Please note that there is no expectation that longer is better. Rather, producing a very compact short video can take an extremely long amount of time, which is not the intent of this task.)
The video should include the following:
• An introduction to the team. Each team member must introduce themselves on camera.
• For each part of the coursework attempted, explain your solution. You do not need to produced a polished
presentation. It is sufficient to highlight parts of the report or code using a mouse cursor and to discuss the presented text. Simply reading out the text of the solution is not sufficient. Instead, you should discuss your solution and identify things such as where the challenges lie.
• For each part of the coursework not attempted, provide a brief explanation of why this was the case.
For the group, video taken with a handheld camera (such as a mobile phone) with the built-in microphone is sufficient. However, please ensure that video and audio quality is clear. For capturing solutions / code there are a variety of methods. My colleagues recommend Snagit (https://www.techsmith.com/screen-capture.html) because it offers a free month-long evaluation period, it is easy to switch between webcam and screen recording, and includes a video editing too. Please have a look at the tutorial via https://www.techsmith.com/tutorial-snagit-how-to-document-process-video.html#transcript.
There are a variety of ways to encode videos. There are only two technical requirements. First, the video must be playable by VLC 3.0.5 (https://www.videolan.org/vlc/releases/3.0.5.html). (VLC is supported on Linux, Mac and Windows. It is typically plays a much wider range of media than, say, the Windows Media Player or the QuickTime Player.) Second, the video must be less than 160M in size to permit upload to Moodle.
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 14:53 LICENSE 12 22 Mar 14:53 README.md
192 22 Mar 14:53 comp0037_cw3
160 22 Mar 14:53 comp0037_example
160 22 Mar 14:53 comp0037_launch
320 22 Mar 14:53 comp0037_mapper
256 22 Mar 14:53 comp0037_obstacler
256 22 Mar 14:53 comp0037_reactive_planner_controller 256 22 Mar 14:53 comp0037_resources
192 22 Mar 14:53 comp0037_the_boss
160 22 Mar 14:53 comp0037_time_server
416 22 Mar 14:53 stdr_simulator
COMP0037 Coursework 3 Term 2, 2019
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.
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.
Report Marking Guidelines
Each subsection of this report shows the marks allocated to it. Within each subsection, we use the following weighting scheme:
COMP0037 Coursework 3 Term 2, 2019
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 Marking Guidelines
The video will be assessed by comparing the explanation of each part in the video with each part in the submitted report. We will assess clarity and quality of explanation. The mark allocation for each part is indicated above.
Submission and Feedback
The deadline for submission is 23:55 19th April 2019. Feedback will be by early May.