ACM Computing Surveys 28A(4), December 1996, http://www.acm.org/surveys/1996/ChenDeveloping/. Copyright © 1996 by the Association for Computing Machinery, Inc. See the permissions statement below.

Danny Z. Chen

---

Abstract: Computing shortest paths is a fundamental topic in computational geometry and arises in many applications. We assess the status of the current research on solving geometric shortest path problems and suggest several possible directions for future work on these and related problems.

Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems - Geometrical problems and computations

General Terms: Algorithms, Design, Theory

Additional Key Words and Phrases: Computational geometry, shortest paths, optimization, implementation

---

The problem of path planning is in general concerned with finding paths connecting different locations in an environment (e.g., a network, a graph, or a geometric space). Depending on the specific applications, the desired paths often need to satisfy certain constraints (e.g., obstacle-avoiding) and optimize certain combinations of criteria (e.g., various distance metrics and cost functions). A well-known example of path planning problem is that of computing shortest paths in graphs [Fredman 1987] (i.e., finding a path in a graph connecting two vertices with the minimum total length). The problems of planning shortest paths arise in many disciplines, and in fact are one of the several most powerful tools for modeling combinatorial optimization problems.

The geometric version of the shortest path problem can be stated as follows: Given a d-dimensional space scattered with obstacles, compute a path P connecting two points p and q such that the path P does not intersect the interior of any obstacle and that the total length of P (based on a certain metric such as the Euclidean) is minimized. Figure 1 gives an example of such a path in the plane. There are many variations of this problem.

  
Figure 1: A shortest obstacle-avoiding path connecting points p and q.

Computing shortest paths is one of the most fundamental topics in computational geometry. Geometric shortest path problems play an important role in many practical applications (e.g., geographical information systems, operations research, plant and facility layout, robotics, transportation, and VLSI design). Also, they have significant connections with other fundamental topics in computational geometry (e.g., convexity, visibility, Voronoi diagrams, triangulation, and geometric optimization) and with other disciplines (e.g., graph theory, combinatorial optimization, and networks). For example, geometric path planning problems address quite naturally the combinatorial and algorithmic aspects of robot motion and navigation.

In the past two decades, a great deal of research work has been done on solving geometric shortest path problems, especially for the planar and 3-dimensional (3-D) settings (see [Mitchell 1996] for a survey). For computing shortest paths in the plane with polygonal obstacles, Hershberger and Suri [Hershberger 1993] developed an optimal O(n log n) time algorithm (where n is the total number of obstacle vertices). For computing shortest paths in the 3-D space with polyhedral obstacles, Canny and Reif [Canny 1987] showed that the problem is NP-hard, and several efficient approximation algorithms have been discovered (e.g., [Choi 1994]). However, despite of the significant progress already made, much research work on geometric shortest paths and related problems remains to be done. Besides the importance and applicability of these problems, the following reasons also motivate further research in this area.

1. There are still many important and useful geometric shortest path problems for which efficient theoretical solutions remain largely elusive. Examples of such problems are various geometric shortest path queries [Chen 1995a], shortest paths in 3-D and higher dimensional spaces [Canny 1987, Choi 1994], and geometric paths that are optimal under multiple criteria (e.g., distance, number of links, angle, etc). It is not yet clear how commonly-used approaches (e.g., visibility graphs [Ghosh 1991, Lozano-Perez 1979] and shortest path maps [Hershberger 1993]) shall be applied to solve these problems efficiently. Since many of such problems have been shown to be NP-hard, efficient techniques for computing their approximate solutions are particularly useful. Approximate shortest paths are of great practical and theoretical value, and often require different methods to compute.
2. From the viewpoint of practical applications, many theoretically efficient geometric shortest path algorithms are not without considerable drawbacks. One such potential drawback is that these theoretical solutions often are quite environment-specific. For instance, many path algorithms extensively exploit the structures of specific geometric environments (e.g., obstacles are polygons on a perfectly ``flat'' land, obstacles are stationary and are of fixed shapes, etc), and hence their efficiency hinges heavily on certain properties of these (probably simplified) environments. Certainly, algorithms of this kind may be useful for some application-specific systems (e.g., VLSI), and they may also reveal structures that could be utilized by geometric path planning algorithms for other types of applications and environments. However, it is also quite possible that algorithms which are too environment-specific can be difficult to extend to more complex environments, which very likely are what people must deal with in practical applications. For example, in real robotic path planning, obstacle shapes can be very complicated and the paths may have to go up and down on various landscapes. Therefore, the cost of a path may depend on many factors (e.g., distance, shapes and types of areas passed through, slopes and directions of various subpaths). Hence, environment-specific algorithms may have limited practical applicability. Furthermore, many known path algorithms were designed for simplified versions of the problems (e.g., assume the paths are for a point robot, the motion of the robot has little constraint, etc). However, in reality, useful robots always are of various shapes and are capable of only limited movement [Hopcroft 1987, Latombe 1991] (e.g., it cannot make a turn at an arbitrary angle). Only a few (approximate) optimal path planning algorithms for robots of various shapes or with a certain constrained motion capability are known.
3. To practitioners, the costs of incorporating geometric shortest path algorithms into application systems are still overwhelmingly high. There are several potentially intimidating factors to a practitioner who would like to achieve implementation efficiency out of such algorithms. (i) There is a lack of general framework for implementing different geometric algorithms (which are usually environment or problem specific). Hence, a user would very likely have to do his/her own coding which may be difficult to share with other potential users. (ii) Many known geometric shortest path algorithms are very involved and depend on a number of other sophisticated geometric procedures and data structures (e.g., visibility, Voronoi diagrams, triangulation, space point-location, space decomposition, etc). Although some significant software development efforts have been made (e.g., LEDA), efficient and friendly software and software environments for many algorithms on which geometric shortest path solutions rely are still not yet available. The current situation is: For a practitioner to develop a program for a geometric shortest path algorithm, he/she would have to carefully implement quite a few sophisticated geometric algorithms and data structures; but, before being able to do so, he/she would also have to make a great deal of efforts to study and understand these algorithms and data structures. To many users, this can be too high a price to pay. (iii) Certain geometric shortest path algorithms involve complicated computational operations. For example, algorithms for computing approximate 3-D shortest paths may involve considerable numerical manipulation. These factors have played a big role in impeding a fast and smooth technology transfer from computational geometry to applied fields.

