양유영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 경로 생성에서 중요한 것은 무엇인가?
무인기(UAV; Unmanned Aerial Vehicle)는 주로 군사 용도로 사용되었지만 기술 발전에 따라 다양한 민간 산업과 레저 분야까지 활용 범위가 확대되었습니다.
특히 사람이 접근하기 어려운 산업현장 등 다양한 임무에 활용되고 있으며, 원활한 임무 수행을 위해서는 안전성과 신뢰성 확보가 우선되어야 합니다.
따라서 UAV가 목표 지점까지 이동하는 과정에서 장애물과 충돌하지 않으면서 최단 경로를 생성하는 것은 필수적인 기술입니다.
경로 생성 알고리즘의 세 가지 방식
경로 생성 알고리즘은 크게 다음 세 가지로 구분할 수 있습니다.
① 그리드 기반 알고리즘
대표적으로 Dijkstra와 A* 알고리즘이 있습니다.
모든 구간을 균등하게 나누어 검색하기 때문에 직관적이고 국소 최댓값에 빠질 확률이 적다는 장점이 있습니다.
반면 탐색 구간이 커질수록 계산 시간이 기하급수적으로 증가하는 단점이 있습니다.
② 수학적 모델 기반 알고리즘
선형 계획법과 최적 제어와 같은 방식으로, 주어진 환경과 동적 시스템을 모델링해 최적 경로를 도출합니다.
경로 최적화에는 효과적이지만,
환경 조건을 모델링하고 제약 조건을 계산하는 데 많은 시간이 필요합니다.
③ 샘플링 기반 알고리즘
실현 가능한 공간에서 무작위로 점을 선택하고 이를 확장하면서 목표 지점까지의 경로를 생성합니다.
주요 장점은 아래와 같습니다.
- 낮은 계산 비용
- 고차원 환경 대응
- 복잡한 환경에서도 효율적인 경로 탐색
대표적인 알고리즘으로 PRM(Probabilistic Road Maps)과 RRT(Rapidly Exploring Random Tree)가 있습니다.
RRT 계열 알고리즘의 한계
논문에서 다루는 핵심은 기존 RRT 계열 알고리즘이 가진 장단점을 보완하는 것입니다.
RRT
[장점]
- 낮은 계산 비용
- 빠른 경로 생성
[한계]
- 생성 경로가 비연속적
- 기하학적 최적성을 보장하지 못함
- UAV 비행에 필요한 부드러운 경로 생성에 한계
RRT*
RRT 구조를 개선해 경로의 최적성을 점진적으로 확보할 수 있습니다.
그러나 추가적인 계산 과정으로 인해 계산 비용이 크게 증가하며, 실시간 경로 생성이 요구되는 UAV 환경에서는 적용에 제약이 발생합니다.
Biased RRT
목표 지점을 지향하는 확률적 요소를 추가하여 수렴성을 향상시킨 방식입니다.
하지만 장애물이 많은 환경에서는 경로가 극소값(Local minima)에 빠질 가능성이 높아져 전체 탐색 효율이 떨어질 수 있습니다.
UAV 경로 생성에 필요한 세 가지 요소
실시간 UAV 경로 생성에서는 특히 다음 세 가지 요소가 중요합니다.
1. 계산 시간
계산 시간이 짧을수록 UAV는 장애물 밀집 환경에서도 빠르게 경로를 변경하고 대응할 수 있습니다.
2. 수렴성
높은 수렴성은 복잡한 환경에서도 목표 지점까지 안정적으로 도달할 가능성을 높입니다.
3. 최적성
UAV가 장애물을 회피하면서도 가장 효율적인 경로를 선택할 수 있어야 합니다.
이러한 요소들은 UAV의 안전성뿐만 아니라 임무 성공률과 에너지 효율에도 직접적인 영향을 미칩니다.
계산 시간이 단축되면 불필요한 경로 변경과 에너지 소비를 줄일 수 있으며, 결과적으로 비행 시간을 연장할 수 있습니다.
본 연구에서 제안한 방법
본 연구에서는 기존 알고리즘의 한계를 해결하기 위해 아래 개념을 결합한 새로운 경로 생성 방법을 제안합니다.
Dubins 경로 + RRT + Biased RRT*
Dubins Path
UAV의 최소 회전 반경과 같은 비행 특성을 반영합니다.
RRT*
경로의 최적성을 확보합니다.
Biased RRT
특정 목표 지점을 지향하도록 하여 수렴성을 높이고 계산 시간을 단축합니다.
이를 통해 UAV 경로 생성에서
최적성 + 기하학적 연속성 + 빠른 계산
을 동시에 확보하는 것이 연구의 핵심입니다.
알고리즘 성능 비교
제안된 알고리즘은 기존 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-420-3203
- 홈페이지: https://moasoftware.co.kr/contact-us/
