The DOI matches its Crossref record; 27 of the 27 references it cites were found in a registry or an index.
Chance-Constrained Optimal Path Planning With Obstacles
Open accessAbstract
Autonomous vehicles need to plan trajectories to a specified goal that avoid obstacles. For robust execution, we must take into account uncertainty, which arises due to uncertain localization, modeling errors, and disturbances. Prior work handled the case of set-bounded uncertainty. We present here a chance-constrained approach, which uses instead a probabilistic representation of uncertainty. The new approach plans the future probabilistic distribution of the vehicle state so that the probability of failure is below a specified threshold. Failure occurs when the vehicle collides with an obstacle or leaves an operator-specified region. The key idea behind the approach is to use bounds on the probability of collision to show that, for linear-Gaussian systems, we can approximate the nonconvex chance-constrained optimization problem as a disjunctive convex program. This can be solved to global optimality using branch-and-bound techniques. In order to improve computation time, we introduce a customized solution method that returns almost-optimal solutions along with a hard bound on the level of suboptimality. We present an empirical validation with an aircraft obstacle avoidance example.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
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
Boyd, S., & Vandenberghe, L. (2004) · doi:10.1017/cbo9780511804441 · Cited by 56,601
System Identification: Theory for the User
Lennart Ljung, A. (1987) · Cited by 17,690
System identification—Theory for the user
Sinha, N. K. (1989) · Automatica · doi:10.1016/0005-1098(89)90019-8 · Cited by 9,184
YALMIP : a toolbox for modeling and optimization in MATLAB
Lofberg, J. (2005) · 2004 IEEE International Conference on Robotics and Automation (IEEE Cat. No.04CH37508) · doi:10.1109/cacsd.2004.1393890 · Cited by 9,149
Latombe, J.-C. (1991) · Springer eBooks · doi:10.1007/978-1-4615-4022-9 · Cited by 6,396
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 · cited 1×
“A large body of work exists on the topic of path planning with deterministic system models, including [1], [2], [3], [4], [19].”
BackgroundLaValle, S. M. (2006) · Cambridge University Press eBooks · doi:10.1017/cbo9780511546877 · Cited by 5,211
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
Robust constrained model predictive control using linear matrix inequalities
Kothare, M. V., Balakrishnan, V., & Morari, M. (1996) · Automatica · doi:10.1016/0005-1098(96)00063-5 · Cited by 2,516
Branch-and-Bound Methods: A Survey
Lawler, E. L., & Wood, D. E. (1966) · Operations Research · doi:10.1287/opre.14.4.699 · Cited by 1,997
Prékopa, A. (1995) · Springer eBooks · doi:10.1007/978-94-017-3087-7 · Cited by 1,535
The Scenario Approach to Robust Control Design
Calafiore, G. C., & Campi, M. C. (2006) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2006.875041 · Cited by 1,150
Interior Point Algorithms: Theory and Analysis
Ye, Y. (1997) · Wiley eBooks · doi:10.1002/9781118032701 · Cited by 939
Mixed integer programming for multi-vehicle path planning
Schouwenaars, T., De Moor, B., Feron, E., & How, J. (2001) · 2001 European Control Conference (ECC) · doi:10.23919/ecc.2001.7076321 · Cited by 566
Progress in Linear Programming-Based Algorithms for Integer Programming: An Exposition
Johnson, E. L., Nemhauser, G. L., & Savelsbergh, M. W. P. (2000) · INFORMS Journal on Computing · doi:10.1287/ijoc.12.1.2.11900 · Cited by 206
Prékopa, A. (2003) · Handbooks in operations research and management science · doi:10.1016/s0927-0507(03)10005-9 · Cited by 204
A probabilistic approach to optimal robust path planning with obstacles
Blackmore, L., Li, H., & Williams, B. (2006) · 2006 American Control Conference · doi:10.1109/acc.2006.1656653 · Cited by 178
Self-citationPath Planning and Obstacle Avoidance for Autonomous Mobile Robots: A Review
Kunchev, V., Jain, L. C., Ivancevic, V. G., & Finn, A. (2006) · Lecture notes in computer science · doi:10.1007/11893004_70 · Cited by 136
Robust constrained model predictive control
Richards, A. G. (2005) · Cited by 96
A Probabilistic Particle Control Approach to Optimal, Robust Predictive Control
Blackmore, L. (2006) · AIAA Guidance, Navigation, and Control Conference and Exhibit · doi:10.2514/6.2006-6240 · Cited by 90
Self-citationSafe Path Planning in an Uncertain-Configuration Space using RRT
Pepy, R., & Lambert, A. (2006) · IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) · doi:10.1109/iros.2006.282101 · Cited by 89
Model predictive control for stochastic systems by randomized algorithms
Batina, I. (2004) · TU/e Research Portal · doi:10.6100/ir573294 · Cited by 84
Plume avoidance maneuver planning using mixed integer linear programming
Schouwenaars, T., Richards, A. G., Féron, É., & How, J. P. (2001) · AIAA Guidance, Navigation, and Control Conference and Exhibit · doi:10.2514/6.2001-4091 · Cited by 70
Safe path planning in an uncertain-configuration space
Lambert, A., & Gruyer, D. (2004) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.2003.1242246 · Cited by 50
Safe Task Planning Integrating Uncertainties and Local Maps Federations
Lambert, A., & Fort-Piat, N. L. (2000) · The International Journal of Robotics Research · doi:10.1177/027836490001900604 · Cited by 48
Robust, Optimal Predictive Control of Jump Markov Linear Systems Using Particles
Blackmore, L., Bektassov, A., Ono, M., & Williams, B. C. (2007) · Springer eBooks · doi:10.1007/978-3-540-71493-4_11 · Cited by 34
Self-citation
Cited by
Stochastic Model Predictive Control: An Overview and Perspectives for Future Research
(2016) · IEEE Control Systems · doi:10.1109/mcs.2016.2602087 · Cited by 923
Perception, Planning, Control, and Coordination for Autonomous Vehicles
Pendleton, S., Andersen, H., Du, X., Shen, X., Meghjani, M., Eng, Y., Rus, D., & Ang, M. (2017) · Machines · doi:10.3390/machines5010006 · Cited by 657
Hoy, M., Matveev, A. S., & Savkin, A. V. (2015) · Robotica · doi:10.1017/s0263574714000289 · Cited by 469
Optimization-Based Collision Avoidance
Zhang, X., Liniger, A., & Borrelli, F. (2021) · IEEE Transactions on Control Systems Technology · doi:10.1109/tcst.2019.2949540 · Cited by 444
Stochastic linear Model Predictive Control with chance constraints – A review
Farina, M., Giulioni, L., & Scattolini, R. (2016) · Journal of Process Control · doi:10.1016/j.jprocont.2016.03.005 · Cited by 342
Metadata
- Authors
- Blackmore, L., Ono, M., & Williams, B. C.
- Venue
- IEEE Transactions on Robotics
- Published
- 2011-12
- Volume
- 27
- Issue
- 6
- Pages
- 1080-1094
- ISSN
- 1552-3098 (ISSN-L)
- 1941-0468
- OpenAlex
- W1999131722
- Cited by
- 427
- References
- 27
- FWCI
- 7.25
- Type
- journal article
- Language
- en
- Open access
- green
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.