[논문]해양 로봇의 회전 반경을 고려한 경로 계획 알고리즘

김한근; 명현; 최현택

doi:10.5302/j.icros.2012.18.4.365

해양 로봇의 회전 반경을 고려한 경로 계획 알고리즘
Any-angle Path Planning Algorithm considering Angular Constraint for Marine Robot 원문보기

제어·로봇·시스템학회 논문지 = Journal of institute of control, robotics and systems, v.18 no.4, 2012년, pp.365 - 370

김한근 (한국과학기술원 건설 및 환경공학과) , 명현 (한국과학기술원 건설 및 환경공학과) , 최현택 (한국해양연구원)

Abstract ▼ AI-Helper

Most path planning algorithms for a marine robot in the ocean environment have been developed without considering the robot's heading angle. As a result, the robot has a difficulty in following the path correctly. In this paper, we propose a limit-cycle circle set that applies to the $Theta^*$ algorithm. The minimum turning radius of a marine robot is calculated using a limit-cycle circle set, and circles of this radius is used to generate a configuration space of an occupancy grid map. After applying $Theta^*$ to this configuration space, the limit-cycle circle set is also applied to the start and end nodes to find the appropriate path with specified heading angles. The benefit of this algorithm is its fast computation time compared to other 3-D ($x,y,{\theta}$) path planning algorithms, along with the fact that it can be applied to the 3-D kinematic state of the robot. We simulate the proposed algorithm and compare it with 3-D $A^*$ and 3-D $A^*$ with post smoothing algorithms.

주제어

AI 본문요약
AI-Helper

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

문제 정의

또한 대부분의 수중 로봇들은 기동성의 제한을 받는다는 가정 하에 경로 계획 알고리즘이 제안되고 있지만[9-13], 대부분의 경우는 회전 반경을 고려하지 않았다. 따라서 해양 로봇의 조종 성능과 그림 1의 문제를 해결하는 것이 본 논문의 연구 주제이다. 본 논문에서는 해양 로봇의 회전 반경을 고려한 경로 계획 알고리즘을 제안하고자 한다.
따라서 해양 로봇의 조종 성능과 그림 1의 문제를 해결하는 것이 본 논문의 연구 주제이다. 본 논문에서는 해양 로봇의 회전 반경을 고려한 경로 계획 알고리즘을 제안하고자 한다. 제안한 방법은 해양 로봇의 실제 회전 반경을 고려한 구성 공간을 생성하고, 리미트 사이클 원 집합(limit-cycle circle set)을 출발점과 도착점에 적용하여 3-D (x,y,^Θ) 경로를 생성한다.
본 논문에서는, Theta* 알고리즘을 확장하여 해양 로봇의 3-D 기구학 특성을 반영하는 경로 계획 알고리즘을 제안하였다. 해양 로봇의 회전 반경을 고려한 경로 계획을 하기 위해 우선 그리드 맵을 구성하는데 있어서 장애물 경계에 회전 반경의 반지름 크기를 갖는 원으로 확장하였고, 리미트 사이클 원 집합을 생성하여 이를 출발점과 도착점에 적용하였다.

가설 설정

그림1. (a) 잘못된 경로 생성의 예, 로봇이 장애물 근처에서 회전할 수 없다 (b) 로봇의 최대 조향 성능의 한계로 인해 경로를 추종할 수 없는 경우.
제안된 알고리즘은 출발점과 도착점의 왼편과 오른편에 최소 회전 반경을 갖는 순응 (accommodation) 원을 생성한 뒤, 포텐셜 필드(potential field) 방법으로 경로를 생성한다. 그 결과, 로봇의 기구학을 반영하는 경로를 생성하지만, 제안한 알고리즘은 포텐셜 필드 방법의 단점인 국소 최소점 문제를 피하기 위해, 출발점과 도착점 사이에 장애물이 없다는 가정을 하였다.

제안 방법

