An Analysis on the Influential Factors to Set the Path Planning Algorithm for Unmanned Ground Vehicle in Combat Environment

전장환경에서 무인전투차량의 경로계획 알고리즘설정 영향요인 분석

An Analysis on the Influential Factors to Set the Path Planning Algorithm for Unmanned Ground Vehicle in

Combat Environment

백 종 성

·이 춘 주

Jong Sung Baek

·Choonjoo Lee

Abstract

This paper briefly reviews the path planning methods that are applicable to the autonomous mobile robots for the military. Two distinct path search algorithms, A* and D* that are most popular and flexible in public applications, among those reviewed are coded and analyzed in terms of combat environment assessment factors called METT+TC for the area of operations. The results imply that it is important to consider the characteristics of defense acquisition process and the specific requirements of defense operation so that the successful technology development of the Robot products is directly linked to the defense procurement of Robot products.

Keywords:

Unmanned Ground Vehicle, Path Planning, A* Algorithm, D* Algorithm, METT+TC, Defense Acquisition Process

1. 서 론

우리나라 정부에서 지능형 로봇 기술을 중점육성기술로 선정하여 투자를 확대하고 국방로봇사업을 신성장 동력사 업으로 추진하고 있는 가운데 민간부문에서 뿐만아니라 군사부문에서도 인간을 대체하거나 새로운 개념의 전쟁수 행 수단으로써 로봇의 역할기대가 높아지고 있다. 로봇의 군사부문 응용은 무인무기체계로 불리어지며 응용분야에 따라서 지상, 공중, 해상, 수중 등으로 구분되고 유인전투 체계와 무인장비를 네트워크 기반으로 통합운용하는 복합 체계를 무인전투체계라 한다^[6].

국방로봇 개발사업은 2006년 이후 본격적으로 국방부와 정통부(현 교과부)가 협력개발을 추진하여 반자율주행이 가능한 국방로봇 개발을 위해 2012년까지 개발목표로 네 트워크 기반 차륜형 견마로봇 사업을 진행중이다. 우리나 라 국방로봇의 기술수준은 자율주행기술 3단계 경로주행

Received: 8.June.2009, Reviewed: 24.August, Accepted: 26.August

1 육군 대위, 포병학교 지원처

† 교신저자국방대학교 무기체계과 조교수

수준에 있다^[5]. 위험작업 원격조종용 로봇(ROBHAZ), 지능 형 경계전투로봇(aEgis)은 2004년에 개발완료 되어 성능보 완 중에 있고 수송, 감시정찰 임무를 수행하게 될 다족형 견 마로봇은 2012년까지 민군겸용으로 개발완료 할 계획이다.

국방과학연구소 등은 2008년 10월 네트워크 기반 다목 적 견마형 로봇, 무인 자율주행 차량, 휴대용 소형 지상로 봇, 소형 항공로봇(무인헬기) 등 군사 로봇 4종류를 공개하 고, 기동 시범을 선보인 바 있다. 이 가운데 견마형 로봇의 경우 응용연구가 완료되는 2012년에 100㎏가량의 무기나 짐을 싣고 들판이나 낮은 언덕을 최대 시속 40㎞로 무인 자율주행이 가능하도록 설계되었다. 원격 제어되는 기관 총으로 무장해 전투수행도 가능하다. 하지만 전투로봇 개 발을 위해서는 아직 해결해야 할 과제가 많다. 한국의 현 재 기술수준은 사전에 설정된 짧은 거리를 스스로 장애물 을 피해 이동하는 수준이다. 로봇이 스스로 판단하고 임무 를 수행하는 완전 자율화 단계를 10으로 보고 단계를 나눌 경우에 미국은 자율주행 6단계수준에서 알고리즘을 구현 하고 있으며 우리나라는 현재 3단계에서 4단계 반자율주 행 수준화를 위하여 기술개발단계에 있다^[5].

그림 1. 연구개발 무기체계 획득절차 기본절차도^[8]

그리고 부처간 협력사업으로 추진되고 있는데 기술개발 이 성공하더라도 군사 운용요구를 충족하기 위해서는 국 방획득사업의 표준과 규격에 부합하고 운용시험평가절차 를 통과해야 한다. 그림 1은 연구개발 무기체계 획득절차 기본절차도를 나타낸다. 획득절차는 선행연구에서 양산결 정까지 최소 수년이 걸리고 심지어 프로세스가 진행되다 가 획득환경 변화에 따라 소요자체가 사라질 수 있기 때문 에 조기에 사업화를 원하는 개발업체 입장에서는 어려움 을 겪게 되는 주요한 요인 중에 하나이다²⁾.

또한 국방분야에 민수부문의 성숙된 기술을 적용하여 체계개발을 진행하는 신개념기술시범(Advanced Concept Technology Demonstration, ACTD) 등의 사업이 2008년부터 추진되고 있지만 민수기술이 국방부문에서 사업화 성과를 거두기 위해서는 군사적 운용개념에 부합하고 운용요구 충족도를 만족해야 한다.

즉, 기술적 개발의 성공이 국방조달과 연결되기 위해서 는 전장환경변화에 따르는 다양한 군사운용요구를 고려하 여 전략적이고 유연한 기술개발을 시도하는 것이 필요하다.

로봇 관련한 기존 논문은 운용개념에 관한 논의보다는 개별 산업분야 응용을 위한 연구성과를 제시하는데 초점 이 있다. 하지만 국방분야는 임무유형³⁾ 또는 공격∙방어작 전에 따라서 그 운용개념이 다양하며 운용환경의 불확실 성 정도, 위험정도, 운용목적 등에 따라서 원격제어에서부 터 자율주행에 이르기까지 유연한 기술적 구현을 요구하

