An enhanced A* method incorporating an encrypted memory database for ASV efficient local path planning

Yuanshuo Liu; Defeng Wu; Zheng You; Yuanshuo Liu; Defeng Wu; Zheng You

doi:10.3934/mbe.2024101

Mathematical Biosciences and Engineering

2024, Volume 21, Issue 2: 2302-2322. doi: 10.3934/mbe.2024101

Previous Article Next Article

Research article Special Issues

An enhanced A* method incorporating an encrypted memory database for ASV efficient local path planning

1.
School of Marine Engineering, Jimei University, Xiamen, China
2.
Fujian Provincial Key Laboratory of Naval Architecture and Ocean Engineering, Xiamen 361021, China

Received: 15 November 2023 Revised: 25 December 2023 Accepted: 09 January 2024 Published: 12 January 2024

For the autonomous surface vehicle (ASV) planning problem, an enhanced A* method incorporating encrypted memory database for ASV efficient local path planning is proposed. Considering the current various path planning problems mostly use methods with high time complexity, such as neural networks, we select the A* algorithm with low time complexity as the basis. To speed up the path planning rate and further improve the real-time and realistic algorithm, this paper modifies the heuristic function of the A* algorithm by combining the motion mode of ASV. In response to the problem that the target point is far from the detection, we improve the target point design mechanism and create a new temporary target point within the detection range. In addition, the algorithm incorporates a memory database, which can record commonly used waters or retain the environmental path of navigated waters as a priori information. When the same waters are reencountered, the memory database information can be read directly to complete the navigation. Moreover, the memory database is encrypted to prevent information leakage. Finally, a simulation environment is built to verify the effectiveness of the proposed algorithm by comparison with some existing algorithms.
- autonomous surface vehicle (ASV),
- path planning,
- memory database,
- enhanced A* algorithm,
- improved heuristic function
Citation: Yuanshuo Liu, Defeng Wu, Zheng You. An enhanced A* method incorporating an encrypted memory database for ASV efficient local path planning[J]. Mathematical Biosciences and Engineering, 2024, 21(2): 2302-2322. doi: 10.3934/mbe.2024101

Related Papers:

Abstract

For the autonomous surface vehicle (ASV) planning problem, an enhanced A* method incorporating encrypted memory database for ASV efficient local path planning is proposed. Considering the current various path planning problems mostly use methods with high time complexity, such as neural networks, we select the A* algorithm with low time complexity as the basis. To speed up the path planning rate and further improve the real-time and realistic algorithm, this paper modifies the heuristic function of the A* algorithm by combining the motion mode of ASV. In response to the problem that the target point is far from the detection, we improve the target point design mechanism and create a new temporary target point within the detection range. In addition, the algorithm incorporates a memory database, which can record commonly used waters or retain the environmental path of navigated waters as a priori information. When the same waters are reencountered, the memory database information can be read directly to complete the navigation. Moreover, the memory database is encrypted to prevent information leakage. Finally, a simulation environment is built to verify the effectiveness of the proposed algorithm by comparison with some existing algorithms.

References

