1.서 론

현대 항공우주 산업 분야에서는 과학기술의 발전과 더불어 기존에 존재하는 정찰 유인기와 위성을 대체할 수 있는 무인항공기의 개발이 중요해지고 있다. 무인 항 공 분야는 군사적 목적으로 1990년대부터 연구가 진행되 기 시작했으며, 최근 전 세계적으로 각 국에서 무인항공 기의 개발을 진행하고 있는 실정이다. 초기 군사용 목적 으로 연구되기 시작된 무인기는 최근 들어 감시용, 물류 용, 통신용 등의 민간 분야에까지 이용되고 있다.

본 연구는 군수분야에 무인기를 이용하기 위한 연구 를 진행하면서 물자의 적절한 이송수단으로서의 무인기 활용은 효과적이고 효율적인 경로계획이 필수적이라는 것을 인지하고 이에 대한 연구의 현주소를 파악하기 위 해 시작되었다. 따라서 이 연구는 무인항공기 경로계획 에 관한 리뷰형식을 갖추고 있다.

일반적으로 경로계획은 출발지로부터 목적지까지 목적 하는 바(최단거리, 최소비용 등)를 달성하기 위해 이동체 또는 차량의 방문점을 계획하는 것을 의미한다. 지면에서 이동하는 차량의 경로계획 연구는 그 동안 많은 연구자들 로부터 이행되어 왔고 이를 위한 방법론 또한 다양하게 소개되어 왔다[30]. 무인 항공기의 경로계획은 출발지로 부터 목적지까지의 이동 경로를 계획한다는 기본 개념은 동일 하지만, 이동체에 운전자가 탑승해 있지 않다는 조 건과 수직이동이 가능하다는 조건이 추가됨으로 인해 기 존의 차량경로 계획과 다른 접근법이 적용될 수 있다.

본 연구에서는 이러한 국내 경로계획 연구에 대해 종 합하고 분석하여, 무인기가 임무활동을 하는데 필요한 여 러 가지 경로계획 기법들이 어떤 방식으로 이루어지는가 를 검토한다. 이러한 분석을 통해 무인기를 활용한 정찰, 감시 등의 임무수행, 또는 원격 배송업무 등, 관련된 연구 분야에 활용할 수 있도록 그 기본 토대를 마련하고자 한다.

논문의 구성은 제 2장에서 무인기의 개념과 비행체의 구분에 대해 설명하고 지상통제 시스템과 지상 터미널, 지상 지원시스템, 이·착륙 장비에 대한 소개가 이루어 진다. 제 3장에서는 일반적인 무인항공기 경로계획의 범 위와 구분에 대해 제 4장에서는 기존의 국내 무인기 경 로계획 연구에 대한 분류와 분석의 내용이 포함되었다. 제 5장에서는 각 경로계획 기법에 대한 소개와 이에 대 한 활용에 대해 언급하였다. 마지막으로 결론에서는 무 인기 경로계획 연구를 종합하여 정리하고 향후 연구의 필요성에 대해 언급한다.

2.무인항공기 시스템

무인항공기란 일반적으로 조종사의 탑승 없이 반자동, 자동, 원격조종으로 비행하며, 일정기간 동안의 임무수행 에 적합한 여러 종류의 임무 탑재 장비(mission payload) 를 수용하고 특정한 임무를 수행할 수 있도록 설계·제 작된 비행체를 의미한다.

무인항공기 시스템이란 이러한 무인기를 원격 조정하 거나, 입력된 프로그램에 따라 자율비행을 하여 인명피해 없이 정찰감시, 목표 감지, 통신 중계 및 목표타격, 보급 품 배송임무를 수행하는 시스템을 의미한다[5, 8, 19, 24, 35, 55]. 즉, 무인항공기 단일로는 복잡한 방식의 임무를 수행할 수 없으며, 이를 가능하게 하는 것이 무인항공기 시스템이라고 볼 수 있다.

무인항공기 시스템의 구성요소는 비행체, 지상통제 및 통신장비, 임무장비, 지상지원 시스템으로 구분할 수 있 다[24, 55]. 또는 위의 시스템 구성요소에서 운영 시스템, 데이터 링크, 이·착륙 장치 요소를 별도로 분리한 구분 을 하기도 한다[22, 27, 32]. 또 다른 구분으로는 <Figure 1>에서와 같이 크게 임무장비를 포함한 무인항공기 자 체와 이를 지원해주는 지상통제시스템으로 구분 지을 수 있다[27, 31].

무인항공기는 인간을 대신해 3D(dull, dirty, dangerous) 임무를 수행하는 대상이다[42]. 지상과 무인항공기간의 연 동을 가능케 만드는 지상통제시스템은 무인 항공기의 운 용에 있어서 가장 광범위한 영향을 미치는 요소이다. 지 상통제시스템은 무인항공기 비행의 시작부터 임무 완수 에 이르기까지 전 범위에 걸쳐 기체를 제어하며, 목적한 임무를 수행할 수 있도록 만든다[37].

2.1.무인항공기