2) 방위사업관리규정(방위사업청훈령 제88호, 2009, p.345)은 무기체계 연구개발사업관리 기본절차를 규정하고 있는데 선행연구, 탐색개발, 체계개발, 양산, 운용/유지로 단계화하고 각 단계마다 주요의사결정 시점을 두어 사업 단계 진입 및 종료를 결정하고 사업진행 중 설계검 토, 양산승인을 위한 적합판정, 초도양산, 전략화 평가 확인 및 후속양 산 등 주요 이벤트를 거치도록 하고 있다. 부처간 협력사업이 국방부 문에 조달되기 위해서는 이러한 기본절차의 적용을 받거나 준용해서 평가받게 된다.

3) 예를 들면 기동, 화력, 장애물개척 등의 임무유형은 감시정찰 기능을 위한 전장감시, 첩보수집, 표적획득, 전투피해평가, 수색정찰, 화생방 탐지 등과 전투를 위한 장애물 극복, 적 인원 및 장비 파괴, 화력지원, 경계, 그리고 수송, 기동지원, 지뢰탐지 등과 같은 특수기능으로 분류 가 가능하다.

고 있다.

따라서 기존에 민간부문에서 이미 성숙된 기술의 국방 분야 적용을 위해서는 응용적합성을 평가하는 단계를 거 치게 되는데 경로계획 알고리즘을 개발하는데 있어서도 전장환경 요소가 운용개념과 자율주행 알고리즘에 미치는 영향을 분석하는 것은 의미가 있다.

한편 작전환경의 변화와 더불어 신기술과 첨단 과학기 술의 발전이 가져올 수 있는 군사적인 측면에서의 파급효 과는 매우 클 것이며 이러한 발전은 새로운 지상전 개념을 요구하게 될 것이다. 즉 기술적 진보가 운용개념의 변화와 혁신을 가져다 주는 경우이다. 특히 미래에는 국제적인 네 트워크를 형성한 테러집단, 대량살상무기 확산, 환경오염 등 초국가적인 위협이 상당기간 안보논의의 핵심이 될 것 이며, 이에 대한 적절한 군사적 대응이 필요하다.

이에 인간을 대신해서 전투현장에 투입하거나 위험한 작업현장에 투입할 수 있는 무인전투체계는 경제적이고 효율적으로 임무를 수행할 수 있도록 해주어 오래전부터 인간이 꿈꾸어온 무기체계였으나 그동안 천문학적인 개발 비와 과학기술의 한계로 실용화 되지 못했다. 그러나 최근 관련기술의 성장으로 미국, 영국 등 주요선진국에서는 무 인전투체계 개발에 노력해 왔으며 특히 미국은 걸프전과 코소보 및 보스니아 분쟁에서 급조한 지뢰탐지/처리로봇 을 사용하여 로봇활용의 효과를 확인하고 향후의 전투에 대비해 로봇화를 추진하여 이미 전투에 제한적으로 활용 할 수 있는 수준까지 도달하였다.

민수분야에서 내비게이션에 많이 활용되고 있는 지형정 보가 완전한 경우의 경로탐색 알고리즘으로부터 불확실한 지형정보에서의 자율주행 알고리즘까지 현황과 군사적 목 적에 부합하기 위하여 이들 알고리즘의 적용가능성을 살 펴보고 경로계획 알고리즘의 성능특성에 영향을 미치는 요소를 식별함으로써 로봇을 비롯한 무인무기체계의 경로 계획 알고리즘 선정에 참고가 될 것이다.

로봇의 운용개념을 가시화하기 위해서 작전지역분석을 위해서 고려되는 METT+TC요소⁴⁾가 민과 군에서 각개약 진 방식으로 다양하게 개발되고 있는 자율주행을 위한 경 로계획 알고리즘 설정에 미치는 영향을 연구범위로 한정 하고 무인전투차량이나 견마형로봇 등에 고려되는 주행경 로탐색 알고리즘을 A*계열과 D*계열로 구분하여 성능특 성을 살펴보았다.

본 연구의 구성은 2장에서 전장환경과 자율주행 기술수

4) 전장환경이 군사운용에 미치는 영향은 지대하며 지휘관은 상황판단을 위해 임무(Mission), 적(Enemy), 지형(Terrain), 가용병력(Troops), 가용 시간(Time available), 민간인(Civilian) 요소를 기본적으로 고려하는데 이를 METT+TC요소라 부른다.

단계구분 단계 자율주행수준 주요체계 작전지역

협동 및 협력단계

10 완전 자율

-

광대역

국지적 9 협동 작전

8 협력 작전

자율단계 7 완전자율주행 ARV

6 제한자율주행

MULE 반자율

단계

5 목표점 주행

4 기동점 주행 MDARS-E, Avantguard, 3 경로 주행 XAV

원격제어단계 2 비가시권제어 PackBot TALON

1 가시권제어

표 1. 지상무인전투체계의 자율주행수준[1, 2, 4, 7]

준을 알아보고 3장에서 분석방법론을 제시하였다. 4장에 서는 지상무인전투체계 자율주행 알고리즘을 컴퓨터 프로 그램상에서 구현하고 자율주행 알고리즘을 군사적으로 운 용하기 위한 고려요소로서 지형정보의 불확실성과 알고리 즘 자체 특성을 분석하고 5장 결론에서 전장환경에 부합 하는 알고리즘 선정을 위한 시사점을 도출하였다.

2. 전장환경과 자율주행 기술수준

2.1 미래 전장환경의 특성

미래전은 네트워크 중심의 작전환경이 조성될 것이므로 제대별 전장영역이 대폭 확장될 것이다. 실제로 국방개혁 2020에 의하면 제대별 병력규모는 현재와 대동소이하나 작전영역은 3배∼10배정도 증가된다⁵⁾. 이에 따라 무인감 시 또는 무인타격수단 등 인간을 대신하여 작전지역을 담 당해 줄 무기체계의 요구가 증대 될 것이다.

