 |
Multi-Goal Path Planning for Cooperative Sensing
Doctoral thesis [pdf, print version, presentation]
Jan Faigl [cv, publications], supervisor: Libor Přeučil |
|
||||||
AbstractThe 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. |
Videos
|
Consecutive workOngoing 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.
|
Videos
|
|||||||||||||||||||||||||||||||
