Open access peer-reviewed chapter

Meta-Heuristic Optimization Techniques and Its Applications in Robotics

By Alejandra Cruz-Bernal

Submitted: May 1st 2012Reviewed: October 17th 2012Published: January 30th 2013

DOI: 10.5772/54460

Downloaded: 2656

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].

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.

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  Xaccording 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 : XY with Y  Ris a mathematical function which is subject to optimization.

Global optimization comprises all techniques that can be used to find the best elements x* in Xwith 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 Xwhich are obtained via the genotype-phenotype mapping (gpm) [82, 83, 84, 85], where Gis 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 Gis 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.

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 Xis 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.

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.

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.

How to cite and reference

Link to this chapter Copy to clipboard

Cite this chapter Copy to clipboard

Alejandra Cruz-Bernal (January 30th 2013). Meta-Heuristic Optimization Techniques and Its Applications in Robotics, Recent Advances on Meta-Heuristics and Their Application to Real Scenarios, Javier Del Ser, IntechOpen, DOI: 10.5772/54460. Available from:

chapter statistics

2656total chapter downloads

2Crossref citations

More statistics for editors and authors

Login to your personal dashboard for more detailed statistics on your publications.

Access personal reporting

Related Content

This Book

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

Edited by Javier Del Ser

Next chapter

A Comparative Study on Meta Heuristic Algorithms for Solving Multilevel Lot-Sizing Problems

By Ikou Kaku, Yiyong Xiao and Yi Han

Related Book

First chapter

A Tutorial on H.264/SVC Scalable Video Coding and its Tradeoff between Quality, Coding Efficiency and Performance

By Iraide Unanue, Inigo Urteaga, Ronaldo Husemann, Javier Del Ser, Valter Roesler, Aitor Rodriguez and Pedro Sanchez

We are IntechOpen, the world's leading publisher of Open Access books. Built by scientists, for scientists. Our readership spans scientists, professors, researchers, librarians, and students, as well as business professionals. We share our knowledge and peer-reveiwed research papers with libraries, scientific and engineering societies, and also work with corporate R&D departments and government entities.

More About Us