Open access

Meta-Heuristic Optimization Techniques and Its Applications in Robotics

Written By

Alejandra Cruz-Bernal

Submitted: 01 May 2012 Published: 30 January 2013

DOI: 10.5772/54460

From the Edited Volume

Recent Advances on Meta-Heuristics and Their Application to Real Scenarios

Edited by Javier Del Ser

Chapter metrics overview

3,798 Chapter Downloads

View Full Metrics

1. Introduction

Robotics is the science of perceiving and manipulating the physical world. Perceive information on their envioronments through sensors, and manipulate through physical forces. To do diversity tasks, robots have tobe able to accomodate the ennormous uncertainty that exist in the physical world. The level of uncertainty depends on the application domain. In some robotics applications, such as assembly lines, humans can cleverly engineer the system so that uncertainty is only a marginal factor. In contrast, robots operating in residential homes, militar operates or on other planets will have to cope with substantial uncertainty. Managing uncertainty is possibly the most important step towards robust real-world robot system.

If considerate that, for reduce the uncertainty divide the problem in two problems, where is the first is to robot perception, and another, to planning and control. Likewise, path planning is an important issue in mobile robotics. It is to find a most reasonable collision-free path a mobile robot to move from a start location to a destination in an envioroment with obstacles. This path is commonly optimal in some aspect, such as distance or time. How to find a path meeting the need of such criterion and escaping from obstacles is the key problem in path planning.

Optimization techniques are search methods, where the goal is to find a solution to an optimization problem, such that a given quantity is optimized, possibly subject to a set of constraints. Modern optimization techniques start to demonstrate their power in dealing with hard optimization problems in robotics and automation such as manufacturing cells formation, robot motion planning, worker scheduling, cell assignment, vehicle routing problem, assembly line balancing, shortest sequence planning, sensor placement, unmanned-aerial vehicles (UAV) communication relaying and multirobot coordination to name just a few. By example, in particle, path planning it is a difficult task in robotics, as well as construct and control a robot. The main propose of path planning is find a specific route in order to reach the target destination.

Given an environment, where a mobile robot must determine a route in order to reach a target destination, we found the shortest path that this robot can follow. This goal is reach using bio-inspired techniques, as Ant Colony Optimization (ACO)and the Genetics Algorithms (GA).

A principal of these techniques, is by example, with a colony can solve problems unthinkable for individual ants, such as finding the shortest path to the best food source, allocating workers to different tasks, or defending a territory from neighbors. As individuals, ants might be tiny dummies, but as colonies they respond quickly and effectively to their environment. They do it with something called Swarm Intelligence.

These novel techniques are nature-inspired stochastic optimization methods that iteratively use random elements to transfer one candidate solution into a new, hopefully better, solution with regard to a given measure of quality.

We cannot expect them to find the best solution all the time, but expect them to find the good enough solutions or even the optimal solution most of the time, and more importantly, in a reasonably and practically short time. Modern meta-heuristic algorithms are almost guaranteed to work well for a wide rangeof tough optimization problems.

1.1. Previous work

Path planning is an essential task navigation and motion control of autonomous robot. This problem in mobile robotic is not simple, and the same is attached by two distint approaches. In the classical approaches present by Raja et al.[49]cited according to [3]the C-space, where the representation of the robot is a simple point. The same approach is described by Latombe’s book [4]. Under concept of C-space, are developedpath planning approaches with roadmap and visibility graph was introduced[5].Sparce envioroments considering to polygonal obstacles and their edges [6, 7]. The Voroni diagram was introduced [8]. Other approach for roadmap andrecient applications in [9,10]. Cell descomposition approach [11, 12, 13, 14, 15,16]. A efficente use of grids [17].

A related problem is when both, the map and the vehicle position are not know. This problem is usually nown as Simultaneous Localization and Map Building (SLAM), and was originally introduced [18]. Until recently,have been significative advances in the solution of the SLAM problem [19,20,21,22].

Kalman filter methods can also be extended to perform simultaneous localization and map building. There have been several applications in mobile robotic, such as indoors, underwater and outdoors. The potential problems with SLAM algorithm have been the computational requeriments. The complexy of original algortihm is of O(N3) but, can be reduced to O (N2)where, N will be the number of landmarks in the map [23].

In computational complexity theory, path planning is classified as an NP (nondeterministic polynomial time) complete problem [33]. Evolutionary approaches provide these solutions. Where, one of the high advantage of heuristic algorithms, is that it can produce an acceptable solution very quickly, which is especially used for solving NP-complete problems.

A first path planning approach of a mobile robot trated as non-deterministic polynomial time hard (NP-hard) problem is [31]. Moreover, even more complicated are the environment dynamic, the classic approaches to be incompetent [32]. Hence, evolutionary approaches such as Tabu Search (TS), Artificial Neural Network (ANN), Genetic Algorithm (GA), Particle Swarm Optimization (PSO), Ant Colony Optimization (ACO) and Simulated Annealing (SA), name a few, are employed to solve the path planning problem efficiently although not always optimal.

