The objective of Assignment 1 is that you are familiar with the most important motion models used in multi agent systems, and understand how the different motion models impact a typical path planning problem.
Assignment 1 includes the following Tasks, that will be explained in more detail below
- T0 - Project Management including progress reporting
- T1 - Waypoint following for the different motion models
- T2 - Path planning for Discrete motion model
- T3 - Path planning for Kinematic point model
- T4 - Path planning for Dynamic point mass model
- T5 - Path planning for Differential Drive model
- T6 - Path planning for Kinematic Car model
- T7 - Path planning for Dynamic Car model
- T8 - Describe solution to T1-T7 in a scientific paper
The path planning problem to be solved in Tasks 2-7 is the following:
Find the minimum time path from A to B in a polygonal environment
The detailed description of Assignment 1 can be found here (pdf).
A description of the report where you describe your work can be found here (link).
Below you find a set of example problems. Solving these enables us to compare the performance of different algorithms on the course meetings.
Solve the problems, and report you current best solution on the course Wiki.
Problem 1 (Discrete obstacle map)
In these problems you will use the discrete motion models, and find the path with the smallest path length (with a diagonal step having sqrt(2) in path length).
The map, including start and endpoints are given in the data file below.
discObst.mat (the obstacle data)
plotDiscObst.m (m-file to import and plot the data)
Problem 1a: Solve the problem using a 4-neighborhood
Problem 1b: Solve the problem using a 8-neighborhood
Problem 1c: Solve the problem using a 16-neighborhood
Problem 2 (Polygonal obstacle map)
In these problems you will use the different continuous motion models,
searching for the minimum time path.
The map, including start and endpoints are given in the data file below.
polygObst.mat (the obstacle data)
plotPolygObst.m (m-file to import and plot the data)
Problem 2a: Solve the problem using the Kinematic point model (Vmax=1)
Problem 2b: Solve the problem using the Dynamic point model (Amax=0.4, Vmax=1)
Problem 2c: Solve the problem using the Differential Drive model (Vmax=1,Wmax=1 rad/s)
Problem 2d: Solve the problem using the Kinematic Car model (Vmax=1, Phimax=1 rad)
Problem 2e: Solve the problem using the Dynamic Car model (Amax=0.1, Phimax=1 rad)
Problem 3: Same as Problem 2 above, but with this map polyObst2.mat. An ascii-version of the data is found in this file polyObst2.txt (to interpret it, look at the m-file that produced it, same as mat-file, but with '-ascii' option).
Links to possibly (you decide) interesting material
- http://en.wikipedia.org/wiki/Rapidly_exploring_random_tree
- http://en.wikipedia.org/wiki/Visibility_graph
- http://en.wikipedia.org/wiki/Voronoi_diagram
- http://sertac.scripts.mit.edu/web/wp-content/papercite-data/pdf/karaman.frazzoli-ijrr11.pdf
- http://arl.cs.utah.edu/pubs/ICRA2013-1.pdf
- http://repository.cmu.edu/cgi/viewcontent.cgi?article=1967&context=robotics
- http://arxiv.org/pdf/1404.2334v3.pdf