동역학 제약을 반영한 D-Star Lite 알고리즘 기반 무인항공기 경로 계획 연구 = A Study on UAVs Path Planning Based on the D-Star Lite Algorithm Considering Dynamic Constraints

다국어 초록 (Multilingual Abstract)

ABSTRACT
Collision avoidance and path planning technologies for unmanned aerial vehicles (UAVs) have become essential for improving operational safety and efficiency in applications such as delivery drones and future aircraft. Furthermore, research is rapidly progressing on integrating high-precision sensor technologies like LiDAR and vision sensors to enable high-difficulty missions in complex environments, such as indoor exploration, building entry, and disaster relief. This study proposes an algorithm for solving 3D path planning problems in complex environments with high obstacle density, such as urban areas or industrial facilities. Various algorithms exist, and grid-based algorithms have the advantage of generating the shortest path in complex environments and avoiding local minima. Furthermore, considering dynamic obstacles and real-time path regeneration, the grid-based algorithm D* Lite was selected for this study. To generate a UAV-flyable path, there are two methods: expanding the dimensionality by adding state information to search nodes and post-processing the generated path. Adding state information to search nodes can lead to the algorithm suffering from the curse of dimensionality, exponentially increasing computation time. Furthermore, post-processing and interpolating the generated paths carries the risk of generating paths that collide with obstacles. Therefore, this study proposes an approach that prioritizes rapid maneuvers by reflecting the dynamic constraints of UAVs. The proposed approach separates the global computation and path extraction processes of the D* Lite algorithm, utilizing the map information obtained during the global computation as a heuristic function. Furthermore, concepts for parent nodes, current nodes, and next nodes are added, adding angles and weights for the direction of travel. Based on this, the algorithm was designed to effectively generate a path that reflects the dynamic constraints of the UAV. The weights were expressed as parameters reflecting heuristics and rotations. Furthermore, to verify the algorithm, the heuristic and search range were expanded to three dimensions, and an appropriate cost function was selected for heuristic calculation. We also compared and analyzed the algorithms through the initial path generation and path regeneration processes. Initial path generation involves performing a global search to calculate distance cost values ​​for each node and then performing initial path generation. At this time, we compared the performance of existing algorithms and the algorithm proposed in this study by varying the rotation weights. For path regeneration, we measured the time required for regeneration by adding information about arbitrary obstacles to the algorithm, and confirmed that the proposed algorithm generates efficient paths while maintaining dynamic feasibility.

국문 초록 (Abstract)

무인항공기(Ummanned Aerial Vehicle, UAV)의 충돌 회피 및 경로 계획 기술은 배송 드론 및 미래형 항공기(Advanced, Air Mobility, AAM)과 같은 응용 분야에서 운영 안전성과 효율성을 향상하기 위해 필수적인 요소로 자리 잡았다. 또한 LiDAR, 비전 센서와 같은 고정밀 센서 기술과의 융합을 통해 실내 탐색, 건물 내부 진입, 재난 구조 등 복잡한 환경에서의 고난도 임무 수행에 대한 연구가 빠르게 진행되고 있다. 본 연구는 도심 지역이나 산업 시설과 같이 장애물 밀도가 높거나 복잡한 환경에서 3차원 경로 계획 문제를 해결하기 위한 알고리즘을 제안한다. 다양한 알고리즘이 존재하며 그리드 기반 알고리즘은 복잡한 환경에서 최단 경로를 생성할 수 있고 Local Minima에 빠지지 않는 장점이 있다. 또한 동적 장애물 및 실시간 경로 재생성을 고려하여 그리드 기반 알고리즘인 D* Lite을 선정하여 연구를 진행하였다. UAV가 비행 가능한 경로를 생성하기 위해선 탐색 노드에 상태 정보를 추가하여 차원을 확장하는 방법과 생성된 경로를 후처리하는 방법이 존재한다. 탐색 노드에 상태 정보를 추가하는 경우, 알고리즘은 차원의 저주에 빠지게 되며, 계산시간이 기하급수적으로 증가하는 단점이 존재한다. 또한, 생성된 경로를 후처리하여 보간할 경우, 장애물에 충돌하는 경로를 생성할 수 있는 위험성이 존재한다. 따라서 본 연구에서는 UAV의 동역학적 제약 조건을 반영하여 급격한 기동에 가중치를 두는 접근법을 제안한다. 제안된 접근법은 D* Lite 알고리즘의 전역 계산 과정과 경로 추출 과정을 분리하고 전역 계산 과정에서 수행된 지도에 대한 정보를 휴리스틱 함수로 사용하도록 한다. 또한 부모 노드, 현재 노드 및 다음 노드에 개념을 추가 하여 진행 방향에 대한 각도 및 가중치를 더하게 된다. 이를 바탕으로 알고리즘은 UAV의 동역학적 제약을 반영한 경로를 효과적으로 생성하도록 설계되었다. 이때 가중치는 휴리스틱 및 회전을 반영한 파라미터로 표현되었다. 또한 알고리즘을 검증하기 위해 휴리스틱 및 탐색 범위를 3차원으로 확장하고, 휴리스틱 계산을 위해 적절한 비용함수를 선정하였다. 또한 초기 경로 생성 및 경로 재생성 과정을 통해 알고리즘을 비교, 분석을 진행하였다. 초기 경로 생성은 전역 탐색을 수행하여 각 노드에 대한 거리 비용 값을 계산하고 초기 경로 생성을 수행한다. 이때 회전 가중치를 다르게 두어 기존 알고리즘 및 본 연구에서 제안하는 알고리즘의 성능을 비교한다. 경로 재생성의 경우 임의의 장애물에 대한 정보를 알고리즘에 추가하여 재생성에 걸리는 시간을 측정하였으며, 제안된 알고리즘은 동적 실현 가능성을 유지하면서 효율적인 경로를 생성하는 것을 확인하였다.

목차 (Table of Contents)

• 제 1 장 서론 1
• 제 1 절 연구배경 1
• 제 2 절 연구동향 2
• 제 3 절 연구 목표 및 방법 5
• 제 2 장 Dynamic A-Star 알고리즘 8
• 제 1 절 D* Lite 알고리즘 개요 8
• 제 3 장 동역학적 제약을 반영한 알고리즘 설계 13
• 제 1 절 경로 보간 13
• 제 2 절 동역학을 반영한 상태 공간 확장 15
• 제 3 절 동역학적 제약 기반 알고리즘 설계 16
• 제 4 장 알고리즘 튜닝 23
• 제 1 절 비용함수 선정 23
• 가. 유클리디안(Euclidean) 거리 함수 23
• 나. 맨해튼(Manhattan) 거리 함수 24
• 다. 체비셰프(Chebyshev) 거리 함수 24
• 라. 경로 비용 함수 선정 25
• 제 2 절 가중치 선정 29
• 제 5 장 시뮬레이션 결과 33
• 제 1 절 알고리즘 평가 환경 구성 33
• 제 2 절 성능 비교 35
• 1. 경로 계획 결과 35
• 2. 알고리즘 연산속도 비교 38
• 제 3 절 동적 장애물을 반영한 시뮬레이션 40
• 1. CASE I. 장애물 크기에 따른 재계획 성능 평가 40
• 2. CASE II. 장애물 생성 위치에 따른 재계획 성능 평가 42
• 3. 경로 재계획 결과 44
• 제 6 장 결론 47