[논문]구역분할 알고리즘을 이용한 다수 탐색플랫폼의 구역할당 방법

안우선; 조윤철; 이찬선

doi:10.9766/kimst.2018.21.2.225

구역분할 알고리즘을 이용한 다수 탐색플랫폼의 구역할당 방법
A Methodology for Partitioning a Search Area to Allocate Multiple Platforms 원문보기

韓國軍事科學技術學會誌 = Journal of the KIMST, v.21 no.2, 2018년, pp.225 - 234

안우선 (해군 전력분석시험평가단) , 조윤철 (해군 전력분석시험평가단) , 이찬선 (국방과학연구소 분석평가실)

Abstract ▼ AI-Helper

In this paper, we consider a problem of partitioning a search area into smaller rectangular regions, so that multiple platforms can conduct search operations independently without requiring unnecessary coordination among themselves. The search area consists of cells where each cell has some prior information regarding the probability of target existence. The detection probability in particular cell is evaluated by multiplying the observation probability of the platform and the target existence probability in that cell. The total detection probability within the search area is defined as the cumulative detection probability for each cell. However, since this search area partitioning problem is NP-Hard, we decompose the problem into three sequential phases to solve this computationally intractable problem. Additionally, we discuss a special case of this problem, which can provide an optimal analytic solution. We also examine the performance of the proposed approach by comparing our results with the optimal analytic solution.

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

본 논문에서 탐색구역을 직사각형 모양으로 제한하고, 각각의 구역이 중첩되지 않도록 전체 탐색구역을 분할한 후, 각각의 플랫폼을 분할된 구역에 할당하는 문제를 논의하였으며, 이러한 NP-hard 문제를 해결하기 위해, 탐색구역 생성, 조정, 배치와 같은 3단계의 절차를 갖는 알고리즘을 제안하였다. 또한, 탐색구역할당 문제의 제약식을 완화하여 해석적 해를 유도하였으며, 그 해와 비교를 통해 본 논문에서 제안한 구역분할 알고리즘의 성능을 분석하였다.
본 논문은 An^[6]이 연구한 구역할당 문제에 전체 탐색구역을 구성하는 모든 셀이 직사각형으로 분할된 탐색구역에 포함되어야 한다는 제약식을 추가한 확장된 문제를 다룬다. 직사각형 분할은, NP-Hard 문제로, 탐색구역을 구성하는 셀과 플랫폼의 수가 증가함에 따라 최적해를 구하는 것은 매우 어려운 것으로 알려져 있으며^[7], 이러한 문제를 해결하기 위해, 본 논문에서는 탐색구역 생성, 탐색구역 조정, 탐색구역 배치의 3단계 절차로 구성되는 휴리스틱 알고리즘을 제안한다.
이 연구한 구역할당 문제에 전체 탐색구역을 구성하는 모든 셀이 직사각형으로 분할된 탐색구역에 포함되어야 한다는 제약식을 추가한 확장된 문제를 다룬다. 직사각형 분할은, NP-Hard 문제로, 탐색구역을 구성하는 셀과 플랫폼의 수가 증가함에 따라 최적해를 구하는 것은 매우 어려운 것으로 알려져 있으며^[7], 이러한 문제를 해결하기 위해, 본 논문에서는 탐색구역 생성, 탐색구역 조정, 탐색구역 배치의 3단계 절차로 구성되는 휴리스틱 알고리즘을 제안한다. 또한 구역할당 문제를 완화한 후, Lagrange 방법을 이용하여 해석적 해를 손쉽게 얻을 수 있는 특수한 경우를 설명한다.

가설 설정

단일 셀의 넓이가 b = 1이고, 탐지표적 존재 확률이 균일한 40×40 탐색구역에서, 동일한 탐지 성능(ws = 5,vs = 20, τs = 5)을 가진 2개 플랫폼이 배치되는 경우를 가정하자.
각 구역의 좌, 우, 하, 상 좌표를 Rq = [R_q1, R_q2, R_q3,R_q4]으로 정의하고, 유사하게 미할당구역(⑧구역) 범위의 좌표를 X8 = [X₈₁, X₈₂, X₈₃, X₈₄]으로 정의하자. 미할당구역을 포함하여 확장하는 구역은 미할당구역에 인접한 4개의 구역(①,⑤,⑥,⑦)중 임의로 하나의 구역이 선택되며, 본 예에서는 ①구역이 확장구역으로 선택되었다고 가정하자. ①구역이 ⑧구역을 포함하기 위해서 는 ①구역의 하측 범위의 좌표 R13이 ⑧구역의 하측 범위의 좌표 X₈₃까지 확장되어야 한다.
이 절에서는 다수의 플랫폼을 이용하여 단일 탐지 표적을 탐색하는 경우 전체 탐색구역을 직사각형으로 분할하여 각 플랫폼에 할당하는 구역할당 문제를 소개한다. 전체 탐색구역은 탐지표적이 존재할 확률을 내재한 셀들로 구성되며, 구역분할 시 탐지표적은 이웃한 셀로 이동하지 않는 것으로 가정한다.
은 플랫폼의 최적의 탐색경로를 찾는 문제를 연구하였다. 탐색구역은 단일 탐지표적이 존재할 확률을 포함하는 셀들로 구성되며, 탐색자와 탐지표적은 현재 위치하고 있는 셀에서 이웃한 셀들로만 이동이 가능한 것으로 가정하고, Branch and Bound 알고리즘을 통해 최적 탐색경로를 찾았다. 그러나 셀의 수가 증가함에 따라, 계산 복잡도는 지수함수적으로 증가하기 때문에, 최적의 해를 얻는 것이 매우 어려운 단점이 있다.