3-D A*와 3-D A* 후 곡선 처리 알고리즘은 해양 로봇의 회전 반경 구속 조건을 각도 단위로 사용하였고, 제안한 알고리즘은 미터 단위를 사용하여 경로 계획을 하였다. 시뮬레이션에서 로봇은 자북을 기준으로 180도 방향으로 출발하였고, 90도 방향으로 도착하도록 하였다.
본 논문에서는 원 집합을 이용하여 해양 로봇의 회전 반경을 고려할 수 있는 점유 그리드 맵을 생성하였다. 그림 4의 예제처럼, 그리드 맵에 표현된 장애물의 경계를 따라 해양 로봇의 회전 반경 r 의 반지름을 갖는 원으로 확장하여 해양 로봇의 회전 반경을 고려할 수 있는 경로를 생성할 수 있게 하였다. 또한, 이를 통해 얻을 수 있는 장점은 실제 해역에서 회전 반경으로 인해 지나갈 수 없는 지형을 그리드 맵의 장애물 영역을 확장함으로써 좀 더 안전한 경로를 얻을 수 있다는 점이다.
본 논문에서는 실제 지형 지도를 이용하여 제안한 알고리즘을 시뮬레이션 하였다. 시뮬레이션 결과는 기존에 제안 되었던 3-D A*, 3-D A* 후 곡선 처리 알고리즘과 비교하였고, 시뮬레이션 조건은 아래의 표 1에 나타내었다.
본 논문에서는 원 집합을 이용하여 해양 로봇의 회전 반경을 고려할 수 있는 점유 그리드 맵을 생성하였다. 그림 4의 예제처럼, 그리드 맵에 표현된 장애물의 경계를 따라 해양 로봇의 회전 반경 r 의 반지름을 갖는 원으로 확장하여 해양 로봇의 회전 반경을 고려할 수 있는 경로를 생성할 수 있게 하였다.
3-D A*와 3-D A* 후 곡선 처리 알고리즘은 해양 로봇의 회전 반경 구속 조건을 각도 단위로 사용하였고, 제안한 알고리즘은 미터 단위를 사용하여 경로 계획을 하였다. 시뮬레이션에서 로봇은 자북을 기준으로 180도 방향으로 출발하였고, 90도 방향으로 도착하도록 하였다. 그림 7은 같은 조건에서 각각 3-D A*와 3-D A* 후 곡선 처리, 리미트 사이클 원 집합과 Theta* 알고리즘의 시뮬레이션 결과를 나타내고 있다.
또한 Yong 등은 Dubin의 비홀로노믹 로봇을 위한 짧은 경로 생성 알고리즘을 제안하였다[5]. 제안된 알고리즘은 출발점과 도착점의 왼편과 오른편에 최소 회전 반경을 갖는 순응 (accommodation) 원을 생성한 뒤, 포텐셜 필드(potential field) 방법으로 경로를 생성한다. 그 결과, 로봇의 기구학을 반영하는 경로를 생성하지만, 제안한 알고리즘은 포텐셜 필드 방법의 단점인 국소 최소점 문제를 피하기 위해, 출발점과 도착점 사이에 장애물이 없다는 가정을 하였다.
제안한 방법은 해양 로봇의 실제 회전 반경을 고려한 구성 공간을 생성하고, 리미트 사이클 원 집합(limit-cycle circle set)을 출발점과 도착점에 적용하여 3-D (x,y,Θ) 경로를 생성한다.
출발점과 도착점의 선수각과 회전 반경을 고려하기 위해, 본 논문에서는 리미트 사이클 원 집합의 개념과 Theta*알고리즘을 통합하였다. II 장에서 소개하였던 리미트 사이클 방정식을 이용하여 그림 5와 같이, 출발점과 도착점에 시계 방향 및 반시계 방향의 원을 생성하였다.
본 논문에서는, Theta* 알고리즘을 확장하여 해양 로봇의 3-D 기구학 특성을 반영하는 경로 계획 알고리즘을 제안하였다. 해양 로봇의 회전 반경을 고려한 경로 계획을 하기 위해 우선 그리드 맵을 구성하는데 있어서 장애물 경계에 회전 반경의 반지름 크기를 갖는 원으로 확장하였고, 리미트 사이클 원 집합을 생성하여 이를 출발점과 도착점에 적용하였다. 결과적으로 다른 3-D 경로 계획 알고리즘에 비해 연산 속도가 매우 향상되었고, 현실적으로 추종이 가능한 경로를 생성할 수 있었다.
해양 로봇의 회전 반경을 고려한 경로를 생성하기 위해, 리미트 사이클 원 집합과 Theta* 알고리즘을 통합하였다. 그림 6의 알고리즘과 같이, 경로를 생성하기 전에 점유 그리드 맵에서 장애물을 로봇의 회전 반경 r 만큼 확장하고, Theta* 알고리즘을 통해 출발점과 도착점의 방향각을 고려 하지 않은 경로를 생성한다.

