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 thumb|250 px|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: Turn to the nearest waypoint if there is one left. If there is no waypoint left, stop. Move toward the nearest waypoint. If there is something in the way: Go around it. After every 1.5 body lengths, go to step 1. If the robot has reached the waypoint: Remove the reached waypoint from the list. 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 roboticidehttp://www.newscientist.com/article/dn4337-smart-software-helps-robots-dodge-collisions.html Smart software helps robots dodge collisions Duncan Graham-Rowe 2003. 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 problemshttp://webdiis.unizar.es/~jminguez/810.pdf A “Divide and Conquer” Strategy based on Situations to achieve Reactive Collision Avoidance in Troublesome Scenarios Javier Minguez, Javier Osuna, Luis Montano 2004. 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 treeshttp://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=00506853 A Comprehensive Robot Collision Avoidance Scheme by Two-Dimensional Geometric Modeling Sabyasachi Ghoshray, K.K. Yen 1996 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. thumb|250 px|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