[논문]Modified A* Algorithm for Obstacle Avoidance for Unmanned Surface Vehicle

Vo, Anh Hoa; Yoon, Hyeon Kyu; Ryu, Jaekwan; Jin, Taekseong

doi:10.26748/ksoe.2019.067

**Modified A* Algorithm for Obstacle Avoidance for Unmanned Surface Vehicle** 원문보기

韓國海洋工學會誌 = Journal of ocean engineering and technology, v.33 no.6, 2019년, pp.510 - 517

Vo, Anh Hoa (Department of Naval Architecture and Marine Engineering, Changwon National University) , Yoon, Hyeon Kyu (Department of Naval Architecture and Marine Engineering, Changwon National University) , Ryu, Jaekwan (Unmanned) , Jin, Taekseong (Unmanned)

Abstract ▼ AI-Helper

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

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

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.

제안 방법

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.
), 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.
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.
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.
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 study was supported by the research project “Development of 6-DOF dynamic modeling and simulation of a unmanned surface vehicle” of LIG Nex1.
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.

대상 데이터

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.

참고문헌 (15)

Campbell, S., Naeem, W., 2012. A Rule-based Heuristic Method for COLREGs Compliant Collision Avoidance for an Unmanned Surface Vehicle. Proceedings of 9th IFAC on Maneuvering and Control of Marine Craft, Italy, 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 Avoid-ance for Unmanned Surface Vehicles. [Online] Available at: [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: [Accessed June 2018]
Mohammadi, A., Rahimi, M., Suratgar. A.A., 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 Un-manned Surface Vehicle. Proceedings of OCEANS 2016, Shanghai China. https://doi.org/10.1109/OCEANSAP.2016.7485430
Patle, B.K., Parhi, D., Jagadeesh, A., Sahu, O.P., 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, W.C., 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, N.K., Qaiduzzaman M.K., Islam, A.M., 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 Opti-mal 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 Environ-ment 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

LOADING...

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증