大 韓 土 木 學 會 論 文 集 第26卷 第1D 號·2006年 1月 pp. 195~202
測量 및 地形空間情報工學
지형공간정보 및 최적탐색기법을 이용한 최적침투경로 분석
Analysis of Infiltration Route using Optimal Path Finding Methods and Geospatial Information
방수남*·허 준**·손홍규***·이용웅****
Bang, Soo Nam · Heo, Joon · Sohn, Hong Gyoo · Lee, Yong Woong
···
Abstract
The infiltration route analysis is a military application using geospatial information technology. The result of the analysis would present vulnerable routes for potential enemy infiltration. In order to find the susceptible routes, optimal path search algorithms (Dijkstra’s and A*) were used to minimize the cost function, summation of detection probability. The cost function was produced by capability of TOD (Thermal Observation Device), results of viewshed analysis using DEM (Digital Ele- vation Model) and two related geospatial information coverages (obstacle and vegetation) extracted from VITD (Vector prod- uct Interim Terrain Data). With respect to 50m by 50m cells, the individual cost was computed and recorded, and then the optimal infiltration routes was found while minimizing summation of the costs on the routes. The proposed algorithm was experimented in Daejeon region in South Korea. The test results show that Dijkstra’s and A* algorithms do not present sig- nificant differences, but A* algorithm shows a better efficiency. This application can be used for both infiltration and sur- veillance. Using simulation of moving TOD, the most vulnerable routes can be detected for infiltration purpose. On the other hands, it can be inversely used for selection of the best locations of TOD. This is an example of powerful geospatial solution for military application.
Keywords :
geospatial information, optimal path, infiltration route analysis, Dijkstra, A*···
요 지
침투경로분석은 지형공간정보 기술을 활용한 군사응용분야 중 하나이다 . 분석결과는 잠재적인 적의 침투에 대해 취약한 경 로를 보여줄 것이다 . 가능한 침투경로를 찾기 위하여 탐지확률의 합으로 표현되는 비용함수를 최소화하는 최적경로알고리듬
( 다익스트라 및 A*) 을 사용하였다 . 열상장비의 성능 , 수치고도모형을 이용한 가시선분석 결과와 지형분석도 (VITD) 에 포함된 지형공간정보 커버리지 (coverage) 중 2 개의 관련된 커버리지를 사용하여 비용함수를 계산하였다 . 50m × 50m 셀 (cell) 크기 단
위로 각각의 비용이 계산되고 저장되었으며 , 최적경로로서 경로상의 모든 비용의 합을 최소화하는 경로를 찾아내었다 . 제안 된 방법은 대한민국의 대전지역을 대상으로 실험하였다 . 실험 결과 다익스트라와 A* 알고리듬은 큰 차이가 없었으며 , 다만
A* 알고리듬의 수행시간 측면에서 유리하였다 . 이러한 응용분야는 침투와 감시의 두 가지 측면에서 모두 활용될 수 있다 .
열상장비의 위치를 바꿔서 시뮬레이션을 수행하면 , 가장 취약한 경로를 침투목적으로 찾아낼 수 있다 . 다른 측면으로 보면
열상장비의 최상의 위치를 선택하기 위하여 사용될 수 있다 . 이는 군사응용분야에 대한 강력한 지형공간정보 활용 해법의 한 가지 예제가 될 것이다 .
핵심용어 : 지형공간정보 , 최적경로 , 침투경로분석 , 다익스트라 , 에이스타
···
1. 서 론
지형공간정보의 군사적 응용분야는 매우 넓으며 현대전에
서 더욱 그 중요성이 부각되고 있다 . 2000 년대에 들어서 지
구관측위성 및 첩보위성으로부터 1m 이내의 고해상도 위성 영상 획득이 가능해졌으며 , 수집센서의 다양화 ( 광학 , 레이더 ,
초분광센서 등 ) 로 인하여 비접근 지역에 대한 지표상의 특성
을 분석하는 것이 가능하게 되었다 . 지형공간정보를 이용한 군사응용분야는 주로 지형고도자료를 활용하는 순항미사일과 비행기의 임무계획과 지형추적 및 시뮬레이션 그리고 가시 선분석 등과 같이 비행항법 및 가시화 등의 분야에서 주로 활용되었다 (Meng, 1988; John 등 , 2001; Helgason 등 ,
2001). 센서의 공간해상력 및 분광해상력이 증가됨에 따라
지표상에 나타나는 상세한 특징정보 뿐만 아니라 지표상의
*국방과학연구소선임연구원
,
연세대학교사회환경시스템공학부박사과정(E-mail: [email protected])
**정회원연세대학교사회환경시스템공학부교수
(E-mail: [email protected])
***정회원연세대학교사회환경시스템공학부교수
(E-mail: [email protected])
****국방과학연구소책임연구원
(E-mail: [email protected])
토질 , 수분함량 , 식생 등의 다양한 속성을 분석할 수 있게 될 것이다 . 따라서 지형공간정보의 군사적 활용분야는 지표 속성을 활용하는 침투로 분석 , 낙하지점 분석 , 은거지 분석 ,
시가전 분석 등의 육군전술작전으로 확대될 것이다 ( 유복모 등 , 1994; 함영국 등 , 2000). 본 논문에서는 미국 국가지형 공간정보국 (NGA; National Geospatial-intelligence Agency)
의 표준성과품 중 하나인 지형분석도 (VITD; Vector product Interim Terrain Data) 에 포함된 지형속성과 수치고도모형을 이용하여 최적 침투경로를 자동분석하기 위한 방법을 제시 하고 실험을 통해 활용가능성을 보였다 .
경로계획 (path planning) 은 주로 로봇공학 , 기동경로계획 ,
비행임무계획 등의 분야에서 활발히 연구되고 있다 . Meng
(1988) 은 래스터 방식의 경로분석이 자료의 처리량이 많다는
점과 계산시간이 많이 소모된다는 점을 지적하고 실시간환 경이 아닌 사전경로분석에서 사용할 수 있는 방법임을 지적 하고 , 처리수준을 3 단계로 나누어 최적화가 필요한 경우에는
A* 와 다익스트라 알고리듬을 적용하고 실시간처리를 위하 여 브루노이 다이어그램 (Voronoi diagram) 을 적용하였다 . Helgason 등 (2001) 은 정적인 환경에서 브루노이 다이어그램을
적용하여 최적경로를 분석하였으며 , John 등 (2001) 은 지역 감시정찰를 위하여 임무계획을 최적화하기 위해 직사각형 그 리드를 정의하고 정수 프로그래밍 (integer programming) 방 법과 유전자 (genetic) 알고리듬을 적용하였다 . Niederberger
등 (2004) 은 정적환경에서 다각형 장애물을 표현하고 A* 알
고리듬을 개선하여 보다 직관적인 경로를 찾아내는 고속 / 강 건한 새로운 알고리듬을 제안하였다 . 이 방법은 다각형에 의 한 중간 목표지점을 설정하고 A* 알고리듬과 욕심쟁이 방법
(greedy method) 을 혼합하여 적용하는 방법으로서 , 기존의
A* 알고리듬에 비하여 중간 계산량이 많아지는 것이 단점임 을 밝히고 있다 . 즉 , 래스터방식은 다각형에 비해 계산 고려 대상이 매우 크기 때문에 오히려 수행시간이 오래 크게 늘 어날 가능성이 크다 . 이상과 같이 비행경로나 로봇기동경로 분석은 실시간환경에서의 빠른 응답시간을 위하여 세밀한 지 형의 정보를 유사한 특성을 갖는 다각형으로 군집화
(grouping) 하여 분석하며 처리속도와 정확도를 개선하기 위
한 연구개발이 계속되고 있다 .
반면 , Kwok 등 (1999) 은 굴곡이 심한 지형에서 최적경로를 찾기 위하여 기동 / 기동불가의 2 단계로 구분되는 래스터 확률 지도를 사용하여 동적 프로그래밍 (dynammic programming)
기법을 적용하였으며 , Howard 등 (2002) 은 지형의 특성에 따 라 5 개의 등급으로 래스터방식의 퍼지맵 (fuzzy map) 을 구성 하고 A* 알고리듬을 적용하여 행성탐사기 (Planetary rover)
의 최적경로를 계산하였다 . Marti 등 (1994) 은 고해상도의 지 형정보특성 및 다양한 조건을 모두 적용하기 위하여
ArcGIS 소프트웨어의 연산을 이용하여 래스터방식의 경로계
획 및 평가분석하는 방안을 제시하였으며 , 도로나 지형경사 와 같은 이동특성에 대한 최적경로분석을 수행하였다 . 감시 장비가 배치되어 있는 정적환경에서 개인침투경로 분석 작 업 역시 이와 같은 형태의 문제로서 래스터방식의 확률지도 를 사용하는 것이 적절할 것이다 . 또한 컴퓨터 환경의 계산
능력이 급속히 발전되어가고 있기 때문에 , 대용량의 계산이 필요한 경우도 A* 알고리듬과 같은 경험적 알고리듬을 적용
하여 적절한 시간 내에 분석을 수행할 수 있다 .
본 연구에서는 감시장비로서 열상장비 (TOD; Thermal
Observation Device) 가 배치되어 있는 정적인 환경에서 지 형공간정보에 포함된 장애물이나 위험수준에 대한 고해상도 의 지형특성을 이용하여 래스터형태의 확률지도를 구성하고 최적경로분석기법을 적용하여 탐지확률이 가장 적은 침투경 로를 분석하는 방안을 제시하였다 . 래스터 탐지확률지도를 작성하기 위하여 상용소프트웨어 (ArcGIS Software) 의 기능 을 활용하였으며 , 확률지도를 입력으로 최적경로분석 알고 리듬을 적용한 프로그램을 Visual C++ 언어로 작성하여 실험을 수행하였다 . 최적경로분석을 위하여 대표적으로 사 용되는 A* 알고리듬 (Hart 등 , 1972) 과 동적 프로그래밍 방 법인 다익스트라 알고리듬 (Dijkstra, 1959) 을 적용하여 비교 분석하였다 .
2. 자료 및 처리과정
2.1 문제정의
침투경로 분석은 다양한 상황에서 이루어 질 수 있다 . 본
연구에서는 군사분계선 형태의 대치상황을 가정하여 지형특 성과 상대의 감시망을 고려한 침투경로를 분석하는 것을 목 표로 하였다 . 실험을 위하여 선정된 대전지역에 가상의 군사 분계선을 설정하고 침투경로분석에 대한 문제정의를 그림 1
에 보였다 . 그림 1 의 중간에 위치한 수평선 상단은 출발지 역이며 하단에 위치한 수평선 하단은 도착지역이다 . 탐지확 률 누적함수 F가 최소인 경로인 최적침투경로를 생성하는 것을 목표로 하였다 .
그림 2 는 최적경로분석을 위한 제안된 방법의 처리과정을 보여주고 있다 . 먼저 입력 자료로 군사용 지형분석도인
VITD 와 , 1:5,000 수치지도의 등고선자료를 이용하여 생성된
그림 1. 최적침투경로분석의 문제 개요(가상의 군사분계선; 대전
지역)
수치고도모형을 사용하였다 . 최적경로 결정을 위하여 2 차원 평면공간을 일정크기 (50m × 50m) 의 정사각형 영역으로 분할 하고 , 각 영역에 대한 침투자의 탐지확률값을 갖는 래스터
탐지확률지도를 생성하였다 .
감시장비로서는 열상장비 (Thermal Observation Device)
TAS-970K 모델에 대한 거리별 탐지확률을 ACQUIRE 모델
에 의해 계산된 값을 사용하였다 . ACQUIRE 모델은 미 육 군 야시장비 연구소에서 개발된 야시장비 성능예측 모델로서 최소분해가능온도차 (MRTD; Minimum Resolvable Tempera- ture Difference) 를 이용하여 거리별 , 기상별로 특정 표적의 탐지확률을 계산하는 모델이다 ( 홍석민 등 , 2003). 본 연구에 서는 맑은 날씨를 실험대상으로 하였다 .
2.2 입력자료
VITD 는 NGA 규격서에 의해 규정된 디지털 성과품으로서
군사작전에 활용하기 위한 지형지물의 상세한 속성자료들을 저장하고 있는 표준지형공간정보 디지털 파일형식이다 . 그림
3 에서 보인 것과 같이 장애물 (OBS; Obstacle), 경사도 / 지형
(SLP; Slope/Surface Configuration), 토질 / 토양 (SMC; Soil/
Surface Materials), 배수 (SDR; Surface Drainage), 수송
(TRN; Transportation), 식생 (VEG; Vegetation) 의 6 개의 커
버리지 (coverage) 로 구성되어 있으며 , 각 커버리지는 서로
다른 속성값들을 갖는다 .
OBS 커버리지는 급경사면 , 함몰지 , 화성암 ( 절벽 ) 과 같은 자연장애물과 절단지 , 둔덕 , 제방 및 벽과 같은 인공장애물
에 관련된 지형지물 속성을 포함한다 . SLP 커버리지는 동종
의 지면 경사범위를 표현하는 지형지물을 포함한다 . 경사도 는 % 경사로 표현되며 , 지형지물의 최소크기는 5,000 평방미 터 (50m × 100m) 이다 . SMC 커버리지는 토양분류체계 및 광 맥 , 만년설 및 염전지와 같은 다른 토질에 근거한 토양군을 표현한다 . SDR 커버리지는 강 , 운하 , 수문 , 댐 및 호수와 같은 배수 지형지물과 관련한 속성을 표현한다 . TRN 커버 리지는 도로 , 철도 , 교량 , 터널 및 활주로 등 교통 ( 수송 ) 과
관련된 지형지물 속성을 표현한다 . VEG 커버리지는 군사적
응용과 관련된 토지이용 및 토양분류 방법 내의 여러 가지 식생을 표현한다 .
본 연구에서는 OBS 커버리지와 VEG 커버리지에 포함된
속성정보를 이용하였다 . OBS 커버리지는 이동 불가능 지역 을 선정하는데 사용하였으며 , VEG 커버리지는 나무의 지면 차폐율을 적용하였다 . 이 밖에 TRN, SLP, SMC 는 기동차 량이 포함된 경우의 이동가능 여부를 판단하는데 활용할 수
있으며 , SDR 커버리지는 은둔지 선정과 같은 목적으로 사
용될 수 있다 ( 함영국 등 , 2000).
경계임무를 위한 관측위치는 전방에 시야가 완전히 개방된 위치에 두는 것이 일반적이다 . 상세한 분석을 위해서는 지표
의 표고 및 나무나 구조물 등이 상세히 표현되는 DSM (Digital Surface Model) 을 사용하는 것이 이상적이나 , 현실 적으로 정확한 DSM 을 제작하여 활용하기는 어렵다 . 본 연 구에서는 VITD 의 정밀도 ( 공간해상도 50m × 100m) 를 고려하
그림 2. 최적경로분석 처리흐름도
그림 3. 지형분석도(VITD)의 6가지 커버리지
여 1:5,000 수치지도의 등고선 레이어를 이용하여 50m 간 격의 수치고도모형을 이용하였다 ( 그림 5).
3. 탐지확률지도 생성
탐지확률지도는 그림 2 에서 설명한 바와 같이 은폐확률 ,
이동불가지역 , 가시선분석 및 TOD 장비의 탐지확률을 이용 하여 생성하였다 . 은폐확률은 수목에 의한 지형의 차폐정도 를 이용하여 침투자의 노출정도를 확률로 표시한 것이며 , 이 동불가지역은 대상지역내에 장애물로 인하여 경로생생이 불 가능한 지역을 말한다 . 가시선분석은 TOD 장비가 배치된 지점에 대하여 지형으로 인한 차폐여부를 계산한 결과이며 , TOD 장비의 탐지확률이란 거리에 따른 장비의 탐지확률을 말한다 .
최적경로분석을 위하여 대상지역을 50m × 50m 를 하나의 셀 로 갖는 래스터 확률지도를 작성하였다 . 각 셀은 해당 셀에 침투자가 있을 경우 모든 제반환경을 고려하여 TOD 장비로 탐지될 수 있는 확률값을 갖도록 구성하였다 . 가상적인 실험 을 위하여 대전인근지역의 자료를 이용하였으며 , 모든 자료
는 기준타원체 WGS84, 투영좌표계 UTM 52 zone 으로 변 환하여 사용하였다 . 확률지도 생성은 대표적인 지리정보체계 소프트웨어 패키지인 ArcGIS 9.0 버전을 이용하여 수행되 었다 .
3.1 은폐확률
은폐확률은 VEG 커버리지에 포함된 3 개의 레이어 정 보 , 즉 VEGAREA(vegetation area), VGFAREA(vegi- tation forested area), VGWAREA(vegitation water area)
를 기준으로 설정하였다 . VGFAREA 레이어에 포함된
DMT(Density Measure of % Tree/Canopy Cover) 속성값 을 이용하여 침투자의 노출정도를 확률값으로 설정하였다 .
DMT 속성값은 수목에 의해 지면이 차폐되는 확률을 표현한
것으로 표 1 에 표시된 바와 같이 25%, 50%, 75% 를 경계 로 4 개의 코드로 저장되어 있다 . 실험에서는 각 구간의 중간 값으로 은폐확률을 설정하였다 . VEGAREA 와 VGWAREA 는
지면의 차폐정도에 대한 확률값이 지정되어 있지 않으나 완 전히 개방되어 있다고 보기는 어려우므로 DMT 속성값에 정의된 가장 낮은 구간과 동일한 값을 사용하였다 . 그림 4
에서 어두운 부분은 은폐확률이 낮은 경우를 , 밝은 부분은 은폐확률이 높은 경우를 나타낸다 .
3.2 가시선분석 및 TOD 장비탐지확률
TOD 장비의 위치와 지형을 고려한 탐지확률을 계산하기
위하여 , TOD 장비의 거리별 탐지확률을 계산하고 수치고도
모형으로부터 가시선분석을 수행한 결과와 합성하였다 . 그림
5 는 실험에 사용된 TOD 장비의 배치도를 나타내고 있으며 ,
그림 6 은 TOD 장비의 설치위치로부터 거리에 따른 탐지확
률을 보여준다 . TOD 장비의 배치위치 별로 4 개의 다른 색
상으로 탐지확률을 표현하였으며 , 색의 농도가 짙을수록 탐 지확률이 낮아지도록 도시하였다 . 그림 7 은 각 TOD 장비의 위치별로 가시선분석을 한 결과를 보여주고 있다 . 가시선분 석은 지형차폐를 계산하기 위하여 2.2 절에서 설명한 수치고 도모형을 이용하였으며 , ArcGIS 의 가시선분석 (viewshed) 기능 을 적용하였다 . 그림 7 에서 밝은 부분으로 표시된 영역이
TOD 에서 관측 가능한 지역이며 , 그 외의 영역은 관측이 불
가능한 지역이다 . 그림 6 의 TOD 장비탐지확률과 그림 7 의 가시선분석 결과를 합성하여 지형을 고려한 TOD 장비탐지 확률을 각 위치별로 계산하였다 ( 그림 8).
TOD 장비에 각각에 대한 탐지확률은 중첩되는 지역에 대한 탐지확률을 고려하여 확률의 합공식인 식 (1) 을 적용 하여 4 개의 탐지확률을 하나의 탐지확률로 통합하였다 ( 그 림 9).
(1)
P A B ( ∪ ) = P A ( ) + P B ( ) – P A B ( ∩ ) 그림 4. 은폐확률 계산결과
그림 5. TOD 장비 배치
표 1. 은폐확률 설정
Layer DMT 은폐확률
VEGAREA - 0.125
VGFAREA 0~25% 0.125 VGFAREA 25~50% 0.375 VGFAREA 50~75% 0.625 VGFAREA 75~100% 0.875
VGWAREA - 0.125
여기서 P(A)와 P(B)는 임의의 TOD에 대한 탐지확률을 의 미하며, P(A∩B)는 두 개의 TOD에서 모두 탐지될 확률, P(A∪B)는 두 개의 TOD중 최소 하나의 TOD에서 탐지될 확률을 의미한다. 4개의 탐지확률을 통합하기 위하여 처음 2 개의 TOD에 대한 탐지확률을 통합하고 나머지 2개의 TOD 에 대한 탐지확률을 통합한 다음, 통합된 2개의 탐지확률을 다시통합하여 최종 탐지확률을 계산하였다. 그림 9에 표시된 탐지확률은 최소한 4개의 TOD 중 하나 이상의 TOD에 의 해 침투자가 탐지될 확률을 의미한다.
3.3 탐지확률지도
최종적인 탐지확률지도를 완성하기 위하여 3.1절에서 설명 한 은폐확률 C(x, y)와 3.2절에서 설명한 TOD 장비의 탐지 확률 D(x, y)을 합성하였다. 여기서 x, y는 2차원 지도상의
셀의 위치를 표현한다. TOD 장비의 탐지확률 D(x, y)는 그 대로 탐지확률의 성격을 가지며, 은폐확률 C(x, y)는 탐지확 률에 반비례의 성격을 갖는다. 은폐가 전혀 없을 경우 탐지 확률은 1.0이 되며, 100% 은폐가 되었을 경우 탐지확률이 0이 된다는 점을 고려할 때 최종탐지확률과의 관계는 식 (2) 으로 표현할 수 있다. 따라서 두 개의 확률을 최종적으로 합성하기 위한 수식은 식 (3)과 같이 적용하였다. 최종적으 로 완성된 탐지확률지도는 그림 10에 보였다.
(2) (3)
3.4 이동특성
지형분석도의 OBS 커버리지의 OBSLINE(obstacle line) P x y ( , ) ∝ ( 1 C x y – ( , ) )
P x y ( , ) = D x y ( , ) ( 1 C x y – ( , ) ) 그림 6. TOD장비 거리별 탐지확률
그림 7. TOD 위치별 가시선분석 결과
그림 8. 가시선분석결과와 TOD 탐지확률 합성
그림 9. TOD 장비의 탐지확률
레이어의 F_CODE(feature code) 와 OBSAREA(obstacle
area) 레이어를 이용하여 이동 가능지역과 불가능지역을 설
정하였다 . 표 2 는 레이어와 F_CODE 에 따른 이동가능 / 불가 능 설정값을 보여주고 있으며 , 그림 11 은 장애물에 의한 이 동 불가능 지역을 도시한 것이다 . 이동특성지도는 경로에 포 함되지 않게 하기 위해 사용되며 , 확률지도와는 독립적으로 사용된다 .
VITD 규격에서 장애물은 용치 (Dragon Teeth), 함몰지
(Depression), 지리정보표시점 (Geographic Information Point),
벽 (Wall), 파이프 (Pipeline/Pipe), 위치분류 (Location Category),
해자 (Moat), 절벽 / 단애 / 급경사면 (Bluff/Cliff/Escarpment), 절단 지 (Cut), 제방 (Embankment), 화성암 (Volcanic Dike), 산울타 리 (Hedgerow), 경사로 (Ramp) 로 분류되어 있으며 , 본 논문에
서는 대상지역에 포함된 장애물에 대해서만 이동특성을 정 의하였다 .
4. 최적경로분석
최적경로의 분석을 위한 탐색방법은 다양한 방법을 선택할 수 있다 . 현재의 문제영역에서 래스터구조는 2 차원으로 구성 된 각 셀이 이웃한 셀과 8 방향으로 연결된 그래프라고 가정 할 수 있다 . 현재 노드의 수는 500 × 500 = 250,000 개로 구성 되며 대상지역이 확대되거나 셀의 공간해상도가 정밀해질 경 우 노드와 연결의 수는 매우 급격히 커지게 된다 . 따라서 깊이우선탐색 (depth first search) 나 폭우선탐색 (breadth first
search) 와 같은 단순한 알고리듬으로는 시간비용이 크게 증
가하게 되며 , 욕심쟁이 기법 (greedy method) 와 같은 방법은 최적해나 근사최적해를 찾기에 부적절한 방법이다 (Horowitz
등 , 1978). 따라서 경로탐색에서 최적해를 찾기 위하여 가장
널리 사용되고 있는 다익스트라 (Dijkstra, 1959) 알고리듬과 근사최적해를 찾아내며 계산효율이 높은 A* 알고리듬 (Hart
등 , 1972) 을 적용하여 실험하고 그 결과와 수행시간을 비교
분석하였다 .
A* 알고리듬은 비용함수 f = g + h로 정의한다 . 여기서 g는 지나온 경로에 대한 비용을 의미하며 , h는 현재의 노드에서 최종목적지까지 경로에 대한 경험적 추정비용을 말한다 . 실 제 인 경우는 다익스트라 알고리듬과 동일하다 . Russell 등
(1995) 은 A* 알고리듬이 경험적 추정함수가 과대평가 되지
않을 경우에 효과를 보임을 말하였다 . 그러므로 A* 알고리 듬의 시간복잡도 , 완전성 , 최적성 등에 대한 평가는 경험적
추정함수가 적절히 정의되었는가에 달려있다 . 본 연구에서는 비용함수 g를 식 (4) 과 같이 이미 지나온 노드들의 누적탐 지확률로 정의 하였으며 , 추정비용함수 h를 식 (5) 과 같이 현재 노드에서 최단거리와 셀의 기준탐지확률
μdetect과의 곱 으로 표현하였다 .
μdetect의 값이 작아질수록 최적해에 접근하 게 될 것이다 .
(4)
여기서 A 는 이미 지나온 노드들의 집합을 의미한다 . (5)
여기서 Y
goal은 그림 1 의 하단에 목표지점에 대한 y좌표를 의미하며 , 따라서 | y − Y
goal| 은 목표지역까지 남은 최단거리를 의미한다 . 실제 목표지점이 복잡한 구조를 가질 경우 거리를
계산하는 수식으로 대체되어야 할 것이다 .
5. 실험 및 결과분석시작지점에 대해서 일정간격으로 7 개의 지점에 대한 최적 경로를 탐색하였다 . 그림 12 는 다익스트라 알고리듬을 이용 하여 처리한 결과이며 , 그림 13 은
μdetect=0.01 일 경우의 A*
알고리듬의 결과를 보여준다 . 표 3 에서 나타난 바와 같이 1
번에서 출발한 침투경로가 4.60, 4.63 으로 두 알고리듬에서 g P x y ( , )
x y, (
∑
) A∈=
h y Y = –
goal× μ
detect그림 10. 완성된 탐지확률지도
표 2. 이동특성 설정
Layer F_CODE 설명 이동특성
OBSLINE AL260 벽 (Wall) 이동불가
OBSLINE DB010 절벽 / 단애 / 급경사면
(Bluff/Cliff/Escarpment) 이동불가
OBSLINE DB070 절단지 (Cut) 이동가능
OBSLINE DB090 제방 (Embankment) 이동가능
OBSAREA DB080 함몰지 (Depression) 이동불가
그림 11. 이동 불가능 지역
모두 가장 낮은 누적탐지확률을 보였다. A* 알고리듬과 다 익스트라 알고리듬에서 거의 동일한 결과를 얻었다.
μdetect
의 값을 변화시켰을 경우 A* 알고리듬의 결과를 그 림 14에서 보였다.
μdetect값이 커질수록 목표지점에 대한 방 향성이 강해지는 것을 알 수 있다. 즉, 남은 거리가 전체비 용함수 추정에 미치는 영향이 커지면서 경로는 남쪽방향으 로 진행하려는 성향을 보이며, 누적탐지확률이 커짐을 알 수
있다. 누적탐지확률이 커진다는 것은 최적경로에 비해 비용 이 커진다는 의미가 된다.
표 4는 두 알고리듬으로 수행된 결과를 수행시간과 최적 경로의 누적탐지확률을 비교한 것이다. A* 알고리듬이 다익 스트라 알고리듬에 비해서 수행시간이 감소됨을 알 수 있 다. 즉, 대상지역이 소규모이고 자료의 처리양이 적을 경우 에는 다익스트라 알고리듬을 사용하는 것이 적절하지만, 대 상지역이 크게 확대되고 공간해상도를 증가하여 정밀 분석 을 할 경우 수행시간을 고려하여 A* 알고리듬을 사용하는 것이 대안이 될 수 있음을 보여준다.
6. 결 론
전술 군사작전에서 침투경로분석은 공격적인 입장에서는 지상침투분석을 위해 활용이 가능하며, 방어적인 입장에서는 감시체계장비와 경계병의 감시위치를 결정하는데 활용할 수 있다. 본 연구를 통하여 지형공간정보를 이용하여 래스터방 식의 확률지도를 작성하고 이를 침투로 분석에 활용하는 방
표 3. 침투경로의 누적탐지확률
경로번호 다익스트라 A*
1 4.60 4.63
2 4.69 4.71
3 5.62 5.64
4 6.23 6.25
5 7.16 7.18
6 7.75 7.76
7 7.45 7.47
그림 12. 다익스트라 알고리듬 적용결과
그림 13. A* 알고리듬(=0.01) 적용결과
그림 14. 값에 따른 최적경로탐색 결과
표 4. 수행시간 및 최적경로의 누적탐지확률 비교
μ
detect소요시간 (단위:초) 누적탐지확률
A* (0.01) 8.27 4.63
A* (0.02) 3.17 5.06
A* (0.03) 1.77 5.91
A* (0.10) 1.22 6.76
Dijkstra 15.87 4.60
법을 제시하였으며, 실험을 통해 그 활용 가능성을 보였다.
또한 다익스트라 알고리듬과 A* 알고리듬을 적용하여 컴퓨 터를 이용한 침투로 분석이 효율적으로 이루어짐을 보였다.
보다 정확한 침투로 분석을 위하여 확률지도 작성을 위한 이론적 근거를 강화하는 연구가 필요하며, 현재의 침투로 분 석 모델을 동적인 시뮬레이션 기법을 적용하여 움직이는 경 계병 등과 같은 요인을 추가함으로서 실제 전장환경에 근접 한 침투분석기법으로 발전시켜야 할 것이다. 또한 실제상황 과의 부합성을 판단할 수 있는 정확도 검증방안 개발 또는 전문가에 의한 침투경로분석과 결과비교 등과 같은 연구가 수행되어야 할 것이다.
참고문헌
유복모 , 서정헌 , 조홍석 (1994) 군의 전술적 자료기반 구축에 관 한 연구 , 한국지형공간정보학회논문집 , 한국지형공간정보학회 ,
제 2 권 , 제 1 호 , pp. 107-119.
함영국 , 김영환 , 주진천 (2000) 특수전 전장정보분석 연구 , 연구보
고서 , KTRC-409-000221L, 국방과학연구소
홍석민 , 김창우 , 유위경 , 최세철 , 이주형 (2003) 열상장비 성능분석
결과 , 시험평가보고서 , TEDC-317-030544, 국방과학연구소
Dijkstra, E.W. (1959) A note on two problems in connection with graphs.
Numeriche Mathematik, Vol. 1, pp. 269-271.
Hart, P.E., Nilsson N.J. and Raphael, B. (1972) A formal basis for the heuristic determination of minimum cost paths.
SIGART Newslett, Vol. 37, pp. 28-9.
Helgason, R.V., Kennington, J.L. and Lewis, K.R. (2001) Cruise Missile Mission Planning: A Heuristic Algorithm for Auto- matic Path Planning,
Journal of Heuristics,Kluwer Academic
Publishers, Vol. 7, No. 5, pp. 473-494.
Horowitz, E. and Sahni, S. (1978)
Fundamentals of Computer Algorithms, Computer Science Press, Maryland, USA.
Howard, A., Seraji, H. and Werger, B. (2002) Fuzzy terrain-based path planning for planetary rovers,
Fuzzy Systems, 2002, FUZZ-IEEE'20, Proceedings of the 2002 IEEE International Conference on,IEEE, Vol. 1, pp. 316-320.
John, M., Panton, D. and White , K. (2001) Mission Planning for Regional Surveillance,
Annals of operations research, Baltzer, Vol. 108, No. 1/4, pp. 157-173.
Kwok, K.S. and Driessen, B.J. (1999) Path planning for complex terrain navigation via dynamic programming,
American Con- trol Conference, 1999, Proceedings of the 1999,IEEE, Vol. 4, pp. 2941-2944.
Marti, J. and Bunn, C. (1994) Automated Path Planning for Simu- lation,
AI, Simulation, and Planning in High Autonomy Sys- tems, 1994, Distributed Interactive Simulation Environments., Proceedings of the Fifth Annual Conference on,IEEE Com- put. Soc. Press, pp. 122-128.
Meng, A.C.C. (1988) AMPES: adaptive mission planning expert system for air mission tasks,
Aerospace and Electronics Con- ference 1988 NAECON, Proceedings of the IEEE 1988 National,IEEE, pp.1225-1231.
Niederberger, C., Radovic, D. and Gross, M. (2004) Generic path planning for real-time applications,
Computer Graphics Inter- national 2004 Proceedings,IEEE, pp. 299-306.
Russell , S . and Norvig , P. (1995)
Artificial intelligence: a modern approach. New Jersey: Prentice-Hall.
http://www.nga.mil/StaticFiles/OCR/nga_history.pdf
