Planning under topological constraints using beam-graphs

Venkatraman Narayanan, Paul Vernaza, Maxim Likhachev, Steven M. Lavalle

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


We present a framework based on graph search for navigation in the plane with a variety of topological constraints. The method is based on modifying a standard graph-based navigation approach to keep an additional state variable that encodes topological information about the path. The topological information is represented by a sequence of virtual sensor beam crossings. By considering classes of beam crossing sequences to be equivalent under certain equivalence relations, we obtain a general method for planning with topological constraints that subsumes existing approaches while admitting more favorable representational characteristics. We provide experimental results that validate the approach and show how the planner can be used to find loop paths for autonomous surveillance problems, simultaneously satisfying minimum-cost objectives and in dynamic environments. As an additional application, we demonstrate the use of our planner on the PR2 robot for automated building of 3D object models.

Original languageEnglish (US)
Title of host publication2013 IEEE International Conference on Robotics and Automation, ICRA 2013
Number of pages7
StatePublished - Nov 14 2013
Event2013 IEEE International Conference on Robotics and Automation, ICRA 2013 - Karlsruhe, Germany
Duration: May 6 2013May 10 2013

Publication series

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


Other2013 IEEE International Conference on Robotics and Automation, ICRA 2013

ASJC Scopus subject areas

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


Dive into the research topics of 'Planning under topological constraints using beam-graphs'. Together they form a unique fingerprint.

Cite this