Planning multi-goal tours for robot arms

摘要

This paper considers the following multi-goal motion planning problem: a robot arm must reach several goal configurations in some sequence, but this sequence is not given. Instead, the robot's planner must compute an optimal or near-optimal path through the goals. This problem occurs, for instance, in spot-welding, inspection, and measurement tasks. It combines two computationally hard sub-problems: the shortest-path and traveling-salesman problems. This paper describes a greedy algorithm that operates under the assumption that the number of goals is relatively small (a few dozen at most) and the computational cost of finding a good path between two goals dominates that of finding a good tour in a graph with edges of given costs. Although the algorithm computes a quadratic number of goal-to-goal paths in the worst case, it is much faster in practice.