×

An evolutionary and local search algorithm for motion planning of two manipulators. (English) Zbl 0983.68206

Summary: A method for obtaining coordinated motion plans of robot manipulators is presented. A decoupled planning approach has been used; that is, the problem has been decomposed into two subproblems: path planning, where a collision-free path is found for each robot independently only considering fixed obstacles, and trajectory planning, where the paths are timed and synchronized to avoid collisions with other robots. This article focuses on the second problem. The proposed plan can easily be implemented by programs written in most industrial robot programming languages. The generated programs minimize the total motion time of the robots along their paths. The method does not require accurate dynamic models of the robots and uses an evolutionary algorithm followed by a local search which produces near optimal solutions with a relatively small computational cost.

MSC:

68T40 Artificial intelligence for robotics
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Robot motion planning, Kluwer Academic Publishers, Norwell, MA, 1991. · doi:10.1007/978-1-4615-4022-9
[2] Schwartz, Int J Robotic Res 2 pp 45– (1983) · doi:10.1177/027836498300200304
[3] and Coordinated motion of two robot arms, Proc IEEE Int Conf Robotics Automat, San Francisco, 1986, pp. 1216-1223.
[4] and Optimisation of collision free strategies in multi-robot systems, ICRA ‘98, 1998, pp. 2910-2915.
[5] and On multiple moving obstacles, AI Memo 883, Artificial Intelligence Laboratory, MIT, 1986.
[6] Kant, Int J Robotics Res 5 pp 72– (1986) · doi:10.1177/027836498600500304
[7] and Planning collision free trajectories in time varying environments: a two-level hierarchy, Proc IEEE Conf Robotics and Automat, 1988, pp. 1644-1649.
[8] Motion planning in dynamic environments, Springer-Verlag, Tokyo, 1991. · doi:10.1007/978-4-431-68165-6
[9] Lee, IEEE Trans Syst Man Cybernet SMC-17 pp 21– (1987) · doi:10.1109/TSMC.1987.289330
[10] Chang, IEEE Trans Syst Man Cybernet 24 pp 517– (1994) · doi:10.1109/21.279000
[11] and Deadlock-free and collision-free coordination of two robot manipulators, Proc IEEE Int Conf Robotics Automat, 1989, pp. 484-489.
[12] Bien, IEEE Trans Robotics Automat 8 pp 414– (1992) · doi:10.1109/70.143360
[13] Lee, IEEE Trans Robotics Automat 11 pp 160– (1995) · doi:10.1109/70.345949
[14] and Agent-based control and planning of a multiple-manipulator assembly system, Proc 1999 IEEE Int Conf Robotics Automat, Detroit, 1999.
[15] and ? Coordinated motion of two robot arms for real applications,? Task and methods in applied artificial intelligence, and (Editors), Lecture Notes in Computer Science 1416, Springer-Verlag, Berlin, 1998, pp. 122-131. · doi:10.1007/3-540-64574-8_398
[16] and ? An evolutionary+local search algorithm for planning two manipulators robot,? Task and methods in applied artificial intelligence, and (Editors), Lecture Notes in Computer Science 1416, Springer-Verlag, Berlin, 1998, pp. 336-346.
[17] and Automatic motion programming of robots working in a colliding environment, Proc IMACS IEEE-SMC Multiconf Computational Eng Syst Applications, Lille (France), 1996.
[18] Adaptation in natural and artificial systems, The University of Michigan Press, Ann Arbor, 1975.
[19] Genetic algorithms in search, optimization and machine learning, Addison-Wesley, Reading, MA, 1989. · Zbl 0721.68056
[20] The design of innovation: lessons from genetic algorithms, lessons for the real world, Internal Report 98004, Illinois Genetic Algorithms Laboratory, Department of General Engineering, University of Illinois at Urbana-Champaign, Illinois, 1997.
[21] Adaptation in natural and artificial systems, University of Michigan Press, Ann Arbor, 1975.
[22] ? Incorporating problem specific knowledge into genetic algorithms,? Genetic algorithms and simulated annealing, (Editor), Morgan Kauffmann Publishers, San Francisco, 1987, pp. 42-46.
[23] and Optimization of simulation models with REMO, Proc Conf Modeling Simulation, 1994, pp. 274-281.
[24] and (Editors), Practical motion planning in robotics, Wiley, New York, 1998.
[25] Lozano-Pérez, IEEE J Robotics Automat RA-3 pp 224– (1987) · doi:10.1109/JRA.1987.1087095
[26] The genetic programming: on the programming of computers by means of natural selection, MIT Press, Cambridge, MA, 1992. · Zbl 0850.68161
[27] Robot manipulators: mathematics, programming and control, MIT Press, Cambridge, MA, 1982.
[28] Luh, ASME Trans 102 pp 142– (1981)
[29] Tondu, J Robotic Syst 11 pp 77– (1994) · doi:10.1002/rob.4620110202
[30] Kondo, IEEE Trans Robotics Automat 7 pp 267– (1991) · doi:10.1109/70.88136
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.