그리고 미래전은 무엇보다도 인명피해를 최소화하면서 작전목적을 달성하는데 중점을 둘 수밖에 없을 것이다. 이 는 정밀타격수단의 발달로 요망효과만 달성할 수 있는 핀 포인트(Pinpoint) 타격이 가능해졌으며, 매스컴의 발달이 군사작전에 미치는 영향이 매우 커졌기 때문이다. 이에 무 인무기체계는 시대적으로 요구되는 무기체계로 인식되기 시작했다.

또한 미래에는 특수한 성격의 작전활동이 현재보다 더 욱 증가할 것으로 예측된다. 즉 전통적인 군사적 위협 외 에도 테러와 국제범죄 등 비군사적 위협이 더욱 가중될 것 이며 미래에도 아프칸전과 같은 산악작전 소요는 여전히 존재 할 것이고 특히 도시화 현상이 점차 심화되고 있어 도시지역작전 소요가 급증할 것이다.

이러한 무기체계 개발의 불확실성 및 작전지역의 변화 에 따른 지형요소, 그리고 적정이 불명확하고 대응 속도가 중요해 지며 비대칭 무기체계 등 복잡도가 더욱 높아지는 전장환경 하에서는 관련기술 성숙에 의한 지상무인전투체 계의 자율주행 수준을 높여 목표하는 임무수행지점까지 최적의 경로로 찾아가는 것이 더욱 중요해 질 것이다⁶⁾.

2.2 자율주행 수준과 탐색 알고리즘

국방 로봇개발에 있어서 가장 중요한 인식 및 판단분야 는 무인화 및 자율화를 위한 핵심분야로 인간이 원격조종

5) 작전영역을 구성하는 그리드 셀 방식으로 표현할 때 을 셀을 세분화 하는 정도에 따라 동일한 작전영역에 대해서도 작전영역의 증가와 동 일한 효과를 나타낼 수 있다.

6) 나폴레옹이 “전장에서 시간을 제외하고 원하는 것은 무엇이든지 용납 할 수 있다.”고 하였는데 첨단과학기술전의 양상을 띄는 현대전에서 시간의 활용은 더욱 중요하게 전쟁의 승패를 좌우하게 될 것이다.

하지 않더라도 만일의 사태에 스스로 판단하고 행동할 수 있도록 한다. 통신기술이 발전한 요즘에는 적군이 아군의 통신을 감청하거나 가로챌 가능성이 높기 때문에 원격조 종에만 의존하는 로봇은 활용도가 떨어진다.

무인화 기술의 핵심대상기술을 포괄하는 자율주행 기술 을 10단계로 구분하면 표 1과 같이 지상무인전투체계의 자율주행수준을 제시할 수 있다.

1∼2단계는 원격조종이 가능한 수준이다. 미국의 경우 2002년부터 이라크전에 배치한 휴대용 감시정찰 로봇이 여기에 해당한다. 3∼4단계가 되면 주요 시설을 감시하고 주둔지의 외곽을 돌며 경계하는데 사용할 수 있다. 미국에 서 2007년부터 배치한 ‘MDARS-E’나 이스라엘이 실험배치 중인 ‘아방가르드(Avantguard)’가 여기에 해당하는 대표적 인 로봇이다. 우리의 XAV도 자율주행 4단계에 해당하며 일정한 지역에서 감시정찰을 수행할 수 있다. 전투에 본격 적으로 활용하기 위해서는 5∼6단계 수준의 자율성능이 필요하다. 이 정도 수준이면 경전투에 활용할 수 있다. 미 국이 2012년에 배치할 MULE이 대표적인 로봇이다. 기갑 전에 사용하기 위해서는 로봇이 적어도 7단계 수준을 만 족해야 한다. 자율주행이 7단계에 이르면 로봇은 사람이 운전할 때처럼 자연스럽게 움직인다. 미국의 경우 미래전 투체계에 포함된 무장차량로봇(ARV: Armed Robotic Vehicle)이 7단계를 목표로 현재 개발중이며, 기술개발이 완전히 마무리되는 2014년 배치할 계획이다.

우리의 경우 현재 비가시권 원격제어(자율화 2단계)와 기동점 기반의 무인자율주행이 가능한 수준(자율화 3단계) 을 확보하고 있으며 향후 지속적인 기술개발을 통하여 2013년에는 제한속도 자율주행(자율화 6단계)을 만족시킬 예정이다. 그리고 2010년대 중반이후 7단계 수준을 개발할

구 분 내 용

경로탐색 알고리즘

정보 탐색

Replanning Methods: D*, D* Lite, Field D*

Heuristic Search: Best-first, A*

무 정보 탐색

Breadth First: Uniform Cost, Wavefront NF, Dijkstra’s Algorithm, Trulla

Depth First: Iterative Deepening

탐색공간 표현방법

Cell Decomposition: Approximate(Regular Grids), Exact, Adaptive(Quad-Tree, Adaptive Quad-Tree)

Roadmap Method: Visibility, Probabilistic Roadmaps, Rapidly Exploring Random Trees

Potential Fields

표 2. 주요 경로계획 기법^{[9, 16]}

수 있을 것으로 보인다. 이 속도라면 2020년경에는 다목적 군사로봇과 중전투로봇도 개발해 실전에 배치할 수 있다. 국방부문의 자율주행 알고리즘 개발수준은 세계최고수 준과 비교하면 중하위권 수준에 있는 것으로 평가되며 2020년까지 선진국과 대등한 자율주행수준으로 기술개발 을 한다는 목표를 두고 있다. 따라서 획득기간을 단축하고 개방형 혁신을 위하여 민간부문의 성숙된 기술을 국방부 문에서 공식적인 획득프로세스로 진입시키기 위한 노력으 로서 민간부문과 국외에서 개발활용중인 알고리즘을 살펴 볼 필요가 있다.