무인항공기의 주된 임무는 감시·정찰에서부터 목표 타격, 농업에 이르기까지 다양하며, 근래에는 무인항공기 를 물류분야에 사용하려는 연구가 이뤄지고 있다. 무인 기의 물류분야 활용으로는 접근이 어려운 외곽 지역이나 인구 밀도가 낮은 지역, 배나 항공편 등 운송 대안이 없 는 긴급 상황에서 유용하게 쓰인다. 이러한 다양한 목적 에 맞춰 임무장비의 개발도 지속적으로 이루어지고 있다. 고고도 무인항공기(High Altitude Long Endurance, HALE) 의 감시 및 정찰임무를 위한 초고성능 카메라에서부터, 저 고도를 비행하는 소형 무인 비행체(drone)를 위한 저전력 카메라에 이르기까지 다양한 촬영장비가 존재한다[39, 42].

비행체는 임무나 운용환경에 따라 매우 다양한 형상을 가질 수 있다[14]. 비행체에 대한 일반적인 구분방법은 조 종방식에 따른 구분, 중량에 따른 구분, 성능에 따른 구분, 비행 방식 별 구분 등이 존재 한다[8, 14, 24]. 비행체의 조종 방식은 수동형 (manual), 반자동형(semi-autonomous), 완전 자동형(fully-autonomous)으로 구분할 수 있다.

수동형(manual) 조종방식은 조종사의 시야 내에서 조종간 (controller)을 통해 비행체를 운용하는 것을 의미한다[24].

반자동형(semi-autonomous) 조종방식은 조종사의 시야 를 벗어난 곳에서 통신을 통한 탑재된 시스템(embedded system)에 의해 비행한다. 또한 반자동형 비행조종 방식은 가시거리(Line-Of-Sight distance, LOS) 내에서 운용되며, 이·착륙, 임무수행 등 특별한 상황에서는 조종사가 원격 으로 조작하는 특징을 갖는다. 반자동형 조종방식은 완 전 자동형 조종방식과는 다르게 비 가시거리에서는 운용 될 수 없다[24].

완전자동형(fully-autonomous) 조종방식은 조종사의 시 야를 벗어난 곳에서 탑재된 시스템에 의해 비행체가 비행 한다는 점에서는 반자동형 조종방식과 동일하나, 비 가시 거리(Beyond Line-Of-Sight, BLOS) 상에서도 조종사의 제 어 없이 자율적인 비행 및 임무수행이 가능하다[24].

중량에 따른 구분은 아직까지는 정해진 틀이 존재하 지 않으며, 국가나 기관별로 상이함을 보이고 있다. 중량 은 비행체의 비행에 있어서 역학적인 요소에 큰 영향을 미치며, 비행체의 최대 이륙중량과 기체중량으로 표시된 다. 최대 이륙중량에서 기체중량 및 연료중량을 제외하 고 남은 중량만큼 임무장비를 탑재할 수 있다. 일반적으 로 무인항공기의 중량이 클수록 탑재하는 임무장비의 제 한이 적어진다[24].

성능에 따른 분류는 국가별, 기관별로 상이하게 나타 난다(<Table 1> 참조). 보통 비행고도에 따른 분류가 사 용되며, 비교적 높은 고도에서 비행하는 비행체는 긴 체 공시간을 갖는다.

무인항공기는 <Figure 2>에서와 같이 다양한 방식의 비행체가 있다.

고정익 방식과 틸트로터(tilt rotor) 방식은 일반 항공기 들과 동일하게 양 날개의 양력을 이용한 비행을 하게 된 다. 그러나 고정익 방식의 무인기는 이륙을 위한 설비들 이 요구되는 반면, 틸트로터형 항공기는 여타 장비가 없 어도 이륙할 수 있는 장점을 지니고 있다. 회전익 방식은 로터의 회전을 통해 얻어진 양력을 이용해 비행하는 방식 으로 수직 이·착륙이 가능하다는 장점을 갖는다. 생물 모방형(living things imitation)은 자연의 새, 곤충의 비행 방식을 모방한 형태로 주로 초소형 무인항공기 형태로 개발되었다[8].

2.2.지상통제지원시스템

지상통제시스템(Ground Control System, GCS)은 사람 과 무인항공기 사이의 핵심 인터페이스로 무인항공기를 운용하기 위해 반드시 필요한 시스템으로[17, 32], 성공 적인 임무수행을 위해 현재 무인항공기에 대한 자세, 위 치, 상태정보, 비행을 위한 조종명령 및 임무 전송의 기 능을 갖추고 있다[15, 60].

<Figure 3>은 지상통제 시스템과 무인 항공기 간의 연 결을 나타낸다. 지상통제시스템은 데이터 링크를 통해 무 인항공기와 연결되며, 다중 장비간의 효율적 및 원활한 통신을 위한 지상 데이터 터미널(Ground Data Terminal) 이 구성된다[17].

일반적으로 지상통제 시스템은 비행제어 및 임무수행 을 위한 컴퓨터로 구성되며, 컴퓨터는 다시 목표물 탐지 를 위한 센서운용 컴퓨터와 탐지된 영상데이터를 분석하 는 영상분석컴퓨터로 나누어진다.

여기에 임무수행 의사결정을 위한 지휘체계로 송신하 는 외부연동 컴퓨터까지를 포함한다[4, 17].

