Evolutionary Path Planning for Robot Navigation Under Varying Terrain Conditions

Introduction

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.