데이터처리

본 논문에서는 실제 지형 지도를 이용하여 제안한 알고리즘을 시뮬레이션 하였다. 시뮬레이션 결과는 기존에 제안 되었던 3-D A*, 3-D A* 후 곡선 처리 알고리즘과 비교하였고, 시뮬레이션 조건은 아래의 표 1에 나타내었다.

이론/모형

출발점과 도착점의 선수각과 회전 반경을 고려하기 위해, 본 논문에서는 리미트 사이클 원 집합의 개념과 Theta*알고리즘을 통합하였다. II 장에서 소개하였던 리미트 사이클 방정식을 이용하여 그림 5와 같이, 출발점과 도착점에 시계 방향 및 반시계 방향의 원을 생성하였다. 리미트 사이클 원 집합은 출발점에서 로봇의 방향각을 기준으로 왼쪽에는 시계방향 원을, 오른쪽에는 반시계 방향 원을 생성하고, 도착점에서는 반대로 로봇의 방향각을 기준으로 왼쪽 편에는 반시계 방향 원을, 오른쪽에는 시계 방향 원을 생성한다.
리미트 사이클 해석은 비선형 시스템에서 널리 사용되는 방법으로 본 논문에서는 리미트 사이클 수식을 이용하여 시계 방향 및 반 시계 방향의 원을 생성하여 로봇의 선수각 및 최대 회전각을 고려하기 위해 시작점과 출발점에 적용하였다[14-19].

성능/효과