Genetic Algorithm (GA) based search and optimization techniques have recently found increasing use in machine learning, scheduling, pattern recognition, robot motion planning, image sensing and many other engineering applications. The first research of Robot Motion Planning (RMP), according to Masehian et al.[53] although GA, was first used in [42] and [43]. An approach for solution the problem of collision-free paths is presented in [44].GA was applied [45, 46, 48] in planning multi-path for 2D and 3D environment dimension and shortest path problem. A novel GA searching approach for dynamic constrained multicast routing is developed in [49]. Parallel GA [50], is used for search and constrained multi-objective optimization. Differentials optimization used hybrid GA, for path planning and shared-path protections has been extended in [51, 52]. In [62, 63, 64, 65], has been a compared of differential algorithms optimization GA (basically for dynamic environment), subjected to penalty function evaluation.

By other side, thetechnique PSO have some any advantages [35], such as simple implementationwith a few parameters to be adjusted. Binary PSO [37] withouta mutation operator[36]are used to optimize the shortest path. Planning in dynamic environment, that containing invalid paths (repair by a operator mutation), are subjected to penalty function evaluation [38]. Recently, [39] proposedwith multi-objective PSO and mutate operator path planning in dangerous dynamics environment.Finally, a newperspective global optimization is propossed [40].

Ant Colony Optimization (ACO) algorithms have been developed to mimic the behavior of real ants to provide heuristic solutions for optimization problems. It was first proposed by M. Dorigoin 1992 in his Ph. D. dissertation [54]. The first instance of the application of Ant Colony Optimization in Probabilistic Roadmap is the work [55, 56]. In [57] 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 [58]. ACRMP is presented in [60]. An articulated RMP using ACO is introduced in [59]. 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 Potential Fields (PF) and ACO is introduced in [61] to path planning in dynamic environment. In [66] a fast two-stage ACO algorithm for robotic path planning is used.

The notion of using Simulated Annealing (SA) for roadmap was initiated in [67]. PFapproach was integrated with SA to escape from local minimaand evaluation [68,70]. Estimates using SA for a multi-path arrival and path planning for mobile robotic based on PF, is introduced in [69, 72]. A path planning based on PF approach with SA is developed in [72].Finally, in [71] was presented a multi operator based SA approach for navigation in uncertain environments.

A case particle are militar applications, with an uninhabited combat air vehicle (UCAV). The techniques employed, have been proposed to solve this complicated multi-constrained optimization problem, solved contradiction between the global optimization and excessive information. Such techniques used to solution this problem are differential evolution [24], artificial bee colony [29], genetic algorithm [25], water drops optimization (chaotic and intelligent) [30] and ant colony optimization algorithm [26, 27, 28].

Advertisement

2. Robot navigation

2.1. Introduction

Mobile robots and manipulator robots are increasingly being employed in many automated envionments. Potential applications of mobile robots include a wide range such a service robots for elderly persons, automated guide vehicles for transferring goods in a factory, unmmaned bomb disposal robots and planet exploration robots. In all thes applications, the mobile robots perform their navegation task using the building blocks (see figure 1) [1], the same, is based on [2] known with the Deliberative Focus.

Figure 1.

Deliberative Focus.

While perception of enviroment refers to understanding its sensory data, finding its pose or configuration in the surroundings is localization and map building. Planning the path in accordance with the task by using cognitive decision making is an essential phase before actually accomplishing the preferred trajectory by controlling the motion. As each of the building blocks is by itself a vast research field.

2.2. Map representation methods

When, Rencken in1993 [73] defined the map building problem as sensing capacity of robot, can be split in two, where robot know a pre-existing map or it has to build this, through information of the environment. According to above is assumed that the robot begins a exploration without having any knowledge of the environment, but with a exploration strategy, and it depends strongly on the kind of sensors used, the robot builds its own perception of environment[74].

A proposal of spatial representation is to sample discretely the two- or three-dimensional environment. This isa sample space in cells of a uniform gridfor two-dimensional or considering the volume of elementsthat are used to represent objets named voxel.

Geometric maps are composed of the union of simple geometric primitives. Such maps are characterized by two key properties: the set of basic primitives used for describing objects, and the set of operators used to manipulate objects. The fundamentals problems with this technique are lack of stability, uniqueness, and potentiality.

Within the geometric representations, the topological representation can be used to solve abstract tasks that are not void reliance on error-prone metric, provided an explicit representation of connectivity between regions or objects. A topological representation is based on an abstraction of the environment in terms of discrete places (landmarks) with edges connecting them. In [76], present an example of this topological representation, where after of delimited region of interest, used a GA for the landmark search through the image.

