The DOI matches its Crossref record; 47 of the 47 references it cites were found in a registry or an index.
Optimization-Based Collision Avoidance
Open accessAbstract
This article presents a novel method for exactly reformulating nondifferentiable collision avoidance constraints into smooth, differentiable constraints using strong duality of convex optimization. We focus on a controlled object whose goal is to avoid obstacles while moving in an n-dimensional space. The proposed reformulation is exact, does not introduce any approximations, and applies to general obstacles and controlled objects that can be represented as the union of convex sets. We connect our results with the notion of signed distance, which is widely used in traditional trajectory generation algorithms. Our method can be applied to generic navigation and trajectory planning tasks, and the smoothness property allows the use of general-purpose gradient- and Hessian-based optimization algorithms. Finally, in case a collision cannot be avoided, our framework allows us to find “least-intrusive” trajectories, measured in terms of penetration. We demonstrate the efficacy of our framework on an automated parking problem, where our numerical experiments suggest that the proposed method is robust and enables real-time optimization-based trajectory planning in tight environments. Sample code of our example is provided at https://github.com/XiaojingGeorgeZhang/OBCA.
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
Boyd, S., & Vandenberghe, L. (2004) · doi:10.1017/cbo9780511804441 · Cited by 56,601
A Formal Basis for the Heuristic Determination of Minimum Cost Paths
Hart, P., Nilsson, N., & Raphael, B. (1968) · IEEE Transactions on Systems Science and Cybernetics · doi:10.1109/tssc.1968.300136 · Cited by 12,738
Rockafellar, R. T. (1970) · Princeton University Press eBooks · doi:10.1515/9781400873173 · Cited by 10,801
Wächter, A., & Biegler, L. T. (2006) · Mathematical Programming · doi:10.1007/s10107-004-0559-y · Cited by 9,483
Real-Time Obstacle Avoidance for Manipulators and Mobile Robots
Khatib, O. (1986) · The International Journal of Robotics Research · doi:10.1177/027836498600500106 · Cited by 7,894 · cited 1×
“One way of dealing with obstacle avoidance is to use unconstrained optimization, in which case the objective function is augmented with “artificial potential fields” that represent the obstacles [35]–[39].”
BackgroundSampling-based algorithms for optimal motion planning
Karaman, S., & Frazzoli, E. (2011) · The International Journal of Robotics Research · doi:10.1177/0278364911406761 · Cited by 5,275
LaValle, S. M. (2006) · Cambridge University Press eBooks · doi:10.1017/cbo9780511546877 · Cited by 5,211
Rajamani, R. (2012) · Mechanical Engineering Series · doi:10.1007/978-1-4614-1433-9 · Cited by 4,401
Randomized Kinodynamic Planning
LaValle, S. M., & Kuffner, J. J. (2001) · The International Journal of Robotics Research · doi:10.1177/02783640122067453 · Cited by 3,254
A Survey of Motion Planning and Control Techniques for Self-Driving Urban Vehicles
Paden, B., Cap, M., Yong, S. Z., Yershov, D., & Frazzoli, E. (2016) · IEEE Transactions on Intelligent Vehicles · doi:10.1109/tiv.2016.2578706 · Cited by 2,585
A Review of Motion Planning Techniques for Automated Vehicles
Gonzalez, D., Perez, J., Milanes, V., & Nashashibi, F. (2016) · IEEE Transactions on Intelligent Transportation Systems · doi:10.1109/tits.2015.2498841 · Cited by 1,670
Optimal paths for a car that goes both forwards and backwards
Reeds, J., & Shepp, L. (1990) · Pacific Journal of Mathematics · doi:10.2140/pjm.1990.145.367 · Cited by 1,447
Predictive Control for Linear and Hybrid Systems
Borrelli, F., Bemporad, A., & Morari, M. (2017) · Cambridge University Press eBooks · doi:10.1017/9781139061759 · Cited by 1,443
Self-citationThe complexity of robot motion planning
Canny, J. (1988) · Medical Entomology and Zoology · Cited by 1,375
JuMP: A MODELING LANGUAGE FOR MATHEMATICAL OPTIMIZATION
Dunning, I., Huchette, J., & Lubin, M. (2016) · Cited by 1,355
JuMP: A Modeling Language for Mathematical Optimization
Dunning, I., Huchette, J., & Lubin, M. (2017) · SIAM Review · doi:10.1137/15m1020575 · Cited by 1,250
Conflict resolution for air traffic management: a study in multiagent hybrid systems
Tomlin, C., Pappas, G. J., & Sastry, S. (1998) · IEEE Transactions on Automatic Control · doi:10.1109/9.664154 · Cited by 1,042
Path Planning for Autonomous Vehicles in Unknown Semi-structured Environments
Dolgov, D., Thrun, S., Montemerlo, M., & Diebel, J. (2010) · The International Journal of Robotics Research · doi:10.1177/0278364909359210 · Cited by 976
STOMP: Stochastic trajectory optimization for motion planning
Kalakrishnan, M., Chitta, S., Theodorou, E., Pastor, P., & Schaal, S. (2011) · 2011 IEEE International Conference on Robotics and Automation · doi:10.1109/icra.2011.5980280 · Cited by 876
Motion planning with sequential convex optimization and convex collision checking
Schulman, J., Duan, Y., Ho, J., Lee, A., Awwal, I., Bradlow, H., Pan, J., Patil, S., Goldberg, K., & Abbeel, P. (2014) · The International Journal of Robotics Research · doi:10.1177/0278364914528132 · Cited by 866
Katrakazas, C., Quddus, M., Chen, W.-H., & Deka, L. (2015) · Transportation Research Part C: Emerging Technologies · doi:10.1016/j.trc.2015.09.011 · Cited by 800
CHOMP: Covariant Hamiltonian optimization for motion planning
Zucker, M., Ratliff, N., Dragan, A. D., Pivtoraiko, M., Klingensmith, M., Dellin, C. M., Bagnell, J. A., & Srinivasa, S. S. (2013) · The International Journal of Robotics Research · doi:10.1177/0278364913488805 · Cited by 758
Optimization‐based autonomous racing of 1:43 scale RC cars
Liniger, A., Domahidi, A., & Morari, M. (2015) · Optimal Control Applications and Methods · doi:10.1002/oca.2123 · Cited by 537
Self-citationPlanning Long Dynamically Feasible Maneuvers for Autonomous Vehicles
Likhachev, M., & Ferguson, D. (2009) · The International Journal of Robotics Research · doi:10.1177/0278364909340445 · Cited by 512
Trajectory planning for Bertha — A local, continuous method
Ziegler, J., Bender, P., Dang, T., & Stiller, C. (2014) · 2014 IEEE Intelligent Vehicles Symposium Proceedings · doi:10.1109/ivs.2014.6856581 · Cited by 443
Collision Avoidance and Stabilization for Autonomous Vehicles in Emergency Scenarios
Funke, J., Brown, M., Erlien, S. M., & Gerdes, J. C. (2017) · IEEE Transactions on Control Systems Technology · doi:10.1109/tcst.2016.2599783 · Cited by 439
Chance-Constrained Optimal Path Planning With Obstacles
Blackmore, L., Ono, M., & Williams, B. C. (2011) · IEEE Transactions on Robotics · doi:10.1109/tro.2011.2161160 · Cited by 427
Online Verification of Automated Road Vehicles Using Reachability Analysis
Althoff, M., & Dolan, J. M. (2014) · IEEE Transactions on Robotics · doi:10.1109/tro.2014.2312453 · Cited by 412
Autonomous driving in urban environments: approaches, lessons and challenges
Campbell, M., Egerstedt, M., How, J. P., & Murray, R. M. (2010) · Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences · doi:10.1098/rsta.2010.0110 · Cited by 353
Fast Direct Multiple Shooting Algorithms for Optimal Robot Control
Diehl, M., Bock, H. G., Diedam, H., & Wieber, P.-B. (2007) · Lecture Notes in Control and Information Sciences · doi:10.1007/978-3-540-36119-0_4 · Cited by 344
Shortest paths of bounded curvature in the plane
Boissonnat, J.-D., C�r�zo, A., & Leblond, J. (1994) · Journal of Intelligent & Robotic Systems · doi:10.1007/bf01258291 · Cited by 235
Predictive Control of Autonomous Ground Vehicles With Obstacle Avoidance on Slippery Roads
Gao, Y., Lin, T., Borrelli, F., Tseng, E., & Hrovat, D. (2010) · ASME Dynamic Systems and Control Conference (DSCC) · doi:10.1115/dscc2010-4263 · Cited by 213
Self-citationLi, B., & Shao, Z. (2015) · Knowledge-Based Systems · doi:10.1016/j.knosys.2015.04.016 · Cited by 195
Determining the minimum translational distance between two convex polyhedra
Cameron, S., & Culley, R. (1986) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.1986.1087645 · Cited by 195
Autonomous Parking Using Optimization-Based Collision Avoidance
Zhang, X., Liniger, A., Sakai, A., & Borrelli, F. (2018) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2018.8619433 · Cited by 187
Self-citationAine, S., Swaminathan, S., Narayanan, V., Hwang, V., & Likhachev, M. A. (2015) · The International Journal of Robotics Research · doi:10.1177/0278364915594029 · Cited by 186
Autonomous Vehicle Control: A Nonconvex Approach for Obstacle Avoidance
Rosolia, U., De Bruyne, S., & Alleyne, A. G. (2017) · IEEE Transactions on Control Systems Technology · doi:10.1109/tcst.2016.2569468 · Cited by 182
Nageli, T., Alonso-Mora, J., Domahidi, A., Rus, D., & Hilliges, O. (2017) · IEEE Robotics and Automation Letters · doi:10.1109/lra.2017.2665693 · Cited by 173
ITOMP: Incremental Trajectory Optimization for Real-Time Replanning in Dynamic Environments
Park, C., Pan, J., & Manocha, D. (2012) · Proceedings of the International Conference on Automated Planning and Scheduling · doi:10.1609/icaps.v22i1.13513 · Cited by 160
Autonomous racing using learning Model Predictive Control
Rosolia, U., Carvalho, A., & Borrelli, F. (2017) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.23919/acc.2017.7963748 · Cited by 123
Self-citationNavigating car-like robots in unstructured environments using an obstacle sensitive cost function
Ziegler, J., & Werling, M. (2008) · IEEE Intelligent Vehicles Symposium · doi:10.1109/ivs.2008.4621302 · Cited by 122
Trajectory Generation for Aircraft Avoidance Maneuvers Using Online Optimization
Patel, R., & Goulart, P. J. (2010) · Journal of Guidance Control and Dynamics · doi:10.2514/1.49518 · Cited by 88
Margellos, K., & Lygeros, J. (2012) · IEEE Transactions on Control Systems Technology · doi:10.1109/tcst.2012.2220773 · Cited by 77
Soloperto, R., Köhler, J., Allgöwer, F., & Müller, M. A. (2019) · European Control Conference (ECC) · doi:10.23919/ecc.2019.8796049 · Cited by 62
Banzhaf, H., Palmieri, L., Nienhüser, D., Schamm, T., Knoop, S., & Zöllner, J. M. (2017) · IEEE International Conference on Intelligent Transportation Systems (ITSC) · doi:10.1109/itsc.2017.8317757 · Cited by 46
Automatic parallel parking with geometric continuous-curvature path planning
Vorobieva, H., Glaser, S., Minoiu-Enache, N., & Mammar, S. (2014) · IEEE Intelligent Vehicles Symposium · doi:10.1109/ivs.2014.6856443 · Cited by 45
Efficient implementation of Randomized MPC for miniature race cars
Carrau, J. V., Liniger, A., Zhang, X., & Lygeros, J. (2016) · European Control Conference (ECC) · doi:10.1109/ecc.2016.7810413 · Cited by 39
Self-citation
Cited by
Control of connected and automated vehicles: State of the art and future challenges
Guanetti, J., Kim, Y., & Borrelli, F. (2018) · Annual Reviews in Control · doi:10.1016/j.arcontrol.2018.04.011 · Cited by 643
Self-citationSafety-Critical Model Predictive Control with Discrete-Time Control Barrier Function
Zeng, J., Zhang, B., & Sreenath, K. (2021) · 2021 American Control Conference (ACC) · doi:10.23919/acc50511.2021.9483029 · Cited by 390
Deep Learning-Based Trajectory Planning and Control for Autonomous Ground Vehicle Parking Maneuver
Chai, R., Liu, D., Liu, T., Tsourdos, A., Xia, Y., & Chai, S. (2023) · IEEE Transactions on Automation Science and Engineering · doi:10.1109/tase.2022.3183610 · Cited by 273
Metadata
- Authors
- Zhang, X., Liniger, A., & Borrelli, F.
- Venue
- IEEE Transactions on Control Systems Technology
- Published
- 2021-05
- Volume
- 29
- Issue
- 3
- Pages
- 972-983
- ISSN
- 1063-6536 (ISSN-L)
- 1558-0865
- 2374-0159
- OpenAlex
- W3015470607
- Cited by
- 444
- References
- 47
- FWCI
- 17.52
- 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.