본 논문은 무인항공기(UAV)를 위한 마르코프 의사결정 과정(Markov Decision Process, MDP) 기반의 온라인 경로 계획 알고리즘을 제시한다. 제한된 계산 자원을 고려하여 일반적인 MDP의 높은 메모리 요구사항으로 인해 경로 계획을 온라인으로 구현하는 것은 적합하지 않다. 본 논문에서는 다중해상도 격자 분할 기법을 이용하여 장애물 격자 지도를 근사화하고, 다양한 크기의 격자에 대한 연결성을 고려하여 MDP에 필요한 데이터 구조를 재정의함으로써 온라인 구현에 적합한 새로운 알고리즘을 제시한다. 제안하는 알고리즘의 성능은 수치 시뮬레이션을 통해 검증되었으며, 이는 제안하는 알고리즘이 메모리 요구 사항뿐만 아니라 계산량 측면에서도 일반적인 MDP보다 더 효율적임을 보여준다. 또한, 개발된 높은 충실도를 갖는 통합 시뮬레이터를 이용하여 제안하는 알고리즘의 실제 시스템 적용 가능성을 판단하였다. 이 시뮬레이션을 통해 제안하는 알고리즘이 온라인으로 경로를 계획하고, 계획된 결과를 따라 비행함으로써 안전하게 목적지에 도달할 수 있음을 확인하였다.
This paper presents the Markov Decision Process(MDP) based online path planning algorithm for unmanned aerial vehicle (UAV). It is not suitable for path planning to be implemented online due to the high memory requirement of the general MDP by taking into account the limited computational resources. This paper presents a novel algorithm suitable for online implementation by approximating the grid map using a multiresolution grid decomposition technique and redefining the data structure required for the MDP by considering the connectivity for various gird sizes. The performance of the proposed algorithm is verified through the numerical simulation, which shows that the proposed algorithm is more efficient than the general MDP in terms of the computational throughput as well as the memory requirement. In addition, the applicability of the proposed algorithm to real systems is determined using the developed high-fidelity integrated simulator. Through this simulation, it is confirmed that the proposed algorithm can safely reach the destination by planning the path online and flying according to the planned result.