Coverage of a Planar Point Set With Multiple Robots Subject to Geometric Constraints

Abstract

This paper focuses on the assignment of N discrete points among K geometrically constrained robots and determination of the order in which the points should be processed by the robots. This path planning problem is directly motivated by an industrial laser drilling system with two robots that are constrained to translate along a common line while satisfying collision avoidance constraints. The points lie on a planar base plate that translates normal to the axis of motion of the robots. The geometric constraints on the motions of the robots lead to constraints on points that can be processed simultaneously.We use a two step approach to solve the path planning problem: (1) Splitting Problem: Assign the points to the K robots, subject to geometric constraints, to maximize parallel processing of the points. (2) Ordering Problem: Find an order of processing the split points by formulating and solving a multidimensional Traveling Salesman Problem (TSP) in the if-tuple space with an appropriately defined metric to minimize the total travel cost. For K = 2, we solve the splitting problem optimally in O(N <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">3</sup> ) time by converting it to a maximum cardinality matching problem. Since this is too slow for large datasets, we also provide a greedy O(N log N) algorithm. We provide computational results showing that the greedy algorithm solution is very close to the optimal solution for large datasets. For the ordering problem we present local search based heuristics to improve the multidimensional TSP tour. We give computational results for the ordering problem and for the overall performance gain obtained (over a single robot system) by using our algorithm. Finally, we extend our approach to a K-robot system and give computational results for K = 4.