Numerical simulation of collision-free near-shortest path generation for Dubins vehicle via Hamilton–Jacobi–Bellman equation: A case study

References

• Aguiar, A. P., Bayer, F. A., Hauser, J., Häusler, A. J., Notarstefano, G., Pascoal, A. M., & Saccon, A. (2017). Constrained optimal motion planning for autonomous vehicles using PRONTO. In Sensing and control for autonomous vehicles (pp. 207–32). Springer.
   Google Scholar
• Bardi, M., & Capuzzo-Dolcetta, I. (2008). Optimal control and viscosity solutions of Hamilton-Jacobi-Bellman equations. Springer Science and Business Media.
   Google Scholar
• Ben-Asher, J. Z., Wetzler, M., & Rimon, E. D. (2020). Time optimal trajectories for a mobile robot under nonsliding and radius-of-turn constraints. Journal of Dynamic Systems, Measurement, and Control, 142(6), 11. https://doi.org/10.1115/1.4046331
   Web of Science ®Google Scholar
• Bertolazzi, E., & Frego, M. (2018). Semianalytical minimum‐time solution for the optimal control of a vehicle subject to limited acceleration. Optimal Control Applications & Methods, 39(2), 774–791. https://doi.org/10.1002/oca.2376
   Web of Science ®Google Scholar
• Bokanowski, O., Garcke, J., Griebel, M., & Klompmaker, I. (2013). An adaptive sparse grid semi-Lagrangian scheme for first order Hamilton-Jacobi Bellman equations. Journal of Scientific Computing, 55(3), 575–605. https://doi.org/10.1007/s10915-012-9648-x
   Web of Science ®Google Scholar
• Botkin, N., Hoffmann, K. H., Mayer, N., & Turova, V. (2011). Computation of value functions in nonlinear differential games with state constraints. IFIP conference on system modeling and optimization (pp. 235–244). Berlin, Heidelberg: Springer.
   Google Scholar
• Bui, X. N., Boissonnat, J. D., Soueres, P., & Laumond, J. P. (1994). Shortest path synthesis for Dubins non-holonomic robot. IEEE International Conference on Robotics and Automation, 1, 2–7. https://doi.org/10.1109/ROBOT.1994.351019
   Google Scholar
• Castro, A. L., & Koiller, J. (2013). On the dynamic Markov-Dubins problem: From path planning in robotics and biolocomotion to computational anatomy. Regular and Chaotic Dynamics, 18(1–2), 1–20. https://doi.org/10.1134/S1560354713010012
   Web of Science ®Google Scholar
• Chen, Q. Y., Lu, Y. F., Jia, G. W., Li, Y., Zhu, B. J., & Lin, J. C. (2018). Path planning for UAVs formation reconfiguration based on Dubins trajectory. Journal of Central South University, 25(11), 2664–2676. https://doi.org/10.1007/s11771-018-3944-z
   Web of Science ®Google Scholar
• Chen, Z., & Shima, T. (2019). Shortest Dubins paths through three points. Automatica, 105, 368–375. https://doi.org/10.1016/j.automatica.2019.04.007
   Web of Science ®Google Scholar
• Consolini, L., Laurini, M., & Locatelli, M. (2019). Graph-based algorithms for the efficient solution of optimization problems involving monotone functions. Computational Optimization and Applications, 73, 101-128. https://doi.org/10.1007/s10589-019-00070-4
   Web of Science ®Google Scholar
• Crandall, M. G., & Lions, P. L. (1984). Two Approximations of Solutions of Hamilton-Jacobi Equations. Mathematics of Computations, 43(167), 1–19. https://doi.org/10.1090/S0025-5718-1984-0744921-8
   Web of Science ®Google Scholar
• Desaulniers, G. (1996). On shortest paths for a car-like robot maneuvering around obstacles. Robotics and Autonomous Systems, 17(3), 139–148. https://doi.org/10.1016/0921-8890(96)80512-4
   Web of Science ®Google Scholar
• Dolgov, D., Thrun, S., Montemerlo, M., & Diebel, J. (2008). Practical search techniques in path planning for autonomous driving. 1st international symposium search technology and artificial intelligence and robotics, Chicago, USA.
   Google Scholar
• Dubins, L. E. (1957, July). On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents. American Journal of Mathematics, 79(3), 497–516. https://doi.org/10.2307/2372560
   Web of Science ®Google Scholar
• Falcone, M. (2013). Recent results in the approximation of nonlinear optimal control problems. International conference on large-scale scientific computing (pp. 15–32). Berlin, Heidelberg: Springer.
   Google Scholar
• Fedotov, A. A., & Patsko, V. S. (2018). Investigation of reachable set at instant for the Dubins’ car, 58th Israel annual conference on aerospace sciences, IACAS 2018 (pp.1655–1669). Tel-Aviv and Haifa, Israel.
   Google Scholar
• Ferretti, G., Ferretti, R., Junge, O., & Schreiber, A. (2017). An adaptive multilevel radial basis function scheme for the HJB equation. IFAC-PapersOnLine, 50(1), 1643–1648. https://doi.org/10.1016/j.ifacol.2017.08.331
   Google Scholar
