Comparing the efficiency of five algorithms applied to path planning for industrial robots

This article is (c) Emerald Group Publishing and permission has been granted for this version to appear here https://riunet.upv.es/. Emerald does not grant permission for this article to be further copied/distributed or hosted elsewhere without the express permission from Emerald Group Publishing Limited.Purpose The purpose of this paper is to compare the quality and efficiency of five methods for solving the path planning problem of industrial robots in complex environments. Design/methodology/approach In total, five methods are presented for solving the path planning problem and certain working parameters have been monitored using each method. These working parameters are the distance travelled by the robot and the computational time needed to find a solution. A comparison of results has been analyzed. Findings After this study, it could be easy to know which of the proposed methods is most suitable for application in each case, depending on the parameter the user wants to optimize. The findings have been summarized in the conclusion section. Research limitations/implications The five techniques which have been developed yield good results in general. Practical implications The algorithms introduced are able to solve the path planning problem for any industrial robot working with obstacles. Social implications The path planning algorithms help robots perform their tasks in a more efficient way because the path followed has been optimized and therefore they help human beings work together with the robots in order to obtain the best results from them. Originality/value The paper shows which algorithm offers the best results, depending on the example the user has to solve and the parameter to be optimized.Rubio Montoya, FJ.; Abu-Dakka, FJM.; Valero Chuliá, FJ.; Mata Amela, V. (2012). Comparing the efficiency of five algorithms applied to path planning for industrial robots. Industrial Robot: An International Journal. 39(6):580-591. doi:10.1108/01439911211268787580591396Brooks, R. A. (1983). Solving the find-path problem by good representation of free space. IEEE Transactions on Systems, Man, and Cybernetics, SMC-13(2), 190-197. doi:10.1109/tsmc.1983.6313112Brooks, R.A. and Lozano‐Pérez, T. (1983), “A subdivision algorithm configuration space for findpath with rotation”,International Joint Conference on Artificial Intelligence, pp. 799‐806.Davidor, Y. (1991), “Genetic algorithms and robotics, a heuristic strategy for optimisation”,World Scientific Series and Automated Systems, Vol. 1.Dubowsky, S. and Shiller, Z. (1984), “Optimal dynamic trajectories for robotic manipulators”,Fifth CISM‐IFToMM Symposium on Theory and Practice of Robots and Manipulators, Udine, Italy, pp. 96‐103.Fares, A.D., Valero, F., Mata, V. and Assad, I.F.I. (2007), “Path planning optimization of industrial robots using genetic algorithm”,Proceedings of 16th International Workshop on Robotics in Alpe‐Adria‐Danube Region, Liubliana, p. 104.Hsu, D., Kindel, R., Latombe, J.-C., & Rock, S. (2002). Randomized Kinodynamic Motion Planning with Moving Obstacles. The International Journal of Robotics Research, 21(3), 233-255. doi:10.1177/027836402320556421Isto, P. (1996), “Path planning by multiheuristic search via subgoals”,Proceedings of the 27th International Symposium on Industrial Robots, CEU, pp. 712‐26.Kavraki, L. E., Svestka, P., Latombe, J.-C., & Overmars, M. H. (1996). Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Transactions on Robotics and Automation, 12(4), 566-580. doi:10.1109/70.508439Khatib, O. (1985), “Real‐time obstacle avoidance for manipulators and mobile robots”,IEEE International Conference on Robotics and Automation, St Louis, MO, USA, pp. 500‐5.LaValle, S. M., & Hutchinson, S. A. (s. f.). Optimal motion planning for multiple robots having independent goals. Proceedings of IEEE International Conference on Robotics and Automation. doi:10.1109/robot.1996.506594Lozano-Perez. (1983). Spatial Planning: A Configuration Space Approach. IEEE Transactions on Computers, C-32(2), 108-120. doi:10.1109/tc.1983.1676196Monteiro, D. C., & Madrid, M. K. (1999). Planning of robot trajectories with genetic algorithms. Proceedings of the First Workshop on Robot Motion and Control. RoMoCo’99 (Cat. No.99EX353). doi:10.1109/romoco.1999.791079Hart, P., Nilsson, N., & Raphael, B. (1968). A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100-107. doi:10.1109/tssc.1968.300136Ó’Dúnlaing, C., & Yap, C. K. (1985). A «retraction» method for planning the motion of a disc. Journal of Algorithms, 6(1), 104-111. doi:10.1016/0196-6774(85)90021-5Rubio, F., Valero, F., Sunyer, J., & Mata, V. (2009). Direct step‐by‐step method for industrial robot path planning. Industrial Robot: An International Journal, 36(6), 594-607. doi:10.1108/01439910910994669Schwartz, J. T., & Sharir, M. (1983). On the «piano movers» problem. II. General techniques for computing topological properties of real algebraic manifolds. Advances in Applied Mathematics, 4(3), 298-351. doi:10.1016/0196-8858(83)90014-3Valero, F., Mata, V., Cuadrado, J. I., & Ceccarelli, M. (1996). A formulation for path planning of manipulators in complex environments by using adjacent configurations. Advanced Robotics, 11(1), 33-56. doi:10.1163/156855397x00038Yang, Z.Q., Liu, L.B. and Yang, W.D. (2008), “Flexible inspection path planning based on adaptive genetic algorithm”,Proceedings of Control and Decision Conference, China, pp. 1558‐63