Modified A* Algorithm for Obstacle Avoidance for Unmanned Surface Vehicle

Article information

J. Ocean Eng. Technol. 2019;33(6):510-517
Publication date (electronic) : 2019 November 14
doi : https://doi.org/10.26748/KSOE.2019.067
*Department of Naval Architecture and Marine Engineering, Changwon National University, Changwon, Korea
**Unmanned/Robotic Systems, LIG Nex1 Co., Ltd., Seongnam, Korea
Corresponding author Hyeon Kyu Yoon: +82-55-213-3683, hkyoon@changwon.ac.kr
It is a recommended paper from the Proceedings of the 2019 Spring Symposium of the Korea Marine Robot Technology (KMRTS), which is one of the divisions of the Korean Society of Ocean Engineers (KSOE).
Received 2019 August 5; Revised 2019 October 24; Accepted 2019 November 11.

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.

Fig. 1

Resultant path generated by modified A* algorithm while considering safety distance

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.

Fig. 2

Collision-avoiding rules in COLREGs

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.

Fig. 3

Path planning approach

Fig. 4

Grid map of study area

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.

Fig. 5

Resultant path generated by considering heuristic cost

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:

Fig. 6

4-connectivity and 8-connectivity

Fig. 7

Resultant jagged path

(1) f(Xi)=h(Xi)+g(Xi)

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.

Fig. 8

USV domain for behavior according to COLREGs

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.

Fig. 9

Resultant path generated in 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.

Fig. 10

Comparison of resultant paths generated during static obstacle avoidance in grid map

Fig. 11

Comparison of computational time for various safety distances

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. 12

Resultant path generated in overtaking case

Navigation information for overtaking case

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.

Fig. 13

Comparison of resultant paths generated at various starting times for overtaking case

Fig. 14

Comparison of path length and computational time with respect to change in starting time for overtaking case

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. 15

Resultant path generated in crossing case

Navigation information for crossing case

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.

Fig. 16

Comparison of resultant paths generated at various starting times for crossing case

Fig. 17

Comparison of path length computational times obtained by changes in starting time for crossing case

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.

Fig. 18

Resultant path generated in head-on case

Fig. 19

Comparison of resultant paths generated at various starting times for head-on case

Fig. 20

Comparison of path length and computational time obtained owing to changes in starting time for head-on case

Navigation information for head-on case

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.

References