2.3.데이터링크 및 이·착륙 장비

데이터링크는 무인항공기와 지상의 운용자를 연결시 켜주는 생명줄로서 원거리의 무인항공기를 통제하고, 무 인항공기의 상태정보 및 임무수행 중 획득한 정보를 수 신할 수 있게 한다[25]. 안정적인 무인항공기의 운용을 위해서는 안정적인 데이터링크 구축이 필수적인데, 이를 위해서는 가시선(Line-Of-Sight, LOS)의 확보와 신호 안 정화, 이론적 통달거리의 추정이 기반이 되어야 한다. 그 리고 데이터링크는 무인항공기뿐만 아니라 무인선박, 무 인로봇 등 다양한 무인시스템에서도 사용된다[55].

<Table 2>는 여러 가지 이·착륙 방식과 필요로 하는 이·착륙 장비를 나타낸다. 무인항공기의 지상으로부터 의 이륙을 돕고, 안전한 착륙을 통한 재사용이 가능하게 도와주는 장비이다.

과거 자동 이·착륙 시스템 개발 전에는 외부 조종사 의 도움을 받아 이·착륙이 이루어 졌다. 중·대형 무인 항공기들은 활주로를 통한 활주이륙 및 활주착륙이 주로 이루어졌으며, 소형 무인항공기들은 발사대를 통한 이륙 과 그물망을 통한 착륙 및 회수가 이루어졌다. 최근 들어 자동 이·착륙 시스템에 대한 연구가 지속되고, 다중 로 터 형태의 무인항공기들이 많이 개발되면서 크기와 상관 없이 자율적인 이·착륙이 가능하게 되었다.

3.무인항공기 경로계획

로보틱스(robotics) 분야에서 경로계획이란 지도 상에 서 주어진 초기위치에서 목표지점까지 지형 혹은 장애물 을 피해 이동하는 경로를 찾는 과정을 의미 한다[16, 22, 30, 46].

경로계획은 오프라인에서 수행되는 전역경로 계획과 온 라인에서 수행되는 지역경로계획으로 구분 할 수 있다.

전역경로계획은 오프라인 상에서 미리 주어진 지도 정보를 기반으로 로봇이 목적지에 도달할 때까지의 최적 의 경로를 설정하는 것이다. 하지만 환경 변화가 고려되 지 않았기 때문에 기존에 인지하지 못한 위협이 발생하 거나, 이동하는 장애물에 대한 회피를 수행할 수 없다. 전역 경로계획의 일반적인 진행 방법은 지도상의 장애물 을 이산화(discretize) 하고 위상 그래프(topological graph) 를 구하는 모델링으로 시작 된다[7, 19, 30, 46, 50].

지역경로계획은 정보가 주어지지 않았거나, 혹은 정보 가 주어졌으나 목표지점까지 이동함에 있어 예측치 못한 장애물을 회피하기 위해 센서장비 등을 이용해 지역적으 로 새로운 경로를 생성하는 과정을 말한다. 그러나 지역 경로계획은 최적 경로를 얻을 수 없다는 단점을 지닌다. 지역경로계획은 이동체가 장애물을 감지(sensing)하는 것 으로부터 시작되며, 이를 통한 지역적인 경로재구성이 이루어지게 된다[7, 30, 61].

전역 경로계획과 지역 경로계획에 사용되는 알고리즘 이 상이하지는 않다(<Table 3> 참조). 전역경로 계획에 사용된 알고리즘을 지역 경로계획에도 적용할 수 있으며, 그 반대 역시 가능하다. 일반적인 경로계획 연구를 두 분 야로 구분하는 이유는 알고리즘이 시작되는 시점이 다르 기 때문이다[7].

지역경로계획은 전역경로계획에 비해 예측 불가능한 환경(dynamic environment)에서 경로를 생성해야 하기 때 문에 상대적으로 빠른 속도의 경로계획 방법이 요구된다 [61]. 여기에 주로 사용되는 방법은 셀 분할법(cell decomposition) 을 이용한 방식, 포텐셜 필드(potential field)를 이 용한 방식 등이 존재한다.

무인항공기의 경로는 이륙지점에서부터 목표 지점까 지 가능한 짧은 것이 효과적이다. 이러한 목적들을 만족 시키면서 목적지에 도달하는 경로를 생성하는 것이 무인 항공기 경로계획이라고 볼 수 있다[22, 40].

무인항공기의 경로계획을 위해서는 비행체 및 임무장 비의 성능, 기상의 영향, 장애물 및 위협물의 존재여부, 비행 금지구역의 존재 여부 등 많은 제한사항들을 고려 해야 한다[40].

이처럼 무인항공기 경로계획에 요구되는 다양한 요소 들은 공통된 목표를 달성하기도 하지만 서로 상충되는 경우도 다수 존재한다. 어떤 목적 달성에 목표를 두고 경 로계획 목적함수를 설정하느냐에 따라 생성되는 경로는 다양하며, 무인항공기 운용자는 이를 적절하게 판단하여 최적 경로를 선택해야 한다.

4.국내 경로계획 기존 연구

