Classic and Heuristic Approaches in Robot Motion Planning A Chronological Review
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.
[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.
[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.
@article{"International Journal of Mechanical, Industrial and Aerospace Sciences:59357", author = "Ellips Masehian and Davoud Sedighizadeh", title = "Classic and Heuristic Approaches in Robot Motion Planning A Chronological Review ", 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.", volume = "1", number = "5", pages = "250-6", }
