Search Graph Formation for Minimizing the Complexity of Planning

Published

August 1, 2000

Author(s)

Alberto Lacaze, Stephen B. Balakirsky

Abstract

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

Pub Type

Conferences

Download Paper

Local Download

Keywords

complexity, evaluation, path planning, planning graphs, robotics

Citation

Lacaze, A. and Balakirsky, S. (2000), Search Graph Formation for Minimizing the Complexity of Planning, Performance Metrics for Intelligent Systems, Workshop | | | NIST, [online], https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=823373 (Accessed May 13, 2026)

Additional citation formats