| Volume 25 Issue 3 - Publication Date: 1 March 2006 |
| |
| Planning Tours of Robotic Arms
among Partitioned Goals |
| |
| M. Saha, T. Roughgarden,
J.-C. Latombe Computer Science Department, Stanford University,
Stanford, CA, USA and G. Sánchez-Ante Computer Science
Department, National University of Singapore, Singapore |
| |
In this paper we consider a
motion planning problem that occurs in tasks such as spot welding, car painting,
inspection, and measurement, where the end-effector of a robotic arm must
reach successive goal placements given as inputs. The problem is to compute
a nearoptimal path of the arm so that the end-effector visits each goal
once. It combines two notoriously hard subproblems: the collisionfree shortest-path
and the traveling-salesman problems. It is further complicated by the fact
that each goal placement of the end-effector may be achieved by several
configurations of the arm (distinct solutions of the arm’s inverse
kinematics). This leads to considering a set of goal configurations of the
robot that are partitioned into groups. The planner must compute a robot
path that visits one configuration in each group and is near optimal over
all configurations in every goal group and over all group orderings. The
algorithm
described in this paper operates under the assumption that finding a good
tour in a graph with edges of given costs takes much less time than computing
good paths between all pairs of goal configurations from different groups.
So, the algorithm balances the time spent in computing paths between goal
configurations and the time spent in computing tours. Although the algorithm
still computes a quadratic number of such paths in the worst case, experimental
results show that it is much faster in practice. |
| |
| Return
to Contents |
