무인기의 경로 생성을 위한 두빈스 경로 편향 RRT*
양유영1, 김성수1, 이광현1, 이현재2, †
1㈜모아소프트, 2조선대학교
Dubins Path Biased RRT* for UAVs Path Planning
Youyoung Yang1, SungSu Kim1, KwangHyun Lee1, Henzeh Leeghim2, †
1MOASOFT Corp.
2Dept. of Aerospace Engineering Chosun University
초 록
본 연구는 무인항공기(Unmanned Aerial Vehicle)가 장애물을 피하면서 목표 지점에 도달할 수 있는 실시간 경로 생성 알고리즘을 제안합니다. 기존의 RRT(Rapidly Exploring Random Tree) 알고리즘은 계산 속도가 빠르고 계산 비용이 낮다는 장점이 있지만, 최적 경로를 보장하지 않으며 UAV의 최소 회전 반경을 고려하지 않는 한계가 있습니다. 본 논문에서는 Dubins 경로와 RRT* 알고리즘을 결합한 새로운 알고리즘을 제안하여, UAV의 회전 반경을 고려함으로써 최적의 경로를 생성합니다. 그리고, 제안된 알고리즘은 Biased RRT의 개념을 활용하여 특정 목표 지점을 지향하도록 개선하여 수렴성을 향상시키고 계산 시간을 단축합니다. 제안된 알고리즘은 기존의 RRT 알고리즘과의 성능 비교를 통해 검증되었습니다.
Key Words: Unmanned Aerial Vehicle(무인기), Path Planning(경로 생성), Rapidly Exploring Random Tree(급속탐색랜덤트리), Dubins Path(두빈스 경로)
1. 서론
무인기(UAV; Unmanned Aerial Vehicle)는 주로 군사 용도로 사용되었지만 기술 발전으로 다양한 민간 산업 및 레저 분야 영역까지 활용 범위가 확대되었습니다. 사람의 접근이 어려운 산업현장 등 다양한 임무에 활용되고 있습니다[1,2]. 원활한 임무 수행을 위해 안전성과 신뢰성 확보가 우선시되어야 합니다. 따라서 목표 지점까지 장애물을 충돌하지 않으며 최단 경로를 생성하는 것은 필수적입니다.
경로 생성 알고리즘은 크게 그리드 기반, 수학적 모델 기반, 샘플링 기반으로 나뉩니다[3]. Dijkstra와 A*와 같은 노드 기반 알고리즘은 직관적이며, 모든 구간을 균등하게 나누어 검색하기 때문에 국소 최댓값에 빠질 확률이 적습니다 [4-6]. 하지만 탐색 구간이 커질수록 계산 시간이 기하급수적으로 증가하는 단점이 있습니다 [7]. 선형 계획법과 최적 제어와 같은 수학적 모델 기반 알고리즘은 주어진 환경과 동적 시스템을 모델링하여 최적의 경로를 도출하는 방식입니다[8,9]. 이러한 알고리즘은 경로 최적화에 효과적이지만, 환경 조건을 모델링하고 제약 조건을 계산하는 데 많은 시간이 소요됩니다.
반면, 샘플링 기반 알고리즘은 실현 가능한 공간에서 무작위로 선택된 점들을 탐색하고, 가능한 경우 이들을 확장하여 목표 지점까지의 경로를 생성합니다.이러한 알고리즘의 주요 장점은 계산 비용이 낮고, 고차원 및 복잡한 환경에서도 효율적으로 경로를 탐색할 수 있다는 점입니다. 대표적인 샘플링 기반 알고리즘으로는 PRM (Probabilistic Road Maps)과 RRT (Rapidly Exploring Random Tree)가 있습니다. [10,11]. PRM 알고리즘은 주로 고정된 장애물 환경에서 사용되며, RRT 알고리즘은 트리를 확장하여 환경 변화에 민감하게 대응할 수 있는 특성이 있습니다[12].
RRT알고리즘은 낮은 계산 비용으로 빠른 경로 생성이 가능하여 초기 연구에서 많이 사용되었으나, 생성된 경로가 비연속적이며 기하학적 최적성을 보장하지 못하는 한계가 있다. 이러한 단점은 UAV가 비행하는 동안 부드럽고 안정적인 경로가 필요한 상황에서 문제가 될 수 있다.
RRT알고리즘은 기본 RRT의 구조를 개선하여 경로 의 최적성을 점진적으로 보장할 수 있다[13]. 그러나, 추가적인 계산 단계로 인해 계산 비용이 크게 증가하 며, 실시간 경로 생성이 요구되는 UAV 응용 분야에서 는 적용하기 어렵다는 문제가 있다. 특히, 복잡한 환경 에서 최적 경로를 탐색하는 동안 발생하는 계산 지연 은 실시간 운영에 큰 장애가 된다.
Biased RRT알고리즘은 RRT 알고리즘에 목표 지점을 지향하는 확률적 요소를 추가하여 수렴성을 향상시켰다[14-16]. 이는 목표 지점으로의 빠른 수렴을 가능하게 하지만, 장애물이 많은 환경에서는 경로가 극소값(Local minima)에 빠질 가능성이 높아져 전체 탐색 효율이 저하되는 문제가 있다. 결과적으로, Biased RRT는 장애물 밀도가 높은 환경에서는 효과적이지 않다.
UAV는 다양한 비행 환경에서 실시간으로 최적의 경로를 생성하고 변경해야 하며, 이 과정에서 계산 시간, 최적성, 수렴성이 매우 중요한 요소로 작용합니다. 계산 시간이 짧을수록, UAV는 장애물 밀집도가 높은 환경에서 더 신속하게 경로를 수정하고 빠르게 대응할 수 있습니다. 이러한 신속한 경로 생성은 UAV의 수렴성을 높여, 복잡한 환경에서도 안정적으로 목표 지점에 도달할 수 있게 합니다. 이는 UAV의 안전성을 크게 향상시켜, 위험을 최소화하고 임무 성공률을 높입니다. 또한, 최적성은 UAV가 장애물을 피하면서도 가장 효율적인 경로를 선택하는 능력과 직결됩니다. 실 시간 의사 결정이 필요한 고속 비행이나 긴급 상황에서는, 빠른 계산 시간과 높은 수렴성 덕분에 UAV는 더 적절하고 최적화된 경로를 신속하게 찾아 임무를 성공적으로 수행할 수 있습니다. 효율적인 에너지 관리 역시 UAV 운영에서 중요한 요소입니다. 계산 시간이 짧아지면, 불필요한 경로 변경을 줄이고, 에너지 소비를 최소화하여 비행 시간을 연장할 수 있습니다. 이는 UAV의 운영 효율성을 극대화하는 데 중요한 역할을 합니다. 따라서, 제안된 알고리즘의 최적성, 수렴성, 계산 시간 개선은 UAV의 다양한 비행 환경에서 효율 성과 안전성을 크게 향상시키는 데 핵심적인 요소입니다.
본 연구에서는 이와 같은 기존 알고리즘들의 한계를 극복하기 위해, UAV의 경로 생성 문제를 해결하기 위해 Dubins 경로와 RRT 알고리즘을 결합한 새로운 방법을 제안합니다. 제안된 알고리즘은 RRT의 구조적 장점과 Dubins 경로의 기하학적 특성을 통합하여, UAV의 최소 회전 반경과 같은 비행 특성을 반영한 최적의 경로를 생성합니다. 또한, 제안된 알고리즘은 Biased RRT의 개념을 활용하여 특정 목표 지점을 지향하도록 개선되었으며, 이를 통해 수렴성을 높이고 계산 시간을 단축합니다. 이러한 접근 방식을 통해 UAV의 경로 생성에서 최적성과 기하학적 연속성을 동시에 향상시키고자 합니다. 이를 위해 제안된 알고리즘의 성능을 RRT, RRT, Biased RRT 알고리즘과 최적성, 수렴성, 계산시간을 기준으로 비교하여 검증하였습니다.
…중략…
5. 결론
본 연구에서는 UAV의 경로 생성 문제를 해결하기 위해 Dubins 경로와 RRT* 알고리즘을 결합한 Dubins 경로 편향 RRT* 알고리즘을 제안했습니다. 기존 RRT 알고리즘은 계산 비용이 낮고 경로 생성 속도가 빠르지만, 경로가 비연속적이고 최적성을 보장하지 못하는 한계가 있었습니다. RRT*는 경로 최적화를 가능하게 했으나, 계산 시간이 길어 실시간 경로 생성에는 제약이 있었습니다. 또한, Biased RRT는 수렴성을 향상시키지만 복잡한 환경에서는 극소값에 빠질 가능성이 존재했습니다.
제안된 알고리즘은 Dubins 경로의 기하학적 특성을 적용해 최소 회전 반경을 고려한 경로를 생성하고, Biased RRT의 개념을 적용하여 수렴성을 개선하고 계산 시간을 단축했습니다. 이를 통해 UAV의 다양한 비행 환경에서 최적 경로를 안정적으로 생성할 수 있습니다. 100회 시뮬레이션 결과, 제안된 알고리즘은 기존 RRT, RRT*, Biased RRT 알고리즘에 비해 경로 길이, 계산 시간, 노드 개수에서 월등한 성능을 보였습니다.
No Obstacles 환경에서 경로 길이는 16.85%, 계산 시간은 99.6% 단축되었고, Center Obstacles에서는 경로 길이를 19.6%, 계산 시간을 50.5% 단축했습니다.Scattered Obstacles 환경에서는 경로 길이를 21.4%, 계산 시간을 19.8% 단축했습니다.
결론적으로, Dubins 경로 편향 RRT*는 실시간 UAV 경로 생성에서 최적화된 성능을 보이며, 복잡한 환경에서도 안정적인 경로 생성과 빠른 계산 시간을 제공할 수 있음을 확인했습니다. 이 알고리즘은 UAV 응용 분야에서 실질적으로 활용될 수 있는 가능성을 제시합니다.
- UAV 경로 생성 위한 두빈스 경로 편항 RRT 알고리즘 관련 문의 : 02-6945-2156 / Contact us – (주)모아소프트
