Modified A* Algorithm for Obstacle Avoidance for Unmanned Surface Vehicle
Article information
Abstract
Efficient path planning is essential for unmanned surface vehicle (USV) navigation. The A* algorithm is an effective algorithm for identifying a safe path with optimal distance cost. In this study, a modified version of the A* algorithm is applied for planning the path of a USV in a static and dynamic obstacle environment. The current study adopts the A* approach while maintaining a safe distance between the USV and obstacles. Two important parameters―path length and computational time―are considered at various start times. The results demonstrate that the modified approach is effective for obstacle avoidance by a USV that is compliant with the International Regulations for Preventing Collision at Sea (COLREGs).
1. Introduction
Advances in unmanned surface vehicle technology, particularly in matters related to path planning optimization, have recently gained substantial attention. As they can operate under several different environmental conditions with high flexibility and several sensors that can be installed based on the demands of the mission, USVs (unmanned surface vehicles) offer the benefits of minimized casualty risk and reduced costs. This study focuses on improving the path planning of an obstacle avoidance system for an autonomously operated USV.
In the development of an obstacle avoidance system for USVs that is compliant with the COLREGs (International Regulations for Preventing Collision at Sea), path planning is extended to use the A* algorithm to improve its efficiency (Loe, 2008). The safe, optimal, and feasible paths produced by the path planning technique have been implemented successfully (Campbell and Naeem, 2012). When a USV operates in an obstacle field, the distance from the USV to the obstacles, the computational time, and the smoothness of the final path are essential factors that are employed to assess the ability of the USV (Mohammadi et al., 2014).
An effective path planning approach is required to improve the level of autonomy of USVs. When calculating the most efficient path between a starting point and a goal point in a grid map consisting of nodes, Dijkstra’s algorithm is often used (Singh et al., 2018; Niu et al., 2016a). The more general algorithm, A*, which is the best-first search algorithm, is also used for path planning. An optimal path planning method has been shown to generate a feasible path using a constrained A* algorithm for a USV in a confined maritime environment, where dynamic obstacles are a concern (Singh et al., 2019). Several other methods have been used for path planning for marine vessels, including artificial potential field (Xie et al., 2014), fast marching (FM) (Liu and Bucknall, 2015), real-time R* (RTR*), and partitioned learning real-time A* (PLRTA*) (Cannon et al., 2012). A modified A* algorithm is applied in this study using a grid map and heuristic cost.
It is essential to consider environments containing static as well as dynamic obstacles in path planning for obstacle avoidance by a USV, which makes it more complicated to find a path when considering computational time and travelling distance (Ripon et al., 2016). An effective controller must be designed for optimal path generation in an environment including both static and dynamic obstacles (Patle et al., 2015). In this paper, we consider a dynamic obstacle environment with dynamic obstacles moving in various directions at a constant velocity for several different situations in accordance with the COLREGs.
Autonomous navigation, obstacle avoidance, and path planning are essential for a USV in a practical marine environment (Larson et al., 2006). The waypoint approach is widely used for path planning algorithms for obstacle avoidance (Petereit et al., 2013). The present study adopts a waypoint approach for USV navigation in a practical marine environment. When a USV operates in an environment containing both static and dynamic obstacles, the waypoint selection is impacted, as it is refined to reduce the number of waypoints for the reliability of the path-following mission (Niu et al., 2016b).
The A* approach is modified to make it suitable for identifying the sequence of optimal waypoints that help a USV operate in a practical environment while conserving energy. During obstacle avoidance, computational time and safety distance are crucial factors in determining the feasibility of the approach. In addition, path length and time consumption are also considered in this study.
2. Problem Definition and Assumptions
Autonomous navigation is an essential requirement of an USV. A path planning algorithm must be implemented with high efficiency to achieve accurate autonomous navigation. In this study, we have selected the modified A* algorithm to generate the optimal path with a sequence of waypoints for the autonomous navigation of a USV, which navigates in a practical environment, where static and dynamic obstacles have a significant impact on the sequence of waypoints selected from the program.
To develop the conventional A* approach and improve the autonomy of the USV, the current study adopts the A* approach with a safety distance between the USV and static obstacles as well as dynamic obstacles to ensure safety. When a sequence of waypoints is generated in a grid map, the safety distance is generated by expanding the boundary of obstacles, as depicted in Fig. 1. The relationship between the computational time and path length over starting time in the simulation is used to evaluate the effectiveness of the proposed algorithm in certain specific environmental situations stated in the COLREGs, such as overtaking, head-on, and crossing. The confined sea environment in South Korea is selected as the study area and the velocity and direction of the target vessel are pre-defined. The grid cell boundary of the dynamic obstacle is expanded to prevent the resultant paths from crossing in this area.
The COLREGs published by the IMO (International Maritime Organization) are a set of international rules aiming to avoid collisions at sea. It consists of three main parts: Part A―General, Part B―Steering and Sailing, and Part C―Lights and Shapes. The current study focuses on Part B, the main rules of which are described in Fig. 2.
3. Research Methodology
3.1 Map Processing
Fig. 3 indicates that map processing is the first step in the implementation of the path planning approach. Information regarding the topographic map and dynamic obstacles is predefined before implementing the path planning approach. In this study, as shown in Fig. 4, an image of the sea area in South Korea with a regional range of 30.052°–30.070°N, 128.562°–128.595°E is selected as the study area. For a USV to be able to navigate in the practical marine environment, the image requires preprocessing to generate an effective grid map. To solve this problem, the Otsu algorithm (Song et al., 2019), which is widely used to convert an image into its binary form, is used to create a threshold image from an initial image that is converted into a screen coordinate frame from the earth coordinate frame. Subsequently, the generated binary image is divided into two areas―an area with obstacles and a rest area with no obstacles. The obstacle area has a grid cell value equal to 1, whereas the rest area has a grid cell value equal to 0. These values are stored in a file as a matrix, and this is considered as input data for the path planning algorithm. The study area of 6,000,000 m2 has a width of 2000 m and a length of 3000 m, and the size of each grid cell is 20 m × 20 m.
3.2 Modified A* Algorithm for Obstacle Avoidance
In the current study, the A* approach is modified to make it suitable for using the grid map and safety distance between the USV and obstacles. The modified A* algorithm generates a sequence of safer waypoints for the USV to help it navigate along an optimal path, which is the highest priority in practical marine navigation. The A* algorithm is selected because it has shown the ability to determine a path with a short computational time. The computational time of the modified A* algorithm is shorter than those of the conventional A* algorithm and some of the algorithms mentioned in Section 1.
The priority queue is the place in which all nodes are stored; if a node has a minimum of f(Xi), it is placed in the front of the priority queue. Heuristic guidance is used in this study to optimize the cost of the path from the considered node to the goal node. Fig. 5 illustrates the difference between using the heuristic cost and ignoring the heuristic cost to identify the path. It indicates that the number of searched nodes is substantially reduced when the heuristic cost is applied, which is one of the factors that aids in reducing the computational time.
As depicted in Fig. 6, there are two styles to expand each node in the grid map: 4-connectivity and 8-connectivity. For node expansion, 8-connectivity, which indicates that there are eight searched nodes in each iteration, is applied to improve the efficiency of the program and search further in other directions, as illustrated in Fig. 7. When a node is selected from the priority queue, the costs of all child nodes in all possible directions for that node are updated using the following formula:
where h(Xi) is the distance remaining to the goal and g(Xi) is the total length of a path from the starting node to the considered node to avoid selecting impractical nodes. A Euclidian function is used to determine the value of h(Xi).
To determine the optimal path with a safety distance generated by extending the nodes surrounding the obstacles, which is a sequence of waypoints, each node is identified by the matrix stored in its parent node.
On the grid map, additional nodes around the target vessel are added to the closed list to prevent the USV from crossing this area. The following domain regions around the USV are illustrated in Fig. 8: O representing the overtaking region, C representing the crossing region, and H representing the head-on region.
4. Simulation Results and Discussions
4.1 Static Obstacle Avoidance with various safety distances
To determine the optimal path for the USV with static and dynamic obstacles, the safety distance illustrated in Fig. 1 is applied to the proposed algorithm with a safety distance value consisting of 0, 1, 2, 3, and 4 pixels. The resultant path is generated using the modified A* algorithm shown in Fig. 9 with the number of searched nodes depicted on the grid map. Computational efficiency is achieved with the resultant path generated from the program and 3183 search nodes in a static obstacle environment.
Various resultant paths are generated with the various safety distances indicated in Fig. 10. When the safety distance is set to a greater value, it indicates that the number of searched nodes has decreased, leading to reduced computational time. The modified A* algorithm will produce a computationally efficient path with a larger safety distance compared to the path generated without considering the safety distance, as depicted in Fig. 11.
4.2 Dynamic Obstacle Avoidance Complying with COLREGs
In a dynamic obstacle avoidance environment, various COLREGs cases such as overtaking, crossing, and head-on scenarios are simulated. The safety distance used for all scenarios is 1 pixel. The two main parameters used in this study are computational time and path length, obtained as the output data of the program and computed for each starting time of the mission. The path length and trajectories of an USV and target vessel are stored using the matrix at all locations in the grid map. This helps the USV determine the distance to the target vessel at any time.
First, the overtaking case depicted in Fig. 12 is simulated in the grid map of the confined sea. Table 1 provides the navigation information for the USV and the target vessel.
Fig. 13 shows the resultant path generated by the modified A* algorithm with various starting times. The position of the target vessel is plotted at each starting point on the grid map, which is based on navigation information for the target vessel such as its velocity and direction. In this case, the target vessel navigates at a velocity of 5.144 m/s along the straight line. The relationship between the path length and computational time at each starting time is depicted in Fig. 14. The general trend presented in these figures is that the computational time increases with increasing path length.
Further, the USV starts to cross the target vessel at 8 s while the target vessel moves in the direction of 135° measured counterclockwise from the X-coordinate with a velocity of 10.289 m/s as shown in Fig. 15. Table 2 provides the navigation information for the USV and the target vessel.
Fig. 16 shows the resultant paths generated by the modified A* algorithm at various starting times. The relationship between path length and computational time with each starting time is presented in Fig. 17. When the starting time is 0 s, a potential collision is confirmed, leading to increases in path length and computational time. In the other cases, the potential collision is not confirmed, which leads to resultant paths generated with the same path length value.
Finally, the target vessel is assumed to move on a specific course, which continuously changes when the potential collision is confirmed, with a velocity of 10.289 m/s in the head-on scenario as shown in Figs. 18-20. Table 3 provides the navigation information for the USV and the target vessel.
5. Conclusions
A modified A* algorithm for planning the path of a USV in a confined sea was proposed and evaluated. The results indicate that the modified A* algorithm, which incorporates a safety distance to ensure sufficient distance between the USV and any obstacles, was evaluated in a marine environment. The safer path with a sequence of waypoints was generated in various scenarios in accordance with the COLREGs.
Techniques including map processing and 8-connectivity were used to strengthen the results. The modified A* algorithm provides robust and computationally efficient path planning for the USV in a static and dynamic obstacle environment. In future studies, the wind, wave, and current will be included in the environmental conditions for planning the path of the USV. Further, the path obtained from the modified A* algorithm will be smoothened to become the shortest path.
Acknowledgements
This study was supported by the research project “Development of 6-DOF dynamic modeling and simulation of a unmanned surface vehicle” of LIG Nex1.