본 연구에서는 활용중인 경로계획 알고리즘의 기본이 되고 경로탐색 알고리즘을 대별하는 특성을 지닌 A*와 D*

알고리즘을 비교분석하여 시사점을 얻고자 한다. 즉, 주요 알고리즘이 가지는 특성을 식별하고 이러한 특 성이 군사운용개념에 영향을 미치는 정도를 확인한다면 향후 개발표준화 선정시 시사점을 줄 수 있을 것이다.

지상무인전투체계에 사용이 가능한 자율주행 알고리즘 개발은 최초 지형정보가 완전하다는 가정하에 출발지점에 서부터 목표지점을 탐색하는 알고리즘과 광역경로계획에 대한 불확실한 지형정보에서의 최적 경로탐색 알고리즘으 로 구분할 수 있다.

일반적인 경로계획 프로세스는 1단계 사전정보와 센서 자료를 이용한 지형정보 획득, 2단계 탐색공간을 표현하는 방법 설정, 3단계 경로탐색 알고리즘을 설정하고, 4단계에 서는 최적의 경로를 도출해 내는 것이다[3, 5, 16]. 본 연구 의 범위는 3단계인 탐색알고리즘을 설정하는데 국방로봇 의 요구특성이 미칠 수 있는 영향을 살펴보는 것이다.

표 2는 선진국에서 개발∙활용중이고 국방로봇에 적용되 는 경로탐색 알고리즘과 탐색공간을 표현하는 방법을 분 류한 것이다. 경로탐색 알고리즘의 선정에 있어서 일반적 인 고려사항은 최적 경로가 있다면 이를 식별이 가능해야 하는데 이를 완전성(completeness)이라 하고, 가능한 경로 에서 최소의 희생으로 달성 가능한 최적의 경로를 달성하 는 최적화 가능성(optimality), 알고리즘이 표현해야 하는 시공간의 규모에 따른 시간과 메모리의 소모와 관련한 시 공간의 복잡성(complexity)이 있다.

경로탐색 알고리즘의 분류는 휴리스틱 정보를 활용하는 정보탐색(informed search)과 탐색공간에 대한 정보없이 경 로를 탐색하는 무정보탐색(uninformed search)으로 구분할 수 있다. 무정보탐색 방법으로서 Depth-First는 계산시간의 단축을, Breadth-First는 탐색공간을 완전히 분석하는 완전 성을 지향하고, 정보탐색 방법으로서 Heuristic은 추단법에 의한 정보를 활용하여 효율적인 경로탐색이 가능하고 Replanning은 초기 정보가 불확실한 경우에 적용 가능한

방법으로써 지형정보가 변화하여도 알고리즘이 갖추어야 하는 완전성, 최적화 경로, 시공간 복잡성 등의 특성을 유 지할 수 있다.

전장공간을 표현하는 방법으로 전통적인 2차원의 군사 지도와 최근에 부각된 벡터지도 등의 방식을 고려할 수 있 는데 이를 탐색공간으로 표현하는 방법으로는 전체 탐색 공간을 상호배타적이고 이산적인 셀로 분해하는 셀 분해 (cell decomposition), 이동경로를 연결하는 방식의 로드맵 방법론(roadmap method), 탐색공간을 수리함수 모형으로 표현하는 포텐셜 필드(potential fields)가 있다.

2.3 자율주행기술의 구성과 분류

그림 2에서 자율주행계획에 따른 경로계획은 자율주 행계획, 속도계획, 궤적계획과 연계되고 서보제어를 거 쳐서 구동장치와 연계된다. 따라서 알고리즘 설정의 결 과는 지상무인차량의 획득규격에 영향을 미치게 되고 획득규격은 획득프로세스상에서 군사적 운용가능여부를 평가하는 시험평가에서 주요한 기준으로 작용하게 된다.

그림 3은 임무수행능력 관점에서 무인주행계획, 자율주 행기술이 임무수행과 연계되어 작동됨을 나타낸다.

따라서 지형, 표적, 위협을 감지하고 처리하여 대응하는 일련의 임무수행은 이러한 지형, 표적, 위협을 어떻게 가 정하고 인식하는가에 따라서 현격한 차이를 나타낼 것이 다. 그리고 지형을 인식하고 인지하는 기술적 접근과 불확 실성을 고려한 표적의 변화를 어느수준에서 고려하느냐는

그림 2. 자율주행기술 구성도^[5]

무인전투체계

그림 3. 임무수행능력 관점의 무인전투체계 WBS^[3]

무기체계적 분류 학제적 기술 분류

기동력

자율주행

인식, 항법, 계획, 행동 및 기술, 학 습 및 적응, 통신, 인간-로봇 연동, Health/유지

능동현수/ 다 축추진

인식, 행동 및 기술, 학습 및 적응, 동력/에너지, 기동, Health/유지

화력

무장기술 임무장비

정밀구동/ 고

속장전 학습 및 적응, Health/유지, 임무장비 사격통제 지

능화

인식, 학습 및 적응, Health/유지, 임 무장비

원격 실시간

지휘통제 통신, 인간-로봇 연동, Health/유지

방호력

능동방호 인식, 행동 및 기술, 학습 및 적응, 통신

장갑 Health/유지

장애물

폭발물 탐지/

처리 인식, 학습 및 적응, 임무장비 장애물 개척 인식, 행동 및 기술, 동력/에너지, 임

무장비

표 3. 학제적 관점과 무기체계적 관점의 무인체계 소요기술 연관성^[5]

기술과 운용관점에 많은 영향을 미치게 된다.

한편 표 3에서 학제적인 무인체계 소요기술과 무기체 계 관점의 소요기술의 연관성을 살펴보면 학제적으로 다루는 인식기술, 항법기술, 계획기술, 행동기술, 학습 및 적응, 통신기술, 인간-로봇 연동기술, Health/유지 분 야가 무기체계적 분류에서 자율주행과 연관되어 있음을 알 수 있다. 이는 기초/응용연구 단계에서의 학제적인 연구가 무기체계 적용단계에 부합하기 위해서는 기술적 연관성을 유지하면서 사용자 요구를 부합화하는 것이 조달기간을 단축하고 민군겸용기술의 개발을 통한 규모 의 경제성도 추구할 수 있다는 것을 시사한다.

