Abstract
In this paper, a hierarchical evolutionary algorithm is proposed for the path planning of manipulators. The proposed algorithm consists of a global path planner (GPP) and a local motion planner (LMP). The global planner, a MAKLINK based approach, plans a trajectory for a robot end-effector from a starting free-space to goal free-space. An evolutionary algorithm with a non-random initial population is adopted to plan the manipulator configurations along a path given by the former stage. Once the optimal configuration is obtained by the evolutionary algorithm, the optimal chromosomes will be reserved as the initial population. Since the initial population is non-random, the evolution is more efficient and the planned path is smoother than traditional GA. Simulation results show that the proposed algorithm works well, specifically in terms of collision avoidance and computation efficiency.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Reif, J.H.: Complexity of the mover’s problem and generalizations. In: Proceedings of Foundations of Computer Science, pp. 421–427 (1979)
Habib, M.K., Asama, H.: Efficient method to generate collision Free paths for an autonomous mobile robot based on new Free space structuring approach. In: Proceedings of IEEE/RSJ International Workshop on Intelligent Robots and Systems, vol. 2, pp. 563–567 (1991)
Lozano-Perez, T., Wesley, M.A.: An Algorithm for planning collision-Free paths among polyhedral obstacles. Communications of the ACM 22, 560–570 (1979)
Lozano-Perez, T.: Spatial Planning: a configuration space approach. IEEE Transactions on Computers C-32, 108–120 (1983)
Kavraki, L.E., Svestka, P., Latombe, J.C., Overmars, M.H.: Probabilistic Roadmap for path planning in high-dimensional configuration spaces. IEEE Transactions on Robotics & Automation 12(4), 566–580 (1996)
Lozano-Perez, T.: A simple motion-planning algorithm for general robot manipulator. IEEE Journal of Robotics and Automation 3(3), 224–238 (1987)
LaValle, S.M.: Rapidly-exploring random tree: A new tool for path planning. Technology Report, no. 98–11 (1998)
Kuffner, J.J., LaValle, S.M.: RRT-connect: An efficient approach to single-query path planning. In: Proceedings of. IEEE International Conference on Robotics and Automation, pp. 995–1001 (2000)
Laliberte, T., Gosselin, C.: Efficient algorithms for the trajectory planning for redundant manipulators with obstacle avoidance. In: Proceedings of IEEE International Conference on Robotics and Automation, vol. 3, pp. 2044–2049 (1994)
Ralli, E., Hirzinger, G.: Fast path planning for robot manipulators using numerical potential fields in the configuration space. In: Proceedings of the IEEE/RSJ/GI Intl. Conf. on Intelligent Robots and Systems, Advanced Robotic System and the Real World, vol. 3, pp. 1922–1929 (1994)
Barraquand, J., Lotombe, J.C.: Robot motion planning: a distributed representation approach. International Journal of Robotics Research 10(6), 628–649 (1991)
Khatib, O.: Real-time obstacle avoidance for manipulators and mobile robots. International Journal of Robotics Research 5(1), 90–98 (1986)
Latombe, J.C.: Motion planning: A journey of robots, molecules, digital actors, and other artifacts. International Journal of Robotics Research 18(11), 1119–1128 (1999)
Barraquand, J., Langois, B., Latombe, J.C.: Numerical potential field techniques for robot path planning. IEEE Transactions on Robotics and Automation 22, 224–241 (1992)
Masoud, A.A., Bayoumi, M.M.: Intercepting a maneuvering target in a multidimensional stationary environment using a ware equation potential field strategy. In: IEEE International Symposium on Intelligent Control, pp. 243–248 (1994)
Chuang, J.-H., Lin, C.-C., Hsieh, C.-T.: A Potential-Based Path Planning of Articulated Robots with 2-DOF joints. In: Proceedings of the IEEE International Conference on Robotics and Automation, pp. 1827–1832 (2005)
Lin, C.-C., Pan, C.-C., Chuang, J.-H.: A Novel Potential-Based Path Planning of 3-D Articulated Robots with Moving Bases. Robotica 22(4), 359–367 (2004)
Chuang, J.-H., Lin, C.-C., Kuo, L.-W.: Potential-Based Path Planning for Robot Manipulators. In: Proceeding of IEEE International Conference on Method and Models in Automation and Robotics, pp. 1031–1036 (2002)
Lin, C.-C., Chuang, J.-H.: Potential-Based Path Planning for Robot Manipulators in 3D Workspace. In: Proceedings of. IEEE International Conference on Robotic and Automation, pp. 3353–3358 (2003)
Lin, C.-C., Pan, C.-C., Chuang, J.-H.: A Novel Potential-Based Path Planning of 3-D Articulated Robots with Moving Bases. In: Proceedings of IEEE International Conference on Robotic and Automation, pp. 3365–3370 (2004)
Chuang, J.-H.: Potential-Based Modeling of Three-Dimensional Workspace for Obstacle Avoidance. IEEE Transactions on Robotics and Automation 14(5), 778–785 (1998)
Brooks, R., Lozano-Perez, T.: A subdivision algorithm in configuration space for findpath with rotation. IEEE Transcations on System, Man & Cybernetics 15(2), 224–233 (1985)
Aron, O., Lozano-Perez, T.: Visible Decomposition: Real-Time path Planning in Large Planar Environments. AI Memo 1638 (1996)
Solterio-Pires, E.J., Tenrerio-Machado, J.A.: A trajectory planner for manipulators using genetic algorithm. In: Proceedings of the IEEE International Symposium on Assembly and Task Planning, pp. 163–168 (1999)
Parker, J.K., Khoogar, A.R., Goldberg, D.E.: Inverse Kinematics of redundant robots using genetic algorithms. In: Proceedings of IEEE International Conference on Robotics and Automation, pp. 271–276 (1989)
Khoogar, A.R., Parker, J.K.: Obstacle avoidance of redundant manipulators using genetic algorithms. In: Proceedings of IEEE International Conference on Robotic and Automation, pp. 317–320 (1991)
Chen, H., Du, X., Gu, W.-K.: Global Path Planning Based on Neural Network and Genetic Algorithm in a Static Environment. Artificial Neural Networks, 34–42 (2004)
Gill, M., Zomaya, A.: A parallel collision-avoidance algorithm for robot manipulators. IEEE Concurrency 6(1), 68–78 (1998)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Lin, CC. (2009). An Evolutionary Algorithm with Non-random Initial Population for Path Planning of Manipulators. In: Chien, BC., Hong, TP., Chen, SM., Ali, M. (eds) Next-Generation Applied Intelligence. IEA/AIE 2009. Lecture Notes in Computer Science(), vol 5579. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-02568-6_20
Download citation
DOI: https://doi.org/10.1007/978-3-642-02568-6_20
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-02567-9
Online ISBN: 978-3-642-02568-6
eBook Packages: Computer ScienceComputer Science (R0)