Time-Optimal Task Scheduling for Two Robotic Manipulators Operating in a Three-Dimensional Environment

Abstract

The present paper introduces a method for determining the optimal task scheduling for a two-robot work cell. This problem is reminiscent of the classic Travelling Salesman Problem (TSP), but the measure to be optimized is the time instead of the distance. In addition, this is a much more complex problem, since it involves two robots (salesmen), which have to visit different task-points (cities) considering the multiplicity of the robots' inverse kinematics. The optimization problem addressed in this work concerns the determination of the (near-)optimum sequence of task-points that should be visited by each one of the two robots while ensuring minimum total cycle time and collision avoidance among their links. The proposed approach is based on genetic algorithms and a special encoding is used to incorporate the division of the task-points for both robots and the multiple solutions of the inverse kinematics. The method was tested in different scenarios and the experimental results demonstrated the efficiency and effectiveness of the proposed approach.

Keywords

multi-robot system scheduling optimization robotic manipulator genetic algorithms

Get full access to this article

View all access options for this article.

References

Nakamura

Advanced robotics, redundancy and optimization 1991 (Addison-Wesley, Reading, Massachusetts, USA).

Lawer

Lenstra

Kan

Rinnooy A

Shmoys

, The travelling salesman problem 1985(John Wiley, Chichester, UK).

Latombe

J. C.

Robot motion planning , 1991 (Kluwer Academic Publishers, Boston, Massachusetts, USA).

Nof

S. Y.

Drezner

The multiple-robot assembly plan problem. J. Intell. Robot. Syst. 1993, 5(1) 57–71.

Jiang

Seneviratne

L. D.

Earles

S. W. E.

Assembly scheduling for an integrated two-robot workcell. Robot. Comput. Integrated Mfg 1997, 1997, 13(2), 131–143.

Jiang

Seneviratne

L. D.

Earles

S. W. E.

Scheduling and compression for a multiple robot assembly workcell. Prod. Plann. Contr. 1998, 9(2) 143–154.

Preparata

F. P.

Shamos

M. I.

Computational geometry 1985 (Springer-Verlag Inc., New York, New York, USA).

Wurll

Henrich

Point-to-point and multi-goal path planning for industrial robots. In Special Issue on Advances in Practical Motion Planning. J. Robot. Syst. , 18(8), 445–461.

Saha

Roughgarden

Latombe

J.-C.

Sánchez-Ante

Planning tours of robotic arms among partitioned goals. Int. J. Robot. Res. , 2006, 25(3), 207–223.

10.

Goldberg

D. E.

Genetic algorithm in search, optimization and machine learning 1989 (Addison-Wesley, Reading, Massachusetts, USA).

11.

Davis

Applying adaptive algorithms to epistatic domains. In Proceedings of 9th the International Joint Conference on Artificial Intelligence, Los Angeles, CA, August 1985, pp. 162–164.

12.

Thomsen

Fogel

Krink

A clustal alignment improver using evolutionary algorithms. In Proceedings of the Fourth Congress on Evolutionary Computation - CEC1902, 2002, vol. 1, pp. 121–126.

13.

Zacharia

Aspragathos

Optimal robot task scheduling based on genetic algorithms. Robot. Comput. Integrated Mfg 2005, 21(1), 67–79.

14.

Falkenauer

Genetic algorithms and grouping problems , 1998 (John Wiley and Sons Ltd, Chichester, UK).

15.

Michalewitz

Genetic algorithms + data structures = evolution programs , edition 3, 1996 (Sprnger-Verlag Inc., New York, New York, USA).