Receive a 20% Discount on All Purchases Directly Through IGI Global's Online Bookstore

Lee Gim Hee (DSO National Laboratories, Singapore) and Marcelo H. Ang Jr. (National University of Singapore, Singapore)

DOI: 10.4018/978-1-59904-849-9.ch158

Chapter Preview

TopGlobal path planning algorithms refer to a group of navigation algorithms that plans an optimal path from a point of origin to a given goal in a known environment. This group of algorithms requires the environment to be free from dynamic and unforeseen obstacles. In this section, two key global path planning algorithms: *navigation functions* and *roadmaps* will be discussed.

The most widely used global path planning algorithm is perhaps the navigation function computed from the “wave-front expansion” (J.-C Latombe, 1991; Howie Choset et al, 2005) algorithm due to its practicality, ease in implementation and robustness. The navigation function *N* is the *Manhattan distance* to the goal from the free space in the environment. The algorithm requires information of the environment provided to the robot to be represented as an array of grid cells.

The navigation function assigns a numeric value *N* to each cell with the goal cell having the lowest value, and the other unoccupied cells having progressively higher values such that a steepest descent from any cell provides the path to the goal. The value of the unoccupied cell increases with the distance from the goal. Each grid cell is either free or occupied space denoted by *gC _{free}* and

The shaded cells are the 1-Neighbor of the cell (x, y) and the number shows the priority of the neighboring cells

Finally, a path to the goal is generated by following the steepest descent of the *N* values. To prevent the path from grazing the obstacles, the grid cells which are less than a safety distance α from the obstacles are omitted in the computation of the navigation function. Figure 2 shows a path generated by the navigation function. The black cells are the obstacles and the grey cells are the unsafe regions.

Local Minima: It is also known as relative minima. Local minimum refers to a minimum within some neighborhood and it may not be a global minimum.

Graph Edge: Graph edge is usually drawn as a straight line in a graph to connect the nodes. It is used to represent connectivity between two or more nodes and may carry additional information such as the Euclidean distance between the nodes.

Hybrid Methods: A group of navigation methods that combine the global path planning and local navigation algorithms. The objective is to combine the advantages eliminate the inherent weaknesses of both groups of algorithms.

Global Path Planner: A group of navigation algorithms for planning an optimal path that connects a point of origin to a given goal in a known environment.

Graph Node: Graph Node is also known as graph vertex. It is a point on which the graph is defined and maybe connected by graph edges.

Manhattan Distance: The distance between two points measured along axes at right angles. For example, given two points p1 and p2 in a two-dimensional plane at (x1, y1) and (x2, y2) respectively, the Manhattan distance between p1 and p2 is given by |x1 - x2| + |y1 - y2|.

Local Navigation Methods: A group of navigation algorithms that do not require a known map of the environment to be provided to the robot. Instead, local navigation methods rely on current and local information from sensors to give a mobile robot online navigation capability.

Search this Book:

Reset

Copyright © 1988-2018, IGI Global - All Rights Reserved