국내 무인항공기 경로계획에 대한 연구는 2000년대 초 반부터 경로탐색, 임무할당 등 여러 목적을 가지고 이루 어졌으며, 대부분의 알고리즘은 무인로봇의 경로탐색을 확장한 형태를 택하고 있다.

경로계획에 관한 기존연구는 여러 방향으로 이루어졌 는데 이를 분류하면 다음과 같다. 대부분의 경로계획은 출발지에서 목적지까지 최적의 경로를 찾는 연구이다. 이러한 연구들은 미리 주어진 경로를 통하여 목표점까지 장애물을 회피하여 최단의 경로로 이동하는 경로계획이 다. Kim[22]에서는 이러한 경로 설계 문제를 해결하기 위하여 궤적 최적화를 통해 최적제어 문제의 해를 구하 였다. 즉 적의 위협을 회피하면서 최단시간에 임무 수행 지역에 도착할 수 있는 성능지수를 제안한다. Lee[36]에 서는 임무 계획의 자동화를 위하여 목표물을 탐지하기 위한 패턴화 된 정찰비행궤적을 생성하고 이를 최적화 하였다. 또 다른 경로계획의 문제로는 목표점이 주어지 지 않은 무인기의 자율비행이다[52]. 무인기가 자율 비행 을 하면서 만나는 정적 장애물과 이동 중에 순간적으로 나타나는 동적 장애물을 회피하는 문제를 다루어 경로를 생성하는 것에 관한 연구이다[11].

Moon[42]에서는 각 주어진 경로점을 경유 하는 방식 과 임무할당을 문제를 수행하여 이 해를 바탕으로 경로 를 생성하는 방법으로 접근하였다. 그 외의 경로계획 논 문들은 무인기의 생존성을 극대화하고 안전한 비행을 하 기 위한 경로계획에 관한 연구이다. 대표적으로 Kim[28] 에서는 다수 UAV가 장애물과 적의 대공위협을 회피하 여 생존성이 극대화되도록 임무를 수행해야 할 셀 간의 이동경로와 다수 셀들의 순회경로를 계획하는 문제에 대 하여 연구하였다. 표는 기존에 진행된 연구들을 위 항목 들로 나누어 분류하였다. Table 4

경로계획에 있어서 차원(dimension)은 생성된 경로의 현실성을 판단하는 중요한 척도이다. 기존 이동로봇의 경로계획과는 다르게 무인항공기 경로 계획의 경우 3차 원의 항로를 지정해줘야 한다는 특징을 갖는다. 무인항 공기의 동적 특성을 반영한 3차원 경로계획은 2차원 계 획에 비해 문제의 난이도가 급격하게 상승하게 되며, 경 로계획에 있어서 비효율성을 가져오게 된다[7]. 때문에 많은 경로계획 문제들은 무인항공기가 일정한 순항고도 를 기준으로 비행한다는 가정 하에 비행이라는 3차원의 문제를 2차원으로 단순화시켜 접근하였다.

<Table 5>은 기존 연구들을 2차원경로계획과 3차원경 로계획으로 나누어 분류해 보인다.

무인항공기의 임무는 정찰, 감시에서부터 물품 운송, 표적타격에 이르기까지 다양하다. 요구되는 임무수행 정 도 또한 각 임무 별로 상이하다.

하지만 무인항공기는 운용시간, 탑재능력의 제한을 가 지고 있으므로 임무완수를 위해서는 복수의 무인기 운용 이 요구된다[28]. 복수 무인기는 편대를 이뤄 하나의 임 무를 수행할 수도 있지만, 각기 다른 지역을 할당 받고 각각의 임무를 수행할 수도 있다.

<Table 6>은 기존연구를 단일 무인항공기와 복수 무 인항공기로 구분하였다. 복수 무인기의 운용은 단일의 경우에 비해 경로계획의 복잡도가 증가한다. 여러 임무를 다수의 무인항공기가 어떻게 나눠가져야 효율적인지에 대한 문제가 존재하기 때문이다. 국내에서는 주로 임무 지역을 무인항공기의 대수만큼 나누고, 그 일부를 단일 무인항공기가 할당 받아 개별 임무를 수행하는 형식의 경로연구가 진행되었다.

5.기법과 활용

전장이나 위험지역에서 무인기를 활용한 임무 수행은 그 성공확률을 높이기 위해 경로 계획이 필요하다. Kim[28] 에서는 무인기가 적의 위험 영역을 통과하여 목표물을 정 찰하거나 타격하기 위한 경로 계획을 연구하였다. 유사한 활용 방안으로 Choi[6]에서는 무인기가 위험지역의 위협 이 변화 할 때 이를 회피하여 안전하게 임무수행을 할 수 있도록 비행경로를 생성해 주는 알고리즘을 연구하였다.

Sin[60]에서는 특히 복수 무인 항공기를 운용할 때에 지상 통제 시스템의 구성방식에 대한 연구를 진행하였다. 또 다른 연구로는 항공기 사고 방지를 위한 지상 통제 시스템의 운용, 데이터의 활용성을 높이기 위한 네트워 킹 연구 등이 있다.

