Sampling-based planning, control and verification of hybrid systems
Publication: IEE Proceedings - Control Theory and Applications
Abstract
A sampling-based approach to planning, control and verification inspired by robotics motion planning algorithms such as rapidly exploring random trees (RRTs) and probabilistic roadmaps (PRMs) is surveyed. With the focus on RRTs, how to adapt them to solve standard non-linear control problems is demonstrated. RRTs are extended to purely discrete spaces (replacing distance metrics with cost-to-go heuristic estimates and substituting local planners for straight-line connectivity) and computational experiments comparing them to conventional methods, such as A* are provided. Finally, RRTs are extended to the case of hybrid systems and our modifications to LaValle's motion strategy library to allow for hybrid planning and verification are described. The work on the coverage and optimality properties of sampling-based techniques is also reviewed.
Get full access to this article
View all available purchase options and get full access to this article.
References
1.
LaValle S.M. Rapidly-exploring random trees: a new tool for path planning Iowa, USA 1998 TR 98-11
2.
LaValle S.M. and Kuffner J.J. Randomized kinodynamic planning Proc. IEEE Int. Conf. on Robotics and Automation 1999 473-479
3.
LaValle S.M. and Kuffner J.J. Rapidly-exploring random trees: progress and prospects Proc. Workshop Algorithmic Foundations of Robotics 2000
4.
Kuffner J.J. and LaValle S.M. RRT-connect: an efficient approach to single-query path planning Proc. IEEE Int. Conf. on Robotics and Automation 2000 San Francisco, CA 995-1001
5.
LaValle S.M. and Kuffner J.J. Donald B.R., Lynch K.M., and Rus D. Rapidly-exploring random trees: progress and prospects Algorithmic and computational robotics: new directions 293-308 A.K. Peters Wellesley, Massachusetts 2001
6.
Kavraki L.E., Svestka P., Latombe J.-C., and Overmars M.H. Probabilistic roadmaps for path planning in high-dimensional configuration spaces IEEE Trans. Robot. Autom. 12 4 566-580 1996
7.
Bekris K.E., Chen B.Y., Ladd A.M., Plaku E., and Kavraki L.E. Multiple query probabilistic roadmap planning using single query planning primitives Proc. IEEE/RSJ Intl. Conf. on Intelligent Robots and Systems 2003 Las Vegas, NV 656-661
8.
LaValle S.M. and Branicky M.S. On the relationship between classical grid search and probabilistic roadmaps Proc. Workshop Algorithmic Foundations of Robotics December 2002
9.
LaValle S.M., Branicky M.S., and Lindeman S.R. On the relationship between classical grid search and probabilistic roadmaps Int. J. Robot. Res. 23 7–8 673-692 2004
10.
Branicky M.S. and Curtiss M.M. Nonlinear and hybrid control via RRTs Proc. Int. Symp. Mathematical Theory of Networks and Systems 12-16 August 2002 South Bend, IN
11.
Curtiss M.M. Motion planning and control using RRTs M.S. Project report Case Western Reserve University Cleveland, OH May2002 http://dora.cwru.edu/msb/pubs/mmcMS.pdf
12.
Morgan S.B. and Branicky M.S. Sampling-based planning for discrete spaces Proc. IEEE/RSJ Int. Conf. Intelligent Robots and Systems 28 September-4 October 2004 Sendai, Japan
13.
Morgan S.B. Sampling-based planning for discrete spaces April2004 Department of Electrical Engineering and Computer Science, Case Western Reserve University Cleveland, OH M.S., http://dora.cwru.edu/msb/pubs/sbmMS.pdf
14.
Branicky M.S., Curtiss M.M., Levine J., and Morgan S. Sampling-based planning and control Proc. Twelfth Yale Workshop on Adaptive and Learning Systems 28-30 May 2003 New Haven, CT
15.
Levine J.A. Sampling-based planning for hybrid systems Sept.2003 Department of Electrical Engineering and Computer Science, Case Western Reserve University Cleveland, OH M.S., http://dora.cwru.edu/msb/pubs/jalMS.pdf
16.
Branicky M.S., Curtiss M.M., Levine J., and Morgan S. RRTs for nonlinear, discrete, and hybrid planning and control Proc. IEEE Conf. on Decision and Control 9-12 Dec. 2003 Lahaina, HI
17.
Branicky M.S., LaValle S.M., Olson K., and Yang L. Quasi-randomized path planning Proc. IEEE Int. Conf. Robotics and Automation 2001 Seoul, Korea 1481-1487
18.
Reif J.H. Complexity of the mover's problem and generalizations Proc. IEEE Symp. on Foundation of Computer Science 1979 421-427
19.
Branicky M.S., Frazzoli E., and LaValle S.M. Geometric and algorithmic techiques for design and verification of hybrid control systems NSF Proposal 0208891 5 December 2001
20.
Bhatia A. and Frazzoli E. Alur R. and Pappas G.J. Incremental search methods for reachability analysis of continuous and hybrid systems Hybrid systems: computation and control 142-156 Springer-Verlag Philadelphia, PA 2004 2993 Lecture Notes in Computer Science
21.
Branicky M.S., Curtiss M.M., Levine J., and Morgan S. Sampling-based planning, control, and verification of hybrid systems Proc. IFAC World Congress 2005 Prague
22.
Kim J. and Esposito J.M. Adaptive sample bias for rapidly-exploring random trees with applications to test generation Proc. American Control Conference 2005 Portland, OR
23.
Lindemann S.R. and LaValle S.M. Incrementally reducing dispersion by increasing Voronoi bias in RRTs Proc. IEEE Int. Conf. on Robotics and Automation 2004 New Orleans 3251-3257
24.
Spong M.W. Swing up control of the acrobot Proc. IEEE Intl. Conf. Robotics and Automation 1984 San Diego, CA 2356-2361
25.
Sutton R.S. and Barto A.G. Reinforcement learning MIT Press Cambridge, MA 1998
26.
Latombe J.-C. Robot motion planning Kluwer Academic Publishers Norwell, MA 1991
27.
Russell S.P. and Norvig P. Artificial intelligence: a modern approach Prentice-Hall Upper Saddle River, NJ 2003
28.
Branicky M.S. Studies in hybrid systems: modeling, analysis, and control June1995 M.I.T. Cambridge, MA Sc.D.
29.
Branicky M.S., Borkar V.S., and Mitter S.K. A unified framework for hybrid control: model and optimal control theory IEEE Trans. Autom. Control 43 1 31-45 1998
30.
Frazzoli E., Dahleh M.A., and Feron E. A hybrid control architecture for aggressive maneuvering of autonomous helicopters Proc. IEEE Conf. Decision and Control December 1999 Phoenix 2471-2476
31.
LaValle S.M. Motion strategy library 2003 http://msl.cs.uiuc.edu/msl/
32.
Alur R., Henzinger T.A., and Ho P.-H. Automatic symbolic verification of embedded systems Proc. 14th Annual Real-time Systems Symp. 1993 2-11
33.
Henzinger T.A., Kopke P.W., Puri A.P., and Varaiya P. What's decidable about hybrid automata? Proc. 27th ACM Symp. on Theory of Computing 1995 373-383
Information and Authors
Information
Published in
Copyright
© The Institution of Engineering and Technology.
History
Published in print: 11 September 2006
Published online: 31 March 2024
Inspec keywords
Keywords
Authors
Metrics and Citations
Metrics
Citations
Download article citation data for:
If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.
View Options
Access content
Please select your options to get access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.