Path planning for mobile robots in inspection, surveillance, and exploration missions
Prof. Martin Saska. Faculty of Electrical Engineering, Czech Technical University, República Checa.
Abstract
The course will introduce participants into path planning problems for mobile robots. It will start with fundamental approaches based on the discretization of the problem domain and graph based search techniques. After that, geometrical approaches from the computational geometry will be discussed followed by the grid-based algorithms and wavefront propagation techniques. Then, randomized sampling based techniques PRM and RRT will be presented that will be concluded with the optimality guarantee of the RRT* and RRG algorithms. The rest of the course will be dedicated to path planning in the inspection, surveillance, and exploration missions. In these problems, the planning becomes the multi-goal path planning, which can be formulated as a variant of the traveling salesman problem. Examples of existing approaches will be presented and the course will be concluded with an overview of the recent results on the path planning for autonomous data collection planning.
Outline of the course syllabus
1. Path planning for mobile robots - notations, problem definition, configuration space (C-space) and its representations; roadmap based techniques (visibility graph, cell decomposition, and voronoi diagram methods); overview of graph based search methods: BFE, Dijkstra’s algorithm, A*. In this lecture, the basic path planning approaches will be introduced to the students.
2. Overview of the artificial potential fields (APF) and grid based path planning methods:, D*, Distance Transform (DT), Fast Marching (FM), and Theta* algorithms. Wavefront propagation planning techniques will be discussed in the context of the cell (2D/3D grid) based representations of the mobile robot operational environment.
3. Randomized sampling based techniques (PRM, RRT) and optimal path planning algorithms and their optimality guarantees (RRT*, RRG). Planning approaches that allow to find (optimal) paths for mobile robots with high degrees of freedom in a high dimensional configuration will be shown. Particular sampling based techniques will be evaluated regarding the quality of found solutions and required computational requirements during the lab part of the lesson.
4. Multi-goal path planning - solution of the inspection planning problems, patrolling routes. Overview of the key problem formulations as variants of the traveling salesman problem (with neighborhoods) will be discussed and existing solutions of these problems will be introduced. During the lab part, an influence of the path planning will be studied in the mobile robot exploration of the unknown environment using the provided exploration framework.
5. Path planning for autonomous data collection and robotic information gathering. The lab part will be dedicated to demonstrate an available unifying planning framework for autonomous data collection planning.
Assessment
Practical take-home type with the provided software frameworks for path planning in inspection, exploration, and data collection missions. Path planning frameworks will be provided to students to evaluate particular planning methods in the context of simple path planning, inspection and exploration problems. During the first two days, the course will provide theoretical foundations at the lectures, while the rest of the course will be organized into a lecture part providing theoretical aspects first. Then, the class will continue in the lab for a practical lesson of the discussed topics.
Examination
The evaluation mode will be Take-Home.
Recommended literature
H. Choset, K.M. Lynch, S. Hutchinson, G. Kantor, W. Burgard, L.E. Kavraki, S. Thrun: Principles of Robot Motion: Theory, Algorithms, and Implementations, MIT Press, Boston, 2005.
Steven M. LaValle: Planning Algorithms, Cambridge University Press, 2006 ( http :// planning . cs . uiuc . edu )
S. Karaman, E. Frazzoli: Sampling-based algorithms for optimal motion planning. I. J. Robotic Res. 30(7): 846-894 (2011)
M. Schwager, D. Rus, J.-J. E. Slotine: Unifying geometric, probabilistic, and potential field approaches to multi-robot deployment. I. J. Robotic Res. 30(3): 371-383 (2011)
N. Basilico, F. Amigoni: Exploration strategies based on multi-criteria decision making for searching environments in rescue operations. Auton. Robots 31(4): 401-417 (2011)
G.A. Hollinger, G.S. Sukhatme: Sampling-based robotic information gathering algorithms. I. J. Robotic Res. 33(9): 1271-1287 (2014)
J. Faigl, G.A. Hollinger: Unifying multi-goal path planning for autonomous data collection. IROS 2014: 2937-2942
J. Faigl, T. Krajník, V. Vonásek, L. Preucil: On localization uncertainty in an autonomous inspection. ICRA 2012: 1119-1124
J. Faigl, M. Kulich, K. Preucil: Goal assignment using distance cost in multi-robot exploration. IROS 2012: 3741-3746
J. Faigl, V. Vonásek, L. Preucil: Visiting convex regions in a polygonal map. Robotics and Autonomous Systems 61(10): 1070-1083 (2013)