위 논문들과 같이 실용적 활용을 위한 방법 연구 외에 알고리즘을 주로 한 연구들이 있다. 방식은 다양하게 사 용하였지만 대부분 동적 장애물과 정적 장애물들을 회피 하는 방법에 대한 연구이다. Kim[30]에서는 무인 자율주 행차량의 경로계획에 관한 연구이지만 알고리즘 순서도 가 체계적이고 전역경로계획과 지역경로계획이 잘 활용 되었다. 그 외의 논문들도 충돌회피를 위한 알고리즘 및 방법론 연구에 중점을 두었다. <Table 7>에서는 각 활용 방안에 따라 연구 논문들을 분류 하였다.

5.1.A* 알고리즘

A* 알고리즘은 주어진 공간 안의 특정한 노드에서 인 접한 노드들을 조사해 나가면서 시작 노드로부터 목표 노드로 이르는 가장 비용이 낮은 경로를 찾는 알고리즘 이다.

g (x)는 시작 노드로부터 해당 노드까지의 누적경로비 용이다. h(x)는 시작 노드로부터 해당 노드까지의 추정 (heuristic)된 경로비용이다. 추정된 경로비용은 해당 노드 로의 도달 비용을 절대 넘지 않는다[27]. f(x)는 적합도 (fitness)로서, 누적 비용함수 g (x)와 추정비용함수 h(x) 의 합으로 나타난다. 적합도가 낮을수록 해당 경로가 최 단 경로로 선택될 가능성이 높음을 의미한다.

이를 경로계획에 적용하면 <Figure 4>와 같이 진행되 는 것을 볼 수 있다. <Figure 4>은 설명을 위해 주어진 공간을 사각의 셀 형태로 분할하였다. 시작 노드 주위의 아직 조사하지 않은 노드(open list)들 중 가장 적합도가 낮은 노드를 조사하는 과정을 반복하여, 공간 내의 모든 노드가 조사된 노드(closed list)가 될 때까지 반복한다. 이후 시작 노드에서 목표 노드에 이르기까지 누적 비용 이 가장 낮은 노드들을 연결하여 경로를 생성하는 방법 이다[1, 62].

<Figure 4>의 Depot 주변에 얇은 테두리 셀(cell)은 조 사된 노드이며, 두꺼운 선으로 둘러싸인 셀은 선택된 최 단경로이고, 그 외에 셀은 조사되지 않은 노드이다.

5.2.보로노이 다이어그램

Park[53]은 무인비행체의 생존율을 최대화 하는 최적 화 문제를 빠르고 안정적으로 풀기 위하여 보로노이 기 법을 사용하였다. 보로노이 다이어그램은 주어진 정보를 이용해서 지도상에 경로점을 직접 선정하는 방식이며, 2 차원의 공간에 n개의 점들이 존재할 때, 그 공간을 n개 로 나누는 것이다. 나눠진 각 공간은 보로노이 타일(tile) 이라고 불린다[22, 26].

<Figure 5>은 보로노이 다이어그램의 예시로 검정색 점들은 위협의 크기 정보를 갖고 있다. 경계선들은 각 점 들이 갖고 있는 위협 간의 균형을 나타낸다. 이동체는 생 성된 경계선들을 서브-최적경로(sub-optimal path)로 삼아 위협을 최소화시키며 이동하게 하며, 다른 경계선과 만 나는 지점에서 다시 경로선택을 이어가 결국 목적지까지 비행하게 된다[22].

어떤 경계선을 따라 이동할지에 대한 의사결정은 성 능평가(J)를 통해 이뤄진다. 성능평가는 일반적으로 위협 비용을 포함한 연료소모비용, 시간비용, 거리비용 등의 평 가항목의 합으로 이뤄진다.

위협비용은 해당 경계선이 위협의 중심과 떨어져 있 는 거리, 위협에 노출된 정도와 같은 기준을 두고 평가가 이루어진다. 시간, 거리비용은 경로의 길이에 따라 소요 되는 비용을 의미하는데, 일반적으로 두 점을 잇는 최단 거리로 나타낸다. 상수 k는 평가항목의 중요도에 따른 가중치로 계층 분석법(analytic hierarchy process) 등의 방 법을 통해 구할 수 있다.

결과적으로 이동체는 여러 평가항목들의 값이 반영된 경로방식들 중 최적의 값을 갖는 경로를 택해 이동하게 된다.

5.3.셀 분할법

셀 분할법은 주어진 공간에서 장애물을 제외한 공간 들을 일정한 방법으로 세분화하여 주어진 공간을 단순화 시키는 방법이다. 이렇게 다시 만들어진 그래프 상에서 의 최단 경로를 구하는 방법이다[26]. 정확한(Exact) 셀 분 할법은 사다리꼴(trapezoid) 분할이 대표적이며, 주어진 공 간을 <Figure 6>(a)처럼 수직의 선을 장애물의 모서리들 에 그려서 공간을 분할하는 방식이다.

근사화 셀 분할법은 혼합(mixed) 셀 분할법이 대표적 이다. 주어진 공간을 일정한 격자로 나눠 분할된 공간을 장애물과 이동 가능한 구역으로 나눠 이동 가능한 구역 에 경로를 설정한다. <Figure 6>(b)는 앞서서 <Figure 6>(a) 에 주어진 공간을 사각형의 격자형태로 분할한 것이다. <Figure 7>의 바탕부분은 ‘이동 가능한 셀(free cell)’을 의 미 하고, 그림이 그려진 부분은 ‘장애물 셀(obstacle cell)’ 을 의미한다. 장애물을 둘러싸고 있는 흰 셀들은 ‘혼합 셀 (mixed cell)’로, 사각형태 격자 분할로 인해 표현할 수 없 는 장애물의 구조들을 나타낸다. 결과적으로 옅은 회색 셀을 기준으로 경로설정이 이루어진다. Figure 8

5.4.포텐셜 필드

많은 기존의 연구들이 포텐셜 필드 기법을 사용했으며 포텐셜 필드 기법이 사용된 대표적인 연구로는 Im[10]이 있다. 포텐셜 필드 기법은 이동체가 가상의 포텐셜 필드 상에 존재한다고 가정하고, 포텐셜 함수 (potential function) 을 이용하여 장애물을 회피하고 목표지점에 도달하는 것을 목표로 한다. 그러나 지역적 탐색방법(local method) 의 일종으로 트랩 현상 <Figure 9>을 보면, 이동체가 목표 지점을 향해 주행 중 목표지점과 동일선상에 있는 장애물 을 만나게 되면, 목표지점을 향해 주행하려는 인력장과 장애물을 회피하려는 청력장의 방향이 정반대방향이 되 는 진동현상이 발생하여 더 이상 주행할 수 없는 국부해 (local minimum) 문제가 발생할 수 있다는 단점이 존재 한다[10, 59].

포텐셜 필드 기법은 2차원 공간상에서 목표 지점과 장 애물에 포텐셜 에너지를 부여해, 에너지의 분포가 높은 곳에서 낮은 곳으로 흐르는 형태로 경로를 설정한다. <Figure 8>에서의 공간이 주어 졌을 때, 장애물에는 높은 포텐셜 에너지를 부여하고, 목표점에는 낮은 포텐셜 에 너지를 부여한다. 이동 체는 인력에 따라 에너지가 낮은 목표점을 향해 진행하다가, 높은 에너지를 가진 장애물 에 가까워지면 척력이 발생해 장애물을 회피하게 된다.

무인항공기 경로에 사용되는 인력 포텐셜 함수는 Conical Well(3)과 Quadratic Well(4)의 두 형태가 주로 사용 되고 있다[59]. 여기서 k는 상수이고 x는 위치벡터이다. U 는 포텐셜 함수에 의하여 생기는 인력을 나타낸다.

척력 포텐셜 함수는 장애물 주변에서 거의 무한에 가 까워진다. 여기에는 Conical Well(5)과 FIARS(6) 함수가 주로 사용된다[59]. 여기서 α는 상수이며, p는 무인항공 기로부터 물체의 최단거리를 나타내며, p₀는 적당한 경 계값으로 포텐셜 함수가 미치는 영역을 결정한다. 또한 f(x) = 0은 물체의 표면을 나타내고, f(x₀)은 물체로부터 적당히 떨어진 위치를 나타낸다.

5.5.순회판매원(TSP) & 다중 순회판매원 문제

이동체가 방문해야 할 지점들이 미리 정해져 있는 상 황에서 모든 지점을 빠짐없이 방문해야 한다면, 그 경로 계획 문제는 순회 판매원 문제로 생각할 수 있다[40]. 순 회판매원 문제를 활용하면, 주로 최단거리 알고리즘을 기반으로 경로를 생성되게 되며 어떤 지점을 먼저 방문 하는가에 따라 경로의 형태가 달라진다.

그러나 이동체가 방문해야 하는 지점의 숫자가 많아 질수록 가능한 경로의 숫자는 기하급수적으로 증가하게 되고, 연산에 필요한 시간소요가 늘어나게 된다. 이를 해 결하기 위해 혼합정수 선형계획법과 경험적 기법들이 이 용되고 있다.

다중 순회판매원 문제는 순회판매원 문제의 확장형태 로 차량경로문제(vehicle routing problem)를 단순화시킨 것과 유사하다. 즉, 다수의 이동체가 다수의 임무지점들 을 효과적으로 방문하는 경로를 계획하는 것이다. 이는 임무지역의 할당(assignment)과 연관되어 있다. 정해진 수 혹은 최소한도의 이동체를 활용하여 탐색해야 하는 공간 을 효율적으로 나눠 갖는 경로점 그룹을 만드는 것 이라고 볼 수 있다.

<Figure 10>에서 볼 수 있듯이, 다중 순회판매원 문제 를 이용한 경로계획의 특징은 각 이동체들이 경로를 공 유하지 않기 때문에 이동체 상호 간에 충돌(collision) 위 험이 없지만 갑작스럽게 나타나는(pop-up) 장애물에는 대응하기 어렵다는 것이다.

5.6.배낭 문제

배낭(knapsack or rucksack) 채우기 문제는 조합 최적화 의 한 문제로 이는 경로계획에 있어서 경로점 최적화 문 제로 변형될 수 있다. 각각의 경로점에 대한 정보가 미리 주어져 있다고 가정했을 때, 이를 어떤 순서로 방문해야 하는지에 대한 의사결정을 도울 수 있다. 순회판매원 문 제와는 다르게 용량이 제한되어 있기 때문에, 이동체의 능력을 벗어나지 않는 범위 내에서 경로가 선택되게 된다.

일반적인(standard) 배낭 채우기 문제 (8)은 배낭의 용 량 c 벗어나지 않는 범위 내에서, 배낭 내에 담긴 물건 들의 효용가치 p_i를 최대화 시키는 것이다. i번째 물건의 선택여부는 이항변수(binary variable) x_i를 통해 구분된다. 즉 x_i = 1일 경우, i번째 물건은 선택된 것이고, x_i =0 일 경우, i번째 물건은 선택되지 않은 것을 의미한다.

일반 배낭 채우기 문제를 확장시킨 복수 배낭 채우기 문제(multiple knapsack problem)(9)는 총 m개의 배낭들을 다루며 개체는 j로 표현되고, 용량은 c_j로 나타낸다. 이항 변수 x_ij는 i번째 물건이, j번째 배낭에 들어있는지의 여부 를 의미한다. 두 번째 제한사항인 x_ij의 합이 1보다 작다는 것 은 i번째 물건이 한 번만 사용될 수 있다는 것을 의미한다.

5.7.Dijkstra 알고리즘

Dijkstra 알고리즘은 가중치가 있는 방향 그래프에서 임 의의 두 노드 사이의 최단거리를 구하는 알고리즘이다. 미 로탐색 알고리즘뿐만 아니라 가능한 적은 비용으로 가장 빠르게 해답에 도달하는 경로를 찾아내는 모든 문제에 응 용된다.

<Figure 11>의 각 숫자는 경로의 가중치를 의미한다. 출발지점에서 갈 수 있는 임의의 노드에 대하여 값을 비 교하고 만약 길이가 더 짧게 나타나는 경로가 있을 경우 해당 경로로 값을 갱신시킨다. 그리고 이전 경로는 방문 완료 상태로 더 이상 사용하지 않는다. 이렇게 모든 경로 들이 방문완료 상태가 되거나 혹은 더 이상 선택할 경로 가 없을 때까지 과정을 반복한다. <Figure 11>에서는 이 중화살표를 사용한 A-D-C-F가 최단 경로가 된다.

5.8.궤적최적화, 샘플링기반 경로계획(Sampling Based Path Planning)과 그 외 기법들

궤적최적화는 대부분 무인기 혹은 비행체의 3차원 궤 적을 위해 사용된다. 궤적최적화를 위해서는 비행체의 특 성을 반영한 3차원 운동방정식이 유도되어야 하며, 같이 공기보다 가벼운 비행체의 경우는 일반 고정익 항공기와 는 다른 특성들을 반영하여야 한다. 미분방정식을 표현되는 궤적 최적화 문제는 직접법과 간접법을 통해 최적해를 구 하게 되는데, 직법법은 제어변수나 상태변수들을 비선형 프로그래밍 문제로 변환하여 해를 구하는 방법이고 간접 법은 변분법에 의해 유도된 최적제어의 1차 필요조건을 만족하는 경계조건문제의 해를 구하는 방법이다. 직접법 은 수렴범위가 넓고 간접 법은 수렴속도가 빠른 장점을 갖고 있다[36, 54, 63].

궤적최적화 기법은 비교적으로 3차원 비행경로 도출 이 용이하다. 하지만 복잡한 최적화 알고리즘 포함에 따 라 비행경로 산출 시간이 오래 걸리고 신뢰도가 낮을 수 있다.

샘플링기반 경로계획도 궤적 최적화와 비슷하게 특정 화된 기법보다는 기존의 포텐셜 필드 등의 기법을 기반 으로 하여 수행된 연구를 실제로 무인기에 적용하는 방 식이다. 따라서 3샘플링기반 방법은 경로계획 문제를 해 결하는데 있어서 다양한 방식으로 적용하는 과정이라 할 수 있다. 동적인 제한들이나 움직임을 다루어 경로계획 의 변화와 확장에 기여하기 때문에 실시간 경로 계획에 도 용이하다. 이러한 방법을 적용하기 위해서 기본적으 로 모델예측제어가 필요하고 sampling 영역의 정의에 따 라 궤적 생성이 변화될 수 있다.

그 외의 기법들로는 샘플링 기반의 경로 생성 기법인 RRT(Rapidly-exploring Random Tree) 방식이 있고, UAV Mobility 모델은 무인기가 자율 비행을 하면서 지정된 영 역을 이동하며 임무를 수행하기 위하여 만들어진 모델이 있다. 이 모델의 대표적인 모델로는 PM(pheromone mobility), RD(random direction), PRM(pheromone random mobility) 이 있다[5].

PRM 모델은 로드맵 방식의 하나로 매우 복잡한 정적 환경에 대하여 상당히 강인한 적응력을 보이며, 기본원리 가 간단하여 구현이 용이하다는 장점을 가지고 있는 반 면에, 장애물 환경에 대한 정확한 환경정보를 필요로 하 고, 형상공간으로 많은 시간이 소요되므로, 동적 환경에 대응이 어렵다는 취약점을 가지고 있다[5].