2.3. Path planning

The basic path planning problem refers to determining a path in configuration space between an initial configuration (start pose) of the robot and a final configuration (finish pose). Therefore, several approaches for path planning exist of course a particular problem of application, as well as the kinematic constraints of the robot [77]. Although is neccesary make a serie of simplied with respect to real environment, the techniques for path planning can be group in discrete state space and continuum space.

To efficiently compute of search the path through techniques as A* [14] and Dynamic programming. The difference between them usually, resides in the simplicity to define or compute the evaluation function, which hardly depends on the nature of the environment and the specific problem.Other techniques for mapping a robot’s environment inside a discrete searchable space include visibility graphs and Voronoi diagrams [75].

Path planning in a continuum space is consideret as the determination of an appropriate trajectory within this continuum. Two of the most known techniques for continuous state space are the potentialfields [61] and the vector field histogram methods. Alternatively,these algorithms, can be based on the bug algorithm[41], guaranteed to find a path from the beginning until target, if such path exists. Unfortunately, these methods can be generated arbitrarytrajectories worse than the optimal path to the target.

Advertisement

3. Population-based meta-heuristic optimization

Many results in the literature indicate that metaheuristics are the state-of-the-art techniques for problems for which there is non efficient algortihm. Thus, meta-heuristics approach approximationsallow solving complex optimization problems. Although these methods, cannot guarantee that the best solution found after termination criteria are satisfied or indeed its global optimal solution to the problem.

3.1. Optimization

The theory of optimization refers to the quantitative study of optima and the methods for finding them. Global Opitimization is the branch of applied mathematics and numerical analysis that focuses on well optimization. Of course T. Weise in [81], the goal of global optimization is to find to the best possible elements x* form a set  X according to a set criteria F = {f1, f2,..., fn}These criteria are expressed as mathematical function, that so-called objetive functions. In the Weise’s book[81] the Objective Function is described as:

DefinitionObjective Funcition. An objective funtion f : X Y with Y  R is a mathematical function which is subject to optimization.

Global optimization comprises all techniques that can be used to find the best elements x* in X with respect to such criteria f Є F.

3.2. Nature-inspied meta-heuristic optimization

The high increase in the size of the search space and the need of proccesing in real-time has motivated recent researchs to solving scheduling problem using nature inspired heuristic techniques. The principal components of any metaheuristic algorithms are: intensification and diversification, or explotation and exploration. The optimal combination of these will usually ensure that a global optimization is achievable.

Figure 2.

General Description for Nature Inspired Algorithm

3.3. Genetic algorithms

In essence, a Genetic Algorithm (GA) is a search method based on the abstraction Darwinian evolution and natural selection of biological systems and respresenting them in the mathematical operator: croosover or recombination, mutation, fitness, and selection of the fittest.

The application of GA to path planning problem requires development of a chromosome

representation of the path, appropriate constraint definition to minimize path distance, such that is providing smooth paths. It is assumed that the environment is static and known.

Cited according to [81], the genotypes are used in the reproduction operations whereas the values of the objective funtions f(or fitness function), wheref Є Fare computed on basis of the phenotypes in the problme space X which are obtained via the genotype-phenotype mapping (gpm) [82, 83, 84, 85], where G is a space any binary chain.

gG x X:gpm g=xE1
gG x X:Pgpm g=x>0E2

Figure 3.

GA Modified.

3.4. Swarm intelligence

Swarm intelligence (SI) is based on the collective behavior. The collective behaviorthat emerges is a form of autocatalytic behaviour [34], self-organized systems. It’s typically made up of a population of simple agents interacting locally with one another and with their environment. Natural examples of SI include ant colonies, bird flocking, animal herding, bacterial growth, and fish schooling. Nowadays swarm intelligence more generically, referes design complex adaptive systems.

3.4.1. Particle Swarm Optimization

Particle Swarm optimization (PSO), is a form of swarm intelligence, in which the behavior of a biological social systems. A particullaritied is when, looks for food, its individuals will spreadin the environment and move around independently. According to [81] Particle Swarm Optimization, a swarm of particles (individuals) in a n-dimensional search space G is simulated, where each particle q has a position genotype p.gQ  ⊆ Rn in this case n-dimensional is two, likewise a velocity p.v ∈ Rn. Therefore, each particle p has a memory holding its best position (can be reference to minim distance Euclidian of target (p) respect to q) best (q) ∈ G. In order to realize the social component, the particle furthermore knows a set of topological neighbors N(q) which could well be strong landmarks in the Rn.

This set could be defined to contain adjacent particles within a specific perimeter, using the Euclidian distance measure deuc specified by

deuc=p- qi2=i=1n(p  q(x,y))2E3
dp.g=mindeucp, qiqi  Q}E4
 p.v. =ωvi+αrnd()(pi-p.g)+βrnd()(gbest-p.g)E5
