Multi-Goal Path Planning for Cooperative Sensing
Doctoral thesis [pdf, print version, presentation]
Jan Faigl [cv, publications], supervisor: Libor Přeučil
Czech Technical University in Prague
Faculty of Electrical Engineering
dept. of Cybernetics


The thesis deals with multi-goal path planning for cooperating mobile robots in inspection tasks. The problem is studied in the context of the inspection task in a search and rescue mission. The investigated inspection planning is addressed by two approaches. The first one assumes discrete sensing, while continuous sensing is assumed in the second approach. The discrete sensing leads to a decoupled approach based on the problem decomposition into the problem of finding a set of sensing locations and consecutive the multi-goal path planning problem. The continuous sensing approach is formulated as the watchman route problem. Novel algorithms are proposed for these three problems in the thesis.

A new sensor placement algorithm, called the Boundary Placement is proposed to find a set of sensing locations with restricted visibility range. The algorithm is compared with approaches based on convex polygon partitioning and the randomized dual sampling schema. The proposed algorithm outperforms both algorithms in the number of found locations and also in the required length of the inspection path [1].

The multi-goal path planning problem is addressed using self-organizing map (SOM) for which application in the polygonal domain W is not typical. However, the proposed solution based on approximation of the geodesic path enables application of SOM principles in W [2]. The proposed approach is also able to deal with multi-robot variants of the multi-goal path planning, in particular as a solution of the multiple traveling salesman problem with MinMax criterion. The proposed algorithm is computationally feasible and it provides competitive results to the GENIUS heuristic.

The idea of SOM in W has been considered in the watchman route problem (WRP) with restricted visibility range and novel algorithm has been proposed [3]. The procedure is also able to find solutions of the multiple watchman route problem variants: independent patrolling routes, and closed routes starting from a common depot.

The problem of the multi-goal path planning with respect to kinematic and kinodynamic constraints is considered as a trajectory generation based on the found path. A new motion planner called RRT--Pathext is proposed. The planner is able to find a solution of the multi-goal motion planning problem and it is used to regenerate a ring of nodes in the SOM based algorithm for the WRP. A solution of the WRP is found as inspection trajectories for one or several mobile robots satisfying kinematic and kinodynamic constraints.


Sensor Placement Algorithm: Boundary Placement Multi-Goal Path Planning using Self-Organizing Map
Multi-Robot variant of the Multi-Goal Path Planning Watchman Route Algorithm using Self-Organizing Map

Consecutive work

Ongoing effort based on the thesis work mainly concerns the proposed multi-goal path planning method based on the self-organizing map. The adaptation algorithm has been improved in the solutions quality and also in the required computational time aspects [4]. The speedup is in an order of magnitude while the solutions quality is preserved or improved. The largest multi-goal path planning problem formulated as the traveling salesman problem presented in the thesis is solved one hundred times faster by the new version of the algorithm. The additional work is in generalization of the algorithm, which is now able to solve problems with polygonal goals [5, 6]. This effort leads to a unified approach to solve various multi-goal path planning problems.

Moreover, partial results on consideration of localization uncertainties in the path planning have been achieved. Incorporating a mathematical model of the navigation method [7] to the self-organizing adaptation procedure provides more reliable paths for autonomous navigation. The preliminary results of the new planning method for surveillance task with a simple quad-rotor helicopter are presented in [8]. Regarding the experimental results, the planned paths increase reliability of the seen goals during the autonomous surveillance patrolling up to 95%. Similar work has been done for a ground mobile robot (P3AT), for which the proposed approach finds a path leading to more precise navigation (about 20%) in real outdoor environment [9].

Finally, the approach initiated in the thesis seems to provide a framework for solving various inspection tasks with discrete/continuous sensing models, point/polygonal goals, several robots and models of localization uncertainties. A comprehensive overview of further research directions based on the thesis work is presented in Section 9.2.

Selected publications:
[1] Jan Faigl, M. Kulich, and L. Přeučil. A sensor placement algorithm for a mobile robot inspection planning. Journal of Intelligent & Robotic Systems, 62(3-4):329-353 2011. doi: 10.1007/s10846-010-9449-0.
[2] Jan Faigl, M. Kulich, V. Vonásek, and L. Přeučil. An Application of Self-Organizing Map in the non-Euclidean Traveling Salesman Problem. Neurocomputing 74:671-679, 2011. doi: 10.1016/j.neucom.2010.08.026.
[3] Jan Faigl. Approximate Solution of the Multiple Watchman Routes Problem with Restricted Visibility Range. IEEE Transactions on Neural Networks, 21(10):1668-1679, 2010. doi: 10.1109/TNN.2010.2070518
[4] Jan Faigl. On the Performance of Self-Organizing Maps for the non-Euclidean Traveling Salesman Problem in the Polygonal Domain. Information Sciences, 181(19):4214-4229, 2011. doi: 10.1016/j.ins.2011.05.019
[5] Jan Faigl, L. Přeučil. Self-Organizing Map for the Multi-Goal Path Planning with Polygonal Goals. In T. Honkela et al. (Eds.): ICANN 2011, Part I, LNCS 6791, 85-92, 2011.
[6] Jan Faigl, V. Vonásek, and L. Přeučil. A Multi-Goal Path Planning for Goal Regions in the Polygonal Domain In Proceedings of the 5th European Conference on Mobile Robots. 171-176, 2011.
[7] T. Krajník, Jan Faigl, V. Vonásek, K. Košnar, M. Kulich, and L. Přeučil. Simple yet stable bearing-only navigation. Journal of Field Robotics, 27(5):511-533, 2010, doi: 10.1002/rob.20354 [pdf].
[8] Jan Faigl, T. Krajník, V. Vonásek, and L. Přeučil. Surveillance Planning with Localization Uncertainty for UAVs. In 3rd Israeli Conference on Robotics, Ariel, 2010, [pdf].
[9] Jan Faigl, T. Krajník, V. Vonásek, and L. Přeučil. On Localization Uncertainty in an Autonomous Inspection. ICRA, 1119-1124, 2012.


Autonomous Navigation - UGV Autonomous Navigation - UAV
Multi-Goal Path Planning Considering Localization Uncertainty Autonomous UAV Inspection
Planning with and without considering localization uncertainty
Multi-Goal Path Planning with Convex Goals Multi-Goal Path Planning with Polygonal Goals
Intelligent and Mobile Robotics Group (IMR)
youtube channel

Jan Faigl © 2011,2012