Classic and Heuristic Approaches in Robot Motion Planning A Chronological Review

Authors: Ellips Masehian, Davoud Sedighizadeh

Abstract:

This paper reviews the major contributions to the Motion Planning (MP) field throughout a 35-year period, from classic approaches to heuristic algorithms. Due to the NP-Hardness of the MP problem, heuristic methods have outperformed the classic approaches and have gained wide popularity. After surveying around 1400 papers in the field, the amount of existing works for each method is identified and classified. Especially, the history and applications of numerous heuristic methods in MP is investigated. The paper concludes with comparative tables and graphs demonstrating the frequency of each MP method's application, and so can be used as a guideline for MP researchers.

Keywords: Robot motion planning, Heuristic algorithms.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1074972

References:

[1] Antonelli, G.; Chiaverini, S. and Fusco, G.; "A Fuzzy-Logic-Based Approach for Mobile Robot Path Tracking", IEEE Trans. Fuzzy Sys. Vol. 15, Issue 2, (2007) pp. 211-221.
[2] Aoki, T.; Matsuno, M.; Suzuki, T. and Okuma, S. "Motion planning for multiple obstacles avoidance of autonomous mobile robot using hierarchical fuzzy rules", IEEE Int. Conf. on MFI '94. (1994) pp. 265 - 271.
[3] Araujo; "Prune-able Fuzzy ART Neural Architecture for Robot Map Learning and Navigation in Dynamic Environments", IEEE Trans. Neural Networks, Vol. 7, No. 5, (2006), pp. 1235-1249.
[4] Asano, T., Asano, T, Guibas, L., Hershberger, J., and Imai, H. "Visibility-polygon search and Euclidean shortest path", 26th Symp. Found. Comp. Science (1985) pp. 155-164.
[5] Blackowiak, A. D.; Rajan, S. D.; "Multi-path arrival estimates using simulated annealing: application to crosshole tomography experiment", IEEE J. Oceanic Eng. Vol. 20, No. 3, (1995) pp. 157 - 165.
[6] Canny, J. F. "A new algebraic method for robot motion planning and real geometry" Proc. 28th IEEE Annual Symp. On Found. of Computer Science,(1987), pp. 39-48.
[7] Canny, J. F. "The Complexity of Robot Motion Planning". (1988), MIT Press, Cambridge, Mass.
[8] Canny, J. F., "A Voronoi method for the piano-movers problem". Proc. IEEE ICRA (1985).
[9] Carriker, W. F.; Khosla, P. K.; Krogh, B. H.; "The use of simulated annealing to solve the mobile manipulator path planning problem", Proc. IEEE ICRA (1990), pp. 204-209.
[10] Cazangi, R. R.; von Zuben, F. J. and Figueiredo, M. F., "Evolutionary Stigmergy in Multipurpose Navigation Systems". IEEE CEC Cong. (2006) pp. 370 - 377
[11] Costa, D., Hertz, A. ., "Ants can colour graphs", J. Oper. Res. Soc. 48, (1997) pp. 295-305.
[12] Davidor, Y.; "Robot programming with a genetic algorithm" Proc. IEEE Int. Conf. on Computer Sys. & Soft. Eng. (1990) pp. 186-191.
[13] Deneubourg, J. -L.; Clip, P. -L. and Camazine, S. S., "Ants, buses and robots-self-organization of transportation systems", Proc. From Perception to Action, (1994), pp. 12-23.
[14] Doh, N. L.; Cho, N.; Lee, K.; Lee, J.; Chung, W. K. and Oh, S. R., "A Systematic Representation of Edges in Topological Maps for Mobile Robots using Wavelet Transformation", IEEE ICRA 2005, pp. 2822- 2827.
[15] Dorigo, M. and Gambardella, L. M. "Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem," IEEE Trans. in Evolutionary Comput., vol. 1, no. 1, (1997) pp. 53-56.
[16] Erickson, D.; "Non-learning artificial neural network approach to motion planning for the Pioneer robot". IEEE/IROS Vol. 1,(2003) pp. 112-117.
[17] Faverjon, B., and Tournassoud, P. "A local approach for path planning of manipulators with a high number of degrees of freedom". Proc. IEEE Int. Conf. on Robotics and Automation (1987), pp. 1152-1159.
[18] Frontzek, T.; Goerke, N.; Eckmiller, R.; "Flexible path planning for realtime applications using A*-method and neural RBF-networks",Proc. IEEEICRA,(1998) pp.1417- 1422
[19] Fukuda, T. and Kubota, N. "An intelligent robotic system based on a fuzzy approach", Proc. IEEE Vol. 87, No. 9,(1999) pp. 1448-1470.
[20] Gen, M.; Runwei C. and Dingwei W. "Genetic algorithms for solving shortest path problems", Proc. IEEE Int. Conf. on Evolutionary Comput. (1997) pp. 401 - 406.
[21] Gerke, M. and Hoyer, H. "Fuzzy collision avoidance for industrial robots" Proc. IEEE Int. Conf. Human Robot Interaction and Cooperative Robots (1995), pp. 510-517
[22] Glasius, R.; Komoda, A. and Gielen, S., C., A., M., "Neural network dynamics for path planning and obstacle avoidance". (1995) Proc. IEEE Neural Networks, pp. 125-133.
[23] Glover, F. and Laguna, M., Tabu Search, Kluwer Academic Publishers, Boston, 1997.
[24] Hamdan, M.; El-Hawary, M. E.;"A novel genetic algorithm searching approach for dynamic constrained multicast routing", Proc. IEEE/CCECE (2003) pp. 1127-1130.
[25] Heng, K. H.; Li, Q. and Wu, X. J.; "Development of a vector-based fuzzy logic approach for motion planning", Proc. IEEE Int. Conf. on Cybern. Intel. Sys.,(2004) pp. 1380-1385
[26] Hex moor, H.; Vachtsevanos, G.;"A fuzzy logic approach to robotic path planning with obstacle avoidance" Proc IEEE Int. Conf. on Decision and Control, Vol. 25, Part 1, (1986) pp. 1262-1264.
[27] Hocaoglu, C. and Sanderson, A. C.; "Planning multi-paths using speciation in genetic algorithms", Proc IEEE Int. Conf. on Evolutionary Computation,(1996) pp. 378-383.
[28] Hua-Qing M.; Jin-Hui Z.; Xi-Jing Z.; "Obstacle avoidance with multiobjective optimization by PSO in dynamic environment", Proc. Int. Conf. Machine Learning and Cybernetics, Vol. 5, (2005) pp. 2950-2956.
[29] Hwang, Y. K. and Ahuja, N. "Gross motion planning-A survey", ACM Comp. Surv., Vol. 24, No.3,(1992),pp.219-291.
[30] Janabi-Sharifi, F. and Vinke, D.; "Integration of the artificial potential field approach with simulated annealing for robot path planning" Proc. IEEE Int. Conf. on Intel. Control (1993) pp. 536 - 541.
[31] Jian, F.; MinRui, F. and ShiWei M., "RL-ART2 Neural Network Based Mobile Robot Path Planning", Proc. ISDA (2006), Vol. 2, pp. 581-585.
[32] Jing Y., "Collision identification between convex polyhedra using neural networks", IEEE Trans. on Neural Networks, (1995), Vol. (6) No. 6, pp. 1411-1419.
[33] Jones C, and Mataric M. J., "Behavior-Based Co-ordination in Multi- Robot Systems", Autonomous Mobile Robots: Sensing, Control, Decision-Making, and Applications, Sam S. Ge and Frank L. Lewis, eds., Marcel Dekker, Inc., 2005.
[34] Keil, J. M., and Sack, J, R., "Minimum decomposition of polygonal objects" Comp. Geom. (1985), pp. 197-216.
[35] Kennedy J. and Eberhart, R. C. "Particle swarm optimization", Proc. IEEE Int. Conf. on Neural Networks, (1995) pp. 1942-1948.
[36] Khatib, O. "Real-Time Obstacle Avoidance for Manipulators and Mobile Robots", Int. J. of Robotics Research (1986), Vol. 5, No. 1, pp. 90-99.
[37] Kozakiewicz, C., Ejiri, M. "Neural network approach to path planning for two dimensional robot motion". Proc. IEEE/RSJ (IROS '91) vol. 2 (1991) pp. 818 - 823
[38] Kumar Pratihar, D.; Deb, K.; Ghosh, A. "Fuzzy-genetic algorithms and mobile robot navigation among static obstacles" In Proc. CEC'99, Vol. 1, 1999.
[39] Kun H. W.; Chin H. C. and Jiann D. L.; "A cache-genetic-based modular fuzzy neural network for robot path planning", Proc. IEEE Int. Conf. on Systems, Man, and Cybernetics,Vol4, (1996) pp. 3089 - 3094.
[40] Latombe, J. C. "Robot Motion Planning", Kluwer Academic Publishers, Boston\ Dordrecht\London. (1991)
[41] Li W.; Yushu L.; Hongbin D. and Yuanqing X.; "Obstacle-avoidance Path Planning for Soccer Robots Using Particle Swarm Optimization", Proc. IEEE Int. Conf. on Rob. and Biomimetics (ROBIO '06). (2006) pp. 1233- 1238.
[42] Lozano-Perez, T, and Wesley, M A. "An algorithm for planning collision-free paths among polyhedral obstacles". Commune. ACM 22, (1979) pp. 560-570.
[43] Makino, T.; Yokoi, H. and Kakazu, Y. "Development of a motion planning system for an agricultural mobile robot" Proc. SICE Annual(1999) pp. 959 - 962.
[44] Makita, Y.; Hagiwara, M. and Nakagawa, M.; "A simple path planning system using fuzzy rules and a potential field", Proc. IEEE World Cong. Comput. Intel.,(1994) pp. 994-999.
[45] Manousakis, K.; McAuley, T.; Morera, R. and Baras, J. "Using multiobjective domain optimization for routing" Proc. Int. Conf. hierarchical networks; Wireless Networks, Commun. and Mobile Computing (2005), pp. 1460-1465.
[46] Masehian, E, and Amin Naseri, M. R. "A Voronoi diagram-visibility graph-potential field compound algorithm for robot path planning", J. Rob. Sys. Vol. 21, No6, (2004), pp. 275-300
[47] Masehian, E, and Amin Naseri, M. R. "A Tabu Search based Approach for Online Motion Planning", IEEE Int. Conf. Industrial Tech. (2006), Mumbai, India.
[48] Wang, M and Liu, J. N. K., "Fuzzy logic based robot path planning in unknown environment", Proc. Int. Conf. Machine Learning & Cybernetics (2005), pp. 813-818.
[49] Mohamad, M. M.; Dunnigan, M. W. and Taylor, N. K.; "Ant Colony Robot Motion Planning" Proc. Int. Conf. on EUROCON'05. Vol. 1, (2005) pp. 213 - 216.
[50] Mohamad, M. M.; Taylor, N. K. and Dunnigan, M. W.; "Articulated Robot Motion Planning Using Ant Colony" Proc. IEEE Int. Conf. Optimization. Intel. Sys.(2006), pp. 690-695.
[51] Na Lv and Zuren F.; "Numerical Potential Field and Ant Colony Optimization Based Path Planning in Dynamic Environment", IEEE WCICA'06, vol. 2, (2006) pp.8966-8970.
[52] Pai, D. K. and Reissell, L. -M.; "Multiresolution rough terrain motion planning", IEEE Trans. on Rob. and Aut. Vol. 14, No. 1, (1998) pp. 19- 33.
[53] Park, M. G. and Lee, M. C. "Experimental evaluation of robot path planning by artificial potential field approach with simulated annealing", Proc. SICE (2002) Vol.4, pp. 2190-2195.
[54] Parker, J. K.; Khoogar, A. R. and Goldberg, D. E. "Inverse kinematics of redundant robots using genetic algorithms" Proc. IEEE ICRA, Vol. 1, (1989), pp. 271-276.
[55] Payeur, P.; Le-Huy, H. and Gosselin, C. "Robot path planning using neural networks and fuzzy logic" In Proc. IECON '94, Vol. 2, (1994) pp. 800 -805.
[56] Qidan Z.; Yongjie Y. and Zhuoyi X. "Robot Path Planning Based on Artificial Potential Field Approach with Simulated Annealing" Proc. ISDA'06, (2006) pp. 622-627.
[57] Qing L.; Xinhai T.; Sijiang X. and Yingchun Z.; "Optimum Path Planning for Mobile Robots Based on a Hybrid Genetic Algorithm" In Proc. HIS'06. (2006) pp. 53-58
[58] Qingfu Z.; Jianyong S.; Gaoxi X. and Edward T.; "Evolutionary Algorithms Refining a Heuristic: A Hybrid Method for Shared-Path Protections in WDM Networks Under SRLG Constraints", IEEE Trans. on Systems, Man and Cybernetics, Part B, vol. 37, No. 1, (2007) pp. 51- 61.
[59] Ramakrishnan, R. and Zein-Sabatto, S.; "Multiple path planning for a group of mobile robot in a 2-D environment using genetic algorithms" In Proc. Of the IEEE Int. Conf. on SoutheastCon'01, (2001) pp. 65-71.
[60] Sadati, N. and Taheri, J.; "Solving robot motion planning problem using Hopfield neural network in a fuzzified environment" Proc. IEEE/FUZZ.,Vol.2, (2002) pp.1144-1149
[61] Santos, V.; Goncalves, J. G. M. and Vaz, F.; "Perception maps for the local navigation of a mobile robot: a neural network approach" Proc. IEEE Int. Conf. on Rob. and Aut., vol. 3 (1994) pp. 2193-2198.
[62] Saska, M.; Macas, M.; Preucil, L. and Lhotska, L. "Robot Path Planning using Particle Swarm Optimization of Ferguson Splines", Proc. IEEE/ETFA '06, (2006) pp. 833-839.
[63] Sethian, J. A., "Level Set Methods: Evolving Interfaces" in Geometry, Fluid Mechanics, Computer Vision, and Materials Science, Cambridge University Press. (1996)
[64] Shibata, T.; and Fukuda, T., "Coordinative behavior by genetic algorithm and fuzzy in evolutionary multi-agent system" Proc. IEEE/ ICRA'93 (1993), pp. 760-765.
[65] Shibata, T. and Fukuda, T. "Intelligent motion planning by genetic algorithm with fuzzy critic" Proc. IEEE Int. Conf. on Intel. Control, (1993) pp. 565 - 570.
[66] Shirong Liu; Linbo Mao and Jinshou Yu; "Path Planning Based on Ant Colony Algorithm and Distributed Local Navigation for Multi-Robot Systems" Proc. IEEE Int. Conf. on Mechatronics and Automation,(2006) pp. 1733 - 1738.
[67] Skewis, T. and Lumelsky V. "Experiments with a mobile robot operating in a cluttered unknown environment", Proc. IEEE Int. Conf. Rob. Aut. (1992), pp. 1482-1481.
[68] Solano, J. and Jones, D. I.; "Generation of collision-free paths, a genetic approach", IEEE Colloquium on Gen. Alg. for Control Sys. Eng. (1993) pp. 5/1-5/6.
[69] Stilman, B., "Network Languages for Complex Systems", Int J. Computers & Mathematics with Applications, Vol. 26, No. 8,( 1993) pp. 51-80.
[70] Walker, K. and Esterline, A. C.; "Fuzzy motion planning using the Takagi-Sugeno method" Proc. IEEE Southeast. (2000) pp. 56 - 59.
[71] Wilson, L. A.; Moore, M. D.; Picarazzi, J. P. and Miquel, S. D. S.; "Parallel genetic algorithm for search and constrained multi-objective optimization" Proc. Parallel and Distributed Processing Symp., (2004). pp. 165.
[72] Xianyi Y. and Meng, M.; "A neural network approach to real-time motion planning and control of robot manipulators" Proc. IEEE/ SMC, vol. 4,(1999) pp. 674-679.
[73] Xiaoping F. Xiong L. Sheng Y. Shengyue Y. and Heng Z.; "Optimal path planning for mobile robots based on intensified ant colony optimization algorithm" Proc. IEEE on Rob. Intel. Sys. & Sig. Processing, Vol. 1 (2003) pp.131-136.
[74] Xin C. and Yangmin L.; "Smooth Path Planning of a Mobile Robot Using Stochastic Particle Swarm Optimization" Proc. IEEE on Mechatronics and Aut., (2006) pp. 1722-1727.
[75] Xu, J. -X. and Kin, K. C.; "Intelligent mobile robot path planning with fuzzy system approaches" Proc. IEEE Int. Workshop on Emerging Tech. and Fact. Aut.,(1993) pp. 28-41.
[76] Ying-Tung H.; Cheng-Long C. and Cheng-Chih C.; "Ant colony optimization for best path planning" Proc. IEEE/ISCIT'04, Vol.,(2004) pp. 109-113.
[77] Yuan-Qing Q.; De-Bao S.; Ning L. and Yi-Gang C.; Path planning for mobile robot using the particle swarm optimization with mutation operator Proc. Int. Conf. on Machine Learning and Cybernetics, (2004) pp. 2473 - 2478.
[78] Zacksenhouse, M.; DeFigueiredo, R. J. P. and Johnson, D. H.,"A neural network architecture for cue-based motion planning". Proc. IEEE Int. Conf. on Decision and Control,(1988) pp. 324 - 327.
[79] Zein-Sabatto, S. and Ramakrishnan, R.; "Multiple path planning for a group of mobile robots in a 3D environment using genetic algorithms" Proc. IEEE Southeast,(2002), pp. 359-363
[80] Zelinsky, A. "Using path transforms to guide the search for find path in 2D", Int. J. Rob. Res, 1994,(13)4, pp. 315-325.
[81] Zhu, A. and Yang, S. X.;"A Neural Network Approach to Dynamic Task Assignment of Multirobots" IEEE Trans. Neural Networks, Vol. 17, No. 5,(2006) pp. 1278-1287.
[82] Zhu, D. and Latombe, J. C. "New heuristic Algorithms for efficient hierarchical path planning", IEEE Trans. on Rob. & Auto. Vol. 7, No. 1, (1991), pp. 9-20.