본 연구에서는 불확실한 탐색공간의 정보가 주어지고 탐색공간을 표현하는 방법이 그리드 셀 분할로서 정해졌 다는 가정하에 군사 응용요구가 자율주행 경로계획 알고 리즘의 성능에 미치는 영향을 살펴보고, 향후 국방로봇체 계를 개발하는데 필요한 프로세스를 정립하는데 시사점을 주고자 하였다.

이를 위해 기존의 다양한 경로탐색 알고리즘 중에서 상 용부문에서 범용적이고 다양한 분야에 응용되고 있는 A*

알고리즘과 D*알고리즘을 선정하여 분석하고자 한다. A*

알고리즘이 완전한 지형정보를 가정하고 주어진 사전정보 를 바탕으로 전방향 탐색(forward search)으로 최적의 경로 를 산출하는 반면에 D*알고리즘은 불완전한 사전정보를 가정하고 후방향 탐색(backward search)으로 목표지점이 변 하거나 탐색공간의 정보가 변화할 때 적용이 가능하다. 이 두 알고리즘은 1990년대에 초기 버전이 개발되어 운용특 성에 따른 파생된 많은 알고리즘이 존재하지만 범용성과 고유특성을 평가하고 국내 국방부문에서는 적용연구단계 에 있다는 측면에서 본 연구에서 보이고자 하는 목적과 부 합하여 선정되었으며 국방운용요구분석에 기본적으로 고 려되는 METT+TC요소에 따른 알고리즘의 성능특성을 살 펴보고자 하였다.

3. 분석 방법론

전장환경에서 무인전투차량의 경로계획 알고리즘설정 영향요인 분석을 위한 방법론으로써 METT+TC요소를 사 용하였다.

3.1 METT+TC 요소

군사작전에서 부대운용개념은 전장정보분석과 부대지 휘절차에 따라 발전하며 정보분석의 내용은 기본적으로

METT+TC METT+TC 내용 알고리즘 특성 구분 요소

Mission (임무)

임무과제(기동, 정 찰, 화력, 장애물 개척), 교전수칙, 행 동 의도, 위치

원격제어, 자율주행, 정보 탐색, 무정보탐색, 국지적, 광대역

Enemy (적상황)

부대, 위치, (기동) 능력, 장비

이동표적, 고정표적, 정보 의 업데이트 시점/방식, 정보분석 시점, 원격제어, 자율주행

Terrain &

Weather (지형 및

기상)

가시거리, 사격구 역, 엄호사격, 주요 지형지물, 접근로, 안개 등 기상

광역 또는 지역, 인지/인 식정보 입력방식/업데이트 방식, 지형변화, 지형정보 불확실성

Troops &

Support (가용부대)

부대, 위치, (기동) 능력, 장비, 명시된 과업, 추정된 과업

단일부대 또는 네트워크 화 부대, 통신, 위치추정 기법, 기동경로 및 속도표 식, 과업변화 적응성, 예 배속 전환

Time (가용시간)

절대적 또는 상대 적 출발/도착 시간

시공간 경로계획, 경로 계 산시간, 최적화 경로 산출 가능

Civilian (민간요소)

아측 통제지역, 건 물/시설, 민간단체, 주요 활동

군사/민사 과업, 안전장치 표 4. METT+TC와 알고리즘 특성 구분 요소

METT+TC요소, 즉 임무(M), 적상황(E), 가용시간(T), 가용 부대(T), 그리고 지형 및 기상(T)과 민간요소(C)를 포함한 다. 무인전투차량, 무인잠수정, UAV를 비롯한 무인무기체 계의 운용개념 또한 이러한 정보판단절차에 준해서 운용 개념을 발전시킬 수 있으며 운용개념은 그림 1에서 살펴 보았듯이 군사적 운용개념에 적합성 여부를 평가하는데 적용될 수 있는 규격(specification)에 직접적인 영향을 미치 게 된다.

그림 2에서 경로계획 알고리즘은 무인전투차량을 운용 하는 전장상황의 변화에 따라 인식/인지기술과 연계되어 적용된다. 따라서 경로계획 알고리즘을 선택하고 제어하 는데 전장상황의 변화를 분석하는 전장정보분석 요소인 METT+TC를 고려한 판단절차를 적용하면 그 영향정도를 분석할 수 있을 것이다. 표 4는 METT+TC와 알고리즘 특 성을 구분하는 조작적 요소를 나타낸다⁷⁾.

경로계획의 공통적인 구성요소라고 할 수 있는 로봇 행 동(actions) 및 최초/최종 상태(state), 탐색공간(search space), 시간에 따라 일련의 행동과정을 나타내는 시공간(time)은 각각 임무(M), 지형(T), 가용시간(T)과 연관되며, 지형/기상 요소(T)는 경로계획의 고려사항이 되는 수중/공중/지상 등 운용환경(environment)과 연관이 크고, 가용부대(T)는 네트 워크/차륜형/다족형 등 로봇구조(robot structure)와 관련이 있다. 또한 알고리즘의 성능과 관련된 최적화 경로의 달성 (optimality), 목표 탐색공간에 대한 탐색경로설정의 완전성 (completeness), 시공간의 복잡성(complexity), 지형정보의 불확실성(uncertainty)간의 트레이드오프는 임무계획을 위 한 알고리즘 선정에 주요한 고려사항이 된다.

