# Robotics Fundamentals Series: Planning and Navigation

Publish Date: Dec 20, 2011 | 5 Ratings | 4.20 out of 5 |  PDF

## Overview

Planning and navigation for an autonomous mobile robot involves purposeful decision-making and execution that a system utilizes to achieve its highest-order goals. Two skills that a competent, navigating robot usually must demonstrate are path planning and obstacle avoidance.

### 1. Path Planning

Given a map and a goal location, path planning involves identifying a trajectory that will cause the robot to reach the goal location when executed.  Path planning is a strategic problem-solving competence, as the robot must decide what to do over the long term to achieve its goals.

Path planning can be divided into two parts: the representation and the algorithm.  Path planners first transform the robot’s environment into a structure that is suitable for path planning. Some common techniques include generalized Voronoi graphs, regular grids and Quadtrees.  Path planning algorithms generally work on almost any configuration space representation, although some methods work better on certain representations. Figure 1 shows a Voronoi graph plotted in LabVIEW.

Figure 1. Voronoi Graph in LabVIEW

Since most representations can be converted into graphs, the path between the initial node and the goal node can be computed using graph search algorithms.  Graph search algorithms are well understood by computer science, however, many of those algorithms require the program to visit each node on the graph to determine the shortest path between the initial and goal nodes.  Visiting every node may be computationally tractable for a sparsely connected graph such as derived from a Voronoi diagram, but rapidly becomes computationally expensive for a highly connected graph such as from a regular grid.

### 2. Obstacle Avoidance

A path planner can only take into consideration the environment obstacles that are known to the robot in advance.  During path execution the robot’s actual sensor values may disagree with expected values due to map inaccuracy or a dynamic environment.  Therefore, it is critical that the robot modify its path in real time based on actual sensor values. This is where obstacle avoidance becomes important.  Some common obstacle avoidance methods include the Bug algorithm and the Vector Field Histogram (VFH).

### Bug Algorithm

A straightforward path planning approach is to follow the contour of each obstacle in robot’s way and thus circumnavigate it.  With Bug1, the robot fully circles the object, and then departs from the point with the shortest distance to the goal. This approach is inefficient but guarantees that the robot will reach any reachable goal. With Bug2, the robot begins to follow the object’s contour, but departs immediately when it is able to move directly toward the goal.  Bug2 will have significantly shorter total robot travel, but it still not optimal.

### Vector Field Histogram

One limitation of the Bug algorithm is that the robot's behavior at each instant is generally a function of only its most recent sensor readings.  This can lead to problems where the robot's instantaneous sensor readings do not provide enough information for robust obstacle avoidance.  The VFH techniques overcome this limitation by creating a local map of the environment around the robot.  For obstacle avoidance, a polar histogram is generated which determines the steering direction. First, all openings large enough for the robot to pass through are identified. Next, a cost function is applied which takes into account the target direction, wheel orientation, and previous direction.

Figure 2. Front panel of a LabVIEW VI performing a Vector Field Histogram algorithm for obstacle avoidance

### 3. Using Algorithms in LabVIEW

With LabVIEW you can choose the most effective syntax for developing algorithms, or you can use built-in tools to import algorithms written in text-based languages. Search algorithms and other robotics libraries that already exist in legacy code can be easily imported into LabVIEW, LabVIEW Real-Time and LabVIEW FPGA.

### Call Library Function Node

LabVIEW users can leverage the Call Library Function Node to call DLLs on a Windows machine or a Real-Time embedded controller.  This node is used to create an interface in LabVIEW to call existing libraries or new libraries specifically written for use with LabVIEW. The Call Library function node shown below takes in a four byte floating point number and returns its square.

Figure 3.  The Call Library Function Node can be used in LabVIEW to import legacy code

### Formula Node

The Formula Node can be used for algorithm development in both LabVIEW and LabVIEW Real-Time. The Formula Node is a convenient text-based node that is used to perform mathematical operations on the LabVIEW block diagram. You do not have to access any external code or applications, and you do not have to wire low-level arithmetic functions to create equations. In addition to text-based equation expressions, the Formula Node can accept text-based versions of if statements, while loops, for loops, and do loops, which are familiar to C programmers.

Figure 4. The Formula Node Uses a Syntax which is Familiar to C Programmers

Formula Nodes are useful for equations that have many variables or are otherwise complicated and for using existing text-based code. You can copy and paste the existing text-based code into a Formula Node rather than recreating it graphically.

### HDL Node

The HDL Interface Node enables users to integrate algorithms or applications written in a hardware description language (HDL) into LabVIEW FPGA. You can enter HDL code directly into the HDL Interface Node, or you can refer to external HDL files.  In the example shown below, an HDL input node includes VHDL code to add two 32-bit numbers and returns the result.

Figure 5.  The HDL Node Allows Users to Import HDL Code in LabVIEW FPGA