|
Planning /
PathPlanningPath planning deals with the question of how to best move through an environment. In a robot, it the path planner is typically asked to plot a course from point A to point B, while often satisfying some constraints. The path planner then passes on waypoints to a local navigator. See Planning Hierarchy for more architectural information. However, this is not always the case, as with RRT and Gradient. At a base level, the path planner if faced with discretizing a continuous world. The types of planners can be differentiated by the way in which they discretize the world. Discretize via SpaceThis is easy to visualize as overlaying a grid on a 2D map of the area. Each grid location can either be empty (passable) or blocked by an obstacle. These algorithms will find a series of grid cells that connect point A to point B. A*A* is perhaps one of the simplest and most straight forward path planning algorithms, and is both fast and optimal. The algorithm requires an "admissible heuristic" to generate a cost estimate from the current location to the goal. The standard A* algorithm requires that the environment be discretized appropriately. The algorithm is essentially a graph traversal, with each node representing a location, and each node is connected to each of its immediate neighbors (locations that can be reached with one move by the agent). As one can imagine, how the discretization of the world is done can have great impacts: too coarse and the representation is inaccurate, too fine and the search time increases greatly. A* can be used for any graph traversal problem (and is superior to Dijkstra's Algorithm when an admissible heuristic is available). Williams and Ragno (whose work I cover on my research page) extended the algorithm to avoid nodes which share "conflicts" with previously expanded nodes. In their work, the graph represents possible failure states and the admissible heuristic is that the components are in working order. The conflicts are discrepencies between the predicted outputs and the observed outputs of the system.
D*Dynamic A* (often referred to as D*) is a variation of A* that is intended to provide for faster re-planning times. This is useful when there are unknown obstacles in the environment. A* would typically handle this situation by simply restarting, but D* takes advantage of previously computed paths to speed up the process. Unlike A*, D* begins with the goal node and works backwards to the robot. As obstacles are discovered (most likely close to the robot due to their limited sensor range), affected nodes are reevaluted and marked as RAISE since their esitmated cost may have been increased by the discovery of the obstacle. These RAISE nodes are then evaluted: first a check is made to see if a neighbor can lower their cost (avoiding the obstacle). If not, the neighboring nodes are also marked RAISE. LOWER nodes are also propogated in a similar fashion. Focused D* is a natural extension that directs the waves of propagating RAISE and LOWER nodes towards the robot, reducing the number of nodes to evaluate.
Wavefront(TODO: Maybe not really needed. Used for Gradient thought) GradientThe gradient method combines path planning with local navigation by creating waypoints which carry more information than just coordinates. The additional information is similar to that usually calculated by the local navigators, such as a vector indicating the direction and speed of travel, but can be created much more intelligently since more information is available. The gradient method creates a "slope" towards the target, much as one would envision the potential fields method, but the gradient is informed by a variant of the Wavefront planner. See the Kurt Konolige paper for more information. This planner is also used in the CARMEN Framework. Discretize via TimeThis class of path planner has the advantage of being able to represent robot state in a continuous realm. And state beyond that of just location. Orientation for example. Sigh. State space explosion. Time is used as a step. Not optimal. Non-holonomic applications. Comm with local navigator? Replaced, is it not? Does this fuck up my intro? RRTA Rapidly exploring Random Tree is well suited to continuous domains with high dimensionality. This means that the algorithm is suitable for real world applications such as driving a car, which has moment and dynamic limitations of the ways in which it can turn (cutting the wheel 90 degrees while travelling at 100 mph is generally inadvisable). While not optimal, it is fast.
Surely there is a second that I could call upon? Maybe pre-dating RRT?Glossary |