예를 들어 지상 소부대급에서 단일 지상차량을 운용해 서 적 위협이 없는 후방지역에서 발달된 도로망을 이용하 여 보급수송 임무를 수행한다면 원격제어를 이용한 무인 차량의 이용이 효과적일 수 있다. 하지만 적의 정보자산이 지상차량을 원격제어 하는 신호를 탐지하고 활용할 수 있 는 능력이 있다면 적정을 노출하여 보급수송에 지장을 받 을 수 있으므로 자율주행 알고리즘이 유력하게 고려되어 야 할 것이다. 자율주행 알고리즘에서도 후방지역의 발달 된 도로망과 지형/기상정보의 확실성을 고려한다면 A*계 열의 알고리즘이 고려될 수 있을 것이다. 이와 같은 일련 의 시나리오는 운용자와 무인차량간의 인터페이스 기술에 대한 변화를 요구하게 될 것이고 로봇의 운용환경에 따라 서 알고리즘 각각의 성능특성도 두드러지게 될 것이다.

7) METT+TC요소가 운용개념 발전을 위해 중요한 요소인 것은 분명하 나 무인무기체계 알고리즘설정을 위한 상위 수준의 모형이며 본 논문 에서는 무인무기체계의 사용자 운용요구를 사전에 분석하고 경로계획 알고리즘을 설정하는데 유효하다는 것을 말하고자 한다.

3.2 분석조건

본 연구에서는 단일 지상차량이 정보탐색하에 광대역 자율주행 알고리즘을 대상으로 하여 지형정보의 변화, 적 부대 이동 등 적 상황 요소가 알고리즘 성능에 미치는 영 향을 살펴보았다. 분석을 위한 조작적 정의로서 지형정보 의 변화는 각 알고리즘의 고유한 비용지수로 환산하였고 적 부대 이동 등 적 상황 요소는 이동이 감지되는 시점에 비용지수화 하여 고려되도록 하였다.

3.2.1 적 상황 및 지형/기상 변화에 대한 구현능력 이동하는 표적이나 기상의 변화 정보를 실시간 업데이 트 하여 최적화 경로를 탐색하는 알고리즘은 자율주행을 구현하는데 필수적인 기술이다. 특히, 군사운용 목적의 지 상차량 등 장비를 탑재하고 특정한 임무를 수행하는 무인 무기체계는 논밭, 기온, 산악지형, 운무, 적 이동 등 작은 변화에도 민감하므로 실시간 정보를 업데이트하는 성능특 성은 중요한 고려사항이 된다.

적 상황 및 지형/기상 정보 변화시 경로탐색을 비교하기 위하여 최초 정보를 이용한 경로탐색 결과를 살펴보고, 최 초 경로탐색에 이어서 정보변화가 있을 때 경로탐색 그리 고 최초정보와 변화된 정보가 융합된 정보를 이용한 경로 탐색을 비교함으로써 알고리즘의 구현특성을 살펴보았다.

3.2.2 지형정보의 변화에 따른 경로탐색 소요시간 지형의 크기는 셀 분할로 구현하고 지형정보의 변화에 따른 경로탐색 소요시간은 100x100 셀 분할에서 지형변화 건당 시간의 증가분을 측정하였다. 셀 분할수가 증가할수 록 경로탐색 계산시간은 기하급수적으로 증가하는데 본 연구에서는 100x100 셀 분할 조건에서 지형변화에 따른 민감도를 기존연구에 추가로 살펴보았다.

경로탐색 민감도는 초기 지형정보가 완전하다는 조건하 에서의 탐색시간에 대비하여 지형정보 변화시 탐색시간을 측정하였으며 지형정보 변화는 1개소에서 4개소를 가정하 고 무작위 난수를 생성하였다.

구현 속도 측정은 실온의 연구실에서 스톱워치를 이용 하여 측정했으며 지형정보는 매 회 난수를 생성하여 30회 씩 측정한 평균값을 산출하였다. 1개소당 지형변화는 5셀 의 크기로 설정하였고 시스템 사양은 Intel(R) core(TM)2, 2.13GHz이며 운영체제는 Windows XP를 사용하였다.

4. 분석결과 및 시사점 4.1 분석대상 알고리즘과 실행결과

4.1.1 A*, D* 알고리즘과 완전성 및 경로최적화 - A* 알고리즘

A* 알고리즘이란 어떠한 지점에서 목표 지점까지의 경 로를 찾는 그래프 탐색 알고리즘이다. 목표 노드까지의 최 적 경로를 추정하기 위해 각 노드에 랭킹을 부여하는 휴리 스틱 추정을 사용하고 그 순서대로 노드를 방문한다. A*

알고리즘은 그래프에서 최단경로를 찾는 것을 보장하며 계산부하를 최소화하여 수행한다.

시작지점(SP)과 목표지점(GP)을 정하고, 시작지점에서 현재 임의지점까지 이동간 들어간 비용을 평가함수 g(X) 로 정의하고, 인접한 해당 셀로 이동하는데 소모되는 비용 을 상황에 맞게 정의한다. 그리고 현지점으로부터 목표지 점까지 예상되는 최적경로비용(최소비용)을 경험적인 정 보를 토대로 결정하여 h(X)로 정의하면 g(X)와 h(X)값의 합인 평가함수값 f(X)가 결정된다. 이 평가함수는 현재의 임의지점을 중심으로 주변 4방향 또는 8방향 등의 이웃 셀 들을 탐색하여 이 평가함수의 값이 최소인 셀로의 이동을 반복하여 목표지점까지 도달하는 원리로 Open list 와 Closed list의 변화를 통하여 평가함수에 의해 목적지까지 최적의 경로를 찾는다.

A* 알고리즘은 J. Matthews(2001)의 의사코드를 구현하 였다. 시작점은 좌상단으로 하고 목표점은 우하단으로 설 정하였다. 그림 4는 200x200 그리드 셀 분할에서 A*알고