Campbell S, Naeem W. 2012. A Rule-based Heuristic Method for COLREGs Compliant Collision Avoidance for an Unmanned Surface Vehicle. In : Proceedings of 9th IFAC on Maneuvering and Control of Marine Craft. Italy. p. 386–391. https://doi.org/10.3182/20120919-3-IT-2046.00066.
Cannon J, Rose K, Ruml W. 2012;Real-Time Motion Planning with Dynamic Obstacle. Proceedings of the Fifth Annual Symposium on Combinatorial Search :33–40.
Larson J, Bruch M, Ebken J. 2006. Autonomous Navigation and Obstacle Avoidance for Unmanned Surface Vehicles. [Online] Available at: <https://techlinkcenter.org/wp-content/uploads/2018/11/a449463.pdf> [Accessed April 2006.
Liu Y, Bucknall R. 2015;Path Planning Algorithm for Unmanned Surface Vehicle Formations in a Practical Maritime Environment. Ocean Engineering 97:126–144. https://doi.org/10.1016/j.oceaneng.2015.01.008.
Loe G. 2008. Collision Avoidance for Unmanned Surface Vehicles. Norwegian University of Science and Technology. [Online] Available at: <https://core.ac.uk/download/pdf/52106491.pdf> [Accessed June 2018.
Mohammadi A, Rahimi M, Suratgar AA. 2014;A New Path Planning and Obstacle Avoidance Algorithm in Dynamic Environment. Proceedings of the ICEE 2014 :1301–1306. https://doi.org/10.1109/IranianCEE.2014.6999735.
Niu H, Lu Y, Savvaris A, Tsourdos A. 2016a;Efficient Path Planning Algorithm for Unmanned Surface Vehicle. Proceedings of the IFAC 49(23):121–126. https://doi.org/10.1016/j.ifacol.2016.10.331.
Niu H, Lu Y, Savvaris A, Tsourdos A. 2016b. Efficient Path Following Algorithm for Unmanned Surface Vehicle. In : Proceedings of OCEANS 2016. Shanghai China. https://doi.org/10.1109/OCEANSAP.2016.7485430.
Patle BK, Parhi D, Jagadeesh A, Sahu OP. 2015;Real Time Navigation Approach for Mobile Robot. Journal of Computers 12(2):135–142. https://doi.org/10.17706/jcp.12.2.135-142.
Petereit J, Emter T, Frey WC. 2013;Safe Mobile Robot Motion Planning for Waypoint Sequences in Dynamic Environment. Proceedings of IEEE International Conference on Industrial Technology :181–186. https://doi.org/10.1109/ICIT.2013.6505669.
Ripon NK, Qaiduzzaman MK, Islam AM. 2016;Effect of Heuristics in Path Planning for Mobile Robots in Uncertain and Dynamic Environment. Proceedings of IEEE 19th International Conference on Computer and Information Technology :451–456. https://doi.org/10.1109/ICCITECHN.2016.7860240.
Singh Y, Sharma S, Sutton R, Hatton D. 2018;Towards Use of Dijkstra Algorithm for Optimal Navigation of an Unmanned Surface Vehicle in a Real Time Marine Environment with Results from Artificial Potential Field. Journal of Marine Navigation and Safety of Sea Transportation 12(1):125–131. https://doi.org/10.12716/1001.12.01.14.
Singh Y, Sharma S, Sutton R, Hatton D, Khan A. 2019;A Constrained A* Approach Towards Optimal Path Planning for an Unmanned Surface Vehicle in a Aaritime Environment Containing Dynamic Obstacle and Ocean Currents. Ocean Engineering 169:187–201. https://doi.org/10.1016/j.oceaneng.2018.09.016.
Song R, Liu Y, Bucknall R. 2019;Smoothed A* Algorithm for Practical Unmanned Surface Vehicle Path Planning, Applied Ocean Research 83:9–20. https://doi.org/10.1016/j.apor.2018.12.001.
Xie S, Wu P, Peng Y, Luo J, Qu D, Li Q. 2014;The Obstacle Avoidance Planning for USV Based on Improved Artificial Potential Field. Proceedings of the IEEE International Conference on Information and Automation :746–751. https://doi.org/10.1109/ICInfA.2014.6932751.

Article information Continued

Fig. 1

Resultant path generated by modified A* algorithm while considering safety distance

Fig. 2

Collision-avoiding rules in COLREGs

Fig. 3

Path planning approach

Fig. 4

Grid map of study area

Fig. 5

Resultant path generated by considering heuristic cost

Fig. 6

4-connectivity and 8-connectivity

Fig. 7

Resultant jagged path

Fig. 8

USV domain for behavior according to COLREGs

Fig. 9

Resultant path generated in static obstacle environment

Fig. 10

Comparison of resultant paths generated during static obstacle avoidance in grid map

Fig. 11

Comparison of computational time for various safety distances

Fig. 12

Resultant path generated in overtaking case

Fig. 13

Comparison of resultant paths generated at various starting times for overtaking case

Fig. 14

Comparison of path length and computational time with respect to change in starting time for overtaking case

Fig. 15

Resultant path generated in crossing case

Fig. 16

Comparison of resultant paths generated at various starting times for crossing case

Fig. 17

Comparison of path length computational times obtained by changes in starting time for crossing case

Fig. 18

Resultant path generated in head-on case

Fig. 19

Comparison of resultant paths generated at various starting times for head-on case

Fig. 20

Comparison of path length and computational time obtained owing to changes in starting time for head-on case

Table 1

Navigation information for overtaking case

Information Velocity [m/s] Course [rad] Start point [−] Goal point [−] Start time [s]
Target vessel 5.144 0 (35, 59) (100, 59) 0
USV 10.289 --- (15, 30) (135, 85) 0

Table 2

Navigation information for crossing case

Information Velocity [m/s] Course [rad] Start point [−] Goal point [−] Start time [s]
Target vssel 10.289 2.356 (25, 35) (10, 50) 0
USV 10.289 --- (15, 30) (135, 85) 0

Table 3

Navigation information for head-on case

Information Velocity [m/s] Course [rad] Start point [−] Goal point [−] Start time [s]
Target vssel 10.289 --- (140, 90) (100, 70) 210
USV 10.289 --- (15, 30) (135, 85) 0