There are many opportunities for automation in mining, construction, excavation, military scouting, space exploration, and material transport. These applications consist of work machines or navigators operating in dynamically changing environments for which there may be little if any accurate information available to the machines before they commence operation. In the face of this uncertainty, the machines make the best plans possible from all prior information and assumptions and begin execution. As more information is acquired through sensing, the machines have the opportunity improve their plans to yield better performance.
Unfortunately, early work in planning for robots assumed that the robot's world was known and fixed at the time the plan was to be generated. If during the execution of the plan, the robot discovered a discrepancy between the assumed world state and the true state, it either had to heuristically modify the plan or replan from scratch. The problem with the former is that it is difficult to derive good heuristics which work all of the time and are optimal, and the problem the latter is that it is too computationally expensive for real-time operation.
If it weren't for the computational limitations, replanning from scratch would be the right idea, since it guarantees optimal plan generation and execution given all known information at the time it is acquired. The D* algorithm (Dynamic A*) was developed to provide this capability, but in real-time. D* is a planning algorithm that produces an initial plan based on known and assumed information, and then incrementally repairs the plan as new information is discovered about the world. The repaired plan is guaranteed to be optimal and is functionally equivalent to replanning from scratch. D* is fast because for the applications given, discrepancies are generally discovered by sensors carried on-board the robot and thus impact the portion of the plan "local" to the robot's current state; therefore, most of the time only the near-term portion of the existing plan is affected.
Consider an application where a mobile robot must move from a starting location to a goal location with no a priori information about its environment. Initially, the robot plans a straight-line path to the goal, and the robot begins driving the path with its sensors operating. Whenever it discovers an obstacle, the robot stores this information in its "map", and then replans the remaining portion of the path using all accumulated map information. Eventually, the robot reaches the goal or discovers that it cannot. The problem is that for cluttered environments, the robot may discover a new obstacle in every sensor image. Due to its incremental nature, D* is able to repair these plans rapidly to permit continuous operation. Experimental tests show that D* is several hundred times faster than replanning from scratch for large problems.
The D* algorithm is illustrated below. The first figure shows an environment cluttered with obstacles shown in gray. The robot starts at the center of the left wall and heads for the goal in the center of the right wall. In this case, the obstacles are known a priori, so the robot can plan the optimal path (shown in black) before it begins moving. This path is known as "omniscient optimal" since it is the shortest path given full and complete information.
But what if the robot does not have a map of the environment? In the figure below, the robot initially assumes that the environment is devoid of obstacles and plans the shortest path. As it follows the path, it scans for obstacles. The D* algorithm is used to replan each time a discrepancy is seen. The obstacles detected by the robot's sensor are shown in gray. This path is known as "optimistic optimal" since the robot assumed there were no obstacles until they were sensed. Although this path is longer than the omniscient optimal path above, it is still optimal in the sense that at all times the robot followed an optimal path to the goal given all information known in aggregate at each decision point.
The D* algorithm can be applied to continuous cost environments in addition to binary (obstacle/free space) environments. The figure below shows a cost map for fractally-generated terrain. The white areas are easy to traverse, the black areas are prohibitively expensive to traverse, and the gray areas represent the range of values in between. The figure shows the omniscient optimal path through the terrain from the lower left corner to the upper right.
The figure below shows the optimistic optimal case, where the robot assumes the entire environment is "white" until its sensor reports otherwise. The cost of this traverse is roughly twice that of the omniscient optimal one. Note that the robot ends up in several cul-de-sacs and must backtrack out of them. Note also that the robot must replan for literally every step taken, since most of the environment is not "white".
The figure below shows a case where the robot has a coarse map of the environment before it begins its traverse. The coarse map was created by averaging cost values from the environment in each rectangle and could result from a satellite or airplane flyover of the area. This coarse map provides enough information to avoid most cul-de-sacs, and the resultant path is only slightly higher- cost than omniscient optimal.
The above application was tested on a real robot, the NAVigational LABoratory II (NAVLAB II). D* was combined with a laser rangefinder-based obstacle avoidance module, and the system drove 1.4 kilometers in a cluttered environment to find a goal given no prior map information. The traverse is shown in the figure below.
Finally, my graduate student Barry Brumitt is developing a real-time dynamic planner for his Ph.D. thesis to handle multiple robots and multiple goals. The GRAMMPS system dynamically modifies the assignment of robots to goals as more information is discovered about the environment.
Back to home page.