Motion Planning and Decision Making in Robotics

Course guarantor:

Lecturer:

Tutor:

Supervisor:

Department of Computer Science

Synopsis:

The course aims to acquaint students with the use planning approaches and decision-making techniques for autonomous

robotic systems. Students in the course will use the knowledge of motion planning algorithms with the focus on

randomized sampling-based algorithms and their theoretical properties. The further topic deals with employing the

planning methods in the data collection missions such as environment monitoring, coverage, surveillance and inspections

tasks where the motion planning is embedded into variants of the combinatorial routing problems, a.k.a. Robotic variants

of the traveling salesman problem, which is called as the sequencing tasks in robotics. The next part of the course is

dedicated to a discussion of robotic information gathering problems where on-line decision making has to be made

during the mission. Informative adaptive path planning algorithms and existing solutions will be discussed. The last part

of the course is dedicated to planning with uncertainty and sequential decision-making under uncertainty. The course will

be composed of lectures providing an introduction to the topics and reading groups where students will be assigned state-

of-the-art papers and present them to the group.

Requirements:

Syllabus of lectures:

1. Robotic motion planning - notation, terminology, and discrete motion planning techniques

2. Grid and Graph-based path planning methods

3. Lifelong planning approaches and real-time heuristic search - D* lite, LRTA*, ARA*

4. Randomized sampling based-motion planning methods

5. Reading group: Improved asymptotically optimal motion planning algorithms

6. Multi-Goal Motion Planning Problem and Sequencing Tasks - Robotic variants of the traveling salesman problem

7. Data-collection planning - TSP(N), PC-TSP(N), and OP(N) and an extension for curvature constrained vehicles

8. Reading group: Data-collection planning approaches

9. Robotic information gathering - exploration of unknown environment, information theoretic approach

10. Reading group: on-line decision making and adaptive informative path planning

11. Reading group: Motion planning with uncertainty

12. Sequential decision-making under uncertainty - Markov Decision Processes and solution approaches

13. Partially Observable Markov Decision Processes (POMDPs)

14. Reading group: Designing control policies for robotic systems

Syllabus of tutorials:

Study Objective:

Study materials:

* Steven M. LaValle: Planning Algorithms, Cambridge University Press, 2006.

* Mykel J. Kochenderfer et al.: Decision Making Under Uncertainty: Theory and Application, MIT Press, 2015.

* Mohamed Elbanhawi, Milan Simic: Sampling-Based Robot Motion Planning: A Review. 2014. - http://ieeexplore.ieee.org/document/6722915/

* S. Karaman, E. Frazzoli: Sampling-based algorithms for optimal motion planning. 2011. http://journals.sagepub.com/doi/10.1177/0278364911406761

* Kiril Solovey, Oren Salzman, Dan Halperin: New perspective on sampling-based motion planning via random geometric graphs. 2016. http://www.roboticsproceedings.org/rss12/p03.html

* Almadhoun et al.: A survey on inspecting structures using robotic systems. 2016. http://journals.sagepub.com/doi/abs/10.1177/1729881416663664

* Sergey Alatartsev, Sebastian Stellmacher, and Frank Ortmeier: Robotic Task Sequencing Problem: A Survey. 2015. https://link.springer.com/article/10.1007/s10846-015-0190-6

* Enric Galceran and Marc Carreras: A survey on coverage path planning for robotics. 2013. http://www.sciencedirect.com/science/article/pii/S092188901300167X

* Autonomous Robots: Special Issue on Online Decision Making for Multi-Robot Coordination, Chung, Faigl, Hollinger, 2018. https://link.springer.com/journal/10514/topicalCollection/AC_bc4a48da13fff437100d9bd19f492a3c

Note:

Further information:

No time-table has been prepared for this course

The course is a part of the following study plans: