1. 서 론
오늘날 인명손실을 최소화 하면서 작전목적을 달성 케 하여 그 활용도가 큰 무인전투체계에 대한 관심이 크다. 이러한 무인전투체계는 유인체계 대비 경제적이 고 작전의 지속성을 보장 할 수 있다는 장점을 지녔 으며, 각종 첨단기술이 망라된 복합시스템으로 부가가
*Corresponding author, E-mail: [email protected]
Copyright ⓒ The Korea Institute of Military Science and Technology
치가 매우 큰 것으로서 타 분야의 기술을 선도하고 기존의 로봇산업을 견인할 수 있을 것으로 기대되는 무기체계이다. 이러한 무인전투체계의 효과적인 운용 을 위해서는 무엇보다 지휘통제의 주체가 되는 지휘 통제차량에서 군사적 운용개념이 적용된 로봇의 임무 통제 방법이 중요하다. 임무통제는 근접제어, 원격통 제 및 자율 방법이 있으며 기 계획된 임무에 따라 각 기 다른 방법으로 운용이 가능하지만 무인전투체계의 운용개념상 자율 임무통제 방법이 가장 의미가 있는 통제 방법이라 할 수 있다. 이러한 자율 임무통제 방 Research Paper 지상무기 부문
임무유형 기반 전역경로계획을 위한 가중치 결정방법
박원익1)․이호주*,1)․김도종1)
1)국방과학연구소 제5기술연구본부
A Method to Determine the Weights for Mission Type based Global Path Planning
Won-Ik Park1)․Ho-Joo Lee*,1)․Do-Jong Kim1)
1)The 5th Research and Development Institute, Agency for Defense Development, Korea
(Received 10 January 2014 / Revised 15 August 2014 / Accepted 17 October 2014)
ABSTRACT
Global path planning for autonomous driving of unmanned ground vehicle is essential. When setting global path planning, its accuracy and effectiveness is increased if useful information such as terrain type of driving route has been reflected on global path planning. As a method to reflect the terrain type, there is a method to perform global path planning by applying the weight to each terrain type. At this time, how to assign appropriate weights corresponding to the terrain type is more important than anything. In this paper, we proposed a method to determine the weight for terrain type that may affect the results of global path planning. Moreover, we presented effective operation method and design results(GUI) to check the possibility of the use of the proposed method.
Key Words : Unmanned Ground Vehicle(무인지상차량), Autonomous Navigation(자율주행), Global Path Planning(전역 경로계획)
법을 수행함에 있어서 로봇의 주행경로를 설정하는 경로계획(Path Planning) 기술은 필수적이다. 일반적으 로 경로계획 기술은 비교적 넓은 지역을 대상으로 하 여 주행경로를 최적화하는 전역경로계획(GPP : Global Path Planning)과 전역경로계획의 결과로 얻어진 경로 점(Way Points)들을 대상으로 센서 및 항법장치를 이 용하여 실시간 경로 최적화를 수행하는 지역경로계획 (LPP : Local Path Planning)으로 구분된다. 기존의 전 역경로계획 기술은 많은 연구가 진행된 상태이며 어 느 정도 최적화된 상태이다. Dijkstra, A*, D* 등과 같 은 알고리즘이 대표적이다[1-4]. 하지만 기존 알고리즘 은 무인전투체계 도메인의 특성을 반영하지 못하며 일반적인 경로탐색만을 제공한다. 실제 무인전투 체계 에서 로봇의 효과적인 전역경로계획을 위해서는 다양 한 임무유형을 반영한 경로탐색이 이루어져야 한다.
관련 연구로 격자기반의 지형분석 정보(주행정도, 위 협정도, 통신정도)에 가중치를 부여하여 로봇의 임무 와 연계하는 전역경로계획을 제공하는 연구가 있다[5]. 하지만 이와 같은 방법은 임무유형에 따른 전역경로 계획을 제공하기 위해 필요한 지형분석 정보에 대한 가중치 부여가 지휘자 및 운용자 한사람의 경험적 선 택으로 결정되어 전역경로계획의 일관성 및 정확도가 떨어지는 단점이 있다.
본 논문에서는 가중치기반의 임무지향 전역경로를 실시함에 있어서, 지형분석 정보를 효과적으로 반영하 기 위한 가중치 결정 방법에 대해 제안한다. 또한, 제 안방법을 포함하는 임무계획에 있어서, 효과적인 운 용방법 및 관련 GUI 설계 결과를 제시하여 그 활용 가능성을 확인한다.
본 논문의 구성은 다음과 같다. 2장에서는 가중치 기반 전역경로계획 알고리즘 소개와 제안한 계층적 가중치 결정방법에 대한 설명을 하고 3장에서는 제안 방법의 활용 가능성을 입증하기위해 운용방법 및 관 련 GUI 설계 결과를 제시한다. 마지막으로 4장에서는 결론을 기술한다.
2. 본 론
2.1 가중치 기반 전역경로계획 알고리즘
일반적인 격자기반의 전역경로계획과는 달리 지형 분석 정보를 반영한 가중치 기반 전역경로계획 방법 은 지형분석 정보를 Fig. 1과 같은 격자기반의 비용맵
으로 생성하여 활용한다. 즉, 생성된 각 지형분석 정 보를 A* 알고리즘의 목적함수인 식 (1)을 이용하여 구 하고 식 (2)에서처럼 선형 조합함으로써 지형정보를 반영한 최적 경로를 생성하는 방법이다.
Fig. 1. Grid based cost map
(1) 여기서 목적함수 f(n)은 로봇이 출발점으로부터 n번 째 격자까지의 비용값 g(n)과 현재의 격자에서 목표점 까지의 비용 예측 값인 h(n)의 합으로 구성된다.
min
∈
∈
∈
(2)
여기서, w1(주행정도 가중치), w2(위협정도 가중치), w3(통신정도 가중치)는 다양한 지형분석정보의 가중치 를 의미한다. 또한 vi는 격자 i의 주행정도 비용을 의 미하며, ri는 격자 i의 위협정도 비용, ci는 격자 i의 통 신정도 비용을 의미한다. 즉, 지휘자 및 운용자는 임 무에 따른 각각의 가중치 w1, w2, w3 값을 임의로 조 절하여 임무유형에 따른 전역경로생성이 가능하다.
따라서 경로탐색 시 임무유형에 따른 가중치 부여 방법이 무엇보다 중요하다고 할 수 있다. 하지만 기존 방법은 지휘자 및 운용자 한두 사람의 경험적 지식만 으로 가중치가 결정되기 때문에 정확도와 일관성이 떨어지는 문제를 갖는다.
2.2 계층적 가중치 결정 방법
본 논문에서는 가중치 기반의 임무지향 전역경로를 생성하기 위한 임무 및 지형분석 정보에 대한 가중치 를 수치적으로 부여하여 정확도 및 일관성을 높이는 방법에 대하여 설명한다.
Fig. 2. Hierarchy of performance factors 임무지향 전역경로계획을 위한 가중치 계산을 위해 서는 Fig. 1과 같은 성능요소를 식별하고 식별된 성능 요소들을 계층화하여 구조화 시킬 필요가 있다. Fig. 2 에서와 같이 전역경로생성 시 관련된 임무로는 이동 임무, 감시경계 임무, 지뢰탐지 임무, 임무대기 임무이 며 각각 지형분석 정보가 관련된다. 즉, 가중치 기반 의 임무지향 전역경로계획을 생성하기 위해서는 이동 임무(M), 감시경계(W), 지뢰탐지(D), 임무대기(S)에 대 한 가중치(w1 ,w2, w3, w4)와 각 임무에 해당하는 지형 분석 정보에 대한 가중치(vi, ui, ti, si, i = 1 : 속도, 2 : 안전, 3 : 통신)가 필요하다. 만약 위 가중치들을 기지 했다면 가중치 기반의 임무지향 경로계획 GPP = f{(w1
× 이동(M)) + (w2 × 감시경계(W)) + (w3 × 지뢰탐지 (D)) + (w4 × 임무대기(S))}와 같이 계산이 가능하다.
마찬가지로 각 임무는 이동(M) = f{(v1 × 속도(v)) + (v2 × 안전(r)) + (v3 × 통신(c))}, 감시경계(W) = f{(u1
× 속도(v)) + (u2 × 안전(r)) + (u3 × 통신(c))}, 지뢰탐 지(D) = f{(t1 × 속도(v)) + (t2 × 안전(r)) + (t3 × 통신 (c))}, 임무대기(S) = f{(s1 × 속도(v)) + (s2 × 안전(r)) + (s3 × 통신(c))}와 같이 계산이 가능하다. 이처럼 각 성 능 요소의 가중치 계산은 Fig. 2에서의 시블링(sibling) 노드들 간의 쌍대비교표를 전문가 집단을 통해 획득 하여 계산되며 쌍대비교표를 구성하는 값들은 미리 정의한 상대 중요도 지표를 이용한다. Table 1은 정의 한 상대 중요도 지표이다.
Fig. 2와 같은 계층구조에서의 각 쌍대비교표는전문 가를 통해 획득가능하며 그 예를 통해 가중치 계산 과 정을 설명한다. Table 3은 Fig. 2에서의 Level 1 임무에 따른 쌍대비교표이다.
Table 3은 Level 1에서의 쌍대비교표 예로써 전역경 로계획을 실시함에 있어서 각 임무간 중요도 비교를 의미한다. Table 3에서 보듯이 첫 번째 이동임무는 감 시경계 임무보다는 중요하지 않고 지뢰탐지 임무와는 비슷한 중요도를 갖는 반면 임무대기 보다는 매우 중 요하게 판단되는 임무이다. 두 번째 감시경계 임무는 지뢰탐지 임무보다 중요하고 임무대기 보다는 매우 중
요하다고 판단되는 임무이며 세 번째 지뢰탐지 임무 는 임무대기보다 중요한 임무임을 나타낸다. 이와 비 슷한 방법으로 레벨 2에 대한 쌍대비교표 예는 Table 4 ～ Table 7과 같다.
Table 1. Relative importance
설명 점수
매우중요
(IF A is absolutely more important than B) 3 중요
(If A is very strongly more important than B) 2 비슷
(If A is equally important with B) 1 중요하지않음
(If A is weakly more important than B) 1/2 전혀중요하지않음
(If A is equally important with B) 1/3
Table 2. Pair-wise comparative matrix(Level 1) GPP : ConsistencyRatio = 0.0153 이동
(M)
감시경계 (W)
지뢰탐지 (D)
대기 (S) 이동
(M) 1 1/2 1 3
감시경계
(W) 2 1 2 3
지뢰탐지
(D) 1 1/2 1 2
대기
(S) 1/3 1/3 1/2 1
Table 3. Pair-wise comparative matrix(Level 2-M) 이동(M) : ConsistencyRatio = 0.0269 속도(v) 안전(r) 통신(c)
속도(v) 1 2 2
안전(r) 1/2 1 2
통신(c) 1/2 1/2 1
Table 4. Pair-wise comparative matrix(Level 2-W) 감시경계(W) : ConsistencyRatio = 0.0046
속도(v) 안전(r) 통신(c)
속도(v) 1 1/3 1/2
안전(r) 3 1 1/2
통신(c) 2 2 1
Table 5. Pair-wise comparative matrix(Level 2-D) 지뢰탐지(D) : ConsistencyRatio = 0.0000
속도(v) 안전(r) 통신(c)
속도(v) 1 1/2 1/2
안전(r) 2 1 1
통신(c) 2 1 1
Table 6. Pair-wise comparative matrix(Level 2-S) 임무대기(S) : ConsistencyRatio = 0.0000
속도(v) 안전(r) 통신(c)
속도(v) 1 1/2 1/2
안전(r) 2 1 1
통신(c) 2 1 1
위와 같은 쌍대비교표는 가중치 계산을 위해 4 × 4, 3 × 3과 같은 정방행렬 형태로 변환한다. 위에서 예로 든 쌍대비교표 Table 3을 행렬형태인 쌍대비교행렬로 변환하여 작성하면 아래와 같다.
⋮ ⋮ ⋮ ⋯⋮
⇒
각 임무간 중요도 비교를 의미하는 쌍대비교행렬 L1
에서의 실제 임무별 가중치 계산을 위해서 일반적으로 식 (3)과 같이 정의되는 고유치(Eigenvalue)와 고유벡터 (Eigenvector)를 이용한다.
∙ ∙ (3)
여기서, A = n × n 행렬, 즉, 예로든 L1 이며 x = n
× 1 벡터, 는 scalar이다. x ≠ 0 일 때 해, det(A-I)
= 0(|A-I| = 0)을 구하면 값이 구해지며 이를 행렬 A의 고유치라 한다. 가장 큰 고유치를 식 (3)에 대입 하여 계산하여 얻어진 n × 1 벡터 x가 행렬 A의 고유 벡터가 되며 이를 가중치로 정의한다. 이때, 쌍대비교 행렬의 일관성이 보장되어야만 가중치에 대한 신뢰성 보장이 가능하다. 따라서 수식 (4)와 같은 일관성 측 정 지표가 필요하다. 만약, 수식 (4)를 통해 계산된 일 관성 비율(CR : Consistency Ratio)이 10% 이내 일 때 는 합리적인 일관성을 포함한 쌍대비교행렬이라 판단 할 수 있고, 20% 이내인 경우 허용 할 수 있는 수준 이라고 판단할 수 있다. 하지만 일관성 비율이 20%
보다 크게 나올 경우에는 해당 쌍대비교행렬의 일관 성이 없는 것으로 판단하여 가중치에 대한 신뢰도를 보장할 수 없다고 판단한다.
max
(4)
Fig. 3. An example of weight generation
위에서 예로든 Table 3 ～ Table 7의 일관성 비율은 0.1보다 모두 작아 일관성이 있다고 판단되며 이를 활 용하여 계산된 고유치와 고유벡터에 대한 신뢰성이 어 느 정도 보장된다고 볼 수 있다.
따라서 실제 예로든 각 쌍대비교행렬 L1의 고유치 및 고유벡터를 이용하여 가중치를 계산해보면 이동 = 0.249, 감시경계 = 0.419, 지뢰탐지 = 0.223, 임무대기
= 0.108와 같이 임무별 가중치 계산이 가능하다. Fig. 3 은 예로든 모든 쌍대비교표를 이용하여 계산된 계층별 실제 가중치 계산 결과를 보인다.
3. 구현 결과
본 논문에서는 전역경로계획 시 지형분석 정보를 효 과적으로 반영하기 위한 가중치 결정 방법에 대해 제 안하였다. 본 장에서는 제안 방법을 활용한 효과적인 임무계획 작성과 관련하여 그 운용방법 및 관련 GUI 설계결과를 제시하여 활용 가능성을 확인한다.
3.1 임무통제 운용방법
로봇은 지휘통제장치를 통해 기본적으로 운용되어지 며 지휘자나 운용자에 의해 임무통제가 이뤄진다. 이 러한 임무통제는 Table 7과 같은 운용 단계를 따르며 각 단계별 지휘자, 운용자, 조종수(지휘통제차량), 통합 지원컴퓨터의 역할을 설명한다.
Table 7. The steps of mission control 1단계 임무환경 분석 단계
2단계 임무계획 단계(전역경로계획 실시) 3단계 임무 실행/수정 단계
4단계 임무평가 단계
1단계 임무환경 분석 단계에서의 지휘자는 명령/전 문/투명도 수신/전파, 작전지역 선정, 전장정보/지원 판 단, 지형정보 설정/명령, 임무복안 수립, 장치설정(상황 일지 등)과 같은 역할을 수행한다. 운용자는 명령/전문/
투명도 수신, 로봇 점검/준비, 지형정보 설정/가시화 역 할을 수행하며 지휘통제차량 조종수는 명령/전문/투명 도 수신, 지휘통제차량 점검/준비, 전시기 설정/가시화 역할을 수행한다. 마지막으로 통합지원컴퓨터는 지형
정보 생성 및 지원 기능을 수행한다.
2단계 임무계획 단계에서의 지휘자는 다중로봇에 대 한 임무작성, 다중로봇에 대한 임무모의(사전), 임무계 획 승인, 우발계획 수립 역할을 수행한다. 운용자는 단 일로봇에 대한 임무작성, 임무계획 승인 상신, 단일로 봇에 대한 임무모의(사전) 역할을 수행한다.
3단계 임무 실행/수정 단계에서의 지휘자는 임무 수행 모니터링(전체 운용로봇), 임무 수정 승인, 다 중로봇에 대한 임무 재계획, 전장/표적정보 등록 승 인, 실시간 전장상황 분석 역할을 수행한다. 운용자 는 1～2대에 대한 임무수행 모니터링, 임무 수정 및 승인의뢰, 단일로봇에 대한 임무 재계획, 전장/표적 정보 등록상신, 실시간 전장정보 분석 역할을 수행 한다. 지휘통제차량의 조종수는 조종수 전시기를 통 해 상황 공유, 사주경계, 지휘통제차량의 이동 역할 을 수행한다. 통합지원컴퓨터는 전장/표적 정보 처리 /저장, 운용이력 저장, 상황일지 생성/전파 기능을 수 행한다.
4단계 임무평가 단계에서의 지휘자는 임무 수행결과 분석/평가, 전장/표적정보 종합/검토, 다중로봇에 대한 임무모의(사후), 차후 임무반영 역할을 수행한다. 운용 자는 임무 수행결과 분석, 로봇 운용정보 분석, 단일로 봇에 대한 임무모의(사후) 역할을 수행한다. 통합지원 컴퓨터는 임무/전장 DB, 임무평가 자료처리, 임무모의 DB 추출/가공 역할을 수행한다.
3.2 GUI 설계결과
임무통제 수행 단계는 순차적으로 수행되기 때문에 메뉴 구성 또한 순차적 접근이 용이해야한다. 따라서 본 논문에서는 지휘자 및 운용자의 화면메뉴를 임무 통제 수행 단계에 따라 구성하여 임무통제 단계에 따 른 순차적 접근이 용이하도록 Fig. 4와 같이 구성하 였다.
Fig. 4. Menu for mission control
임무통제 단계에서의 가중치 기반 임무지향 전역경 로계획을 포함하는 임무계획 가시화를 위해 필요한 각종 부호는 Table 8과 같이 정의한다.
Table 8. Symbols related to mission planning
부호 설명
1 임무계획 종료점
2 임무계획 시작점
3 과업종료점(대기, 감시)
4 과업종료점
5 과업시작점
6 부호 내 과업명
우측 상단에 과업번호 표시
7 동일 지점에 대기, 감시 중복시
Fig. 5. Visualization screen of mission planning
Fig. 6. Mission planning on situation map
임무계획 가시화 관련 부호를 이용하여 임무통제 2 단계 임무계획 작성 예는 Fig. 5와 같다. 여러 임무들 (이동, 감시경계, 지뢰탐지, 대기)이 모여 하나의 전체 임무를 구성한다.
Fig. 5에서 예로든 임무계획을 실제 상황도 화면에 도시하면 Fig. 6과 같다. 그림에서 보듯이 로봇이 투입 될 작전지역에 대한 전체 임무계획을 가시화 한 화면 이다.
본 논문에서 제안하는 화면메뉴와 가시화 방법은 임 무계획을 실시함에 있어서 가중치 기반 임무지향 전역 경로계획의 효과적 실시 및 가시화를 가능케 하여 로 봇의 임무통제를 돕는다.
4. 결 론
본 논문은 로봇의 가중치 기반의 임무지향 전역경로 계획을 실시함에 있어서, 전역경로계획의 정확도에 영 향을 미칠 수 있는 임무 및 지형분석 정보에 대한 가 중치 결정방법에 대한 것이다. 이는 소수의 지휘자 및 운용자에 의해 부여되던 가중치로 인한 경로계획의 정 확도 및 일관성 결여 문제를 어느 정도 보완 가능케 한다. 제안방법의 활용 가능성 확인을 위해 제안방법 을 포함하는 임무계획을 위한 운용방법 및 관련 GUI 설계 결과를 제시하였다.
향후 제안방법은 지상무인체계 뿐만 아니라 모든 무
인전투체계의 지휘통제 분야에 적용하여, 활용이 가능 할 것으로 사료된다.
References
[1] P. Hart, N. Nilsson, and B. Raphael, “A Formal Basis for the Heuristic Determination of Minimum Cost Paths,” IEEE Trans. Syst. Sci. Cybern., Vol. 4, No. 2, pp. 100-107, Jul. 1968.
[2] S. KoenigandM. Likhachev, “D* Lite,” in Proc. 18th Nat. Conf. Artif. Intell., Menlo Park, CA, pp. 476- 483, 2002.
[3] D. Ferguson and A. T. Stentz, “The Field D* Algorithm for Improved Path Planning and Replanning in Uniform and Non-Uniform Cost Environments,” Robot. Inst., Pittsburgh, PA, Tech.
Rep. CMU-RI-TR- 05-19, Jul. 2005.
[4] E. W. Dijkstra, “A Note on Two Problems in Connexion with Graphs,” Numer. Math., Vol. 1, pp.
269-271, 1959.
[5] Won-Ik Park, Do-Jong Kim, and Ho-Joo Lee,
“Terrain Trafficability Analysis for Autonomous Navigation: A GIS-based Approach,” International Journal of Control, Automation, and Systems 11(2), pp. 354-361, 2013.