제안 방법

그러나 식 (2)는 NP-Hard 문제로, 전체 탐색 구역을 구성하는 셀과 플랫폼의 수가 증가하면 탐색 구역을 분할하여 플랫폼을 배치할 수 있는 경우가 지수 함수적으로 증가하기 때문에, 최적의 해(A_s^☆, ∀_s∈S)를 구하는 것은 매우 어려운 일이다. 따라서, 본 논문에서는 An^[6]이 제안한 방법을 확장하여, 다수의 플랫폼을 분할된 탐색구역에 할당하는 휴리스틱 알고리즘을 제안한다.
본 논문에서 탐색구역을 직사각형 모양으로 제한하고, 각각의 구역이 중첩되지 않도록 전체 탐색구역을 분할한 후, 각각의 플랫폼을 분할된 구역에 할당하는 문제를 논의하였으며, 이러한 NP-hard 문제를 해결하기 위해, 탐색구역 생성, 조정, 배치와 같은 3단계의 절차를 갖는 알고리즘을 제안하였다. 또한, 탐색구역할당 문제의 제약식을 완화하여 해석적 해를 유도하였으며, 그 해와 비교를 통해 본 논문에서 제안한 구역분할 알고리즘의 성능을 분석하였다. 향후 본 논문에서 제안한 구역분할 알고리즘의 성능 향상을 위해 임의적인 방법이 아닌, 이전에 생성된 분할 탐색구역 또는 탐지표적이 존재할 확률 정보를 활용하여 효율적으로 구역을 생성하고, 조정하는 방법을 연구할 계획이다.
본 논문에서 다루는 탐색구역 할당문제는 최적의 분할구역(As☆,∀s∈S)을 찾는 비선형 정수계획법 문제로 식(2)와 같이 모델링 한다.
본 논문에서 제안하는 구역할당 알고리즘은 탐색구역 생성, 탐색구역 조정, 탐색구역 배치 단계로 구성되는 휴리스틱 방법이다. 탐색구역 생성 및 조정 단계에서 식 (2)의 제약식을 만족하도록 전체 탐색구역을 플랫폼의 수만큼 임의로 분할하여, 탐색구역(A_q, q∈Q)을 생성한다.
본 논문에서는 다수의 플랫폼을 이용하여 탐색작전을 수행하는 경우에, 전체 탐색구역을 직사각형 모양으로 분할한 후 각 플랫폼에 할당하는 문제를 다루며, 구성은 다음과 같다. 1장의 서론에 이어, 2장에서 기존 문헌을 고찰한다.
이 절에서는 다수의 플랫폼을 이용하여 단일 탐지 표적을 탐색하는 경우 전체 탐색구역을 직사각형으로 분할하여 각 플랫폼에 할당하는 구역할당 문제를 소개한다. 전체 탐색구역은 탐지표적이 존재할 확률을 내재한 셀들로 구성되며, 구역분할 시 탐지표적은 이웃한 셀로 이동하지 않는 것으로 가정한다.
초기 설정이 완료된 후, 처음 선택된 셀들로부터 임의의 셀을 선택하고, 연속적으로 확장 가능한 셀로부터 임의의 셀을 선택한다. Fig.

데이터처리

이와 같이 식 (2)의 제약식을 완화한 후,Lagrange 방법을 이용하여 유도된 해석적 해는 탐색구역할당 문제의 upper-bound를 제공한다. 다음 절에서 시뮬레이션을 통하여 제안한 알고리즘의 모의 결과와 upper-bound와의 비교를 통해 알고리즘의 성능을 검토한다.

이론/모형

식 (1)에서 플랫폼의 탐지능력은 플랫폼의 탐색폭(ws), 탐색속력(vs), 탐색시간(τs)에 비례하고, 탐색구역의 크기에 반비례하는 함수인 Koopman[8] 공식을 적용한다.

후속연구

