Evolutionary Path Planning for Robot Navigation Under Varying Terrain Conditions

Evolutionary Path Planning for Robot Navigation Under Varying Terrain Conditions

Terrence P. Fries (Coastal Carolina University, USA)
DOI: 10.4018/978-1-60566-310-4.ch017
OnDemand PDF Download:


Path planning is an essential component in the control software for an autonomous mobile robot. Evolutionary strategies are employed to determine optimal paths for their robustness and ability to solve complex problems. However, current evolutionary approaches fail to consider varying terrain conditions when determining an optimal path and offer only path planning without trajectory planning. This chapter presents an approach that determines a near optimal path while incorporating trajectory planning in the solution. Fuzzy linguistic variables are used represent the inherent imprecision and uncertainty in the terrain conditions presented to the robot. Most importantly, the method is computationally efficient and robust, providing real-time response and the ability to operate in a dynamic environment.
Chapter Preview


Optimal path planning is critical to the successful operation of autonomous mobile robots and any application in which they are involved. An autonomous robot must be able to determine an optimal or near-optimal path and then follow it. It must also have the capability to detect unexpected obstacles in a dynamic or uncertain environment and adjust its path accordingly. Motion planning consists of two components: path planning and trajectory planning (Latombe, 1991). In many navigation methods, these two components are distinct and separate, although they are combined in some methods. Path planning computes a collision-free path through an environment. The path is optimal or near-optimal with respect to some criteria, such as shortest distance traveled, shortest time, or least hostile environment. Trajectory planning computes the actions the robot must take to follow the path. These actions include turns and straight movements. This chapter presents an evolutionary navigation approach that combines path and trajectory planning and has the capability to adapt in a dynamic environment. Fuzzy linguistic variables are used to represent uncertain terrain conditions.

Several issues must be considered when evaluating a robot navigation scheme. Any practical navigation algorithm must be able to respond in real-time. In a real world application, it is often not practical for a robot to wait for any length of time before proceeding. Usually computational resources are limited onboard an autonomous mobile robot and must be shared with operational algorithms, such as vision and image recognition. Therefore, a useful navigation algorithm must be computationally efficient. An algorithm must be able to adapt to a dynamic environment and take into consideration the myriad of issues associated with traversing various types of terrain.

Due to the complexity and uncertainty involved in autonomous robot navigation, attempts have been made to employ evolutionary algorithms. However, the most of these approaches reduce the computational complexity by constraining the robot’s operation to a static environment (Akbarzadeh, 2000; Cuesta, 2005; Fogel, 2000; Nearchou, 1999; Pratihar, 1999). This is not practical because real world environments are not isolated from external influences. Often, people move about in the environment and obstacles may be moved. When a robot interacts with these dynamic actors, it requires the ability to adjust its path. In addition, due to the nature of sensory data, especially that acquired through vision interpretation techniques, the environment information possesses some level of uncertainty and incompleteness. Most evolutionary approaches to navigation fail to account for these anomalies and assume a smooth and level terrain for the robot. Those that do address these issues are not able to respond in real-time due to computational complexity. The evolutionary navigation method presented in this chapter is sufficiently computationally efficient to provide real-time operation in all tested situations. Furthermore, the approach has the capability to adapt to dynamic and uncertain environments while addressing terrain issues.

The majority of navigation approaches that utilize evolutionary computation fail to provide real-time operation (Akbarzadeh, 2000; Cuesta, 2005; Fogel, 2000; Nearchou, 1999; Pratihar, 1999). The few methods that provide real-time operation do so by placing unacceptable restrictions on the generated path, such as limiting the possible solution paths to x-monotone or y-monotone (Sugihara, 1997). An x-monotone path is one in which the projection of the path on the x-axis is non-decreasing. This limits the robot’s path to always move in the same direction relative to a given axis. Such as restriction prevents the robot from responding to an newly discovered obstacle in a dynamic environment because it is unable to backtrack in its path. A simple path between two rooms in a building is neither x-monotone nor y-monotone as shown in Figure 1.