p.g = dp.g+p.v.E6

3.4.2. Ant Colony Optimization

Ant Colony Optimization (ACO) has been formalized into a meta-heuristic for combinatorial optimization problems by Dorigo and co-workers [78], [79].This behavior, described by Deneubourg [80] enables ants to find shortest paths between food sources and their nest. While walking, they decide about a direction to go, they choose with higher probability paths that are marked by stronger pheromone concentrations.

ACO has risen sharply. In fact, several successful applications of ACO to a wide range of different discrete optimization problems are now available. The large majorities of these applications are to NP-hard problems; that is, to problems for which the best known algorithms that guarantee to identify an optimal solution have exponential time worst case complexity. The use of such algorithms is often infeasible in practice, and ACO algorithms can be useful for quickly finding high-quality solutions.

ACO algorithms are based on a parameterized probabilistic model the pheromone model, is used to model the chemical pheromone trails. Artificial ants incrementally construct solutions by adding opportunely defined solution components of the partial solutions in consideration. The first ACO algorithm proposed in the literature is called Ant System (AS) [56].

In the construction phase, an ant incrementally builds a solution by adding solution components to the partial solution constructed so far. The probabilistic choice of the next solution component to be added is done by means of transition probabilities, which in AS are determined by the following state transition rule:

P(cr|sa[cl])={[ηr]α[τr]β0cuj(sa[cl])[ηu]α[τu]βifcrJ(sa[cl])otherwiseE7

Once all ants have constructed a solution, the online delayed pheromone update rule is applied:

τj(1ρ)τj+aAΔτsajwhereΔτsaj={F0(sq)ifcjisacomponentofsaotherwiseE8

This pheromone update rule leads to an increase of pheromone on solution components that have been found in high quality solutions.

Advertisement

4. Behavior fusion learning

4.1. Representation and initial population

Applied the performance and success of an evolutionary optimization approach given by a set of objective functions F and a problem space X is defined by:

  • Its basic parameter settings like the population size ≤ ms or the crossover and mutation rates.

  • Whether it uses an archive Arc of the best individuals found.

  • The fitness assignment process and the selection algorithm.

  • The genotype-phenotype mapping connecting the search Space and the problem space.

Such that:

  • All ants begin in the same node. Applied (6) to node initiate.

  • Initial population with a frequency f.

  • L+ is evaluated with a cost of T+. This implies, that j is visited only once.

  • The transition rule is (9).

4.2. Genetic operators and parameters

The properties of their crossover and mutatrion operations are well known and an extensive body of search on them is avaible [87, 88].

The natural selections is improved the next form:

  • Select four members to population (two best explorers and two best workers).

  • Applied crossover.

  • The probability the mutation is same to the percentage this.

  • Performed null reproduction.

A string chromosome can either be a fixed-length tuple (9) or a variable-length list (10).

G=(g1,,gn:g[i]Gii1n)E9
G={lists(g:giGT 0ileng}E10

4.2.1. Selection

Elitist selection, returns the k<ms(number of individuals to be placed into the mating)best elements from the list. In general evolutionary algorithms, it should combined with a fitness assignment processs that incorporates diversity information in order to prevent premature convergence.The elitist selection, force to the best individuals, according with to fitness function, to move to the next iteration.

4.2.2. Crossover

Amongst all evolutionary algortihms, genetic algorithms have the recombination operation which probably comes closest to the natural paragon.

Example of a fixed-length string, applied to the best explorer and the best workers obtain the two best gene.

Figure 4.

Crossover Algorithm.

Figure 5.

Example of Crossover, of course steps (b) and (c) crossover algorithm.

4.2.3. Mutation

The mutation operation applied, mutate NN  is used to create a new genotype gn Є N  by modifying an existing one. The way this modification is performed is application-dependent. It may happen in a randomized or in a deterministic fashion.

gn=mutateg:gN E11

Therefore, the mutation performed only one of the three gene in the chromosome offspring. The selected gen must a change in his allele (inherited), by a new random value in the same.

4.2.4. Null reproduction or extinction

After the crossover of the mutation (if is the case) is need performed a null reproduction or extinction of the ant workers or ant explorer. This allows the creation of fixed-length strings individuals means simple to create a new tuple of the structure defined by the genome and initialize it with random values.

4.3. Path planning through evolutive ACO

The modifcation of the proposed ACO algorithm is applied. Due to in this modification have several parameters that determine the behavior of proposed algorithm, these parameters were optimized using a genetic algorithm.

A new transiction rule. The rule of the equation(7) is modified by:

J=argmaxuϵjikτiutηiu    if q q0       J                                                  if  q>q0E12

This rule allows the exploration. Where, an ant k is move through i and j, with a distribution q in a range [0, 1], q0 is a parameter adjusts in the range (0 ≤ q0 ≤0) y J Є Jik, is a state select based in

pij k=αsinβτijkt+γ E13

The transition rule, therefore is different (of equation 7) when q≤q0, this meaning is a heuristic knowledge characterized in the pheromone. The amount of pheromone τij Z, can be positive and negative, allowing a not-extinction, but rather to continue comparison between its these, is obtain the value more high of pheromone.

τijt=1L+ whereL+ T+E14

The update rule allows a global update, only for the path best.

Figure 6.

ACO Modified.

Advertisement

5. Experimental results

In this section, the accuracy of the proposed algorithms described above. Present different start node, implying different grade of complexity.

Firtstly obtain the graph of each environment, the same applied of the landmarks of init and finish, also the centroid of the initial node. Finally, applied the algorithms over each graph, search the shortest path.

Advertisement

6. Conclusions and perspectives

This work was implemented with call selection natural and evolution natural, through basict two types of ants: jobs and explorer. The offspring are considerated for the jobs, the best foragers and for the explorer, the offspring least have lost their path. Each ant have three gene, α, β and γ owned to transition function. The parameters was applied in the same algorithms, but, the best result is obtanained with the ACO-GA algorithm.

The implementation of the ACO-GA in a robot manipulator, is a job in prosess, but the first results prove the effectively of the same. See figures (9) and (10).

Figure 7.

Images of Solution Process applied the ACO-GA Algorithm and parameters of table 1.

Figure 8.

Images of Solution Process applied the ACO-GA Algorithm and parameters of table 1. Note that Different Start Node.

Figure 9.

Solution to Labyrinth Applied ACO-algorithm.

Figure 10.

Example of a variation of epochs with (0 < α <1); β < γ or β > γ applied ACO and ACO-GA.

Figure 11.

Best value applied to the best ACO and the best ACO-GA

Figure 12.

The robot manipulator select to piece of course to pheromone (green). Note, that the manipulator can’t take the first piece. Graphics Displacement and Monitoring of the Manipulator respect to pheromone.

Figure 13.

Besides using the ACO-Modified, is necessary calculate the distance of the first node through of de equation (6). Because the initial pose of manipulator can be “above” of the piece or well to distance not detectable by manipulator of the initial node, of manipulator makes it impossible of take.

References

  1. 1. SiegwartRNourbakhshI. R2004Introduction to autonomous mobile robot. Massachusetts Institute of Technologypress, Cambridge, U.S.A.
  2. 2. BorensteinJEverettH. RFengLWhere am I? Sensors and Methods for Mobile Robot Positioning, Ann Arbor, University of Michigan,1996184186available at http://www-personal.engin.umich.edu/~johannb/position.htm)
  3. 3. UdupaS1977Collision detection and avoidance in computer controlled manipulator. PHD thesis, California Institute Technology, California, USA.
  4. 4. LatombeJ. C1991Robot motion planning. Kluwer Academic Publisher, Boston.
  5. 5. Lozano-Perez T Wesley MA (1979An algorithm for planning collision-free paths among polyhedral obstacles. Commun ACM., 2210560570
  6. 6. LiLYeTTanMChenX2002Present state and future development of mobile robot technology research. Robot., (24)5: 475-480.
  7. 7. SiegwartRNourbakhshI. R2004Introduction to autonomus mobile robot. Massachusets Institute of Technology Press, Cambridge, U.S.A.
  8. 8. DunlaingC. OYapC. K1985A retraction method for planning a motion of a disc. J. Algorithms, 6104111
  9. 9. Masehian _E, KatebiY (2007). Robot motion planning in dynamic environments with mobile obstacles and target. Int. J. Mech. Syst. Sci. Eng., 1(1): 20-25.
  10. 10. GarridoSMorenoLBlancoDJurewiczP2011Path planning for mobile robot navigation using Voronoi diagram and fast marching. Int. J. Robot. Autom., 214264
  11. 11. Lozano-perezT1983spatial planning: A configuration approach. IEEE T. Comput. C, 323108120
  12. 12. ZhuD. JLatombeJ. C1989New heuristic algorithms for efficient hierarchical path planning. Technical report STAN-CS-891279Computer Science Department, Stanford University, USA.
  13. 13. PaytonD. WRosenblattJ. KKeirseyD. M1993Grid-based for mobile robot. Robot Auton. Syst., 1111321
  14. 14. LikhachevMFergusonDGordonGStentzAThrunS2005Anytime dynamic A*: An anytime, replanning algorithm. Proceedings of the international Conference on Automated Planning and Scheduling, 262271
  15. 15. HachourO2008The processed genetic FPGA implementation for path planning of autonomous mobile robot. Int. J. Circ. Syst. Sig. Proc., 22151167
  16. 16. HachourO2008Path planning of autonomous mobile robot. Int. J. Syst. Appl. Eng. Dev., 42178190
  17. 17. ZhengT. GHuanHAaronS2007Ant Colony System Algorithm for Real-Time Globally Optimal Path Planning of Mobile Robots. Acta. Automatica. Sinica, 333279285
  18. 18. CheesemanPSmithRSelfMA stochastic map for uncertain spatial relationships. In 4th International Symposium on Robotic Research, MIT Press, 1987
  19. 19. Jhon Leonard and HFeder. Decoupled stochastic mapping for mobile robot and auto navigation. IEEE Journal Oceanic Engineering, 66, 442001561571
  20. 20. JNeiraand J. DTardosData association in stchocastic mapping using joint compatibility test. IEEE Transaction Robotics and Automation, 8908972001
  21. 21. ClarkSDissanayakeGNewmanPandDurrant-whyteHA Solution Localization and Map Building (SLAM) Problem. IEEE Journal of Robotics and Automation, 173June 2001
  22. 22. Michael Montemerlo SebastianFastslam: A factored solution totje simultaneous localization and mapping problem, http://citeseer.nj.nec.com/503340.html.
  23. 23. NebotE2002Simultaneous localization and mapping 2002 summer school. Australian centre field robotics. http://acfr.usyd.edu.au/homepages/academic/enebot/
  24. 24. H. BDuanX. YZhangand C. FXuBio-Inspired Computing”, Science Press, Beijing, (2011
  25. 25. Y. VPehlivanogluA new vibrational genetic algorithm enhanced with a Voronoi diagram for path planning of autonomous UAV”, Aerosp. Sci. Technol., 1620124755
  26. 26. WYeD. WMaand H. DFanAlgorithm for low altitude penetration aircraft path planning with improved ant colony algorithm”, Chinese J. Aeronaut., 182005304309
  27. 27. H. BDuanY. XYuX. YZhangand SShaoThree-dimension path planning for UCAV using hybrid meta-heuristic ACO-DE algorithm”, Simul. Model. Pract. Th., 18201011041115
  28. 28. H. BDuanX. YZhangJWuand G. JMaMax-min adaptive ant colony optimization approach to multi-UAVs coordinated trajectory replanning in dynamic and uncertain environments”, J. Bionic. Eng., 62009161173
  29. 29. C. FXuH. BDuanand FLiuChaotic artificial bee colony approach to uninhabited combat air vehicle (UCAV) path planning”, Aerosp. Sci. Technol., 142010535541
  30. 30. H. BDuanS. QLiuand JWuNovel intelligent water drops optimization approach to single UCAV smooth trajectory planning”, Aerosp. Sci. Technol., 132009442449
  31. 31. CannyJReifJ1987New lower bound techniques for robot motion planning problems. Proceedings of IEEE Symposium on the Foundations of Computer Science, Los Angeles, California, 4960
  32. 32. SugiharaKSmithJ1997Genetic algorithms for adaptive motion planning of an autonomous mobile robot. Proceedings of the IEEE International Symposium on Computational Intelligence in Robotics and Automation, Monterey, California, 138143
  33. 33. GossSAronSDeneubourgJ. Land PasteelsJ. M1989Self-organized Shortcuts in the Argentine Ant. Naturwissenchaften 76pg. 579581Springer-Verlag.
  34. 34. DorigoMManiezzoVand ColorniA1996The Ant System: Optimization by a colony of cooperating agents”, IEEE Transactions on Systems, Man and Cybernetics-Part-B, 261113
  35. 35. KennedyJEberhartR. C1995Particle Swarm Optimization. Proceedings of the IEEE International Conference on Neural Networks, Perth, Australia, 19421948
  36. 36. QinY. QSunD. BLiNCenY. G2004Path Planning for mobile robot using the particle swarm optimization with mutation operator. Proceedings of the IEEE International Conference on Machine Learning and Cybernetics, Shanghai, 24732478
  37. 37. ZhangQ. RGuG. C2008Path planning based on improved binary particle swarm optimization algorithm. Proceedings of the IEEE International Conference on Robotics, Automation and Mechatronics, Chendu, China, 462466
  38. 38. NasrollahyA. ZJavadi HHS (2009Using particle swarm optimization for robot path planning in dynamic environments with moving obstacles and target. Third European Symposium on computer modeling and simulation, Athens, Greece, 6065
  39. 39. GongD. WZhangJ. HZhangY2011Multi-objective particle swarm optimization for robot path planning in environment with danger sources. J. Comput., 6815541561
  40. 40. YangX. S2011Optimization Algorithms. Comput., optimization, methods and algorithms. SCI 356, 1331
  41. 41. TaylorKLa Valle, M.S. “I-Bug: An Intensity-Based Bug Algorithm”, Robotics and Automation, 2009ICRA’09. IEEE International Conference, 39813986
  42. 42. ParkerJ. KKhoogarA. Rand GoldbergD. EInverse kinematics ofredundant robots using genetic algorithms". Proc. IEEE ICRA, 11989271276
  43. 43. DavidorYRobot programming with a genetic algorithm" Proc. IEEEInt. Conf. on Computer Sys. & Soft. Eng. (1990186191
  44. 44. SolanoJand JonesD. IGeneration of collision-free paths, a geneticapproach", IEEE Colloquium on Gen. Alg. for Control Sys. Eng. (19935
  45. 45. HocaogluCand SandersonA. CPlanning multi-paths usingspeciation in genetic algorithms", Proc IEEE Int. Conf. on EvolutionaryComputation, (1996378383
  46. 46. GenMRunweiCand DingweiWGenetic algorithms for solvingshortest path problems", Proc. IEEE Int. Conf. on Evolutionary Comput. (1997401406
  47. 47. Kumar PratiharD.; Deb, K.; Ghosh, A. "Fuzzy-genetic algorithms and mobile robot navigation among static obstacles" In Proc. CEC’99, 11999
  48. 48. Zein-sabattoSand RamakrishnanRMultiple path planning for agroup of mobile robots in a 3D environment using genetic algorithms"Proc. IEEE Southeast, (2002359363
  49. 49. RajaPAnd Pugazhenthi, S. “Optimal path planning of mobile robots: A review”International Journal of Physical Sciences 7131413202012
  50. 50. WilsonL. AMooreM. DPicarazziJ. Pand MiquelS. D. SParallel genetic algorithm for search and constrained multi-objectiveoptimization" Proc. Parallel and Distributed Processing Symp., (2004165
  51. 51. QingLXinhaiTSijiangXand YingchunZOptimum PathPlanning for Mobile Robots Based on a Hybrid Genetic Algorithm" InProc. HIS’06. (20065358
  52. 52. QingfuZJianyongSGaoxiXand EdwardTEvolutionaryAlgorithms Refining a Heuristic: A Hybrid Method for Shared-PathProtections in WDM Networks Under SRLG Constraints", IEEE Trans.on Systems, Man and Cybernetics, Part B, 37120075161
  53. 53. MasehianEand SedighizadehDClassic and Heuristic Approaches in Robot Motion Planning- A Chronogical Review”, World Academy of Science, Engineering and Technology, (2007100106
  54. 54. MDorigoOptimization, learning and natural algorithms (in italian),” Ph.D. dissertation,Dipartimento di Elettronica, Politecnico di Milano, Italy, 1992
  55. 55. DeneubourgJLClipP. -Land CamazineS. SAntsbuses androbots-self-organization of transportation systems", Proc. FromPerception to Action, (19941223
  56. 56. DorigoMand GambardellaL. MAnt Colony System: A CooperativeLearning Approach to the Traveling Salesman Problem," IEEE Trans. InEvolutionary Comput., 1119975356
  57. 57. XiaopingFXiongLShengYShengyueYand HengZOptimalpath planning for mobile robots based on intensified ant colonyoptimization algorithm" Proc. IEEE on Rob. Intel. Sys. & Sig.Processing, 12003131136
  58. 58. Ying-tungHCheng-longCand Cheng-chihCAnt colonyoptimization for best path planning" Proc. IEEE/ISCIT’04, 2004109113
  59. 59. RamakrishnanRand Zein-sabattoSMultiple path planning for agroup of mobile robot in a 2-D environment using genetic algorithms" InProc. Of the IEEE Int. Conf. on SoutheastCon’01, (20016571
  60. 60. MohamadM. MDunniganM. Wand TaylorN. KAnt ColonyRobot Motion Planning” Proc. Int. Conf. on EUROCON’05. 12005213216
  61. 61. Na Lv and Zuren FNumerical Potential Field and Ant ColonyOptimization Based Path Planning in Dynamic Environment", IEEEWCICA’06, 2200689668970
  62. 62. RajaPPugazhenthiS2008Path planning for a mobile robot to avoid polyhedral and curved obstacles. Int. J. Assist. Robotics. Mechatronics, 923141
  63. 63. RajaPPugazhenthiS2009Path planning for a mobile robot using real coded genetic algorithm. Int. J. Assist. Robot. Syst., 1012739
  64. 64. RajaPPugazhenthiS2009Path planning for mobile robots in dynamic environments using particle swarm optimization. IEEE International Conference on Advances in Recent Technologies in Communication and Computing (ARTCom 2009), Kottayam, India, 401405
  65. 65. RajaPPugazhenthiS2011Path Planning for a mobile robot in dynamic environments. Int. J. Phys. Sci., 62047214731
  66. 66. XiongCh, Yingying K, Xian F, and Quidi W; “A fas two-stage ACO algorithm for robotic planning” Neural Comp., and App., Springer-Verlag (2011DOI:s00521-011-0682-7.
  67. 67. CarrikerW. FKhoslaP. KKroghB. HThe use of simulated annealing to solve the mobile manipulator path planning problem", Proc. IEEE ICRA (1990204209
  68. 68. Janabi-sharifiFand VinkeDIntegration of the artificial potential field approach with simulated annealing for robot path planning" Proc. IEEE Int. Conf. on Intel. Control (1993536541
  69. 69. BlackowiakA. DRajanS. DMulti-path arrival estimates using simulated annealing: application to crosshole tomography experiment", IEEE J. Oceanic Eng. 2031995157165
  70. 70. ParkM. Gand LeeM. CExperimental evaluation of robot path planning by artificial potential field approach with simulated annealing", Proc. SICE (2002421902195
  71. 71. MiaoHA multi-operator based simulated annealing approach for robot navigation in uncertain environments. (2010Int. J. Comput. Sci. Secur., 415061
  72. 72. QidanZYongjieYand ZhuoyiXRobot Path Planning Based on Artificial Potential Field Approach with Simulated Annealing" Proc. ISDA’06, (2006622627
  73. 73. RenckenW. D1993Concurrent Localization and Map Building for Mobile Robots Using Ultrasonic Sensors.” Proceedings of the 1993 IEEE/RSJ International Conference on Intelligent Robotics and Systems, Yokohama, Japan, July 26-30, 21922197
  74. 74. EdlingerTand PuttkamerE1994Exploration of an Indoor Environment by an Autonomous Mobile Robot.” International Conference on Intelligent Robots and Systems (IROS’94). Munich, Germany, Sept. 12-16, 12781284
  75. 75. Y. VPehlivanogluA new vibrational genetic algorithm enhanced with a Voronoi diagram for path planning of autonomous UAV”, Aerosp. Sci. Technol., 1620124755
  76. 76. MMataJ. MArmingolF. JRodríguez2004A deformable Model-Based Visual System for Mobile Robot Topologic Navigation” CICYT Project TAP 990214
  77. 77. DudekGJenkinM2000Computational Principles of Mobile Robotics, Cambridge University Press, Cambridge, UK
  78. 78. MDorigoand G. Di Caro, “The Ant Colony Optimization meta-heuristic,” in New Ideas in Optimization, D. Corne et al., Eds., McGraw Hill, London, UK, 11321999
  79. 79. MDorigoGDiCaro, and L.M. Gambardella, “Ant algorithms for discrete optimization,” Artificial Life, 521371721999
  80. 80. J. -LDeneubourgSAronSGossand J. -MPasteelsThe self-organizing exploratory pattern of the argentine ant. Journal of Insect Behaviour, 31990159168
  81. 81. TWeiseGlobal Optimization Algorithms-Theory and Application”- Second edition e-book. (2007
  82. 82. DavidEGoldberg. Genetic Algorithms in Search, Optimization, and Machine Learning.Addison-Wesley Longman Publishing Co., Inc. Boston, MA, USA, January 19890-20115-767-5
  83. 83. John Henry HollandAdaptation in Natural and Artificial Systems: An IntroductoryAnalysis with Applications to Biology, Control, and Artificial Intelligence. The University of Michigan Press, Ann Arbor, 1975. 047-2-08460-797-8Reprinted by MIT Press, April1992NetLibrary, Inc.
  84. 84. J°orgHeitk°otter and David Beasley, editors. Hitch-Hiker’s Guide to EvolutionaryComputation: A List of Frequently Asked Questions (FAQ). ENCORE (The EvolutioNary Computation REpository Network), 1998. USENET: comp.ai.genetic. Onlineavailable at http://www.cse.dmu.ac.uk/~rij/gafaq/top.htm and http://alife.santafe.edu/~joke/encore/www/
  85. 85. Hui-Chin TangCombined random number generator via the generalized Chinese remainder theorem. Journal of Computational and Applied Mathematics, 1422377388May 15, 20020377-0427doi:10.1016/S0377-0427(01)00424-1.Onlineavailable at http://dx.doi.org/10.1016/S0377-0427(01)00424-1
  86. 86. CBlumand XLiSwarm Intelligence: Swarm Intelligence in Optimization”,Natural Computing Series, 2008Part I, 4385DOI:
  87. 87. DavidEGoldberg. Genetic Algorithms in Search, Optimization, and Machine Learning.Addison-Wesley Longman Publishing Co., Inc. Boston, MA, USA, January 19890-20115-767-5
  88. 88. John Henry HollandGenetic Algorithms. Scientific American, 26714450July1992Online available at http://www.econ.iastate.edu/tesfatsi/holland.GAIntro.htmandhttp://www.cc.gatech.edu/~turk/bio_sim/articles/genetic_algorithm.pdf.

Written By

Alejandra Cruz-Bernal

Submitted: 01 May 2012 Published: 30 January 2013