[1]	G. Zhang, X. Shang, J. Liu, W. Zhang, Improved iterative learning path-following control for usv via the potential-based dvs guidance, Ocean Eng., 280 (2023), 114543. https://doi.org/10.1016/j.oceaneng.2023.114543 doi: 10.1016/j.oceaneng.2023.114543
[2]	D. Wu, K. Yuan, Y. Huang, Z. M. Yuan, L. Hua, Design and test of an improved active disturbance rejection control system for water sampling unmanned surface vehicle, Ocean Eng., 245 (2022), 110367. https://doi.org/10.1016/j.oceaneng.2021.110367 doi: 10.1016/j.oceaneng.2021.110367
[3]	Y. Huang, D. Wu, L. Li, N. Feng, Event-triggered cooperative path following control of multiple underactuated unmanned surface vehicles with complex unknowns and actuator saturation, Ocean Eng., 249 (2022), 110740. https://doi.org/10.1016/j.oceaneng.2022.110740 doi: 10.1016/j.oceaneng.2022.110740
[4]	H. Huang, A. V. Savkin, C. Huang, Reliable path planning for drone delivery using a stochastic time-dependent public transportation network, IEEE Trans. Intell. Transp. Syst., 22 (2021), 4941–4950. https://doi.org/10.1109/TITS.2020.2983491 doi: 10.1109/TITS.2020.2983491
[5]	N. Wang, Y. Zhang, C. K. Ahn, Q. Xu, Autonomous pilot of unmanned surface vehicles: Bridging path planning and tracking, IEEE Trans. Veh. Technol., 71 (2022), 2358–2374. https://doi.org/10.1109/TVT.2021.3136670 doi: 10.1109/TVT.2021.3136670
[6]	N. Feng, D. Wu, H. Yu, A. S. Yamashita, Y. Huang, Predictive compensator based event-triggered model predictive control with nonlinear disturbance observer for unmanned surface vehicle under cyber-attacks, Ocean Eng., 259 (2022), 111868. https://doi.org/10.1016/j.oceaneng.2022.111868 doi: 10.1016/j.oceaneng.2022.111868
[7]	N. Wang, C. K. Ahn, Coordinated trajectory-tracking control of a marine aerial-surface heterogeneous system, IEEE/ASME Trans. Mechatron., 26 (2021), 3198–3210. https://doi.org/10.1109/TMECH.2021.3055450 doi: 10.1109/TMECH.2021.3055450
[8]	Z. You, H. Yan, J. Sun, H. Zhang, Z. Li, Reliable control for flexible spacecraft systems with aperiodic sampling and stochastic actuator failures, IEEE Trans. Cyber., 52 (2022), 3434–3445. https://doi.org/10.1109/TCYB.2020.3008045 doi: 10.1109/TCYB.2020.3008045
[9]	L. Lei, Y. Zhou, G. Yang, Multisource information fusion-based environment perception and dynamic model of underwater vehicle in irregular ocean environment, Inf. Fusion, 94 (2023), 257–271. https://doi.org/10.1016/j.inffus.2023.02.008 doi: 10.1016/j.inffus.2023.02.008
[10]	L. Velasco, J. Balbuena, J. Gonzales, F. Cuella, Development of an asv for oceanographic monitoring on the huarmey coast, in 2021 IEEE 30th International Symposium on Industrial Electronics (ISIE), (2021), 1–7. https://doi.org/10.1109/ISIE45552.2021.9576371
[11]	T. Sato, K. Kim, S. Inaba, T. Matsuda, S. Takashima, A. Oono, et al., Exploring hydrothermal deposits with multiple autonomous underwater vehicles, in 2019 IEEE Underwater Technology (UT), (2019), 1–5. https://doi.org/10.1109/UT.2019.8734460
[12]	C. Specht, E. Świtalski, M. Specht, Application of an autonomous/unmanned survey vessel (asv/usv) in bathymetric measurements, Polish Marit. Res., 24 (2017), 36–44. https://doi.org/10.1515/pomr-2017-0088 doi: 10.1515/pomr-2017-0088
[13]	J. Fraga, J. Sousa, G. Cabrita, P. Coimbra, L. Marques, Squirtle: An ASV for inland water environmental monitoring, in ROBOT2013: First Iberian Robotics Conference: Advances in Robotics, (2014), 33–39. https://doi.org/10.1007/978-3-319-03413-3
[14]	P. Luo, D. Wu, K. Yuan, Y. Yang, Observer-based adaptive integral terminal sliding mode formation control for a vessel train with obstacle avoidance, Ocean Eng., 283 (2023), 115075. https://doi.org/10.1016/j.oceaneng.2023.115075 doi: 10.1016/j.oceaneng.2023.115075
[15]	Y. Kawamura, T. Kato, J. Tahara, K. Masakazu, S. Baba, Development $\mu$-ASV using surfboard, in International Ocean and Polar Engineering Conference, (2020).
[16]	H. Wang, S. Diao, Research on application and key technology of usv in target ship, Ship Electron. Eng., 41 (2021), 5–8.
[17]	T. C. Furfaro, J. E. Dusek, K. D. von Ellenrieder, Design, construction, and initial testing of an autonomous surface vehicle for riverine and coastal reconnaissance, in OCEANS 2009, (2009), 1–6. https://doi.org/10.23919/OCEANS.2009.5422207
[18]	J. Curcio, J. Leonard, A. Patrikalakis, Scout–-A low cost autonomous surface platform for research in cooperative autonomy, in Proceedings of OCEANS 2005 MTS/IEEE, (2005), 725–729. https://doi.org/10.1109/OCEANS.2005.1639838
[19]	M. Caccia, Autonomous surface craft: prototypes and basic research issues, in 14th Mediterranean Conference on Control and Automation, (2006), 1–6. https://doi.org/10.1109/MED.2006.328786
[20]	L. Li, D. Wu, Y. Huang, Z. M. Yuan, A path planning strategy unified with a colregs collision avoidance function based on deep reinforcement learning and artificial potential field, Appl. Ocean Res., 113 (2021), 102759. https://doi.org/10.1016/j.apor.2021.102759 doi: 10.1016/j.apor.2021.102759
[21]	G. Reinelt, The Traveling Salesman: Computational Solutions for TSP Applications, Springer, 2003.
[22]	H. C. Chang, Y. L. Hsu, S. S. Hung, G. R. Ou, J. R. Wu, C. Hsu, Autonomous water quality monitoring and water surface cleaning for unmanned surface vehicle, Sensors, 21 (2021). https://doi.org/10.3390/s21041102
[23]	G. Saiteja, S. Pramod, Design and simulation of an autonomous surface vehicle for trash collection using ros, in 2021 IEEE 9th Region 10 Humanitarian Technology Conference (R10-HTC), (2021), 1–6. https://doi.org/10.1109/R10-HTC53172.2021.9641589
[24]	F. Keppler, N. Dunkelberg, S. Wagner, K. Janschek, Efficient multi-robot path planning for autonomous weed control on complex field configurations, VDI Ber., 2395 (2022), 79–86. https://doi.org/10.51202/9783181023952 doi: 10.51202/9783181023952
[25]	M. Morin, I. Abi-Zeid, C. G. Quimper, Ant colony optimization for path planning in search and rescue operations, Eur. J. Oper. Res., 305 (2023), 53–63. https://doi.org/10.1016/j.ejor.2022.06.019 doi: 10.1016/j.ejor.2022.06.019
[26]	C. Lu, J. Yang, Path planning of subsea mining vehicle, in Proceedings of the International Offshore and Polar Engineering Conference, (2021), 368–374.
[27]	A. K. Sadhu, A. Konar, T. Bhattacharjee, S. Das, Synergism of firefly algorithm and q-learning for robot arm path planning, Swarm Evol. Comput., 43 (2018), 50–68. https://doi.org/10.1016/j.swevo.2018.03.014 doi: 10.1016/j.swevo.2018.03.014
[28]	S. Islam, A. Razi, A path planning algorithm for collective monitoring using autonomous drones, in 2019 53rd Annual Conference on Information Sciences and Systems (CISS), (2019), 1–6. https://doi.org/10.1109/CISS.2019.8693023
[29]	W. J. Harlin, D. A. Cicci, Ballistic missile trajectory prediction using a state transition matrix, Appl. Math. Comput., 188 (2007), 1832–1847. https://doi.org/10.1016/j.amc.2006.11.048 doi: 10.1016/j.amc.2006.11.048
[30]	J. Hu, D. Yan, J. Zheng, Embed behavior decision making into ship collision avoidance path planning based on ant colony and q-learning algorithm, Ind. Eng. Innovation Manage., 5 (2022), 20–28. https://doi.org/10.23977/ieim.2022.050105 doi: 10.23977/ieim.2022.050105
[31]	L. Yu, T. Qian, X. Ye, F. Zhou, Z. Luo, A. Zou, Research on obstacle avoidance strategy of usv based on improved grid method, in 4th International Symposium on Power Electronics and Control Engineering (ISPECE 2021), 2021. https://doi.org/10.1117/12.2620444
[32]	D. Xue, D. Wu, A. S. Yamashita, Z. Li, Proximal policy optimization with reciprocal velocity obstacle based collision avoidance path planning for multi-unmanned surface vehicles, Ocean Eng., 273 (2023), 114005. https://doi.org/10.1016/j.oceaneng.2023.114005 doi: 10.1016/j.oceaneng.2023.114005
[33]	N. Wang, H. He, Y. Hou, B. Han, Model-free visual servo swarming of manned-unmanned surface vehicles with visibility maintenance and collision avoidance, IEEE Trans. Intell. Transp. Syst., 2023 (2023), 1–13. https://doi.org/10.1109/TITS.2023.3310430 doi: 10.1109/TITS.2023.3310430
[34]	J. Yu, Z. Chen, Z. Zhao, P. Yao, J. Xu, A traversal multi-target path planning method for multi-unmanned surface vessels in space-varying ocean current, Ocean Eng., 278 (2023), 114423. https://doi.org/10.1016/j.oceaneng.2023.114423 doi: 10.1016/j.oceaneng.2023.114423
[35]	J. B. Escario, J. F. Jimenez, J. M. Giron-Sierra, Optimisation of autonomous ship manoeuvres applying ant colony optimisation metaheuristic, Exp. Syst. Appl., 39 (2012), 10120–10139. https://doi.org/10.1016/j.eswa.2012.02.069 doi: 10.1016/j.eswa.2012.02.069
[36]	Y. Singh, S. Sharma, R. Sutton, D. Hatton, Path planning of an autonomous surface vehicle based on artificial potential fields in a real time marine environment, in COMPIT'17: 16th International Conference on Computer and IT Applications in the Maritime Industries, (2017), 48–54. https://doi.org/10.1016/j.automatica.2004.10.006
[37]	R. Skjetne, T. I. Fossen, P. V. Kokotović, Adaptive maneuvering, with experiments, for a model ship in a marine control laboratory, Automatica, 41 (2005), 289–298. https://doi.org/10.1016/j.automatica.2004.10.006 doi: 10.1016/j.automatica.2004.10.006
[38]	E. Demirel, D. Bayer, Further studies on the COLREGs (collision regulations), TransNav, 9 (2015), 17–22. https://doi.org/10.12716/1001.09.01.02 doi: 10.12716/1001.09.01.02
[39]	E. W. Dijkstra, A note on two problems in connexion with graphs, in Edsger Wybe Dijkstra: His Life, Work, and Legacy, Association for Computing Machinery, (2022), 287–290. https://doi.org/10.1145/3544585
[40]	P. E. Hart, N. J. Nilsson, B. Raphael, A formal basis for the heuristic determination of minimum cost paths, IEEE Trans. Syst. Sci. Cyber., 4 (1968), 100–107. https://doi.org/10.1109/TSSC.1968.300136 doi: 10.1109/TSSC.1968.300136
[41]	H. Lyu, Y. Yin, Colregs-constrained real-time path planning for autonomous ships using modified artificial potential fields, J. Navig., 72 (2019), 588–608. https://doi.org/10.1017/S0373463318000796 doi: 10.1017/S0373463318000796
[42]	Z. Wang, X. Xiang, Improved astar algorithm for path planning of marine robot, in 2018 37th Chinese Control Conference (CCC), (2018), 5410–5414. https://doi.org/10.23919/ChiCC.2018.8483946

Reader Comments

Your name:*

Email:*
© 2024 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)