• Font, R., & Pedregal, P. (2018). Some numerical tests for an alternative approach to optimal feedback control. Journal of the Franklin Institute, 355(15), 7011–7026. https://doi.org/10.1016/j.jfranklin.2018.08.004
   Web of Science ®Google Scholar
• Gong, Q., Lewis, R., & Ross, M. (2009). Pseudospectral motion planning for autonomous vehicles. Journal of Guidance, Control, and Dynamics, 32(3), 1039–1045. https://doi.org/10.2514/1.39697
   Web of Science ®Google Scholar
• Guo, B. Z., & Wu, T. T. (2017). Numerical solution to optimal feedback control by dynamic programming approach: A local approximation algorithm. Journal of Systems Science and Complexity, 30(4), 782–802. https://doi.org/10.1007/s11424-017-5149-1
   Web of Science ®Google Scholar
• Hota, S., & Ghose, D. (2010). Optimal path planning for an aerial vehicle in 3D space. 49th IEEE conference on decision and control (pp. 4902–4907). Atlanta, Georgia, USA.
   Google Scholar
• Jamhour, E., & Andr’e, P. J. (1996). Planning smooth trajectories along parametric paths. Mathematics and Computers in Simulation, 41(5–6), 615–626. https://doi.org/10.1016/0378-4754(95)00105-0
   Web of Science ®Google Scholar
• Kang, W., & Wilcox, L. C. (2017). Mitigating the curse of dimensionality: Sparse grid characteristics method for optimal feedback control and HJB equations. Computational Optimization and Applications, 68(2), 289–315. https://doi.org/10.1007/s10589-017-9910-0
   Web of Science ®Google Scholar
• Kao, C.-Y., Osher, S., & Qian, J. (2004, May). Lax-Friedrichs sweeping scheme for static Hamilton-Jacobi equations. Journal of Computational Physics, 196(1), 367–391. https://doi.org/10.1016/j.jcp.2003.11.007
   Web of Science ®Google Scholar
• Kaya, C. Y. (2017). Markov-Dubins path via optimal control theory. Computational Optimization and Applications, 68(3), 719–747. https://doi.org/10.1007/s10589-017-9923-8
   Web of Science ®Google Scholar
• Liang, H., Zhong, W., & Chunhui, Z. (2015, July 28). Point-to-point near-optimal obstacle avoidance path for the unmanned aerial vehicle. 34th Chinese control conference, Hangzhou, China.
   Google Scholar
• Lugo-Cárdenas, I., Flores, G., Salazar, S., & Lozano, R. (2014). Dubins path generation for a fixed wing UAV. IEEE international conference on unmanned aircraft systems (ICUAS), 2014 (pp. 339–346). Wyndham Grand Orlando Resort, Orlando, FL USA.
   Google Scholar
• Manor, G., Ben-Asher, J. Z., & Rimon, E. (2018). Time optimal trajectories for a mobile robot under explicit acceleration constraints. IEEE Transactions on Aerospace and Electronic Systems, 54(5), 2220–2232. https://doi.org/10.1109/TAES.2018.2811158
   Web of Science ®Google Scholar
• Mehrali-Varjani, M., Shamsi, M., & Malek, A. (2018). Solving a class of Hamilton-Jacobi-Bellman equations using pseudospectral methods. Kybernetika, 54(4), 629–647. https://doi.org/10.14736/kyb-2018-4-0629
   Web of Science ®Google Scholar
• Michael, G. (1983). Crandall and Pierre-Louis Lions, viscosity solutions of Hamilton-Jacobi equations. Transaction of the American Mathematical Society, 277(1), 1–42. https://doi.org/10.1090/S0002-9947-1983-0690039-8
   Web of Science ®Google Scholar
• Patten, W. N., Wu, H. C., & Cai, W. (1994). Perfect parallel parking via Pontryagin’s principle. Journal of Dynamic Systems, Measurement, and Control, 116(4), 723–728. https://doi.org/10.1115/1.2899271
   Web of Science ®Google Scholar
• Pham, Q. C. (2014). A general, fast, and robust implementation of the time-optimal path parameterization algorithm. IEEE Transactions on Robotics, 30(6), 1533–1540. https://doi.org/10.1109/TRO.2014.2351113
   Web of Science ®Google Scholar
• Pharpatara, P., Hérissé, B., & Bestaoui, Y. (2015). 3D-shortest paths for a hypersonic glider in a heterogeneous environment. Workshop on Advanced Control and Navigation for Autonomous Aerospace Vehicles-ACNAAV 2015, 28(9), 186–191. https://doi.org/10.1016/j.ifacol.2015.08.081
   Google Scholar
• Poonawala, H. A., & Spong, M. W. (2017). Time-optimal velocity tracking control for differential drive robots. Automatica, 85, 153–157. https://doi.org/10.1016/j.automatica.2017.07.038
   Web of Science ®Google Scholar
• Rousseau, G., Maniu, C. S., Tebbani, S., Babel, M., & Martin, N. (2019). Minimum-time B-spline trajectories with corridor constraints. Application to cinematographic quadrotor flight plans. Control Engineering Practice, 89, 190–203. https://doi.org/10.1016/j.conengprac.2019.05.022
   Web of Science ®Google Scholar