Theta*에서는 비용 함수를 단순히 유클리디언 거리 값으로 하였다. 결과적으로 Theta* 알고리즘에 의해 생성된 경로는 A* 알고리즘에 의해 생성된 경로보다 더 최적이다.
해양 로봇의 회전 반경을 고려한 경로 계획을 하기 위해 우선 그리드 맵을 구성하는데 있어서 장애물 경계에 회전 반경의 반지름 크기를 갖는 원으로 확장하였고, 리미트 사이클 원 집합을 생성하여 이를 출발점과 도착점에 적용하였다. 결과적으로 다른 3-D 경로 계획 알고리즘에 비해 연산 속도가 매우 향상되었고, 현실적으로 추종이 가능한 경로를 생성할 수 있었다. 또한 제안한 알고리즘은 타 기종의 로봇에도 쉽게 적용이 가능하다.
그림 7은 같은 조건에서 각각 3-D A*와 3-D A* 후 곡선 처리, 리미트 사이클 원 집합과 Theta* 알고리즘의 시뮬레이션 결과를 나타내고 있다. 결과적으로 제안한 알고리즘이 해양 로봇의 회전 반경을 만족하면서도 좀 더 최적 경로를 생성하는 것을 알 수 있었다. 마지막으로 그림 8은 제안한 알고리즘이 같은 조건에서 회전 반경을 달리했을 때의 시뮬레이션 결과 이다.
마지막으로 그림 8은 제안한 알고리즘이 같은 조건에서 회전 반경을 달리했을 때의 시뮬레이션 결과 이다. 결론적으로 제안한 경로 계획 알고리즘이 다른 3-D 경로 계획 알고리즘보다 성능적으로 우수한 것을 알 수 있다.
Nash 등은 A*, A* 후 곡선 처리, Field D*, Theta* 등의 그리드 맵 기반의 경로 계획 알고리즘의 성능을 비교하였다[2]. 그 결과, 생성 경로 길이와 연산 시간에 있어서 Theta*가 가장 좋은 성능을 보였다. Theta*는 A*의 변형 알고리즘으로, 방향과 거리에 무관하게 노드를 탐색하고 연결할 수 있는 알고리즘이다.
그림 4의 예제처럼, 그리드 맵에 표현된 장애물의 경계를 따라 해양 로봇의 회전 반경 r 의 반지름을 갖는 원으로 확장하여 해양 로봇의 회전 반경을 고려할 수 있는 경로를 생성할 수 있게 하였다. 또한, 이를 통해 얻을 수 있는 장점은 실제 해역에서 회전 반경으로 인해 지나갈 수 없는 지형을 그리드 맵의 장애물 영역을 확장함으로써 좀 더 안전한 경로를 얻을 수 있다는 점이다. 하지만 제안한 점유 그리드 맵의 표현 방법으로는 출발점과 도착점의 선수각과 회전 반경을 고려할 수 없다는 단점이 있다.

후속연구

또한 제안한 알고리즘은 타 기종의 로봇에도 쉽게 적용이 가능하다. 추후에는 제안한 알고리즘을 수중 로봇의 3차원 경로 계획에 적용하여 회전 반경뿐만 아니라, 3차원적인 움직임을 고려한 경로 계획 알고리즘을 연구할 것이다.

질의응답

핵심어	질문	논문에서 추출한 답변
	Theta와 A알고리즘의 차이점은 무엇인가?	Theta는 기본적으로 A와 유사한 알고리즘으로 유일한 차이점은 부모 노드를 선택하는 방법에 있다. Theta*는 부 모 노드를 선택하는데 있어서 시야 선(line of sight) 함수를 이용하여 연결한다.
	모바일 로봇 항법 분야에서 그리드 기반의 맵은 어떤 것에 널리 사용되고 있는가?	모바일 로봇 항법 분야에서, 그리드 기반의 맵은 위치인식, 매핑, SLAM (Simultaneous Localization And Map-building), 경로 계획 등에 널리 사용되고 있다. 해양 로봇의 항법 문제도 로봇 항법 마찬가지로 그리드 기반의 맵 표현 방법으로 해결할 수 있고, 많은 연구자들이 적용하고 있다[1].
	Theta* 알고리즘이 해양 로봇에 적용되면 갖는 한계점은 무엇인가?	따라서 Theta* 알고리즘은 실시간으로 경로를 생성해야 하는 해양 로봇의 항법 문제를 해결하는데 있어서 적합하다. 하지만 수중 로봇을 제외한 대부분의 해양 로봇은 언더 액츄에이티드(under-actuated) 시스템이므로 방향각을 고려하지 않은 경로를 생성하면 그림 1과 같이, 경로 추종에 실패하거나, 장애물 회피시 위험한 상황에 처할 수 있다.

참고문헌 (20)

