Mobile Robots Navigation, Mapping, and Localization Part I

Mobile Robots Navigation, Mapping, and Localization Part I

Lee Gim Hee, Marcelo H. Ang Jr.
Copyright: © 2009 |Pages: 8
DOI: 10.4018/978-1-59904-849-9.ch158
OnDemand:
(Individual Chapters)
Available
$37.50
Current Special Offers
No Current Special Offers
TOTAL SAVINGS: $37.50

Abstract

The development of autonomous mobile robots is continuously gaining importance particularly in the military for surveillance as well as in industry for inspection and material handling tasks. Another emerging market with enormous potential is mobile robots for entertainment. A fundamental requirement for autonomous mobile robots in most of its applications is the ability to navigate from a point of origin to a given goal. The mobile robot must be able to generate a collision-free path that connects the point of origin and the given goal. Some of the key algorithms for mobile robot navigation will be discussed in this article.
Chapter Preview
Top

Global Path Planners

Global 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 gCfree and gCoccupied. First, the value of N is set to ‘0’ at the goal cell gCgoal. Next, the value of N is set to ‘1’ for every 1-Neighbor (see Figure 1 for the definition of 1-Neighbors) of gCgoal which is in gCfree. It is assumed that the distance between two 1-Neighbors is normalized to 1. In general, the value of each gCfree cell is set to N+1 (e.g., ‘2’) for every unprocessed gCfree 1-Neighbor of the grid cell with value N (e.g., ‘1’). This is repeated until all the grid cells are processed.

Figure 1.

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

978-1-59904-849-9.ch158.f01

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.

Figure 2.

Path generated by the navigation function

978-1-59904-849-9.ch158.f02

Key Terms in this Chapter

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.

Complete Chapter List

Search this Book:
Reset