2009 IGVC

Like its predecessor, Argos employs a three-pronged approach to navigation: a cost map is generated to represent the environment, a desired waypoint is selected, and finally, the path planner calculates an optimal trajectory to the targeted waypoint.

While the path generation and waypoint selection mechanisms remain largely the same, Argos significantly improves upon Kratos in its path planning stage. As a replacement for Kratos’s simplistic A* path planner, Argos uses the Dynamic A* Lite algorithm. By planning backwards from the waypoint, D* Lite avoids unnecessary searches even as the robot moves, increasing computational speed without sacrificing results.

In addition, Argos also employs field searching in its path planning stage. Rather than restrict the search nodes to cost cell centroids, which would only result in paths that moved neatly from centroid to centroid, and only allow for turns in increments of 45 degrees, field search is considerably more flexible. A traditional path planning algorithm searches for the minimum cost path from each of its neighbors s’. Field search also considers paths to s from any point on the boundary between neighboring nodes, and linearly interpolates the depth of novel predecessors to determine cost. This allows for a smoother, more optimal path.

To offset the additional computational cost posed by this more thorough search, Argos optimizes using such methods as a binary heap, cached costs, and compiling with the SSE3 instruction set extensions.

All in all, our Field D* path planner operates at roughly 10 Hz, about the same speed as the less sophisticated A* planner used by Kratos.

2008 IGVC

The obstacles in the field of view of Kratos’ camera are detected by our vision algorithms and then represented as a cost map. The field of view of the camera is represented with a grid, with each box or “cell” corresponding to approximately a 10 cm x 10 cm square. Each cell is then assigned a cost based upon whether there is a detected obstacle occupying it. The more obstacle points in a cell, the higher its cost is.

 

After a cost map has been generated, Kratos plans a path through it to the next waypoint. This is accomplished by performing an A* graph search from its current position to its destination waypoint. In performing this search, multiple paths of the same length may be produced as solutions. Since the path is constantly being re-planned, there is a possibility that in the worst case, the planner would alternate between different paths of the same length. In that case, the robot would oscillate between the two paths, never converging to a single path, and ultimately crash into the obstacle.

To mitigate the possibility of this outcome, Kratos employs a “path straightness” heuristic, which measures how close nodes in the path are to the straight-line path between the current position and the destination waypoint. Therefore, path arbitration problems were always settled in favor of straighter paths. The image below shows an example of a path planned around an obstacle in the cost map.

Optimizations allowed our planner to run at between roughly 5 Hz and 12 Hz, depending on how cluttered of an obstacle field the robot was traversing.

2007 Urban Challenge

The same system as Grand Challenge was used on Prospect 12 for the Urban Challenge.

2005 Grand Challenge

Prospect Eleven’s navigation system guides the vehicle along the GPS route provided by DARPA while avoiding obstacles.

First, the software builds a map of the vehicle’s surroundings using sensor data. This map is binary — it divides the world into areas the vehicle can pass through, and areas that are impassable.

Then the map is converted to a polar representation. Discontinuities are identified and formed into safe ‘gaps’ in the terrain around the vehicle. Prospect Eleven aims for one of these safe gaps.

To produce the final steering command, Prospect Eleven calculates a steering angle that will track the GPS course centerline. This requested steering angle is filtered through the calculated gaps to ensure it does not result in a collision.