Sampling-based planning, control, and verification of hybrid systems

Michael S. Branicky, Michael M. Curtiss, Joshua Levine, Stuart Morgan

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

6 Scopus citations

Abstract

in this paper, we survey a planning, control, and verification approach in terms of sampling-based tools, such as Rapidly-exploring Random Trees (RRTs) and Probabilistic RoadMaps (PRMs). We review RRTs and PRMs for motion planning and show how to use them to solve standard nonlinear control problems. We extend them to the case of hybrid systems and describe our modifications to LaValle's Motion Strategy Library to allow for hybrid planning and verification. Finally, we extend them to purely discrete spaces (replacing distance metrics with cost-to-go heuristic estimates and substituting local planners for straight-line connectivity) and provide computational experiments comparing them to conventional methods, such as A*. We also review our work on the coverage, optimality properties, and computational complexity of sampling-based techniques.

Original languageEnglish (US)
Title of host publicationProceedings of the 16th IFAC World Congress, IFAC 2005
PublisherIFAC Secretariat
Pages271-276
Number of pages6
ISBN (Print)008045108X, 9780080451084
DOIs
StatePublished - 2005
Externally publishedYes

Publication series

NameIFAC Proceedings Volumes (IFAC-PapersOnline)
Volume16
ISSN (Print)1474-6670

Keywords

  • Complexity
  • Computational methods and tools
  • Discrete spaces
  • Hybrid systems
  • Motion planning
  • Sampling-based planning
  • Verification

ASJC Scopus subject areas

  • Control and Systems Engineering

Fingerprint

Dive into the research topics of 'Sampling-based planning, control, and verification of hybrid systems'. Together they form a unique fingerprint.

Cite this