향후 본 논문에서 제안한 구역분할 알고리즘의 성능 향상을 위해 임의적인 방법이 아닌, 이전에 생성된 분할 탐색구역 또는 탐지표적이 존재할 확률 정보를 활용하여 효율적으로 구역을 생성하고, 조정하는 방법을 연구할 계획이다. 또한 탐색임무에 대한 교대가 필요한 경우로 문제를 확장하여 플랫폼의 배치, 운용, 복귀와 관련된 해법을 연구할 계획이다.
또한, 탐색구역할당 문제의 제약식을 완화하여 해석적 해를 유도하였으며, 그 해와 비교를 통해 본 논문에서 제안한 구역분할 알고리즘의 성능을 분석하였다. 향후 본 논문에서 제안한 구역분할 알고리즘의 성능 향상을 위해 임의적인 방법이 아닌, 이전에 생성된 분할 탐색구역 또는 탐지표적이 존재할 확률 정보를 활용하여 효율적으로 구역을 생성하고, 조정하는 방법을 연구할 계획이다. 또한 탐색임무에 대한 교대가 필요한 경우로 문제를 확장하여 플랫폼의 배치, 운용, 복귀와 관련된 해법을 연구할 계획이다.

질의응답

핵심어	질문	논문에서 추출한 답변
	잠수함은 어떤 기능을 하는가?	잠수함은 수중에서 은밀하게 공격대상 표적에 접근한 후 공격하여 손상을 줄 수 있는 함정으로 정보수집, 기뢰부설, 특수부대 침투 등 다양한 작전을 수행하는데 용이하며, 필요시 기습공격을 통해 고가치 수상 또는 육상표적에 막대한 피해를 줄 수 있는 비대칭 핵심전력이다. 현재 북한은 우리군에 비해 절대 우위의 잠수함 전력을 유지하고 있으며, SLBM 탑재 잠수함 건조 및 구형 잠수함의 개조를 통해 잠항시간을 늘리고 자체소음을 감소하는 등 전력 최신화를 꾸준히 추진하고 있다.
	탐색구역 생성 단계는 어떤 단계인가?	탐색구역 생성 단계는 M×N개의 셀들로 구성된 전체 탐색구역에서 플랫폼의 수만큼 임의의 단일 셀들을 선택한 후, 직사각형 모양을 유지하고, 확장하면서 임의의 구역을 생성하는 단계이다. Fig.
	현재 우리나라의 대잠작전이 제한적인 것을 고려할 때, 효과적인 작전수행을 위하여 어떤 요소를 고려해야하는가?	대잠정보를 지속적으로 수집하고 전파해야 하며, 이를 바탕으로 대잠전력의 효율적 배치를 통해 최단 시간에 위협을 탐지하고, 격멸하는 일련의 절차를 통합하고 체계화하는 것 또한 매우 중요하다. 그러나 다수의 플랫폼이 일정한 구역에서 동시에 대잠작전을 수행해야 하는 경우, 탐지장비의 간섭을 피하기 위해지속적으로 플랫폼의 위치를 조정하는 것은 작전 효율성을 저하시키는 요인이 되므로, 각 플랫폼의 기동능력, 탐지성능을 고려하여 사전에 구역을 할당한 후작전을 수행해야 할 것이다.

참고문헌 (9)

J. Eagle, "The Optimal Search for a Moving Target When the Search Path is Constrained," Operations Research, Vol. 32, pp. 1107-1115, 1984.

상세보기
G. H. Martins, "A New Branch-and-Bound Procedure for Computing Optimal Search Paths", Master's Thesis, Naval Postgraduate School, 1993.
H. Lau, "Optimal Search in Structured Environments," PhD Thesis, University of Technology, Sydney, 2007.
A. G. Santos, "Using Multiple Searchers to Locate a Randomly Moving Target," Master's Thesis, Naval Postgraduate School, 1993.
W. An, M. Mishra, C. Park, and K. R. Pattipati, "An Integrated Asset Allocation and Path Planning Method to Search for Targets in a Dynamic Environment," 15th International Command and Control Research and Technology Symposium, Santa Monica, CA, June 2010.
W. An, D. F. Martinez Ayala, D. Sidoti, M. Mishra, X. Han, K. R. Pattipati, E. D. Regnier, D. L. Kleinman and J. A. Hansen, "Dynamic Asset Allocation Approaches for Counter-Piracy Operations," 15th International Conference on Information Fusion, Singapore, July 2012.
S. Muthukrishnan, V. Poosala, and T. Suel, "On Rectangular Partitionings in Two Dimensions: Algorithms, Complexity and Applications," International Conference on Database Theory, Springer Berlin Heidelberg, 1999.
B. O. Koopman, "Search and Screening: General Principles with Historical Applications," Pergamon Press, New York, 1980.
W. L. Winston, "Operations Research," Fourth Edition, Brooks/Cole.

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증