Sampling-based reachability algorithms for control and verification of complex systems

Michael S. Branicky, Michael M. Curtiss, Joshua A. Levine, Stuart B. Morgan
13th Yale Workshop on Adaptive and Learning Systems
May, 2005

In this paper, we survey sampling-based reachability algorithms that may be used for planning, control, and verification of complex systems. These were inspired by two robotics motion planning algorithms: Rapidly-exploring Random Trees (RRTs) and Probabilistic RoadMaps (PRMs). Herein, we review RRTs and PRMs. We review our adaptations and extensions to nonlinear control problems, hybrid systems, and completely discrete problems. We also summarize our work on the properties of sampling-based techniques.

@inproceedings{BCLM05,
  address   = {New Haven, CT},
  author    = {Michael S. Branicky and Michael M. Curtiss and Joshua A. Levine and Stuart B. Morgan},
  booktitle = {13th Yale Workshop on Adaptive and Learning Systems},
  month     = {5},
  title     = {Sampling-based reachability algorithms for control and verification of complex systems},
  year      = {2005}
}