In view of the above reasons, we believe the following are important directions for geometric shortest path research in the coming future.

We think it is necessary to develop simple-to-implement yet reasonably efficient algorithms for more general geometric path planning systems. For many applications, the geometric environments can be very complicated, and thus algorithms hinged on specific geometric structures may be of little use. Therefore, it is highly desirable to design shortest path algorithms that work in some ``general'' geometric settings in an efficient manner. The notion of algorithmic efficiency for such solutions might depend less on the ``standard'' input size of a problem but more on the ``configuration'' of the input (e.g., an octree-like partition of a 3-D obstacle-scattered environment). The paths obtained by such approaches may not be truly shortest but may be very good approximations. The framed-quadtree and framed-octree approaches [Chen 1995b] are a few such examples that are relatively effective yet simple to implement, and could even be extended to higher dimensional spaces than 3-D.

We also believe that serious efforts must be made by the computational geometry community to reach out to applied fields, and that implementing geometric algorithms is an important step in this direction. It is very encouraging that quite a few projects on implementing geometric algorithms are currently under way. However, more efforts should also be made at a higher level of geometric software development. For example, it would be very useful if some tools are available for the automated design of computer programs for geometric shortest path problems. A user could use a ``geometric problem specification language'' to describe a problem that he/she wants to solve. Then a tool set would process this problem specification program from the user and generate target programs in a desired programming language for the needed geometric computation (like Lex and Yacc for constructing components of compilers). Such tools would greatly enhance the accessibility of geometric algorithms to many users. A base to the development of such high level design tools for geometric computing is to make geometric algorithms available not only on paper but also as software.

It is anticipated that further research on developing new algorithms and software for geometric path planning problems will have a great impact on the theoretical study and practical applications of computational geometry. In particular, such work can become relevant to the following application areas: Military applications (e.g., route planning for special operations aircrafts and vehicles), NASA's Remote Exploration and Experimentation program (e.g., autonomous spacecraft path and exploration planning), Geographical Information Systems (e.g., route planning on electronic maps), and robotics (e.g., robot motion and navigation). It is even likely for the work to touch an average person's daily life in the future (e.g., a route planner on cars for tourists or for avoiding traffic jams in daily local traveling).

Acknowledgments

References

[Canny 1987]

J. Canny and J.H. Reif, 1987. New Lower Bound Techniques for Robot Motion Planning Problems, Proc. 28th IEEE Annual Symp. Foundations of Computer Science, pp. 49-60.

[Chen 1995a]

D.Z. Chen, 1995. On the All-Pairs Euclidean Short Path Problem, Proc. 6th Annual ACM-SIAM Symp. on Discrete Algorithms, pp. 292-301.

[Chen 1995b]

D.Z. Chen, R.J. Szczerba, and J.J. Uhran Jr., 1995. Determining Conditional Shortest Paths in an Unknown, Three-Dimensional Environment Using Framed-Octrees, Proc. IEEE International Conf. on Systems, Man, and Cybernetics, pp. 4101-4106.

[Choi 1994]

J. Choi, J. Sellen, and C.-K. Yap, 1994. Approximate Euclidean Shortest Path in 3-Space, Proc. 10th Annual ACM Symp. Computational Geometry, pp. 41-48.

[Fredman 1987]

M.L. Fredman and R.E. Tarjan, 1987. Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms, Journal of the ACM, 34 (3), 596-615.

[Ghosh 1991]

S.K. Ghosh and D.M. Mount, 1991. An Output-Sensitive Algorithm for Computing Visibility Graphs, SIAM J. Comput., 20, 888-910.

[Hershberger 1993]

J. Hershberger and S. Suri, 1993. Efficient Computation of Euclidean Shortest Paths in the Plane, Proc. 34th IEEE Annual Symp. Foundations of Computer Science, pp. 508-517. An improved O(n log n) time version has also been published.

[Hopcroft 1987]

J.E. Hopcroft, J.T. Schwartz, and M. Sharir, 1987. Planning, Geometry, and Complexity of Robot Motion, Ablex Publishing, Norwood, NJ.

[Latombe 1991]

J.-C. Latombe, 1991. Robot Motion Planning, Kluwer Academic Publishers, Boston.

[Lozano-Perez 1979]

T. Lozano-Perez and M.A. Wesley, 1979. An Algorithm for Planning Collision-Free Paths among Polyhedral Obstacles, Communications of the ACM, 22, 560-570.

[Mitchell 1996]

J.S.B. Mitchell, 1996. Shortest Paths and Networks, manuscript. To appear in the CRC Handbook on Computational Geometry.

Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Publications Dept, ACM Inc., fax +1 (212) 869-0481, or permissions@acm.org.