Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Search Graph Formation for Minimizing the Complexity of Planning



Alberto Lacaze, Stephen B. Balakirsky


A large number of path planning problems are solved by the use of graph based search algorithms. There are a variety of techniques available to optimize the search within these graphs as well as thorough studies of thecomplexity involved in searching through them. However, little effort has been dedicated to constructing the graphs so that the results of searching will be optimized.The commonly used approach for the evaluation of complexity assumes that the complexity of a path planner can be evaluated by the number of nodes inthe graph. However, in many path planning problems (especially in complex, dynamic environments) the evaluation of the cost of traversing edges is the major culprit of computational complexity. In this paper we will assume that the complexity associated with the computation of cost of traversing an edge is significantly larger than the overhead of searching through the graph. This assumption creates non-trivial complexity results that allowsto optimize the creation of the graph based on the computational power available.We will present a numerical evaluation of several graph creation algorithms including the commonly used four and eight connected grid. Differentscenarios for which ground truth is available are explored. Comparison among the graph creation algorithms reveals serious downfalls that arecommon practice throughout the literature.
Proceedings Title
Performance Metrics for Intelligent Systems, Workshop | | | NIST
Conference Dates
August 14-16, 2000
Conference Title
Performance Metrics for Intelligent Systems


complexity, evaluation, path planning, planning graphs, robotics


Lacaze, A. and Balakirsky, S. (2000), Search Graph Formation for Minimizing the Complexity of Planning, Performance Metrics for Intelligent Systems, Workshop | | | NIST, [online], (Accessed April 12, 2024)
Created August 1, 2000, Updated February 17, 2017