Robotics/Navigation/Collision Avoidance

Collision avoidance, in comparison to collision detection, is what is done after a possible collision is detected. Possible collisions will depend on the shape and size of both the object and robot as well as the position and motion projection of the object and the robot. When making an attempt to avoid an obstacle, there are many decisions to face. The decisions available depend on the available paths the robot can take to avoid the obstruction. These paths can either be determined upon the robot’s realization of the obstruction or, in case all of the obstructions’ positions are known, once the map is loaded. Finding the “correct” path to use can be troublesome depending on which algorithm is used and the granularity associated with it.

Basic Idea

If there is an object in the robot’s way, avoid it.

Essentially, this is the basic idea in collision avoidance. However, this simple matter to humans is incredibly complex in the computer world. Which algorithm is best in avoiding obstacles? Which is least complex, most efficient? Which algorithm can utilize the robot’s full capabilities effectively? All of these are questions one should ask when searching for a valuable collision avoidance algorithm.

Example Algorithm

File:Figure1.GIF

Example algorithm being put to use using Player/Stage

In the figure to the right, a simple “tank-drive” robot is presented making it’s way to three pre-determined waypoints. The robot’s algorithm is a dignified version of the simple one-liner given at the beginning of this section:

1. Turn to the nearest waypoint if there is one left.
   1. If there is no waypoint left, stop.
   2. Move toward the nearest waypoint.
2. If there is something in the way:
   1. Go around it.
   2. After every 1.5 body lengths, go to step 1.
3. If the robot has reached the waypoint:
   1. Remove the reached waypoint from the list.
   2. Go to step 1.

Albeit this algorithm works well for an over-simplified map where all obstacles are simple geometric shapes, in more complex scenarios it may not fare as well. For instance, nestling a waypoint in the middle of a U-shaped obstacle would cause this algorithm to never end.

Major Problem

With robots having greater and greater importance in our everyday lives, it is no wonder that collision avoidance (particularly dealing with human safety) is becoming an increasingly greater concern. Such concerns are not to be taken lightly. There is already one death associated with roboticide.

In addition to safety, other concerns can be generated:

• Collision Avoidance Algorithmic Complexity
• Computer Power
• Sensor Accuracy / Throughput
• Sensor Data Interpretation

Of course, as the algorithmic complexity of the collision avoidance algorithm increases, so does the required computer power. Some researchers are even finding it beneficial to use multiple processors in parallel (parallel processing) to “divide and conquer” such problems.

Sensor accuracy and throughput is becoming less a threat to successful collision avoidance. However, this doesn’t mean it is non-existent. During the process of engineering a collision-avoiding robot, trade-offs can be made that could potentially compromise the effectiveness of the sensors in how the robot behaves.

Detection vs. Avoidance

Collision detection is simply the act of surveying the known vicinity of the robot and detecting the presence (or absence) of a possible collision. In order for a robot to avoid a collision, a collision must first be detected. Without collision detection, it doesn’t seem reasonable to have collision avoidance because there wouldn’t be anything to avoid (in the robot’s scope).

Collision avoidance is the plan for action the robot takes to evade the oncoming collision. As previously stated, there is no need for collision avoidance if there are no collisions to avoid.

Collision Avoidance Algorithms

Quad Trees

The use of quad trees allows for a simple collision avoidance algorithm. An approximation technique used here uses a type of data structure called a quad tree. A quad tree is similar to that of a binary tree except that a quad tree has four child nodes for each parent instead of just two.

Each child node is represented by a square of pixels in a “top-down” image of the robot’s surrounding landscape. Each square simply acts as a binary answer to the question, “Is there any possibility for a collision inside of this square?” If the answer is yes, then the square is avoided, otherwise, the square is noted for safe travel. An example of this is given in the figure below.

File:Figure3.PNG

Approximation of a triangle using squares.

Advantages

An advantage to using this algorithm is that retreating can be done fairly easily – by climbing back up the tree and trying a different approach. Of course, in a case where all of the obstacles have been found, a minimal path can easily be created using simple distance algorithms.

Disadvantages

A disadvantage to using this algorithm is that, due to the granularity of each square of pixels, it is possible for the obstacles to be close enough such that a robot wouldn’t notice that it could actually fit through a gap.

References

• Player/Stage Wiki Page