Sampling-Based Planning, Control, and Verification of Hybrid Systems
| Authors: | Branicky Michael S., Case Western Reserve University, United States
Curtiss Michael M., Case Western Reserve University, United States
Levine Joshua, Case Western Reserve University, United States
Morgan Stuart, Case Western Reserve University, United States |
|---|
| Topic: | 1.3 Discrete Event and Hybrid Systems |
|---|
| Session: | Analysis and Design of Hybrid Systems I |
|---|
| Keywords: | Sampling-based planning, motion planning, hybrid systems, discretespaces, complexity, verification, computational methods and tools |
|---|
Abstract
In this paper, we survey a planning, control, and verificationapproach in terms of sampling-based tools, such as Rapidly-exploringRandom Trees (RRTs) and Probabilistic RoadMaps (PRMs). We reviewRRTs and PRMs for motion planning and show how to use them tosolve standard nonlinear control problems. We extend themto the case of hybrid systems and describe our modifications toLaValle's Motion Strategy Library to allow for hybrid planningand verification. Finally, we extend them to purely discretespaces (replacing distance metrics with cost-to-go heuristicestimates and substituting local planners for straight-lineconnectivity) and provide computational experiments comparingthem to conventional methods, such as A*. We also review ourwork on the coverage, optimality properties, and computationalcomplexity of sampling-based techniques.