• Sundar, S., & Shiller, Z. (1997). Optimal obstacle avoidance based on the Hamilton-Jacobi-Bellman equation. IEEE Transactions on Robotics and Automation, 13(2), 305–310. https://doi.org/10.1109/70.563653
   Google Scholar
• Szuster, M., & Hendzel, Z. (2018). Optimal control methods for mechatronic systems. In Intelligent optimal adaptive control for mechatronic systems (pp. 61–83). Springer Studies in Systems, Decision and Control.
   Google Scholar
• Takei, R., & Tsai, R. (2013). Optimal trajectories of curvature constrained motion in the Hamilton-Jacobi formulations. Journal of Scientific Computing, 54(2–3), 622–644. https://doi.org/10.1007/s10915-012-9671-y
   Web of Science ®Google Scholar
• Techy, L., & Woolsey, C. A. (2009). Minimum-time path planning for unmanned aerial vehicles in steady uniform winds. Journal of Guidance, Control, and Dynamics, 32(6), 1736–1746. https://doi.org/10.2514/1.44580
   Web of Science ®Google Scholar
• Tonon, D., Aronna, M. S., & Kalise, D. (2017). Optimal control: Novel directions and applications. Springer lecture notes in mathematics 2180.
   Google Scholar
• Tsai, Y.-H. R., Cheng, L.-T., Osher, S., & Zhao, H.-K. (2017). Fast sweeping algorithms for a class of Hamilton-Jacobi equations. SIAM Journal on Numerical Analysis, 41(2), 673–694. https://doi.org/10.1137/S0036142901396533
   Google Scholar
• Tsourdos, A., White, B., & Shanmugavel, M. (2010). Cooperative path planning of unmanned aerial vehicles. John Wiley and Sons.
   Google Scholar
• Wang, S., Gao, F., & Teo, K. L. (2000). An upwind finite-difference method for the approximation of viscosity solutions to Hamilton-Jacobi-Bellman equations. IMA Journal of Mathematical Control and Information, 17(2), 167–178. https://doi.org/10.1093/imamci/17.2.167
   Google Scholar
• Wolek, A., & Woolsey, C. A. (2017). Model-based path planning. In Sensing and control for autonomous vehicles (pp. 183–206). Springer lecture notes in control and information sciences, 474.
   Google Scholar
• Wolek, A., Cliff, E. M., & Woolsey, C. A. (2016). Time-optimal path planning for a kinematic car with variable speed. Journal of Guidance, Control, and Dynamics, 39(10), 2374–2390. https://doi.org/10.2514/1.G001317
   Web of Science ®Google Scholar
• Wu, W., Chen, H., & Woo, P. Y. (2000). Time optimal path planning for a wheeled mobile robot. Journal of Robotic Systems, 17(11), 585–591. https://doi.org/10.1002/1097-4563(200011)17:11<585::AID-ROB1>3.0.CO;2-7
   Google Scholar
• Yang, D., Li, D., & Sun, H. 2D Dubins path in environment with obstacle. Mathematical Problems in Engineering, 2013. https://doi.org/10.1155/2013/291372
   Web of Science ®Google Scholar
• Yang, G., & Kapila, V. (2002). Optimal path planning for unmanned air vehicles with kinematic and tactical constraints. 41st IEEE conference on decision and control (pp. 1301–1306), Las Vegas, NV, USA.
   Google Scholar
• Zdesar, A., & Škrjanc, I. (2018, January). Optimum velocity profile of multiple Bernstein-Bézier curves subject to constraints for mobile robots. ACM Transactions on Intelligent Systems and Technology 9(5). Article No. 56. https://doi.org/10.1145/3183891
   Web of Science ®Google Scholar
• Zhakatayev, A., Rubagotti, M., & Varol, H. A. (2017). Time-optimal control of variable-stiffness-actuated systems. IEEE/ASME Transactions on Mechatronics, 22(3), 1247–1258. https://doi.org/10.1109/TMECH.2017.2671371
   Web of Science ®Google Scholar
• Zhao, H. (2005). A fast sweeping method for Eikonal equations. Mathematics of Computation, 74(250), 603–627. https://doi.org/10.1090/S0025-5718-04-01678-3
   Web of Science ®Google Scholar
• Zhao, H. (2016). The fast sweeping method for stationary Hamilton-Jacobi equations. In Handbook of numerical analysis chapter 22 (Vol. 17, pp. 585–601), Science Direct.
   Google Scholar
• Zhu, J., Trélat, E., & Cerf, M. (2017). Geometric optimal control and applications to aerospace. Pacific Journal of Mathematics for Industry, 9(8), 41. https://doi.org/10.1186/s40736-017-0033-4
   Google Scholar
• Zollars, M. D., Cobb, R. G., & Grymin, D. J. (2018). Simplex optimal control methods for urban environment path planning. 2018 AIAA information systems-AIAA Infotech@ aerospace (pp. 16), Kissimmee, Florida, USA.
   Google Scholar