리즘을 이용한 경로탐색결과를 보여준다. 각각의 그리드 셀에서 비용함수는 흰색에서 검정색으로 증가하도록 표현 하였으며 청색실선은 최적화경로를 표현한다.

그림 4. A* 경로탐색 결과

- D* 알고리즘

D* 알고리즘이란 최초 또는 실시간 식별된 장애물을 회 피함과 동시에 비용과 관계된 백포인터를 따라 인접 지점 으로 이동을 반복하여 목표지점까지 경로를 찾아주는 불 확실성하 최적 경로탐색 알고리즘이다.

그림 5는 D* 알고리즘의 의사결정과 작동 순서도이다.

로봇의 이동 시작점과 목표점이 선정되면 k값과 h값을 D*

알고리즘상에서 계산하여 셀별 백포인터를 형성한 후 초기 경로를 생성하고 로봇이 백포인터를 따라 이동중 실시간 감지된 장애물은 해당셀 주변의 백포인터만을 변경하여 최 종 목적지에 도달하게 된다. 이때 가장 상위의 Function인 MOVE-ROBOT() 의 기능 하에 PROCESS-STATE() Function 을 중심으로 로봇이 이동가능한 경로를 따라 희생을 최소 화하는 최적화 경로를 생성하게 된다.

A* 알고리즘과 특징적으로 구분되는 것은 그림 5에서 최초지형정보와 경로탐색 과정에서 주어지는 추후지형정 보가 동일한지를 평가하는 MODIFY-COST()기능이다.

구현 알고리즘은 Anthony Stentz(1994), Dave Ferguson and Anthony Stentz(2005, 2006)에서 표현된 D*기본 의사코 드(pseudo code)를 선정하였으며 시스템 사양 및 운영체제 는 A* 구현시와 동일하다.

그림 6은 200x200그리드 셀에서 D*알고리즘을 적용한 경로탐색 결과이다. 각각의 그리드 셀에서 비용함수는 초 록색에서 검정색으로 증가함을 나타내고 적색실선은 최적 화경로를 표현한다.

그림 5. MOVE-ROBOT() 작동 순서도^[9]

그림 6. D* 경로탐색 결과

4.1.2 적 상황 및 지형/기상 정보 변화시 경로탐색 그림 7은 이동표적 또는 전장환경 정보가 변하거나 불 확실한 가운데 경로계획설정의 결과를 나타낸다. 기존의 경로계획 알고리즘 중에서 불확실한 전장환경에서 경로계 획이 가능한 D*알고리즘을 적용하였다⁸⁾.

8) 가용한 정보자산-육안, 광학장비, 영상장비, GPS 등-에 따라서 적이 동, 지형변화 등에 관하여 탐지할 수 있는 범위가 달라지고 그에 따라 셀 방식에서 구현되는 정보업데이트 시점이 연동된다.

그림 7에서 (a)는 최초정보를 바탕으로 한 경로탐색 결 과를 나타내며 최적의 경로를 탐색하고, 완전성과 효율성 이 보장되며 D*는 물론이고 A*를 적용하여도 동일한 결과 가 보장된다. (b) 정보변화가 있는 상황에서 경로탐색이 가 능한 알고리즘은 D*계열 또는 A*의 반복적인 적용에 의하 여 구현할 수 있다. 하지만 이 경우에 A*는 포워드 탐색 (forward search)이고 매번 탐색시에 탐색공간을 재설정하 지만 D*는 백워드 탐색(backward search)이며 최초에 탐색 공간 전체에 대하여 탐색한 결과정보를 활용하고 차후에 정보가 변화한 부분을 식별하여 경로를 재탐색한다는 차 이가 있다. (c) 최초정보와 최종정보가 융합된 지형정보가 주어질 경우에 탐색경로는 (b)에서 살펴본 경로탐색의 결 과와 다른 결과를 나타내는데 이는 변화된 정보가 주어지 는 시점에 따라서 나타나는 결과이다.

적 상황 및 지형/기상 변화에 따른 경로탐색 기능은 완 전한 최초 정보를 가정하는 선정한 A*알고리즘으로는 불 가능하고 D*알고리즘으로도 제한적으로 가능하다는 것을 확인하였다.

D*는 지형정보가 변화하여 최초정보와 최초경로에 영 향을 미칠 경우에는 이를 재탐색하여 새로운 경로를 제시 하는데 새롭게 제시되는 경로는 목표지점과 가까운 경로 만 재탐색함으로써 A*에 비해 계산시간이 단축된다. 이때 최초 경로탐색의 결과로 도출한 경로에서 재탐색을 하는 범위에 관한 설정이 커지면 계산시간이 증가하는 결과를 낳고 설정범위가 좁으면 최적화 경로를 탐색하지 못하는 결과를 낳을 수 있는데 이는 최초정보의 잔상이 그대로 남 기 때문이다. 따라서 경로탐색 알고리즘은 탐색공간 범위, 지형정보의 불확실성 등에 따라 경로탐색의 완전성, 경로 의 최적화, 새로운 정보의 업데이트 효율성간에 트레이드 오프(tradeoff)가 발생하며 이는 운용목적 적합성에 영향을 미친다.

따라서 작전지역내 적의 이동이나 정보자산 가용성 등 을 고려하여 경로탐색 알고리즘을 설정하고 이를 구현하 는 기술적 요소를 식별하여 자율주행 기술과 체계를 개발 하는데 고려할 필요가 있다.

4.1.3 A*와 D* 알고리즘의 경로탐색 효율성

A*와 D* 경로계획 알고리즘은 경로탐색범위에 따라 계 산속도에서 차이가 급증하며 동일한 탐색범위에 대하여 지형정보가 변화하는 정도에 따라서도 산술적으로 차이가 커진다는 것을 확인하였다. 탐색범위(그리드 셀의 크기)에 따른 경로탐색 속도는 Stentz(1994), Giebrecht(2004)에서 제 시한 결과와 유사하게 탐색범위가 커질수록 A*의 경로탐 색 시간은 D*에 비해 급증하였다.

