TY - GEN
T1 - A repartitioning algorithm to guarantee complete, non-overlapping planar coverage with multiple robots
AU - Hungerford, Kurt
AU - Dasgupta, Prithviraj
AU - Guruprasad, K. R.
N1 - Publisher Copyright:
© Springer Japan 2016.
PY - 2016
Y1 - 2016
N2 - We consider the problem of coverage path planning in an initially unknown or partially known planar environment using multiple robots. Previously, Voronoi partitioning has been proposed as a suitable technique for coverage path planning where the free space in the environment is partitioned into non-overlapping regions called Voronoi cells based on the initial positions of the robots, and one robot is allocated to perform coverage in each region. However, a crucial problem arises if such a partitioning scheme is used in an environment where the location of obstacles is not known a priori—while performing coverage, a robot might perceive an obstacle that occludes its access to portions of its Voronoi cell and this obstacle might prevent the robot from completely covering its allocated region. This would either result in portions of the environment remaining uncovered or requires additional path planning by robots to cover the disconnected regions. To address this problem, we propose a novel algorithm that allows robots to coordinate the coverage of inaccessible portions of their Voronoi cell with robots in neighboring Voronoi cells so that they can repartition the initial Voronoi cells and cover a set of contiguous, connected regions. We have proved analytically that our proposed algorithm guarantees complete, non-overlapping coverage. We have also quantified the performance of our algorithm on e-puck robots within the Webots simulator in different environments with different obstacle geometries and shown that it successfully performs complete, non-overlapping coverage.
AB - We consider the problem of coverage path planning in an initially unknown or partially known planar environment using multiple robots. Previously, Voronoi partitioning has been proposed as a suitable technique for coverage path planning where the free space in the environment is partitioned into non-overlapping regions called Voronoi cells based on the initial positions of the robots, and one robot is allocated to perform coverage in each region. However, a crucial problem arises if such a partitioning scheme is used in an environment where the location of obstacles is not known a priori—while performing coverage, a robot might perceive an obstacle that occludes its access to portions of its Voronoi cell and this obstacle might prevent the robot from completely covering its allocated region. This would either result in portions of the environment remaining uncovered or requires additional path planning by robots to cover the disconnected regions. To address this problem, we propose a novel algorithm that allows robots to coordinate the coverage of inaccessible portions of their Voronoi cell with robots in neighboring Voronoi cells so that they can repartition the initial Voronoi cells and cover a set of contiguous, connected regions. We have proved analytically that our proposed algorithm guarantees complete, non-overlapping coverage. We have also quantified the performance of our algorithm on e-puck robots within the Webots simulator in different environments with different obstacle geometries and shown that it successfully performs complete, non-overlapping coverage.
KW - Coverage path planning
KW - Multi-robot systems
KW - Voronoi partitioning
UR - http://www.scopus.com/inward/record.url?scp=84956674244&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84956674244&partnerID=8YFLogxK
U2 - 10.1007/978-4-431-55879-8_3
DO - 10.1007/978-4-431-55879-8_3
M3 - Conference contribution
AN - SCOPUS:84956674244
SN - 9784431558774
T3 - Springer Tracts in Advanced Robotics
SP - 33
EP - 48
BT - Distributed Autonomous Robotic Systems - The 12th International Symposium
A2 - Cho, Young-Jo
A2 - Chong, Nak-Young
PB - Springer Verlag
T2 - 12th International Symposium on Distributed Autonomous Robotic Systems, DARS 2014
Y2 - 2 November 2014 through 5 November 2014
ER -