Key Terms in this Chapter

Environment Grid: A rectangular grid, usually square, that divides a given area into rows and columns, similar to chess board.

Motion Planning: The process of computing an optimal or near-optimal, collision-free path and then generating the sequence of moves necessary to realize that path. This is a combination of path planning and trajectory planning.

Path Planning: The process of computing an optimal or near-optimal, collision-free path through an environment containing obstacles. The path is optimal with respect to criterion specific to the application.

Autonomous Mobile Robot: A robot capable of planning and executing it own traversal of an environment without human assistance.

Trajectory Planning: The process of generating the actions of the robot necessary to proceed along a computed path.

Genetic Algorithm: A search technique that uses the concept of survival of the fittest to find an optimal or near optimal solution to a problem. Genetic algorithms use techniques inspired by evolutionary biology to generate new possible solutions known as offspring from an existing set of parent solutions. These recombination techniques include inheritance, selection, mutation, and crossover.

Fuzzy Linguistic Variable: The use of English words or phrases to represent information with some degree of uncertainty or vagueness.

Fitness Function: A function in a genetic algorithm that judges which individual chromosomes are most appropriate for a problem. The criteria for judging appropriateness are based upon the particular problem.

Chromosome: The representation of possible solutions of a problem usually using a binary string. This method is utilized by genetic algorithms to represent possible problem solutions for use in a genetic algorithm.

Complete Chapter List