(a) 최초 정보를 바탕으로 한 경로탐색 결과

(b) 정보변화가 있는 상황에서 D* 경로탐색

(c) 최초정보와 정보변화가 융합된 정보하에 경로탐색 그림 7. 변화하는 전장정보를 이용한 경로탐색

표 5는 지형변화에 따른 경로탐색 민감도 평균값을 정 리하였으며 그림 8은 이를 그래프로 표현하였다. 실험결과 식별된 지형변화의 수가 증가할수록 A* 알고리즘의 목적 지까지 도달시간은 선형적으로 증가하였지만 D* 알고리즘 의 경우 미세한 시간의 증가가 있었을 뿐 큰 변화는 없었다.

지형변화

알고리즘 없음 1개소 2개소 3개소 4개소

A* 1 1.56 1.99 2.39 2.85

D* 1 1.01 1.05 1.09 1.12

비율(A*/D*) 1 1.54 1.90 2.19 2.42 표 5. 지형변화에 따른 경로탐색 민감도(비율지수)

0 0.5 1 1.5 2 2.5 3

1 2 3 4 5

지형변화(개소)

탐색시간(비율지수)

A*

D*

그림 8. 지형변화에 따른 탐색시간의 민감도

5. 결 론

본 논문은 현재 민간부문과 국방부문에서 로봇개발에 활용중인 경로계획기법을 살펴보고 국방분야 적용을 위해 서 고려해야할 요소를 식별하고자 하였다.

자동차 내비게이션 등 상용부문에 널리 활용되고 있는 A*, D* 알고리즘을 선택하여 METT+TC를 단일한 지상차 량이 정보탐색하에 광대역 자율주행 하는 경우에 제한적 으로 적용하여 지형정보의 변화, 적부대 이동 등 적상황 요소가 알고리즘 성능에 미치는 영향을 살펴보았다.

두 알고리즘 모두 최적경로를 탐색할 수 있었으나 경로 탐색 효율성면에서 탐색공간이 확대될수록 D*가 A*보다 우월하였으며 적의 이동과 같이 경로계획에 영향을 미치

는 전장정보의 변화에 대한 경로탐색은 제한적으로 D*가 가능하였다.

이 결과는 민간부문의 일반화된 알고리즘을 적용한 민 군로봇의 제품이 국방획득으로 연계되기 위해서는 다양한 알고리즘 특성과 운용개념을 부합화하고 연동시키는 개발 활동이 필요하다는 것을 간접적으로 시사한다.

향후 전장상황에서 고려할 수 있는 여러 가지 요소를 고려하여 각종 전장운용개념에 적합한 세부적인 알고리즘 설정 영향요인 식별 및 개발, 비교분석 및 검증하는데 본 연구가 기여하기를 바란다.

참 고 문 헌

[1] 국방과학연구소, 선진국의 미래전투체계 개발동향, 국방과학연구소 동향분석서, 2004.

[2] 국방과학연구소, “국방로봇개발 추진현황”, 국방과학 연구소 보고서, 2005.

[3] 국방과학연구소, ’04국방지상로봇 종합계획을 위한 조사연구보고서, 국방과학연구소, 2005

[4] 국방과학연구소, 제3회 군사용 로봇 워크샵 논문집, 국방과학연구소, 2008.

[5] 국방기술품질원, 국방과학기술조사서 9-1, 4권, 대한 기획인쇄, 2007.

[6] 국방기술품질원, 국방과학기술 용어 사전, 경성문화 사, 2008.11.

[7] 국방부, “국방로봇 현황과 전망”, 국방부 업무참고자 료, 2006.

[8] 방위사업청, 방위사업관리규정, 방위사업청 훈령 제 88호, 2009.1.

[9] 백종성, 이춘주, “불확실성하 지상 무인 전투체계의 자율주행 알고리즘 연구”, 국방과학기술 제1권, 제2 호, 2008. 12.

[10] 육군본부, 미래지상군 역할 및 모습, 간부교육자료, 2007. 4, p.5.

[11] 최형욱, 미래전장에서의 무인전투체계 발전방향, 석사 학위논문, 국방대학교, 2007.

[12] 합동참모본부, “국방무인화 발전방향 및 군사적 활용 방안”, 업무참고자료, 2007.

[13] Anthony Stentz, Optimal and Efficient Path Planning for Partially-Known Environments, IEEE International Conference on Robotics and Automation, May, 1994.

[14] Dave Ferguson and Anthony Stentz, The Delayed D*

Algorithm for Efficient Path Replanning, Proceeding of the 2005 IEEE International Conference on

Robotics and Automation, April, 2005.

[15] Dave Ferguson and Anthony Stentz, Using Interpolation to Improve Path Planning: The Field D* Algorithm, Journal of Field Robotics, 23(2), pp.79-101, 2006.

[16] J. Giebrecht, Global Path Planning for Unmanned Ground Vehicles, Technical Memorandum, DRDC Suffield TM2004-272, 2004. 12.

[17] J. Matthews, A* Explorer 2.0 BETA R2 Copyright ⓒ 2001-2.

백 종 성

1999 육군사관학교 물리학 (학사)

2009 국방대학교 무기체계학 과(석사)

2009~현재 육군 포병학교 지 원처

관심분야 : 시설관리, 전투공병운용, 국방로봇 E‐mail : [email protected]

이 춘 주

1991 육군사관학교 물리학 (학사)

1997 미국 UC. Berkeley 핵공 학(석사)

2005 KDI 국제정책대학원 국 제관계(석사)

2006 서울대학교 공과대학기술정책대학원(공학 박사) 2006∼현재 국방대학교 무기체계과 조교수

관심분야 : 연구개발 및 기술관리, 민군기술협력체제, 기술혁신, 무인무기체계

E‐mail : [email protected]