Let G(V, E) be a directed graph in which each vertex has a nonnegative weight. The cost of a path between two vertices in G is the sum of the weights of the vertices on that path. We show that, for such graphs, the time complexity of Dijkstra's algorithm (E.W. Dijkstra, 1959), implemented with a binary heap, is O(|E|+|V|log|V|).

In this paper we introduce a new class of geometric robot motion planning problems that we call incremental problems. We also introduce the concept of incremental algorithms to solve this class of problems. As an example, we describe an incremental critical curve based exact cell decomposition algorithm for a line segment robot moving freely amidst polygonal obstacles. In the example, after computing an initial representation of the robot's free space, the algorithm maintains the representation as obstacles are moved between planning problems. The cost to maintain the representation is expected to be small relative to the cost of its initial construction.

Hierarchical approximate cell decomposition is a popular approach to the geometric robot motion planning problem. In many cases, the search effort expended at a particular iteration can be greatly reduced by exploiting the work done during previous iterations. In this paper, we describe how this exploitation of past computation can be effected by the use of a dynamically maintained single-source shortest paths tree. We embed a single-source shortest paths tree in the connectivity graph of the approximate representation of the robot configuration space. This shortest paths tree records the most promising path to each vertex in the connectivity graph from the vertex corresponding to the robot's initial configuration. At each iteration, some vertex in the connectivity graph is replaced with a new set of vertices, corresponding to a more detailed representation of the configuration space. Our new, dynamic algorithm is then used to update the single-source shortest paths tree to reflect these changes to the underlying connectivity graph.>

In this paper, we present a new hybrid motion planner that is capable of exploiting previous planning episodes when confronted with new planning problems. Our approach is applicable when several (similar) problems are successively posed for the same static environment, or when the environment changes incrementally between planning episodes. At the heart of our system lie two low-level motion planners: a fast, but incomplete planner LOCAL, and a computationally costly (possibly resolution) complete planner GLOBAL. When a new planning problem is presented to our planner, an efficient meta-level planner MANAGER decomposes the problem into segments that are amenable to solution by LOCAL. This decomposition is made by exploiting a task graph, in which successful planning episodes have been recorded. In cases where the decomposition fails, GLOBAL is invoked. The key to our planner's success is a novel representation of solution trajectories, in which segments of collision-free paths are associated with the boundary of nearby obstacles. Thus we effectively combine the efficiency of one planner with the completeness of another to obtain a more efficient complete planner.>

GINKO, an integrated learning and planning system that has been applied to an autonomous mobile robot domain, is described. The goal of GINKO's learning system is to partition the robot's configuration space into regions in which actions exhibit a uniform qualitative behavior. This partitioning is performed by an inductive learning algorithm that classifies regions of the configuration space with regard to the effects of the robot's actions when executed in those regions. GINKO's learning is driven by its attempts to perform tasks. Thus, the learned effects of actions are directly applicable to normal system performance.>