Compensated Voronoi Diagram 기반 실시간 경로점 생성 기법 연구

국문 초록 (Abstract)

본 논문은 무인비행체의 경로 생성 기법으로서 Voronoi Diagram 기반의 경로점 생성 기법을 제안한다. 민간 화재나 산불과 같은 재난 지역 또는 적진에 배치된 레이더의 위협을 받는 전장 상황에서 무인비행체의 경로 생성은 생존율을 극대화할 수 있어야 하며 빠르고 안정적으로 이루어져야 한다. 타 경로계획 기법들과 달리 Voronoi Diagram 기반 경로계획은 빠르게 경로점을 산출할 수 있는 장점이 있다. 또한 경로점 후보들을 산출하므로 무인비행체의 유도제어 기법 적용에 있어 용이하다. 하지만 이러한 경로점 세트를 조합하여 생존율을 최대화하는 경로를 찾기 위한 이후의 과정에서 많은 시간이 소요된다. 본 논문은 Compensated Voronoi Vertex 순환 최적화라는 기법을 제안한다. 이 기법은 연산 시간이 매우 짧으며 영역 내의 다양한 가중치를 가지는 위협을 고려하여 준최적에 달하는 해를 찾아낼 수 있다. Compensated Voronoi Vertex 순환 최적화 기법은 총 3가지 과정으로 구성된다. 첫 번째로 Compensated Voronoi Diagram을 통해 다수 위협에 대한 피격율을 최소화하는 Voronoi Vertex 및 Voronoi Edge를 생성한다. Voronoi Vertex는 경로점 후보가 되며 Voronoi Edge는 비행 경로가 된다. 두 번째로 Dijkstra 알고리즘을 통해 시작점과 목표점을 잇는 최소 비용 경로를 산출하여 초기 경로로 선택한다. 이를 위해 생존성을 나타내는 지표를 만들어 비용함수를 구성하였으며 이를 다음 단계인 2-Edge 최적화의 목적함수로도 사용한다. 세 번째로 2-Edge 최적화를 통해 초기 경로의 각 경로점들을 최적의 위치로 이동시킨다. 2-Edge 최적화는 경로 전체를 평가하는 것이 아니라 2개의 Edge만 평가하여 최적화를 여러 번 수행하는 기법이다. 따라서 연산 시간이 매우 짧으면서도 최적성에 있어 손해를 덜 볼 수 있는 특징이 있다. 논문에서는 최종적으로 Compensated Vornoi Vertex 순환 최적화 기법에 대한 시뮬레이션을 수행하며 몇 가지 성능 지표를 통해 그 신속성과 최적성을 평가한다.

목차 (Table of Contents)

• 제 1 장. 개요 1
• 1.1 연구 배경 1
• 1.2 연구 동향 2
• 1.3 논문의 구성 8
• 제 2 장. 경로계획 문제 9
• 2.1 문제 정의 9
• 2.2 Voronoi Diagram 12
• 제 3 장. 경로점 최적화 알고리즘 15
• 3.1 Compensated Voronoi Diagram 16
• 3.2 Dijkstra Algorithm 24
• 3.3 2-Edge 최적화 28
• 제 4 장. 경로계획 시뮬레이션 32
• 4.1 시나리오 구성 32
• 4.2 Compensated Voronoi Diagram의 특징 34
• 4.3 시나리오 1 36
• 4.4 시나리오 2 39
• 4.5 결과 분석 42
• 제 5 장. 결론 43
• 참고문헌 45