Efficient search and hierarchical motion planning using dynamic single-source shortest paths trees

Michael Barbehenn, Seth Andrew Hutchinson

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

In this paper we examine the search aspects of hierarchical motion planning. All previous robot motion planners based on approximated cell decomposition exhibit redundancy between successive searches for a sequence of adjacent EMPTY cells, In this paper we present a search method that eliminates this redundancy. Our search method is founded on the ability to efficiently maintain a single-source shortest paths tree embedded in the connectivity graph that is subject to the dynamic modifications that result from incremental subdivision of cells. The convergence of our algorithm is controlled by the vertex cost function, which relies on an estimate for the proportion of free space in a cell.

Original languageEnglish (US)
Title of host publicationProceedings - IEEE International Conference on Robotics and Automation
Editors Anon
PublisherPubl by IEEE
Pages566-571
Number of pages6
ISBN (Print)0818634529
StatePublished - Jan 1 1993
EventProceedings of the IEEE International Conference on Robotics and Automation - Atlanta, GA, USA
Duration: May 2 1993May 6 1993

Publication series

NameProceedings - IEEE International Conference on Robotics and Automation
Volume1
ISSN (Print)1050-4729

Other

OtherProceedings of the IEEE International Conference on Robotics and Automation
CityAtlanta, GA, USA
Period5/2/935/6/93

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Artificial Intelligence
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Efficient search and hierarchical motion planning using dynamic single-source shortest paths trees'. Together they form a unique fingerprint.

Cite this