使用经典以及启发式方法的机器人运动规划的回顾-综述
Classic and Heuristic Approaches in Robot Motion Planning – A Chronological Review
Ellips Masehian, and 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.
I.I NTRODUCTION
considerable amount of research exists in the field of Robot Motion Planning (RMP). The discipline launched at mid 60’s, but it was not until Lozano-Pérez’s revolutionary contribution [42] on spatial planning that MP drew most researchers’ attention. It is proved that the path planning problem is NP-complete [7]. The current developed classic methods are variations of a few general approaches: Roadmap, Cell Decomposition, Potential fields, and mathematical programming. Most classes of MP problems can be solved using these approaches. These approaches are not necessarily mutually exclusive, and a combination of them is often used in developing a motion planner [46]. In the roadmap approach, the free C-space, i.e., the set of feasible motions, is retracted, reduced to, or mapped onto a network of one-dimensional lines. This approach is also called the Retraction, Skeleton, or Highway approach. The search for a solution is limited to the network, and MP becomes a graph-searching problem. The well-known roadmaps are Visibility graph, Voronoi diagram, Silhouette, and the Subgoal Network. The Visibility Graph (VG) is the collection of lines in the free space that connects a feature of an object to that of another. In its principal form, these features are vertices of polygonal obstacles, and there are O(n2) edges in the visibility graph, which can be constructed in O(n2) time and space in 2D, where n is the number of features. The idea of using Visibility graph for RMP was used in [4]. The Voronoi diagram (VD) of a collection of geometric objects is a partition of space into cells, each of which consists of the points closer to one particular object Authors are with Faculty of Engineering, Tarbiat Modares University, Tehran, Iran. than any others. The idea of using Voronoi diagram for RMP was used in [8]. The other approach is Silhouette. In [6, 7], a general method of constructing a roadmap in arbitrary dimensions is presented. It projects an object in a higher dimensional space to a lower dimensional space and then traces out the boundary curves of the projection, which is called silhouette. The Subgoal Network (SN) method does not build an explicit representation of the configuration obstacles. Instead, the list of reachable configurations from the start configuration is maintained. When the goal configuration is reachable, the MP is solved. The reachability of one configuration from another is decided by a rather simple local MP algorithm called local operator, such as that moving the robot in a straight line between the configurations [17]. In Cell Decomposition (CD) Algorithm, the free C-space is decomposed into a set of simple cells, and the adjacency relationships among the cells are computed. A collision-free path between the start and the goal configuration of the robot is found by first identifying the two cells containing the start and the goal and then connecting them with a sequence of connected cells. The idea of using Cell decomposition for RMP was used in [34]. The Potential Fields (PF) concept was first introduced by Oussama Khatib [36]. A robot in Potential Fields method is treated as a point represented in configuration space as a particle under the influence of an artificial potential field U whose local variations reflect the ‘structure’ of the free space. The potential function can be defined over free space as the sum of an Attractive potential pulling the robot toward the goal configuration, and a Repulsive potential pushing the robot away from the obstacles [40]. The Mathematical programming approach represents the requirement of obstacle avoidance with a set of inequalities on the configuration parameters. MP is formulated then as a mathematical optimization problem that finds a curve between the start and goal configurations minimizing a certain scalar quantity.
A comprehensive review on Classic MP methods can be found in [29].
II.H EURISTIC M ETHODS
The abovementioned classic approaches suffer from many drawbacks, such as high time complexity in high dimensions, and trapping in local minima, which makes them inefficient in practice.In order to improve the efficiency of Classic methods, Probabilistic algorithms have been developed, including Probabilistic Roadmaps (PRM) and Rapidly-
A
exploring Random Trees (RRT), with major advantages is high-speed implementation. Also other approaches exist in RMP such as Level set [63] and Linguistic Geometry (LG) [69].To fix the local minima problem, many Heuristic and Mete-heuristic algorithms are used in RMP. For example, a combination of the Simulated Annealing (SA) technique and PF remedies this problem. Other approaches discussed in this paper include Artificial Neural Network (ANN), Genetic Algorithms (GA), Particle Swarm Optimization (PSO), Ant Colony (ACO), Stigmergy, Wavelet Theory, Fuzzy Logic (FL) and Tabu Search (TS). Heuristic algorithms do not guarantee to find a solution, but if they do, are likely to do so much faster than deterministic methods.
A. Neural Networks (NN)
The concept of using Neural Networks for RMP was first used in [78]. A novel biologically-inspired general neural network approach exists for real-time collision-free RMP in a dynamic environment [80]. This general model can be applied to point mobile robots, manipulator robots, car-like robots, and multi-robot systems. The state space of the NN is the configuration space of the robot, and the dynamically varying environment is represented by the dynamic activity landscape of the neural network. The target globally attracts the robot in whole state space, while the obstacles locally push the robot away to avoid collisions. The real-time robot motion is planned through the dynamic activity landscape of the neural network without explicitly searching over the free space or the collision-free paths, without explicitly optimizing any cost function, without any prior knowledge of the dynamic environment, without any learning process, and without any local collision checking procedures. Therefore, the model algorithm is computationally efficient [22]. In [37] an NN approach to path planning for two dimensional robot motion is developed. Also in [61] a neural network approach for the local navigation of a mobile robot via Perception maps is presented. In 1995, the collision identification between convex polyhedra using neural networks is implemented [32]. A cache-genetic-based modular fuzzy neural network is presented in [39] for robot path planning. Frontzek [18] constructed a flexible path planning method for real-time applications using A* method and Neural Radial Basis Function networks. An NN model is developed in [72] to real-time MP and control of robot manipulators. RMP problem is solved in [60] using Hopfield neural networks in a fuzzified environment. Also in 2003, a Non-learning ANN approach to MP for the Pioneer robot is extended [16]. An NN approach is presented in [81] for dynamic task assignment of multi robots. Eventually,RL-ART2 NN-based mobile robot path planning is developed in 2007 in [31].
B. Genetic Algorithms (GA)
The idea of using Genetic algorithms for RMP was first used in [54] and [12]. The application of GA to the mobile robot path planning problem requires the development of a suitable ‘chromosome’ representation of the path, a path guidance mechanism, a method to cater for obstacle avoidance, and an appropriate constraint definition providing mechanisms to minimize path distance, as well as providing smooth paths. It is assumed that the environment is static and known. For the purpose of representation the working area is discretized in bit-map form with the obstacles providing coloring to aid the obstacle avoidance [67].
In [68] a genetic approach for generation of collision-free paths is presented. In [27] an approach on the basis of GA for planning multi-paths is presented. In 1997, another approach from GA for solving shortest path problem is used [20]. A genetic-fuzzy algorithm is introduced in [38] for mobile robot navigation among static obstacles. A multiple path planning for a group of mobile robots in a 2D environment using GA is developed in [59]. Zein-Sabatto constructed a multiple path planning for a group of mobile robots in a 3D environment using GA [79]. A novel GA searching approach for dynamic constrained multicast routing is developed in [24]. Also in [71], a Parallel GA is used for search and constrained multi-objective optimization. An optimum path planning for mobile robots based on a Hybrid GA has been extended in [57]. Finally,A hybrid method for shared-path protections in WDM Networks under SRLG constraints has been developed in [58].
C.Simulated Annealing (SA)
The notion of using Simulated Annealing for RMP was initiated in [9]. The SA algorithm was first proposed by Metropolis and Kirkpatrick and Cemy modified the original algorithm by letting the temperature decrease to zero. In the SA approach at each step, a new solution x' for the candidate of next position is chosen randomly from a set of neighbors of the current solution x. The new solution is accepted unconditionally if the new position has lower potential energy, U(x') ≤U(x), or else with (uphill move) probability of e–Δ/T, where Δ =U(x') ?U(x). Here U is the cost function (i.e. potential function), and T denotes the temperature. If x' is not accepted, the algorithm proceeds to the next step and the temperature is decreased by cooling rate r. This is repeated until a small value near zero is reached or escape from the local minimum has occurred.
In [30] the PF approach was integrated with SA to escape from local minima. A multi-path arrival estimates using SA is introduced in [5]. The experimental evaluation of robot path planning by PF approach with SA is presented in [53]. Manousakis constructed an algorithm using multi-objective domain optimization and SA for routing in hierarchical networks. [46]. Finally, A robot path planning based on PF approach with SA is developed in 2006 in [56].
D. Ant Colony Optimization (ACO)
The first instance of the application of Ant Colony Optimization in RMP is the work [13]. An approach to RMP exists by applying Ant Colony Optimization with the PRM. The PRM is a path planning method that consists of capturing the connectivity of the robot’s free space in a network called the Roadmap. An Ant Colony RMP (ACRMP) method is proposed that takes the benefit of collective behavior of ants foraging from a nest to a food source. Two groups of ants are placed at both the nest and food sources respectively. A number of ants (agents) are released from the nest (start configuration) and begin to forage (search) towards the food (goal configuration). Each ant has a certain quantity of pheromone to be dropped along the path. The ants track down the pheromone trails previously dropped by the nest's ants to
accomplish the path between the two points of nest and food respectively. Results from preliminary tests show that the ACRMP is capable of reducing the intermediate configuration between the initial and goal configuration in an acceptable running time [15].
In [73] an optimal path planning for mobile robots based on intensified ACO algorithm is developed. Also in 2004, ACO was used to plan the best path [76]. ACRMP is presented in [49]. An articulated RMP using ACO is introduced in [50]. Also, a path planning based on ACO and distributed local navigation for multi robot systems is developed in [66]. Finally, an approach based on Numerical PF and ACO is introduced in [51] to path planning in dynamic environment. E. Particle Swarm Optimization (PSO)
Particle Swarm Optimization (PSO) was invented by Kennedy and Eberhart in 1995 while attempting to simulate the choreographed, graceful motion of swarms of birds as part of a sociocognitive study investigating the notion of “collective intelligence” in biological populations. In PSO, a set of randomly generated solutions (initial swarm) propagates in the design space towards the optimal solution over a number of iterations (moves) based on large amount of information about the design space that is assimilated and shared by all members of the swarm. PSO is inspired by the ability of flocks of birds, schools of fish, and herds of animals to adapt to their environment, find rich sources of food, and avoid predators by implementing an “information sharing” approach, hence, developing an evolutionary advantage [35].
An algorithm for path planning for mobile robot using PSO with mutation operator is developed in [77]. In 2005, an approach for obstacle avoidance with multi-objective optimization by PSO in dynamic environment is presented in [28]. Also, an algorithm is developed in [62] for robot path planning using PSO of Ferguson Splines. Obstacle avoidance path planning for soccer robots using PSO has been extended in [41]. Finally, a smooth path planning of a mobile robot using Stochastic PSO is implemented in [74].
F. Stigmergy
The concept of Stigmergy was introduced by Pierre-Paul Grasse in the 1950's to describe the indirect communication taking place among individuals in social insect societies. Stigmergy was originally defined by Grasse in his studies on the reconstruction of termite nests. He showed that the regulation and coordination of the building activity do not depend on the workers themselves but is mainly achieved by the nest: a stimulating configuration triggers a response of a termite worker, transforming the configuration into another configuration that may trigger in turn another, possibly different, action performed by the same termite or any other worker in the colony [11].
Through the careful design of robot sensing, actuation, and control features, it is possible to utilize the concept of Stigmergy in task-directed MRS. This powerful mechanism of coordination is attractive as it typically requires minimal capabilities of the individual robots. The robots do not require direct communication, unique recognition of other robots or even distinguishing other robots from miscellaneous objects in the environment, or the performance of computationally intensive reasoning or planning [33]. Recently an Evolutionary Stigmergy is introduced in [10] for multipurpose navigation systems.
G. Wavelets
A new approach exists for mobile robot path planning on natural rough terrains. This approach computes a multiresolution representation of the terrain using wavelets, and hierarchically plans the path through sections which are relatively smooth and well approximated on coarser levels. Unlike most methods, the hierarchical approximation errors are used explicitly in a cost function to distinguish preferred terrain sections. The error is computed using the corresponding wavelet coefficients. There is also a new non-scalar path cost measure based on the sorted terrain costs along the path. This measure can be incorporated into standard global path search algorithms and yields paths which avoid high cost terrain areas when possible. Additional constraints for specific robots can be integrated into this approach for efficient hierarchical MP on rough terrain [82]. A multiresolution rough terrain planning is presented in [52]. Finally, a systematic representation of edges in topological maps for mobile robots using wavelet transformation is developed in [14].
H.Tabu Search (TS)
Tabu Search approach is one of the meta-heuristic approaches that can be used in routing and RMP. This algorithm does not suffer from the local minimum problem. In fact, it counts the number of times that a specific move is repeated, and determines the weights of moves, and lists them in a table as a guide to the path planning [23]. In [43] a TS-based planner for an agricultural mobile robot is developed. Also, in [47] an online motion planner is developed to govern the movements of mobile robots during their explorations. By using the TS, a set of tabu (i.e. forbidden) moves are defined at each iteration of the search to confine the robot’s navigable locations, and guide it toward the goal. Based on range-sensor readings and the cost function value defined for each ray, the robot is attracted to certain obstacle vertices, and moves along a path consisted of lines connecting the vertices of different obstacles. The planner also takes advantage of random moves when trapped in dead-ends. Different experiments have shown the efficiency of this approach.
I. Fuzzy Logic (FL)
The idea of using fuzzy logic for RMP was first used in [26]. Fuzzy MP using the Takagi-Sugeno method is presented in [70]. Also, an intelligent MP by GA with fuzzy critic is developed in [65]. An algorithm on the basis of GA and fuzzy in evolutionary multi-agent system for the purpose of coordinative behavior is developed in [67], and an intelligent mobile robot path planning with fuzzy system approach is presented in [75]. In 1994, an MP algorithm is presented in [2] for multiple obstacle avoidance of autonomous mobile robots using hierarchical fuzzy rules. A simple path planning system using fuzzy rules and a PF is extended in [44]. An algorithm on the basis of NN and FL for RMP is developed in [58]. Moreover, an approach on the basis on FL is introduced in
[21] to collision avoidance for industrial robots. A cache-genetic-based modular fuzzy NN for robot path planning is improved in [39]. An intelligent robotic system based on a fuzzy approach is presented in [19]. The RMP problem is solved in [60] using Hopfield NN in a fuzzified environment. In 2004, a vector-based FL approach for motion planning is developed in [25]. An approach on the basis of FL is introduced in [48] for unknown environments. A Prune-able fuzzy ART neural architecture for robot map learning and navigation in dynamic environments is developed in [3]. Lately, a Fuzzy-Logic-Based approach for mobile robot path tracking is demonstrated in [1].
III. C ONCLUSION
A total of 1381 papers were surveyed in this research,
covering a sufficient depth of works in the RMP field for the time span of 1973 to 2007. We have tried to bring together the major applications of heuristic techniques in the literature and come to conclusions about the nature and the course of research in motion planning discipline. The survey reveals that from 1973 to 1982, all papers are within the realms of Classic (non-heuristic) approaches. Between 1983 and 1987 only about 3% of papers dealt with heuristic algorithms. The proportion of heuristic/classic methods however grew to 1/6
for 1988 to 1992, increased to about 1 for 1993 to 1997 and raised further to 1.17 from 1998 up till now. Fig. 1 shows these results for 5-year periods.
Fig. 1 Application of classic and heuristic algorithms
In total, from the emergence of RMP disciple in 1973 about 53.84 % of papers are related to classic algorithms and 46.16% to heuristic approaches. Table I shows the portions of surveyed major methods in detail.
TABLE I
A C OMPARISON OF M AJOR RMP A LGORITHMS
Five year periods ( from 1973 up to now)
Total 03-07
98-02 93-97 88-92 83-87 78-82 73-77 Approach 14.49 4.97 6.73
11.41 49.30 60.94 70.00 100 C-Space 6.88 7.46 6.14 7.05 6.34 4.69 20.00 0 VD 4.93 4.02 2.92 7.38 6.34 9.38 0 0 VG 0.80 0.38 0.88 0.34 2.11 3.13 0 0 Silhouette 0.80 0.57 0.29 1.34 1.41 1.56 0 0 SN 2.90 2.68 3.51 3.36 2.11 1.56 0 0 B-Spline 1.52
0.96
1.46
2.01 2.11
3.13 0 0 CD
11.30 11.09 11.40 9.40 16.20 10.94 10 0 PF 4.93 8.22 6.73 0.67 0.00 0.00 0 0 PRM 1.81 4.02 1.17 0.00 0.00 0.00 0 0 RRT 1.59 0.00 1.75 5.37 0.00 0.00 0 0 LG 1.88 1.72 3.51 1.34 0.00 1.56 0 0 Level Set 15.87 13.77 23.68 18.12 8.45 0.00 0 0 ANN 15.94 20.08 17.25 17.45 2.82 0.00 0 0 GA 1.09 1.15 0.58 2.01 0.70 0.00 0 0 SA 0.94 2.29 0.29 0.00 0.00 0.00 0 0 PSO 2.83 5.73 2.05 0.67 0.00 0.00 0 0 ACO 1.09 1.91 0.88 0.67 0.00 0.00 0 0 Stigmergy 0.72 0.95 0.88 0.34 0.70 0.00 0 0 Wavelet 7.69 8.03 7.90 11.07 1.41 3.11 0 0 FL 100
100
100
100
100
100
100
100
Total
Table I also shows what methods have been applied relatively less, and therefore need more research. As it is illustrated in Fig. 1, the application of heuristic methods has increased due to their success in coping with the problems of combinatorial explosion and local minima. Table II provides a more detailed analysis on the heuristic methods and their relative application in RMP.
TABLE II
H EURISTIC A PPROACHES IN RMP Five year periods ( from 1983 up to now) Total
03-07 98-02 93-97 88-92 83-87 Approach 34. 3825. 5344. 2636.00 60 0 ANN 34. 5437. 2332. 2434. 67 20 0
GA
2. 35 2. 131. 094. 00 5 0 SA 2. 04 4. 260. 550. 00 0 0 PSO 6. 12 10. 64
3. 831. 33 0 0 ACO 2. 35 3. 551. 641. 33 0 0 Stigmergy 1. 57 1. 771. 640. 67 5 0 Wavelet
16. 64
14. 8914. 7522. 00 10 100 FL 100
100
100
100
100
100
Total
R EFERENCES
[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 real-
time 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 multi-
objective 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 multi-
objective 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.