ABSTRACT
Advances in robotics, arti cial intelligence, and computer vision have stimulated considerable interest in the problems of robot motion and shortest path planning [Latombe 1991]. The path-planning problem is concerned with nding paths connecting different locations in an environment (e.g., a network, a graph, or a geometric space). Depending on speci c applications, the desired paths often need to satisfy some constraints (e.g., obstacleavoiding) and optimize certain criteria (e.g., variant distance metrics and cost functions).
