Robot-Dependent Maps for Coverage and Perception Task Planning

As different mobile robots may increasingly be used in everyday tasks, it is crucial for path planning to reason about the robots’ physical characteristics. This thesis addresses path planning where robots have to navigate to a destination, either for coverage tasks or perception tasks, which we introduce. For coverage tasks, robots target the destination position, whereas for perception tasks a robot has to reach a point from where a target can be perceived.
For complex planning problems with multiple heterogeneous robots, it is essential for planning to run efficiently. This thesis introduces robot-dependent maps, which are map transformations that quickly retrieve information related to the feasibility of coverage and perception tasks. The map transformation depends on properties such as footprint, sensing range and field of view. When dealing with perception tasks, this thesis introduces the concept of perception planning, where paths are calculated not only to minimize motion cost but also to maximize perception quality. In order to find optimal paths for the perception of targets, this work uses an informed heuristic search to determine paths considering both motion and perception. Robot-dependent maps are then used to improve the
efficiency of perception planning, by providing dominant heuristics that reduce the number of ray casting
operations and node expansion. The use of robot-dependent maps has a low cost that amortizes over multiple search instances. This thesis also provides a novel technique for multi-robot coverage task planning, with the new
robot-dependent maps used as a pre-processing step. The robot-dependent maps are used to improve the
performance of task allocation when splitting tasks among multiple robots. By using a pre-processing phase, the feasibility of coverage tasks is known for each robot beforehand, and estimates on the cost of each robot executing each task can be quickly computed. This thesis contributes an algorithm to calculate paths for multiple heterogeneous robots that need to perceive multiple regions of interest. Clusters of perception waypoints are determined and heuristically allocated to each robot’s path to minimize overall robot motion and maximize the quality of measures on the regions of interest. Overall, this thesis provides techniques that deal with robot heterogeneity mathematically, modeling the individual characteristics, so that path planning takes into account the perception quality as well. Assuming we have multiple robots with different geometries, ranging from different footprints to different
sensors, the planner accounts for those differences when coordinating the robots. This thesis thus explores algorithms for a planner to dynamically adapt and be able to generate path solutions based on the advantages of each robot. We provide theoretic proofs for some of our contributions and evaluate our algorithms on simulations with a variety of 2D obstacle maps and robots with different physical characteristics.