Coverage of a planar point set with multiple robots subject to geometric constraints

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 K-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³) 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. Note to Practitioners-This paper presents techniques to plan the motions of multiple robots to visit and process a given set of points, subject to geometric constraints on the robot motions. This point set coverage task is motivated by a laser drilling application for electronics manufacturing. The goal is to minimize the time taken to visit the points by parallelizing the robot operations while avoiding robot collisions. Similar tasks arise in many applications including drilling, electronics manufacturing, circuit testing, spot welding, and sensor network data collection. We model the assignment of points in the plane to robots as a matching problem and the point traversal order generation as a Traveling Salesman Problem. We present effective algorithms to plan the motions of the robots for large data sets (involving hundreds of thousands of points), and demonstrate the feasibility of our approach for 2 and 4 robots.