Premium
Multirobot Coverage Search in Three Dimensions
Author(s) -
Dornhege Christian,
Kleiner Alexander,
Hertle Andreas,
Kolling Andreas
Publication year - 2016
Publication title -
journal of field robotics
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.152
H-Index - 96
eISSN - 1556-4967
pISSN - 1556-4959
DOI - 10.1002/rob.21573
Subject(s) - robot , computer science , cover (algebra) , exploit , partition (number theory) , search and rescue , greedy algorithm , set (abstract data type) , travelling salesman problem , motion planning , set cover problem , ranking (information retrieval) , artificial intelligence , real time computing , distributed computing , algorithm , engineering , mathematics , programming language , mechanical engineering , computer security , combinatorics
Searching for objects and observing parts of a known environment efficiently is a fundamental problem in many real‐world robotic applications, e.g., household robots searching for objects, inspection robots searching for leaking pipelines, and rescue robots searching for survivors after a disaster. We consider the problem of identifying and planning sequences of sensor locations from which robot sensors can observe and cover complex three‐dimensional (3D) environments while traveling only short distances. Our approach is based on sampling and ranking a large number of sensor locations for a 3D environment represented by an OctoMap. The visible area from these sensor locations induces a minimal partition of the 3D environment that we exploit for planning sequences of sensor locations with short travel times efficiently. We present multiple planning algorithms designed for single robots and for multirobot teams. These algorithms include variants that are greedy, optimal, or based on decomposing the planning problem into a set cover and traveling salesman problem. We evaluated and compared these algorithms empirically in simulation and real‐world robot experiments with up to four robots. Our results demonstrate that, despite the intractability of the overall problem, computing and executing effective solutions for multirobot coverage search in real 3D environments is feasible and ready for real‐world applications.