TY - GEN
T1 - Sampling-based planning, control, and verification of hybrid systems
AU - Branicky, Michael S.
AU - Curtiss, Michael M.
AU - Levine, Joshua
AU - Morgan, Stuart
N1 - Funding Information:
1 Partially supported by NSF grant CCR-0208919. 2 Corresponding Author: [email protected]
Funding Information:
This work was partially supported by the NSF Embedded and Hybrid Systems program, under the direction of Dr. Helen Gill (grant CCR-0208919); it does not necessarily reflect the views of the NSF.
PY - 2005
Y1 - 2005
N2 - 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.
AB - 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.
KW - Complexity
KW - Computational methods and tools
KW - Discrete spaces
KW - Hybrid systems
KW - Motion planning
KW - Sampling-based planning
KW - Verification
UR - http://www.scopus.com/inward/record.url?scp=79960728794&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=79960728794&partnerID=8YFLogxK
U2 - 10.3182/20050703-6-cz-1902.00330
DO - 10.3182/20050703-6-cz-1902.00330
M3 - Conference contribution
AN - SCOPUS:79960728794
SN - 008045108X
SN - 9780080451084
T3 - IFAC Proceedings Volumes (IFAC-PapersOnline)
SP - 271
EP - 276
BT - Proceedings of the 16th IFAC World Congress, IFAC 2005
PB - IFAC Secretariat
ER -