Planning Tours of Robotic Arms among Partitioned Goals
- 1 March 2006
- journal article
- other
- Published by SAGE Publications in The International Journal of Robotics Research
- Vol. 25 (3), 207-223
- https://doi.org/10.1177/0278364906061705
Abstract
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.Keywords
This publication has 16 references indexed in Scilit:
- A greedy approximation algorithm for the group Steiner problemDiscrete Applied Mathematics, 2006
- Probabilistic Roadmaps of Trees for Parallel Computation of Multiple Query RoadmapsPublished by Springer Nature ,2005
- On Delaying Collision Checking in PRM Planning: Application to Multi-Robot CoordinationThe International Journal of Robotics Research, 2002
- A Polylogarithmic Approximation Algorithm for the Group Steiner Tree ProblemJournal of Algorithms, 2000
- A Practical Approach to Near Time-Optimal Inspection-Task-Sequence Planning for Two Cooperative Industrial Robot ArmsThe International Journal of Robotics Research, 1998
- Sparsification—a technique for speeding up dynamic graph algorithmsJournal of the ACM, 1997
- Probabilistic roadmaps for path planning in high-dimensional configuration spacesIEEE Transactions on Robotics and Automation, 1996
- Optimal robot plant planning using the minimum-time criterionIEEE Journal on Robotics and Automation, 1988
- Data Structures for On-Line Updating of Minimum Spanning Trees, with ApplicationsSIAM Journal on Computing, 1985
- The Euclidean travelling salesman problem is NP-completeTheoretical Computer Science, 1977