혼합정수선형계획법을 이용한 다수 이종 근접 방어 시스템의 최적 무장 할당 Optimal Weapon-Target Assignment of Multiple Dissimilar Closed-In Weapon Systems Using Mixed Integer Linear Programming원문보기
노희건
(Korea Advanced Institute of Science and Technology)
,
오영재
(Korea Advanced Institute of Science and Technology)
,
탁민제
(Korea Advanced Institute of Science and Technology)
,
정영란
(Agency for Defense Development)
본 논문에서는 다수 이종 근접 방어 시스템(Closed-In Weapon System, CIWS)의 최적 무장 할당 문제를 제시하고, 이를 혼합정수선형계획법(Mixed Integer Linear Programming, MILP)으로 변형해 해결하는 기법을 제안한다. 일반적인 무장 할당 문제의 경우 다양한 경우의 수를 고려해야하기 때문에 계산 시간이 기하급수적으로 증가하는 경우가 잦다. 하지만 주어진 문제를 MILP와 같은 혼합정수 최적화 문제로 변형하면 준실시간 내에 전역 최적해를 찾을 수 있다. 본 논문에서는 다수 위협이 각각 다른 시점에 다른 방향에서 방어 자산을 공격하는 상황을 고려한다. 또한, 제원이 다른 다수 CIWS를 동시 운용하는 경우를 추가로 고려한다. 본 논문에서는 이와 같은 문제 상황을 비선형 혼합정수계획 문제로 정식화하고, 이를 MILP로 변형하는 기법을 제시하였다. 또한, 이를 상용 최적화 프로그램으로 구현해 최적화 성능을 검증하였다.
본 논문에서는 다수 이종 근접 방어 시스템(Closed-In Weapon System, CIWS)의 최적 무장 할당 문제를 제시하고, 이를 혼합정수선형계획법(Mixed Integer Linear Programming, MILP)으로 변형해 해결하는 기법을 제안한다. 일반적인 무장 할당 문제의 경우 다양한 경우의 수를 고려해야하기 때문에 계산 시간이 기하급수적으로 증가하는 경우가 잦다. 하지만 주어진 문제를 MILP와 같은 혼합정수 최적화 문제로 변형하면 준실시간 내에 전역 최적해를 찾을 수 있다. 본 논문에서는 다수 위협이 각각 다른 시점에 다른 방향에서 방어 자산을 공격하는 상황을 고려한다. 또한, 제원이 다른 다수 CIWS를 동시 운용하는 경우를 추가로 고려한다. 본 논문에서는 이와 같은 문제 상황을 비선형 혼합정수계획 문제로 정식화하고, 이를 MILP로 변형하는 기법을 제시하였다. 또한, 이를 상용 최적화 프로그램으로 구현해 최적화 성능을 검증하였다.
In this paper, a Mixed Integer Linear Programming(MILP) approach for solving optimal Weapon-Target Assignment(WTA) problem of multiple dissimilar Closed-In Weapon Systems (CIWS) is proposed. Generally, WTA problems are formulated in nonlinear mixed integer optimization form, which often requires imp...
In this paper, a Mixed Integer Linear Programming(MILP) approach for solving optimal Weapon-Target Assignment(WTA) problem of multiple dissimilar Closed-In Weapon Systems (CIWS) is proposed. Generally, WTA problems are formulated in nonlinear mixed integer optimization form, which often requires impractical exhaustive search to optimize. However, transforming the problem into a structured MILP problem enables global optimization with an acceptable computational load. The problem of interest considers defense against several threats approaching the asset from various directions, with different time of arrival. Moreover, we consider multiple dissimilar CIWSs defending the asset. We derive a MILP form of the given nonlinear WTA problem. The formulated MILP problem is implemented with a commercial optimizer, and the optimization result is proposed.
In this paper, a Mixed Integer Linear Programming(MILP) approach for solving optimal Weapon-Target Assignment(WTA) problem of multiple dissimilar Closed-In Weapon Systems (CIWS) is proposed. Generally, WTA problems are formulated in nonlinear mixed integer optimization form, which often requires impractical exhaustive search to optimize. However, transforming the problem into a structured MILP problem enables global optimization with an acceptable computational load. The problem of interest considers defense against several threats approaching the asset from various directions, with different time of arrival. Moreover, we consider multiple dissimilar CIWSs defending the asset. We derive a MILP form of the given nonlinear WTA problem. The formulated MILP problem is implemented with a commercial optimizer, and the optimization result is proposed.
본 논문에서는 단일 근접 방어 시스템의 MILP를 이용한 최적 무장 할당 기법[15]을 토대로, 여러 개의 근접 방어 시스템을 갖춘 함정의 최적 무장 할당 문제를 MILP로 변형 및 해결하고자 한다. 일반적인 근접 방어 시스템의 경우 회전 포탑에 탑재되어 있기 때문에 위협의 접근 방향에 따라 요격 준비 시간에 큰 차이가 날 수 있다.
제안 방법
본 논문에서는 다수 이종 근접 방어 시스템의 최적 무장 할당 문제를 제시하고, 이를 선형화해 MILP 문제로 변형, 빠르게 해결하는 기법을 제안하였다. 또한, 결과로 제시한 선형 문제를 직접 구현하여 전수 조사 기법과 비교 및 분석하였다.
대상 데이터
또한 MILP 기법의 검증 및 성능 확인을 위해 모든 경우의 수를 전수 조사(Exhaustive Search)하는 기법을 python 스크립트로 구현하였다. 전수 조사 기법은 작은 크기(위협 ~10개 내외, 방어 자산 2개 이하)의 문제에서만 현실적인 시간 내에 동작한다.
데이터처리
MILP 기법에서 제공하는 해의 전역 최적성은 전수 조사 기법으로 찾은 전역 최적해와 비교해 검증할 수 있다. 최적해의 검증을 위해 다음과 같은 예시 시나리오를 고려하였다.
본 논문에서는 다수 이종 근접 방어 시스템의 최적 무장 할당 문제를 제시하고, 이를 선형화해 MILP 문제로 변형, 빠르게 해결하는 기법을 제안하였다. 또한, 결과로 제시한 선형 문제를 직접 구현하여 전수 조사 기법과 비교 및 분석하였다. 실제 구현을 바 탕으로 MILP 기법에서 얻은 해와 전수 조사에서 얻은 해를 비교해 MILP 변환의 적절성을 검증하였다.
이론/모형
제시한 MILP 문제는 다양한 상용 최적화 솔버를 사용해 모델링 및 최적화가 가능하다. 본 연구에서는 Gurobi[16] 솔버의 python 인터페이스를 이용해 문제를 직접 구현하였다. Gurobi는 다양한 presolve, branch and bound, cutting plane, 병렬 계산 기법 등을 이용해 MILP 문제의 전역 최적해를 빠른 시간 내에 제공한다.
성능/효과
또한, 위협 및 방어 자산 개수가 늘어날수록 MILP 기법이 계산 시간 측면에서 유리함을 확인하였다. 또한, 위협 개수 15개 내외까지 최적해를 준실시간(10 초 내외) 안에 계산해낼 수 있음을 보였다.
실제 구현을 바 탕으로 MILP 기법에서 얻은 해와 전수 조사에서 얻은 해를 비교해 MILP 변환의 적절성을 검증하였다. 또한, 위협 및 방어 자산 개수가 늘어날수록 MILP 기법이 계산 시간 측면에서 유리함을 확인하였다. 또한, 위협 개수 15개 내외까지 최적해를 준실시간(10 초 내외) 안에 계산해낼 수 있음을 보였다.
또한, 결과로 제시한 선형 문제를 직접 구현하여 전수 조사 기법과 비교 및 분석하였다. 실제 구현을 바 탕으로 MILP 기법에서 얻은 해와 전수 조사에서 얻은 해를 비교해 MILP 변환의 적절성을 검증하였다. 또한, 위협 및 방어 자산 개수가 늘어날수록 MILP 기법이 계산 시간 측면에서 유리함을 확인하였다.
후속연구
하지만 실제 함정 운용 시에는 추가적인 비선형 제약 조건들이 존재한다. 이와 같은 제약 조건들을 추가로 고려하면 실제 함정 방어 시스템에 MILP 기법을 적용 가능할 것으로 기대한다.
질의응답
핵심어
질문
논문에서 추출한 답변
최적 무장 할당 문제란 무엇인가?
현대전에서 지속적으로 함정 방어의 난이도가 상승함에 따라 기존 교전 교리 기반 방어의 한계가 예상 되고 있다. 따라서 탑재된 방어 자산으로 최선의 방어 성능을 내기 위해 방어 자산의 할당 최적화 문제의 중요성이 대두되고 있다. 이와 같은 문제를 최적 무장 할당 문제(Weapon-Target Assignment, WTA) 라 한다[3].
최적 무장 할당 문제의 목표는 무엇인가?
이와 같은 문제를 최적 무장 할당 문제(Weapon-Target Assignment, WTA) 라 한다[3]. 최적 무장 할당 문제의 목표는 방어 자산의 물리적 제약 조건을 만족하면서도 최소의 노력 으로 최선의 방어 효과를 얻는 방법을 찾는 것이다. 따라서, 최적 무장 할당 문제는 (1) 어떤 방어 자산을, (2) 어떤 순서로, (3) 어느 위협에게 공격할지를 결정하는 문제가 되는 것이다.
혼합 정수 선형 최적화 문제는 어떤 문제를 의미하는가?
이와 같은 문제의 대표적인 예가 혼합 정수 선형 최적화(Mixed- Integer Linear Programming, MILP) 문제이다[11,12]. MILP 문제는 모든 목적 함수 및 제약 조건이 선형이면서, 일부 변수가 정수 변수인 문제를 말한다. MILP 문제에는 Simplex 기법 또는 Interior Point 기법 등의 다항 시간 선형 최적화 기법을 적용할 수 있고, 추가로 기하학적 특성을 응용한 Cutting Plane, Branch and Bound 기법 등을 활용할 수 있다[11,12].
참고문헌 (16)
Jeon, I. S., Lee, J. I., and Tahk, M. J., "Impact-time-control guidance law for anti-ship missiles," IEEE Transaction on Control Systems Technology, Vol. 14, No. 2, March 2006, pp. 260-266.
Tahk, M. J., Shim, S. W., Hong, S. M., Lee, C. H., and Choi, H. L., "Impact time control based on time-to-go prediction for sea-skimming anti-ship missile," IEEE Transactions on Aerospace and Electronic Systems, Vol. 54, No. 4, August 2018, pp. 2043-2052.
Rosenberger, J. M., et al, "The Generalized Weapon Target Assignment Problem," 10th International Command and Control Research and Technology Symposium, June 2005.
Ma, F., Ni, M., Gao, B., and Yu. Z., "An Efficient Algorithm for the Weapon Target Assignment Problem," Proceeding of the 2015 IEEE International Conference on Information and Automation, August 2015, pp. 2093-2097.
Xin, B., et al., "An Efficient Rule-Based Constructive Heuristic to Solve Dynamic Weapon Target Assignment Problem," IEEE Transactions on Systems, Man and Cybernetics - Part A: Systems and Humans, Vol. 41, No. 3, 2011, pp. 598-606.
Leboucher, C., et al., "Optimal Weapon Target Assignment Based on an Geometric Approach," Proceedings of the 19th IFAC Symposium on Automatic Control in Aerospace, Vol. 46, Issue 19, 2013, pp. 341-346.
Leboucher, C., et al., "Novel Evolutionary Game Based Multi-Objective Optimisation for Dynamic Weapon Target Assignment," Proceedings of the 19th IFAC World Congress, Vol. 47, Issue 3, 2014, pp. 3936-3941.
Park, J. M., Roh, H., and Tahk, M. J., "Co-evolutionary Method For Dynamic Weapon- Target Assignment," Advances in Control and Optimization of Dynamic Systems, Hyderabad, India, February 2018.
Mouton, H., Roodt, J., and le Roux, H., "Applying Reinforcement Learning to the Weapon Assignment Problem in Air Defence," Scientia Militaria, South African Journal of Military Studies, Vol. 39, No. 2, 2011, pp. 123-140.
Ma, Y., and Chou, C., "Weapon Target Assignment Decision Based on Markov Decision Process in Air Defense," System Simulation and Scientific Computing, Vol. 327, 2012, pp. 353-360.
Vielma, J. P., "Mixed Integer Linear Programming Formulation Techniques," SIAM Review, Vol. 57, No. 1, February 2015, pp. 3-57.
Wolsey, L. A., Nemhauser, G. L., Integer and Combinatorial Optimization, 1st Ed., John Wiley & Sons, New York, 1999.
Richards, A., Schouwernaars, T., How, J. P., and Feron, E., "Spacecraft trajectory planning with avoidance constraints using mixed-integer linear programming," Journal of Guidance, Control, and Dynamics, Vol. 25, No. 4, 2002, pp. 755-764.
Lee, D. R., and Yang, J. H., "A Study on the Allocation and Engagement Scheduling of Air Defense Missiles by Using Mixed Integer Programming," Korean Management Science Review, Vol. 32, No. 4, December 2015, pp. 109-133.
Roh, H., and Tahk, M. J., "Optimization of Closed-In Weapon System Target Assignment Using Mixed Integer Linear Programming," Proceeding of The Korean Society for Aeronautical and Space Sciences Spring Conference, April 2018, pp. 437-438.
AI-Helper
※ AI-Helper는 부적절한 답변을 할 수 있습니다.