잠수함은 수중에서 임무를 수행하며, 은밀성을 강점으로 하는 매우 위협적인 무기 체계이다. 하지만 잠수함 센서에 의해 탐지되거나 수면 위로 부상하여 노출될 경우 적으로부터 공격을 받을 수 있는 위협에 직면하게 된다. 본 연구는 적 수상함정의 탐색활동과 잠수함의 잠항능력을 고려하여 생존율을 극대화하는 최적의 이동경로를 계획하였다. 잠수함의 생존율을 극대화하기 위한 이동경로 계획 수리모형을 구축하고, ILOG CPLEX를 이용하여 수리모형을 검증하였다. 잠수함의 생존율을 보장하고, 목표지점으로 이동하기 위한 휴리스틱 알고리즘을 이용하여 이동경로, 이동 단위시간(거리), 생존율, 계산시간을 도출하였다.
잠수함은 수중에서 임무를 수행하며, 은밀성을 강점으로 하는 매우 위협적인 무기 체계이다. 하지만 잠수함 센서에 의해 탐지되거나 수면 위로 부상하여 노출될 경우 적으로부터 공격을 받을 수 있는 위협에 직면하게 된다. 본 연구는 적 수상함정의 탐색활동과 잠수함의 잠항능력을 고려하여 생존율을 극대화하는 최적의 이동경로를 계획하였다. 잠수함의 생존율을 극대화하기 위한 이동경로 계획 수리모형을 구축하고, ILOG CPLEX를 이용하여 수리모형을 검증하였다. 잠수함의 생존율을 보장하고, 목표지점으로 이동하기 위한 휴리스틱 알고리즘을 이용하여 이동경로, 이동 단위시간(거리), 생존율, 계산시간을 도출하였다.
The submarine is very threatening and secretive weapon system that achieves missions under the sea. However, the submarine is faced with danger that can be attacked from the enemy when is detected by sensor or rose to the surface. This study will be planned optimal path to maximize the survival rate...
The submarine is very threatening and secretive weapon system that achieves missions under the sea. However, the submarine is faced with danger that can be attacked from the enemy when is detected by sensor or rose to the surface. This study will be planned optimal path to maximize the survival rate that considers submarine navigation capability in underwater and search activity of hostile warships. A mathematical programming model and a heuristic algorithm will be suggested in this study. The mathematical programming model is verified by using ILOG CPLEX. The submarine path, unit time(distance) of navigation, survival rate, and computation time is computed by using a heuristic algorithm.
The submarine is very threatening and secretive weapon system that achieves missions under the sea. However, the submarine is faced with danger that can be attacked from the enemy when is detected by sensor or rose to the surface. This study will be planned optimal path to maximize the survival rate that considers submarine navigation capability in underwater and search activity of hostile warships. A mathematical programming model and a heuristic algorithm will be suggested in this study. The mathematical programming model is verified by using ILOG CPLEX. The submarine path, unit time(distance) of navigation, survival rate, and computation time is computed by using a heuristic algorithm.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
본 연구에서는 과 같은 4각형 형태의 셀로 이루어진 활동 공간에서 목표지점으로 이동하는 잠수함의 생존율을 극대화하는 최적의 이동 경로를 구성하고자 한다.
본 연구에서는 수상함에 의해 탐색활동이 이루어지고 있는 해역에서 임무를 수행하기 위하여 목표지점이나 표적에 접근하는 잠수함의 잠항능력을 고려하고, 생존율을 극대화하는 최적의 이동 경로를 계획하였다. 잠수함의 이동경로를 구성하기 위한 수리모형을 구축하고, ILOG CPLEX를 이용하여 수리모형을 검증하였으며, 휴리스틱 알고리즘을 이용하여 해를 도출하였다.
본 연구에서 다루고자 하는 문제는 여러 척의 수상함이 각각 할당된 해역에서 음파탐지기 (Sonar)를 이용하여 잠수함을 탐색하고, 잠수함은 임무 수행을 위해 모항을 출발한 후 생존율을 극대화하는 목표지점으로의 최적 이동경로를 구성하는 문제이다. 잠수함은 수상함의 음파탐지기에 탐지되지 않기 위해 수상함을 회피하여 잠항하며, 부상으로 인한 노출을 방지하기 위하여 잠항능력을 고려하였다.
본 연구에서는 음파탐지기의 성능이 다른 3종류의 수상함(A형, B형, C형)이 각각 할당된 해역에서 음파탐지기를 이용하여 잠수함을 탐색하고, 잠수함이 임무를 수행하기 위하여 목표지점으로 이동하는 예제에 대하여 실험하였다. 활동 공간은 100개(10x10), 200개(20x10), 225개(15x15), 400 개(20x20)로 구성된 4각형 형태의 셀을 이용하였으며, 육지나 섬, 저수심, 항해 장애물 등과 같이 잠수함의 잠항이 불가능한 지형에서의 생존율은 0을 반영하였고, 잠수함과 수상함은 단위시간당 셀 1칸 이동하는 것을 적용하였다.
본 연구는 여러 척의 수상함이 음파탐지기를 이용하여 탐색활동을 수행하는 해역에서 목표지점으로 이동하는 잠수함의 잠항 능력을 고려하고 생존율을 극대화하는 최적의 이동경로를 계획하였다. 잠수함의 생존율을 극대화하기 위한 이동 경로 계획 수리모형을 구축하고, ILOG CPLEX를이용하여 수리모형을 검증하였다.
가설 설정
둘째, 잠수함의 심도는 고려하지 않는다.
제안 방법
잠수함의 생존율을 극대화하기 위한 이동 경로 계획 수리모형을 구축하고, ILOG CPLEX를이용하여 수리모형을 검증하였다. 잠수함의 생존율을 보장하고, 목표지점으로 이동하기 위한 휴리스틱 알고리즘을 이용하여 이동경로, 이동 단위시간(거리), 생존율, 계산시간을 도출하였다.
잠수함의 생존율을 극대화하기 위한 이동 경로 계획 수리모형을 구축하고, ILOG CPLEX를이용하여 수리모형을 검증하였다. 잠수함의 생존율을 보장하고, 목표지점으로 이동하기 위한 휴리스틱 알고리즘을 이용하여 이동경로, 이동 단위시간(거리), 생존율, 계산시간을 도출하였다. 본 연구에서 제안한 휴리스틱 알고리즘은 수상함의 탐색 패턴을 고려하여 제자리 또는 한 지점 주변에서 잠항함으로써 생존율을 극대화하는 경로를 도출하였으며, 탐색속도가 빠른 것으로 나타났다.
문제이다. 잠수함은 수상함의 음파탐지기에 탐지되지 않기 위해 수상함을 회피하여 잠항하며, 부상으로 인한 노출을 방지하기 위하여 잠항능력을 고려하였다.
이를 활동 공간으로 정의한다. 모형화를 위하여 활동 공간을 분할하여 사용하였으며, 분할된 공간을, 셀(Cell), 이라 하고, 셀 사이의 이동을 이 동경로로 정의한다. 셀의 넓이가 작을수록 현실과 유사하게 구현할 수 있으나 셀의 개수가 증가하게 되므로 문제의 복잡도-가 커진다[5].
구성하고자 한다. 각 셀에서의 잠수함 생존율은 수상함에 탐지되지 않을 확률을 적용하였으며, 잠수함의 출발지점과 목표지점은 알려져 있는 것으로 모형을 구축하였다. 모형 구축을 위한 가정 사항은 다음과 같다.
여러 척의 수상함이 음파탐지기를 이용하여 잠수함을 탐색하는 해역에서 목표지점으로 이동하는 잠수함의 잠항 능력을 고려하고, 생존율을 극대화하는 최적의 이동경로를 구성하기 위한 휴리스틱 알고리즘을 구축하였다. 본 연구에서 제시한 휴리스틱 알고리즘은 잠수함의 이동이 가능하고, 서로 인접하여 연결된 셀에 대한 적합도(Fitness) 를 평가한 후 이를 바탕으로 적합도가 극대화되도록 이동경로를 구성하는 알고리즘이다.
적합도 평가 함수는 다음 단위시간에 이동 가능한 인접 셀에서 목표지점까지의 최소 이동 소요단위시간(彼马)에 가중치(a)를 곱하고, 현재 위치에서 다음 단위시간에 이동 가능한 인접 셀의 생존율(易)을 합하여 산출하였다. 가중치(a)는 가로 셀 크기와 세로 셀 크기의 합에 1/2을 곱하여 적용하였다.
본 연구에서 제안한 수리모형의 타당성과 휴리스틱 알고리즘의 유효성을 검증하기 위해 예제 1 을 축소시켜 실험하였으며, 축소실험 예제의 데이터는 다음 과 같다.
Step 1. 현재 셀에서 잠수함의 이동이 가능하고, 서로 인접한 셀에 대한 이동가능경로를 선정한다.
Step 2. 선정된 이동가능 경로에 대한 적합도를 평가한다.
예제에 대하여 실험하였다. 활동 공간은 100개(10x10), 200개(20x10), 225개(15x15), 400 개(20x20)로 구성된 4각형 형태의 셀을 이용하였으며, 육지나 섬, 저수심, 항해 장애물 등과 같이 잠수함의 잠항이 불가능한 지형에서의 생존율은 0을 반영하였고, 잠수함과 수상함은 단위시간당 셀 1칸 이동하는 것을 적용하였다.
2]. 본 연구에서는 수상함이 보유한 음파탐지기의 음탐접촉 예상거리를 함형별 음파탐지기 성능에 따라 A형 셀 1칸(Ml), B형 셀 9칸 (3×3), C형 셀 25칸(5x5)으로 적용하였으며, 탐지확률은 음탐접촉 예상거리까지의 셀에 50%를 적용하였다. 음탐접촉 예상거리 밖의 셀은 정규분포 종형 그래프를 이용하였으며, 확률 값 1에서 셀 1 칸 간격에 해당하는 표준정규분포 누적확률의 중간 값을 뺀 확률 값을 적용하였다.
본 연구에서는 수상함이 보유한 음파탐지기의 음탐접촉 예상거리를 함형별 음파탐지기 성능에 따라 A형 셀 1칸(Ml), B형 셀 9칸 (3×3), C형 셀 25칸(5x5)으로 적용하였으며, 탐지확률은 음탐접촉 예상거리까지의 셀에 50%를 적용하였다. 음탐접촉 예상거리 밖의 셀은 정규분포 종형 그래프를 이용하였으며, 확률 값 1에서 셀 1 칸 간격에 해당하는 표준정규분포 누적확률의 중간 값을 뺀 확률 값을 적용하였다. 수상함 음파탐지기의 탐지거리별 탐지확률은 다음 <그림 3>과같다.
축소실험 예제에 CPLEX와 휴리스틱 알고리즘을 이용하여 잠수함의 이동경로와 이동 단위시간, 생존율 및 계산시간을 산출한 후 비교하였으며, 축소실험 결과는 다음 와 같다.
225(15x15)개의 활동 공간, 수상함 6척이 탐색하는 예제 3에서 잠수함은 수상함의 탐색 패턴을 고려하여 11 단위시간동안 제자리 또는 한 지점 주변에서 잠항하였고, 수상함의 탐지거리 내에서 2회(1, 2단위시간) 잠항하였으며, 잠수함의 총 이동 단위시간은 34, 생존율 0.7이을 도출하였다.
셀의 형태는 활동공간을 분할하는 방법에 따라 결정되는데 본연구에서는 4각형 형태의 셀을 사용하였으며, 이는 제자리를 포함한 인접 셀(5방향)로의 이동이 가능한 모형으로 다음 과 같다.
대상 데이터
Step 6. 목표지점에 도착한 후보경로 중에서 가장 생존율이 높고, 단위시간이 짧은 후보경로를 최종 이동경로로 선정한다.
이론/모형
계획하였다. 잠수함의 이동경로를 구성하기 위한 수리모형을 구축하고, ILOG CPLEX를 이용하여 수리모형을 검증하였으며, 휴리스틱 알고리즘을 이용하여 해를 도출하였다.
수상함이 탐색활동을 수행하는 해역에서 잠수함의 잠항능력을 고려하여 생존율을 극대화하는 이동 경로를 계획하기 위해 휴리스틱 알고리즘을 이용하여 실험하였다. 실험 예제별 활동 공간, 잠수함(출발지점, 목표지점, 잠항능력), 수상함(유형,
성능/효과
첫째, 잠수함 및 수상함은 활동 공간에서 단위시간이 경과시에 제자리 및 인접 셀로만 이동하며, 매 시간 t에서 하나의 셀에 위치한다.
다섯째, 수상함의 탐색 패턴은 탐색 시작지점에서 탐색 종료지점 간을 지속적으로 왕복 기동 탐색하며, 탐색 시작 및 종료지점에서는 1회 제자리 탐색 후 인접 셀로 이동한다. 예를 들어, 다음<그림 2>에서 단위시간에 따른 수상함의 탐색 패턴은(1,1)→(2,1)→(3,1)→(2,1)→(1,1)→(1,1)→(2,1)→.
CPLEX와 휴리스틱 알고리즘을 이용한 축소실험 결과 이동 단위시간, 생존율, 이동경로가 동일하게 산출되었으며, 계산시간은 휴리스틱 알고리 즘이 0.38초로 2.88 ~3.74초가 소요된 CPLEX에비해 빠른 것으로 나타났다. CPLEX를 이용하여 최적해를 산출하였고, 휴리스틱 알고리즘의 실험 결과가 CPLEX와 동일하며, 빠른 계산시간을 도출함으로써 본 연구에서 제시한 수리모형의 타당성과 휴리스틱 알고리즘의 유효성을 입증하였다.
74초가 소요된 CPLEX에비해 빠른 것으로 나타났다. CPLEX를 이용하여 최적해를 산출하였고, 휴리스틱 알고리즘의 실험 결과가 CPLEX와 동일하며, 빠른 계산시간을 도출함으로써 본 연구에서 제시한 수리모형의 타당성과 휴리스틱 알고리즘의 유효성을 입증하였다.
200(20x10)개의 활동 공간, 수상함 5척이 탐색하는 예제 2에서 잠수함은 총 이동 단위시간은 26, 생존율 0.875를 도출하였으며, 수상함의 탐지거리 내에서 1회(1단위시간) 잠항하였다.
400(20x20)개의 활동 공간, 수상함 8척이 탐색하는 예제 4에서 잠수함은 수상함의 탐색 패턴을 고려하여 7 단위시간동안 한 지점 주변에서 잠항하였고, 수상함의 탐지거리 내에서 2회(1, 2단위 시간) 잠항하였으며, 잠수함의 총 이동 단위시간은 41, 생존율 0.627을 도출하였다. 휴리스틱 알고리즘의 계산시간은 1.
627을 도출하였다. 휴리스틱 알고리즘의 계산시간은 1.094~3.204초로 산출되어 탐색속도가 빠른 것으로 나타났다. 예제 4의 잠수함의 이동경로는 다음 <그림 5>와 같다.
잠수함의 생존율을 보장하고, 목표지점으로 이동하기 위한 휴리스틱 알고리즘을 이용하여 이동경로, 이동 단위시간(거리), 생존율, 계산시간을 도출하였다. 본 연구에서 제안한 휴리스틱 알고리즘은 수상함의 탐색 패턴을 고려하여 제자리 또는 한 지점 주변에서 잠항함으로써 생존율을 극대화하는 경로를 도출하였으며, 탐색속도가 빠른 것으로 나타났다.
후속연구
잠수함의 이동경로를 계획함에 있어 이동 가능 경로를 확장하여 적합도를 평가한다면 더 높은 생존율을 가지는 이동경로를 계획할 수 있을 것이며, 현재의 수상함 탐색구역 및 패턴을 바탕으로 도출된 잠수함의 이동경로를 고려한다면 수상함의 탐색구역 및 패턴 결정에 도움이 될 수 있을 것이다.
참고문헌 (17)
해군본부, "해군군사용어사전," 2007.
해군본부, "해군규정 제3권(해군 해양.음향업무 규정)," 2009.
Baston, V. J. and F. A. Bostok, "A One-Dimensional Helicopter-Submarine Game," Naval Research Logistics, Vol.36, No.4(1989), pp.479-490.
Hohzaki, R. and K. Iida, "Optimal Strategy of Route and Look for the Path Constrained Search Problem with Reward Criterion," European Journal of Operational Research, Vol.100, No.1(1997), pp.236-249.
Hong, S. P., S. J. Cho, and M. J. Park, "A Pseudo-polynomial heuristic for Path- constrained Discrete-time Markovian- target Search," European Journal of Operational Research, Vol.193, No.2(2009), pp.351-364.
Hong, S. P., S. J. Cho, M. J. Park, and M. G. Lee, "Optimal Search-relocation Trade-off in Markovian-target Searching," Computers and Operations Research, Vol.36, No.6(2009), pp.2097-2104.
Kim, B. S., C. K. Ryoo, H. C. Bang, and E. H. Chung, "Optimal Path Planning for UAVs under Multiple Ground Threats," Journal of the Korean Society for Aeronautical and Space Sciences, Vol.34, No.1(2006), pp.74-80.
Randal, W. B., W. M. Timothy, and G. Michael, "Coordinated Target Assignment and Intercept for Unmanned Air Vehicles," IEEE Transactions on Robotics and Automation, Vol.18, No.6(2002), pp.80-91.
Scott A. B., "Path Planning for UAVs," Proceedings of the American Control Conference, Chicaco, Illinois, 2000.
Shupenus, J. and D. Barr, "Information Loss due to Target Mobility," Military Operations Research, Vol.4(2000), pp.31-43.
Thomas, L. C. and A. R. Washburn, "Dynamic Search Games," Operations Research, Vol.39, No.3(1991), pp.415-422.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.