RD 모델은 주어진 영역 내의 가장자리 부분을 임의로 선택하여 목적지로 지정한다. 지정된 목적지까지 일정한 속도로 이동하며, 목적지에 도착하면 다시 가장자리 부 분을 임의로 선택하여 목적지로 지정하고 이동하는 것을 반복한다[5].

<Table 8>는 앞서 설명한 기법들의 각 논문에서의 활용 을 정리 하였다. 각 논문에서 방법론으로 이용한 기법은 이보다 더 다양하지만 중점적으로 사용한 방법론 위주로 정리 하였다.

5.9.기법의 비교와 활용

A* 알고리즘은 많은 종류의 문제해결에 이용되어 왔 으며 게임 개발에서 효율적인 path finding으로 많이 사용 되었다.

Dijkstra 알고리즘은 문제 해결방식이 간단하기 때문에 쉽게 적용할 수 있고, 가장 짧은 경로를 명확하게 발견 할 수 있지만 모든 방향에 대하여 탐색해야 하기 때문에, 문제의 크기가 클 경우 탐색시간이 많이 소요되는 단점 이 있다. 이러한 알고리즘은 스마트폰의 지하철 앱과 자 동차 내비게이션 등에서 활용 되고 네이버, 구글 등 여러 검색엔진의 지도 서비스와 건물의 위치를 효율적으로 정 하기 위해 사용하기도 한다. A* 알고리즘은 Dijkstra를 기반으로 하기 때문에 최단경로 찾기 문제에서는 비슷한 활용방안이 될 수 있지만, A* 알고리즘은 heuristic 함수 를 이용하여 더 나은 방향으로 이동하는데 반해 Dijkstra 알고리즘은 모든 경우의 수를 세서 계획하기 때문에 A* 알고리즘보다 계산이 더 복잡하다.

포텐셜 필드 기법은 만들어지는 경로가 부드러운 곡 선이고 쉽게 구현이 가능 하다는 점에서 다른 방법들보 다 이점이 있다. 포텐셜 필드는 주로 이동센서 네트워크 배치와 제어로봇 등에 가장 많이 활용된다. 또한 알려지 지 않은 환경에서 무인자율차량의 실시간 자율항법에도 활용 될 수 있다.

보르노이 다이어그램은 단순하고 신뢰성 높은 비행경 로 산출이 가능하며 공간적으로 위험한 요소들을 고려할 수 있다. 하지만 3차원 비행경로 도출이 어렵다는 단점 이 있다. 보르노이 다이어그램은 로봇 경로계획을 위해 수학과 물리학 에서는 패턴 분리시스템이나 분자구조의 연상에 그리고 이미지 작업으로는 파일 압축방식 이나 공간생성 시뮬레이션 프로그램에 사용되고 있다.

TSP, 배낭문제는 여러 경로점들이 있고 해당 경로점 들로 이동하는데 드는 비용을 알고 있을 때 가장 적은 비용으로 경로를 계획하는데 활용될 수 있다.

셀 분할법은 주어진 고정된 지도상에서 시작점을 출 발해 목적지까지 장애물을 피하여 경로를 생성할 때 사 용된다.

궤적최적화 문제는 비행선이나 제트기의 최적 궤적 도 출, 중고도 무인 비행선, 위성, 미사일, 유도탄 등의 최적 궤적 연구에 이용된다.

Sampling based path planning은 동적 환경을 반영하여 실시간 경로계획이 가능하다. 이 방식은 고차원의 공간 문제를 다루지만 최적 경로를 찾기보다는 충돌회피를 목적 으로 하는데 더 활용 된다. 비용함수에 따른 로봇의 내비 게이션이나 지형 모델을 통한 계산 등에 이용할 수 있다.

<Table 9>는 앞서 설명한 각 기법의 특성에 대해 정리 하였다. 여기서 모든 기법들은 전역 및 지역경로 계획에 모두 사용되지만 좀 더 비중 있게 사용되는 계획법에 표 시하였다.

6.결 론

최근 무인항공기 산업이 전 세계적으로 각광받고 있 으며, 국내에서도 이에 대해 학술적, 사업적 분야의 지속 적인 투자가 이루어지고 있다.

무인항공기의 학술적 연구에서는 주로 하드웨어적인 면이 부각되었으나, 최근 들어 소프트웨어적인 부분에 대한 관심도 증대되고 있다. 또한 무인기 활용에 대한 요 구와 관련된 연구가 어느 때 보다 활성화 되어 있다. 따 라서 무인기 활용에 있어서 효과적인 경로계획에 대한 필요성 또한 새롭게 대두 되고 있다고 할 수 있다.

이에 이 연구에서는 그간 국내에서 무인기 경로계획 과 관련하여 발표된 논문들을 종합하고 이를 토대로 관 련 연구를 진행하고자 하는 연구자들로 하여금 현 주소 를 파악하고 새롭게 시작하는 연구의 적절한 출발점의 위치를 수월하게 파악하는데 도움이 되고자 한다.

무인기 자체의 기술이 빠르게 발전함으로 인해 새로 운 시스템에 적합한 운영 기술 또한 함께 연구되어야 할 것이므로 각 성능과 형태에 맞는 운영기술에 대한 연구 가 추후에 함께 이루어 져야 할 것이다.