Search this Book:
Editorial Advisory Board
Table of Contents
Lipo Wang
Hongwei Mo
Chapter 1
Fabio Freschi, Carlos A. Coello Coello, Maurizio Repetto
This chapter aims to review the state of the art in algorithms of multiobjective optimization with artificial immune systems (MOAIS). As it will be... Sample PDF
Multiobjective Optimization and Artificial Immune Systems: A Review
Chapter 2
Jun Chen, Mahdi Mahfouf
The primary objective of this chapter is to introduce Artificial Immune Systems (AIS) as a relatively new bio-inspired optimization technique and to... Sample PDF
Artificial Immune Systems as a Bio-Inspired Optimization Technique and Its Engineering Applications
Chapter 3
Licheng Jiao, Maoguo Gong, Wenping Ma
Many immue-inspired algorithms are based on the abstractions of one or several immunology theories, such as clonal selection, negative selection... Sample PDF
An Artificial Immune Dynamical System for Optimization
Chapter 4
Malgorzata Lucinska, Slawomir T. Wierzchon
Multi-agent systems (MAS), consist of a number of autonomous agents, which interact with one-another. To make such interactions successful, they... Sample PDF
An Immune Inspired Algorithm for Learning Strategies in a Pursuit-Evasion Game
Chapter 5
Luis Fernando Niño Vasquez, Fredy Fernando Muñoz Mopan, Camilo Eduardo Prieto Salazar, José Guillermo Guarnizo Marín
Artificial Immune Systems (AIS) have been widely used in different fields such as robotics, computer science, and multi-agent systems with high... Sample PDF
Applications of Artificial Immune Systems in Agents
Chapter 6
Xingquan Zuo
Inspired from the robust control principle, a robust scheduling method is proposed to solve uncertain scheduling problems. The uncertain scheduling... Sample PDF
An Immune Algorithm Based Robust Scheduling Methods
Chapter 7
Fabio Freschi, Maurizio Repetto
The increasing cost of energy and the introduction of micro-generation facilities and the changes in energy production systems require new... Sample PDF
Artificial Immune System in the Management of Complex Small Scale Cogeneration Systems
Chapter 8
Krzysztof Ciesielski, Mieczyslaw A. Klopotek, Slawomir T. Wierzchon
In this chapter the authors discuss an application of an immune-based algorithm for extraction and visualization of clusters structure in large... Sample PDF
Applying the Immunological Network Concept to Clustering Document Collections
Chapter 9
Xiangrong Zhang, Fang Liu
The problem of feature selection is fundamental in various tasks like classification, data mining, image processing, conceptual learning, and so on.... Sample PDF
Feature Selection Based on Clonal Selection Algorithm: Evaluation and Application
Chapter 10
Yong-Sheng Ding, Xiang-Feng Zhang, Li-Hong Ren
Future Internet should be capable of extensibility, survivability, mobility, and adaptability to the changes of different users and network... Sample PDF
Immune Based Bio-Network Architecture and its Simulation Platform for Future Internet
Chapter 11
Tao Gong
Static Web immune system is an important applicatiion of artificial immune system, and it is also a good platform to develop new immune computing... Sample PDF
A Static Web Immune System and Its Robustness Analysis
Chapter 12
Alexander O. Tarakanov
Based on mathematical models of immunocomputing, this chapter describes an approach to spatio-temporal forecast (STF) by intelligent signal... Sample PDF
Immunocomputing for Spatio-Temporal Forecast
Chapter 13
Fu Dongmei
In engineering application, the characteristics of the control system are entirely determined by the system controller once the controlled object... Sample PDF
Research of Immune Controllers
Chapter 14
Xiaojun Bi
In fact, image segmentation can be regarded as a constrained optimization problem, and a series of optimization strategies can be used to complete... Sample PDF
Immune Programming Applications in Image Segmentation
Chapter 15
Xin Wang, Wenjian Luo, Zhifang Li, Xufa Wang
A hardware immune system for the error detection of MC8051 IP core is designed in this chapter. The binary string to be detected by the hardware... Sample PDF
A Hardware Immune System for MC8051 IP Core
Chapter 16
Mark Burgin, Eugene Eberbach
There are different models of evolutionary computations: genetic algorithms, genetic programming, etc. This chapter presents mathematical... Sample PDF
On Foundations of Evolutionary Computation: An Evolutionary Automata Approach
Chapter 17
Terrence P. Fries
Path planning is an essential component in the control software for an autonomous mobile robot. Evolutionary strategies are employed to determine... Sample PDF
Evolutionary Path Planning for Robot Navigation Under Varying Terrain Conditions
Chapter 18
Konstantinos Konstantinidis, Georgios Ch. Sirakoulis, Ioannis Andreadis
The aim of this chapter is to provide the reader with a Content Based Image Retrieval (CBIR) system which incorporates AI through ant colony... Sample PDF
Ant Colony Optimization for Use in Content Based Image Retrieval
Chapter 19
Miroslav Bursa, Lenka Lhotska
The chapter concentrates on the use of swarm intelligence in data mining. It focuses on the problem of medical data clustering. Clustering is a... Sample PDF
Ant Colonies and Data Mining
Chapter 20
Bo-Suk Yang
This chapter describes a hybrid artificial life optimization algorithm (ALRT) based on emergent colonization to compute the solutions of global... Sample PDF
Artificial Life Optimization Algorithm and Applications
Chapter 21
Martin Macaš, Lenka Lhotská
A novel binary optimization technique is introduced called Social Impact Theory based Optimizer (SITO), which is based on social psychology model of... Sample PDF
Optimizing Society: The Social Impact Theory Based Optimizer
Chapter 22
James F. Peters, Shabnam Shahfar
The problem considered in this chapter is how to use the observed behavior of organisms as a basis for machine learning. The proposed approach for... Sample PDF
Ethology-Based Approximate Adaptive Learning: A Near Set Approach
Chapter 23
Dingju Zhu
Parallel computing is more and more important for science and engineering, but it is not used so widely as serial computing. People are used to... Sample PDF
Nature Inspired Parallel Computing
Chapter 24
Tang Mo, Wang Kejun, Zhang Jianmin, Zheng Liying
An understanding of the human brain’s local function has improved in recent years. But the cognition of human brain’s working process as a whole is... Sample PDF
Fuzzy Chaotic Neural Networks
About the Contributors