# Path Planning and Collision Avoidance in Unknown Environments for USVs Based on an Improved D* Lite
###### Abstract  
Path planning and collision avoidance during autonomous navigation in unknown environments is a crucial issue for unmanned surface vehicles (USVs). This paper improves the traditional D* Lite algorithm and achieves multi-goal path planning and collision avoidance for USVs in unknown and complex environments. By expanding the adjacent search range and setting a safe distance for USVs, we solve the issue of limited steering maneuverability in USVs with fewer DOF during autonomous navigation. We propose an approach to optimize the planned path during navigation by comparing the estimated distance with the actual distance between the current waypoint and the goal waypoint. A minimum binary heap is used to optimize the priority queue of the D* Lite and significantly reduce the path search time. Simulation results show that the improved D * Lite can significantly reduce the path planning time, optimize the planned path and solve the issue of limited steering maneuverability in USVs. We apply the algorithm to a real USV for further tests. Experimental results show that the USV can plan an optimized path while avoiding both static and dynamic obstacles in complex environments with a safe distance during autonomous navigation. * 29 July 2021  
25 August 2021  
**Published: 26 August 2021**
In 1994, [PERSON], from the Robotics Institute of Carnegie Mellon University, proposed a Dynamic A* algorithm (D*) [11; 12]. It has high path planning efficiency in partially known or continuously changing environments [13]. The D* was applied on the Mars probe launched by the U.S. and achieved huge success [14; 15]. In 2004, [PERSON] introduced an approach involving incremental environmental information and proposed a Lifelong Planning A* algorithm (LPA*) [16], which significantly improves the path planning efficiency by reusing information [17]. The LPA* algorithm is efficient for path planning when it has specific start and goal nodes. However, it has to replan the whole path from the original start node to the goal node when a new obstacle appears on the path. To efficiently plan a path in a scenario with a changing start node and a fixed goal node, [PERSON], [PERSON] et al. developed a D* Lite algorithm based on the LPA* and D* algorithms [18; 19]. It combines heuristic and incremental search and achieves fast path planning from a dynamic start node to a fixed goal node. D* Lite only takes into account the path information between the current node and the goal node while replanning. Therefore, its path planning efficiency is much higher than that of D* and LPA*. Thus, D* Lite is now widely applied to navigation systems for mobile robots and autonomous vehicles, including the prototypes of the Opportunity and Spirit Mars probes and the navigation system that won the Urban Challenge held by the Defence Advanced Research Projects Agency [20]. To further reduce the search space, improve the search efficiency and optimize the path in dynamic and complex environments, scholars are increasingly attempting to combine incremental search with sophisticated heuristic search for path planning. For example, in 2005, [PERSON], et al. developed a delayed D* algorithm [21], which can improve the search efficiency by delaying the update of locally inconsistent nodes. [PERSON] et al. developed a D* Lite-based real-time multi-agent path planning algorithm for dynamic environments [22]. In 2015, [PERSON], et al. proposed a D* lite label algorithm based on D* Lite, which can accelerate the path planning by preventing some nodes from being repeatedly updated. [PERSON], [PERSON] et al. improved the heuristic function of D* Lite to reduce the search area and accelerate the planning speed [23]. [PERSON], [PERSON] et al. proposed ID* Lite, which can increase the speed up to five times for a variety of benchmarks [24]. [PERSON], [PERSON] et al. proposed an enhanced D* lite and implemented it on a real-life situation using Team AmigoBot [25]. [PERSON], [PERSON] et al.