LQR-trees: Feedback Motion Planning via Sums-of-Squares Verification
The DOI matches its Crossref record; 28 of the 28 references it cites were found in a registry or an index.
Abstract
Advances in the direct computation of Lyapunov functions using convex optimization make it possible to efficiently evaluate regions of attraction for smooth non-linear systems. Here we present a feedback motion-planning algorithm which uses rigorously computed stability regions to build a sparse tree of LQR-stabilized trajectories. The region of attraction of this non-linear feedback policy “probabilistically covers” the entire controllable subset of state space, verifying that all initial conditions that are capable of reaching the goal will reach the goal. We numerically investigate the properties of this systematic non-linear feedback design algorithm on simple non-linear systems, prove the property of probabilistic coverage, and discuss extensions and implementation details of the basic algorithm.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Slotine, J.-J. E., & Li, W. (1991) · CERN Document Server (European Organization for Nuclear Research) · Cited by 18,975
Probabilistic roadmaps for path planning in high-dimensional configuration spaces
Kavraki, L. E., Svestka, P., Latombe, J.-C., & Overmars, M. H. (1996) · IEEE Transactions on Robotics and Automation · doi:10.1109/70.508439 · Cited by 6,343
LaValle, S. M. (2006) · Cambridge University Press eBooks · doi:10.1017/cbo9780511546877 · Cited by 5,211
Interior-Point Polynomial Algorithms in Convex Programming
Nesterov, Y., & Nemirovskii, A. (1994) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611970791 · Cited by 4,334
LaValle, S. M. (2006) · Cited by 4,177
SNOPT: An SQP Algorithm for Large-Scale Constrained Optimization
Gill, P. E., Murray, W., & Saunders, M. A. (2005) · SIAM Review · doi:10.1137/s0036144504446096 · Cited by 2,834
Optimal Control: Linear Quadratic Methods
Anderson, B. D. O., & Moore, J. B. (1979) · Cited by 2,823
Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization
Parrilo, P. A. (2000) · doi:10.7907/2k6y-ch43 · Cited by 1,802
System analysis via integral quadratic constraints
Megretski, A., & Rantzer, A. (1997) · IEEE Transactions on Automatic Control · doi:10.1109/9.587335 · Cited by 1,521
Optimal control: Linear quadratic methods
Kučera, V. (1992) · Automatica · doi:10.1016/0005-1098(92)90166-d · Cited by 1,510
Practical Methods for Optimal Control using Nonlinear Programming
Betts, & Kolmanovsky (2002) · Applied Mechanics Reviews · doi:10.1115/1.1483351 · Cited by 1,443
A time-dependent Hamilton-Jacobi formulation of reachable sets for continuous dynamic games
Mitchell, I. M., Bayen, A. M., & Tomlin, C. J. (2005) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2005.851439 · Cited by 1,152
Proceedings. 1988 IEEE International Conference on Robotics and Automation
(1988) · doi:10.1109/robot.1988 · Cited by 991
Real-Time Motion Planning for Agile Autonomous Vehicles
Frazzoli, E., Dahleh, M. A., & Feron, E. (2002) · Journal of Guidance, Control, and Dynamics · doi:10.2514/2.4856 · Cited by 830
On the construction of Lyapunov functions using the sum of squares decomposition
Papachristodoulou, A., & Prajna, S. (2003) · Proceedings of the 41st IEEE Conference on Decision and Control, 2002. · doi:10.1109/cdc.2002.1184414 · Cited by 461
Sequential Composition of Dynamically Dexterous Robot Behaviors
Burridge, R. R., Rizzi, A. A., & Koditschek, D. E. (1999) · The International Journal of Robotics Research · doi:10.1177/02783649922066385 · Cited by 446
A dual to Lyapunov's stability theorem
Rantzer, A. (2001) · Systems & Control Letters · doi:10.1016/s0167-6911(00)00087-6 · Cited by 404
1984 American Control Conference
(1984) · doi:10.23919/acc.1984 · Cited by 367
LQR-trees: Feedback motion planning on sparse randomized trees
Tedrake, R. (2009) · Robotics: Science and Systems · doi:10.15607/rss.2009.v.003 · Cited by 203
Self-citationA Toolbox of Hamilton-Jacobi Solvers for Analysis of Nondeterministic Continuous and Hybrid Systems
Mitchell, I. M., & Templeton, J. A. (2005) · Lecture notes in computer science · doi:10.1007/978-3-540-31954-2_31 · Cited by 145
Computation of Lyapunov functions for smooth nonlinear systems using convex optimization
Johansen, T. A. (2000) · Automatica · doi:10.1016/s0005-1098(00)00088-1 · Cited by 136
Motion planning for humanoid robots under obstacle and dynamic balance constraints
Kuffner, J., Nishiwaki, K., Kagami, S., Inaba, M., & Inoue, H. (2002) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.2001.932631 · Cited by 135
Path planning in 1000+ dimensions using a task-space Voronoi bias
Shkolnik, A. C., & Tedrake, R. (2009) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.2009.5152638 · Cited by 124
Self-citationMason, M. T. (2005) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.1985.1087242 · Cited by 121
Random Sampling of States in Dynamic Programming
Atkeson, C. G., & Stephens, B. J. (2008) · IEEE Transactions on Systems Man and Cybernetics Part B (Cybernetics) · doi:10.1109/tsmcb.2008.926610 · Cited by 57
Analysis of Polynomial Systems With Time Delays via the Sum of Squares Decomposition
Papachristodoulou, A., Peet, M. M., & Lall, S. (2009) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2009.2017168 · Cited by 49
Positivity of trigonometric polynomials
Megretski, A. (2004) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2003.1271743 · Cited by 38
Smooth patchy control Lyapunov functions
Goebel, R. K., Prieur, C., & Teel, A. R. (2009) · Automatica · doi:10.1016/j.automatica.2008.10.023 · Cited by 32
Cited by
Reinforcement learning in robotics: A survey
Kober, J., Bagnell, J. A., & Peters, J. (2013) · The International Journal of Robotics Research · doi:10.1177/0278364913495721 · Cited by 3,160
Incremental Sampling-based Algorithms for Optimal Motion Planning
Karaman, S., & Frazzoli, E. (2010) · Robotics: Science and Systems VI · doi:10.15607/rss.2010.vi.034 · Cited by 680
Certified Defenses against Adversarial Examples
Raghunathan, A., Steinhardt, J., & Liang, P. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1801.09344 · Cited by 520
Hamilton-Jacobi reachability: A brief overview and recent advances
Bansal, S., Chen, M., Herbert, S., & Tomlin, C. J. (2017) · 2017 IEEE 56th Annual Conference on Decision and Control (CDC) · doi:10.1109/cdc.2017.8263977 · Cited by 471
Funnel libraries for real-time robust feedback motion planning
Majumdar, A., & Tedrake, R. (2017) · The International Journal of Robotics Research · doi:10.1177/0278364917712421 · Cited by 350
Self-citation
Metadata
- Authors
- Tedrake, R., Manchester, I. R., Tobenkin, M., & Roberts, J. W.
- Venue
- The International Journal of Robotics Research
- Publisher
- SAGE Publications
- Published
- 2010-04-22
- Volume
- 29
- Issue
- 8
- Pages
- 1038-1052
- ISSN
- 0278-3649 (ISSN-L)
- 1741-3176
- OpenAlex
- W2100538121
- Cited by
- 409
- References
- 28
- FWCI
- 19.53
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.