Theta* algorithm is a searching-based path planning algorithm that gives an optimal path with more flexibility on route angle than A* method. The dynamics of USV is characterized by large inertia, so that larger turning angle is preferred. In view of the shortcomings of traditional Theta* algorithm, such as being hard to balance overall situation and details in long-distance planning, and lacking of waypoint replacement scheme when a waypoint is unreachable, it is inappropriate to make long-distance planning through Theta* algorithm directly. In order to ensure safe navigation for unmanned surface vehicle (USV), this paper proposes a multi-scale Theta* algorithm to solve these defects. Simulation result manifests the proposed scheme can provide a path clear of obstacles with several fold reduction in time consumption. The proposed planning method simplifies path planning process and contributes to the development of marine transportation.
DellingDSandersPSchultesD, et al. Engineering route planning algorithms. In: LernerJWagnerDZweigKA (eds) Algorithmics of large and complex networks. Lecture Notes in Computer Science. Vol. 5515. Berlin, Heidelberg: Springer, 2009, pp.117–139.
2.
TahirZQureshiAHAyazY, et al. Potentially guided bidirectionalized RRT* for fast optimal path planning in cluttered environments. Robotics and Autonomous Systems2018; 108: 13–27.
3.
MavrovouniotisMLiCYangS.A survey of swarm intelligence for dynamic optimization: algorithms and applications. Swarm Evol Comput2017; 33: 1–17.
ZhouBGaoFWangL, et al. Robust and efficient quadrotor trajectory generation for fast autonomous flight. IEEE Robotics and Automation Letters (RA-L). https://arxiv.org/abs/1907.01531 (2019, accessed 15 March 2021).
6.
WangMPanY.Research on optimal path planning with constraints based on GIS. J Beijing Inst Technol2016; 36(8): 851–856.
7.
GuzziJChavez-GarciaRONavaM, et al. Path planning with local motion estimations. IEEE Robot Autom Lett2020; 5(2): 2586–2593.
8.
DoQHMitaSYonedaK.Practical global and local path planning algorithm for autonomous vehicles parking. J Jpn Soc Precis Eng2014; 80(3): 308–315.
9.
GaoFWangLZhouB, et al. Teach-repeat-replan: A complete and robust system for aggressive flight in complex environments. Robotics. https://arxiv.org/abs/1907.00520 (2019, accessed 15 March 2021).
10.
SyedUAKunwarFIqbalM.Guided autowave pulse coupled neural network (GAPCNN) based real time path planning and an obstacle avoidance scheme for mobile robots. Rob Auton Syst2014; 62(4): 474–486.
11.
SinghYBibuliMZereikE, et al. A novel double layered hybrid multi-robot framework for guidance and navigation of unmanned surface vehicles in a practical maritime environment. J Mar Sci Eng2020; 8(9): 624.
12.
MinaTSinghYMinBC.Maneuvering ability-based weighted potential field framework for multi-USV navigation, guidance, and control. Mar Technol Soc J2020; 54(4): 40–58.
13.
DanielKNashAKoenigS, et al. Theta*: any-angle path planning on grids. J Artif Intell Res2010; 39: 533–579.
14.
FanDShiP. Improvement of Dijkstra’s algorithm and its application in route planning. In: Seventh international conference on fuzzy systems and knowledge discovery, Yantai, China, 10–12 August 2010, vol. 4, pp.1901–1904. New York, NY: IEEE.
15.
ValenzanoRSturtevantNSchaefferJ.Adding exploration to greedy best-first search. Report, 2014.
XieLXueSZhangJ, et al. A path planning approach based on multi-direction A* algorithm for ships navigating within wind farm waters. Ocean Eng2019; 184: 311–322.
StentzA.Optimal and efficient path planning for partially known environments. In: HebertMHThorpeCStentzA (eds) Intelligent unmanned ground vehicles. Autonomous navigation research at Carnegie Mellon. Boston, MA: Springer US, 1997, pp.203–220.
20.
HauerFKunduARehgJM, et al. Multi-scale perception and path planning on probabilistic obstacle maps. In: Proceedings – IEEE international conference on robotics and automation, Seattle, WA, 2015, pp.4210–4215. New York, NY: IEEE.
21.
HauerFTsiotrasP. Reduced complexity multi-scale path-planning on probabilistic maps. In: 2016 IEEE international conference on robotics and automation (ICRA), Stockholm, Sweden, 2016, pp.83–88. New York, NY: IEEE.
22.
ZhaoJJiaPFuS. Modeling of uncertain environment based on multi-scale grid method. In: 2012 IEEE 2nd international conference on cloud computing and intelligence systems, Hangzhou, China, 2012, vol. 3, pp.1205–1209. New York, NY: IEEE.
LiaoSBaiY.A new grid-cell-based method for error evaluation of vector-to-raster conversion. Comput Geosci2010; 14(4): 539–549.
25.
ZhouCChenZYafeiW. Research on parallel rasterization algorithm based on containment test method. Geogr Geo Inf Sci2014; 30(1): 32–36.
26.
WesselPSmithWHF. A global, self-consistent, hierarchical, high-resolution shoreline database. J Geophys Res Solid Earth1996; 101(B4): 8741–8743.
27.
ZheDYuanqiaoWLiangH, et al. Route planning for vessel based on dynamic complexity map. J Syst Simul2018; 30(6): 2390–2398.
28.
TamCKBucknallR.Review of collision avoidance and path planning methods for ships in close range encounters. J Navig2009; 62: 455–476.
29.
ShenHHashimotoHMatsudaA, et al. Automatic collision avoidance of multiple ships based on deep Q-learning. Appl Ocean Res2019; 86: 268–288.
30.
LaValleSM.Planning algorithms. New York, NY: Cambridge University Press, 2006.
31.
NashAKoenigSToveyC.Lazy theta*: any-angle path planning and path length analysis in 3D. In: Proceedings of the third annual symposium on combinatorial search, SOCS 2010, Stone Mountain, GA, USA, 2010.
32.
SaranliARussellSNorvigP.Artificial intelligence: a modern approach. 2nd ed. Fort Collins, Colorado: Prentice Hall, 2003, pp.97–104.
33.
DalianCOSCO. Comprehensive performance test report of ship Yupeng. Test report series No.2016Z-C133, 2016. Dalian, China: Dalian COSCO Shipping Engineering Co., Ltd.
34.
ZhangXJinY.Control system modeling and digital simulation. 2nd ed.Dalian, China: Dalian Maritime University Press, 2013, pp.103–117.
35.
SujitPBSaripalliSSousaJB. An evaluation of UAV path following algorithms. In: 2013 European control conference (ECC), Zurich, Switzerland, 2013, pp.3332–3337. New York, NY: IEEE.
