Efficient and scalable path-planning algorithms for curvature constrained motion in the Hamilton-Jacobi formulation
References
[1]
L.E. Dubins, On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents, Am. J. Math. 79 (3) (1957) 497–516.
[2]
J. Reeds, L. Shepp, Optimal paths for a car that goes both forwards and backwards, Pac. J. Math. 145 (2) (1990) 367–393.
[3]
J. Barraquand, J.-C. Latombe, Nonholonomic multibody mobile robots: controllability and motion planning in the presence of obstacles, Algorithmica 10 (2–4) (1993) 121.
[4]
P.K. Agarwal, H. Wang, Approximation algorithms for curvature-constrained shortest paths, SIAM J. Comput. 30 (6) (2001) 1739–1772.
[5]
R. Takei, R. Tsai, H. Shen, Y. Landa, A practical path-planning algorithm for a simple car: a Hamilton-Jacobi approach, in: Proceedings of the 2010 American Control Conference, 2010, pp. 6175–6180.
[6]
R. Takei, R. Tsai, Optimal trajectories of curvature constrained motion in the Hamilton-Jacobi formulation, J. Sci. Comput. 54 (2) (2013) 622–644.
[7]
D.J. Arnold, D. Fernandez, R. Jia, C. Parkinson, D. Tonne, Y. Yaniv, A.L. Bertozzi, S.J. Osher, Modeling environmental crime in protected areas using the level set method, SIAM J. Appl. Math. 79 (3) (2019) 802–821.
[8]
C. Parkinson, D. Arnold, A.L. Bertozzi, Y.T. Chow, S. Osher, Optimal human navigation in steep terrain: a Hamilton–Jacobi–Bellman approach, Commun. Math. Sci. 17 (1) (2019) 227–242.
[9]
C. Parkinson, D. Arnold, A. Bertozzi, S. Osher, A model for optimal human navigation with stochastic effects, SIAM J. Appl. Math. 80 (4) (2020) 1862–1881.
[10]
C. Parkinson, A.L. Bertozzi, S.J. Osher, A Hamilton-Jacobi formulation for time-optimal paths of rectangular nonholonomic vehicles, in: 2020 59th IEEE Conference on Decision and Control (CDC), IEEE, 2020, pp. 4073–4078.
[11]
C. Parkinson, M. Ceccia, Time-optimal paths for simple cars with moving obstacles in the Hamilton-Jacobi formulation, in: 2022 American Control Conference (ACC), IEEE, 2022, pp. 2944–2949.
[12]
B. Chen, K. Peng, C. Parkinson, A.L. Bertozzi, T.L. Slough, J. Urpelainen, Modeling illegal logging in Brazil, Res. Math. Sci. 8 (2) (2021) 1–21.
[13]
M. Gee, A. Vladimirsky, Optimal path-planning with random breakdowns, IEEE Control Syst. Lett. 6 (2021) 1658–1663.
[14]
E. Cartee, L. Lai, Q. Song, A. Vladimirsky, Time-dependent surveillance-evasion games, in: 2019 IEEE 58th Conference on Decision and Control (CDC), IEEE, 2019, pp. 7128–7133.
[15]
A. Shukla, E. Singla, P. Wahi, B. Dasgupta, A direct variational method for planning monotonically optimal paths for redundant manipulators in constrained workspaces, Robot. Auton. Syst. 61 (2) (2013) 209–220.
[16]
F. Zhang, C. Wang, C. Cheng, D. Yang, G. Pan, Reinforcement learning path planning method with error estimation, Energies 15 (1) (2022).
[17]
K. Wan, D. Wu, B. Li, X. Gao, Z. Hu, D. Chen, Me-maddpg: an efficient learning-based motion planning method for multiple agents in complex environments, Int. J. Intell. Syst. 37 (3) (2022) 2393–2427.
[18]
R. Deng, Q. Zhang, R. Gao, M. Li, P. Liang, X. Gao, A trajectory tracking control algorithm of nonholonomic wheeled mobile robot, in: 2021 6th IEEE International Conference on Advanced Robotics and Mechatronics (ICARM), 2021, pp. 823–828.
[19]
J.J. Johnson, M.C. Yip, Chance-constrained motion planning using modeled distance- to-collision functions, in: 2021 IEEE 17th International Conference on Automation Science and Engineering (CASE), 2021, pp. 1582–1589.
[20]
M. Detrixhe, F. Gibou, C. Min, A parallel fast sweeping method for the Eikonal equation, J. Comput. Phys. 237 (2013) 46–55.
[21]
M. Detrixhe, F. Gibou, Hybrid massively parallel fast sweeping method for static Hamilton–Jacobi equations, J. Comput. Phys. 322 (2016) 199–223.
[22]
J. Darbon, S. Osher, Algorithms for overcoming the curse of dimensionality for certain Hamilton–Jacobi equations arising in control theory and elsewhere, Res. Math. Sci. 3 (1) (2016) 19.
[23]
Y.T. Chow, J. Darbon, S. Osher, W. Yin, Algorithm for overcoming the curse of dimensionality for state-dependent Hamilton-Jacobi equations, J. Comput. Phys. 387 (2019) 376–409.
[24]
A.T. Lin, Y.T. Chow, S.J. Osher, A splitting method for overcoming the curse of dimensionality in Hamilton–Jacobi equations arising from nonlinear optimal control and differential games with applications to trajectory generation, Commun. Math. Sci. 16 (7) (1 2018).
[25]
S. Osher, J.A. Sethian, Fronts propagating with curvature-dependent speed: algorithms based on Hamilton-Jacobi formulations, J. Comput. Phys. 79 (1) (1988) 12–49.
[26]
F. Gibou, R. Fedkiw, S. Osher, A review of level-set methods and some recent applications, J. Comput. Phys. 353 (2018) 82–109.
[27]
R. Bellman, Dynamic programming, Science 153 (3731) (1966) 34–37.
[28]
M.G. Crandall, P.-L. Lions, Viscosity solutions of Hamilton-Jacobi equations, Trans. Am. Math. Soc. 277 (1) (1983) 1–42.
[29]
M.G. Crandall, H. Ishii, P.-L. Lions, User's guide to viscosity solutions of second order partial differential equations, Bull. Am. Math. Soc. 27 (1) (1992) 1–67.
[30]
M. Bardi, I.C. Dolcetta, et al., Optimal Control and Viscosity Solutions of Hamilton-Jacobi-Bellman Equations, vol. 12, Springer, 1997.
[31]
H. Chitsaz, S.M. LaValle, Time-optimal paths for a Dubins airplane, in: 2007 46th IEEE Conference on Decision and Control, IEEE, 2007, pp. 2379–2384.
[32]
H.J. Choi, Time-optimal paths for a Dubins car and Dubins airplane with a unidirectional turning constraint, Phd thesis University of Michigan, 2014.
[33]
W. Cai, M. Zhang, Y.R. Zheng, Task assignment and path planning for multiple autonomous underwater vehicles using 3D Dubins curves, Sensors 17 (7) (2017) 1607.
[34]
Y. Duan, S. Patil, J. Schulman, K. Goldberg, P. Abbeel, Planning locally optimal, curvature-constrained trajectories in 3d using sequential convex optimization, in: 2014 IEEE International Conference on Robotics and Automation (ICRA), 2014, pp. 5889–5895,.
[35]
S. Jafarpour, On small-time local controllability, SIAM J. Control Optim. 58 (1) (2020) 425–446.
[36]
C. Parkinson, A rotating-grid upwind fast sweeping scheme for a class of Hamilton-Jacobi equations, J. Sci. Comput. 88 (1) (2021) 13.
[37]
C.-Y. Kao, S. Osher, Y.-H. Tsai, Fast sweeping methods for static Hamilton–Jacobi equations, SIAM J. Numer. Anal. 42 (6) (2005) 2612–2632.
[38]
Y.-T. Zhang, H.-K. Zhao, J. Qian, High order fast sweeping methods for static Hamilton–Jacobi equations, J. Sci. Comput. 29 (2006) 25–56.
[39]
J.N. Tsitsiklis, Efficient algorithms for globally optimal trajectories, IEEE Trans. Autom. Control 40 (9) (1995) 1528–1538.
[40]
J.A. Sethian, Fast marching methods, SIAM Rev. 41 (2) (1999) 199–235.
[41]
K. Alton, I.M. Mitchell, Fast marching methods for stationary Hamilton–Jacobi equations with axis-aligned anisotropy, SIAM J. Numer. Anal. 47 (1) (2009) 363–385.
[42]
J.A. Sethian, A. Vladimirsky, Ordered upwind methods for static Hamilton–Jacobi equations: theory and algorithms, SIAM J. Numer. Anal. 41 (1) (2003) 325–363.
[43]
A. Chambolle, T. Pock, A first-order primal-dual algorithm for convex problems with applications to imaging, J. Math. Imaging Vis. 40 (2011) 120–145.
[44]
M. Zhu, T. Chan, An efficient primal-dual hybrid gradient algorithm for total variation image restoration, Ucla Cam Rep. 34 (2008) 8–34.
[45]
E. Esser, X. Zhang, T.F. Chan, A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science, SIAM J. Imaging Sci. 3 (4) (2010) 1015–1046.
[46]
S. Osher, R.P. Fedkiw, Level Set Methods and Dynamic Implicit Surfaces, vol. 1, Springer New York, 2005.
[47]
J.A. Sethian, Level Set Methods and Fast Marching Methods: Evolving Interfaces in Computational Geometry Fluid Mechanics, Computer Vision, and Materials Science, vol. 3, Cambridge University Press, 1999.
[48]
B. Lee, J. Darbon, S. Osher, M. Kang, Revisiting the redistancing problem using the Hopf–Lax formula, J. Comput. Phys. 330 (2017) 268–281.
[49]
M. Royston, A. Pradhana, B. Lee, Y.T. Chow, W. Yin, J. Teran, S. Osher, Parallel redistancing using the Hopf–Lax formula, J. Comput. Phys. 365 (2018) 7–17.
[50]
N. Amenta, S. Choi, R.K. Kolluri, The power crust, unions of balls, and the medial axis transform, Combinatorial Curves and Surfaces, Comput. Geom. 19 (2) (2001) 127–153.
[51]
F. Cazals, T. Dreyfus, S. Sachdeva, N. Shah, Greedy geometric algorithms for collection of balls, with applications to geometric approximation and molecular coarse-graining, Comput. Graph. Forum 33 (6) (2014) 1–17.
[52]
Luo, Y.; Zhang, Y. (2023): Circle packings, renormalizations and subdivision rules. arXiv preprint arXiv:2308.13151.
Recommendations
Filtered schemes for Hamilton-Jacobi equations
We build a simple and general class of finite difference schemes for first order Hamilton-Jacobi (HJ) Partial Differential Equations. These filtered schemes are convergent to the unique viscosity solution of the equation. The schemes are accurate: we ...
Non-oscillatory methods for relaxation approximation of Hamilton-Jacobi equations
In this paper, a class of high order non-oscillatory methods based on relaxation approximation for solving Hamilton-Jacobi equations is presented. The relaxation approximation transforms the nonlinear weakly hyperbolic equations to a semilinear strongly ...
Convex ENO Schemes for Hamilton–Jacobi Equations
In one dimension, viscosity solutions of Hamilton–Jacobi (HJ) equations can be thought as primitives of entropy solutions for conservation laws. Based on this idea, both theoretical and numerical concepts used for conservation laws can be passed to HJ ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Elsevier Inc.
Publisher
Academic Press Professional, Inc.
United States
Publication History
Published: 18 July 2024
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 24 Dec 2024