T. Lee, H. Chung, and H. Myung, "Multi-resolution path planning for marine surface vehicle considering environmental effects," in Proc. of IEEE OCEANS Conference, Spain, pp. 1-9, 2011.
A. Nash, K. Daniel, S. Koenig, and A. Felner, "Theta*: Any-angle path planning on grids," in Proceedings of AAAI Conference on Artificial Intelligence (AAAI), pp. 1-7, 2007.
J. Latombe, Robot Motion Planning, Kluwer Academic Publishers, Dodrecht, Netherlands, 1991.
J.-P. Laumond, "Finding collision-free smooth trajectories for a non-holonomic mobile robot," International Joint Conference on Artificial Intelligence, vol. 2, pp. 1120-1123, 1987.
C. Yong and E. J. Barth, "Real-time dynamic path planning for dubins' nonholonomic robot," Proc. of the 45th IEEE Conference on Decision & Control, San Diego, USA, pp. 2418-2423, 2006.
C.-K. Tam, R. Bucknall, and A. Greig, "Review of collision avoidance and path planning methods for ships in close range encounters," The Journal of Navigation, vol. 62, pp. 455-476, 2009.

상세보기
R. Szlapczynski, "A new method of ship routing on raster grids, with turn penalties and collision avoidance," The Journal of Navigation, vol. 59, pp. 27-42, 2006.

상세보기
R. Smierzchalski and Z. Michalewicz, Innovations in Robot Mobility and Control, Springer, Berlin, pp. 135-153, 2005.
D. Kruger, R. Stolkin, A. Blum, and J. Briganti, "Optimal AUV path planning for extended missions in complex, fast-flowing estuarine environments," in Proc. of IEEE International Conference on Robotics and Automation (ICRA), Rome, Italy, pp. 4265-4270, 2007.
B. Garau, A. Alvarez, and G. Oliver, "Path planning of autonomous underwater vehicles in current field with complex spatial variability: an A* approach," in Proc. of IEEE International Conference on Robotics and Automation (ICRA), Barcelona, Spain, pp. 194-198, 2005.
J. Witt and M. Dunbabin, "Go with the flow: Optimal AUV path planning in coastal environments," in Proc. of the Australasian Conference on Robotics and Automation, Canberra, Australia, pp. 1-9, 2008.
M. Soulignac, "Feasible and optimal path planning in strong current fields," IEEE Transactions on Robotics, vol. 27, no. 1, pp. 89-98, 2011.

상세보기
J. I. Gonzalez, D. H. Sosa, E. F. Perdomo, J. C. Gamez, A. C. D. Brito, and V. P. Maranon, "Path planning for underwater gliders using iterative optimization," in Proc. of IEEE International Conference on Robotics and Automation (ICRA), Shanghai, China, pp. 2374-2379, 2011.
K.-H. Rew and D.-H. Kim, "Limit-cycle navigation method for fast mobile robots," Journal of Institute of Control, Robotics and Systems (in Korean), vol. 14, no. 11, pp. 1130-1138, 2008.

원문보기 상세보기
J.-J. E. Slotine and W. Li, Applied Nonlinear Control, Prentice Hall, 1990.
E. V. Lewis, Principles of Naval Architecture, 2nd revision, vol. 3, The Society of Naval Architects and Marine Engineers, 1988.
H.-G. Kim, H. Myung, and H.-T. Choi, "Any-angle path planning algorithm considering angular constraint for marine surface vehicle," Proc. of 2011 ICROS (Institute of Control, Robotics and Systems) Daejeon Chungcheong Branch Conference (in Korean), pp. 15-20, Dec. 2011.
S.-M. Han and K. W. Lee, "Mobile robot navigation using circular path planning algorithm," Journal of Institute of Control, Robotics and Systems (in Korean), vol. 15, no. 1, pp. 105-110, Jan. 2009.

원문보기 상세보기
Y.-W. Lim, J.-S. Jeong, J.-U. An, and D.-H. Kim, "Path planning algorithm for UGVs based on the edge detecting and limit-cycle navigation method," Journal of Institute of Control, Robotics and Systems (in Korean), vol. 17, no. 5, pp. 429-435, May 2011.

원문보기 상세보기
Society of Naval Architects and Marine Engineers: Technical Committees - Ship Technical Operations: Panel O-44 : IMO Activities Archive - Standards for Ship Maneuverability.

저자의 다른 논문 :

LOADING...

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, 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

연합인증