Journal Search Engine

ISSN : 2005-0461(Print)
ISSN : 2287-7975(Online)

Journal of Society of Korea Industrial and Systems Engineering Vol.45 No.4 pp.42-52
DOI : https://doi.org/10.11627/jksie.2022.45.4.042

Reinforcement Learning-based Dynamic Weapon Assignment to Multi-Caliber Long-Range Artillery Attacks

Hyeonho Kim^*

, Jung Hun Kim^**

, Joohoe Kong^***

, Ji Hoon Kyung^*†

^*Department of Industrial Engineering, Hannam University
^**Hanwha Systems
^***CSB LAB

^†Corresponding Author : kjh@hnu.kr

Received 15/09/2022 Finally Revised 07/11/2022 Accepted 09/11/2022

Abstract

North Korea continues to upgrade and display its long-range rocket launchers to emphasize its military strength. Recently Republic of Korea kicked off the development of anti-artillery interception system similar to Israel’s “Iron Dome”, designed to protect against North Korea’s arsenal of long-range rockets. The system may not work smoothly without the function assigning interceptors to incoming various-caliber artillery rockets. We view the assignment task as a dynamic weapon target assignment (DWTA) problem. DWTA is a multistage decision process in which decision in a stage affects decision processes and its results in the subsequent stages. We represent the DWTA problem as a Markov decision process (MDP). Distance from Seoul to North Korea’s multiple rocket launchers positioned near the border, limits the processing time of the model solver within only a few second. It is impossible to compute the exact optimal solution within the allowed time interval due to the curse of dimensionality inherently in MDP model of practical DWTA problem. We apply two reinforcement-based algorithms to get the approximate solution of the MDP model within the time limit. To check the quality of the approximate solution, we adopt Shoot-Shoot-Look(SSL) policy as a baseline. Simulation results showed that both algorithms provide better solution than the solution from the baseline strategy.

Key Words : Reinforcement Learning , Dynamic Weapon Target Assignment , Long-Range Artillery

다종 장사정포 공격에 대한 강화학습 기반의 동적 무기할당

김 현호^*, 김 정훈^**, 공 주회^***, 경 지훈^*†

^*한남대학교 산업공학과
^**한화 시스템
^***씨에스비랩

초록

키워드 :

This article has been cited by 0 article in crossref

Cited-By

Funding:

1. 서 론

북한은 탄도탄과 더불어 북방한계선(MDL) 인근에 장 사정포를 배치하여 대한민국의 수도권을 위협하고 있으 며, 최근 다종 다양한 탄도탄을 혼합하여 발사하는 형태를 보임에 따라 장사정포 공격에도 적용될 것으로 예상된다. 북한은 개전 초 수 백여 문의 장사정포를 이용하여 수도권 의 군사시설 및 국가 중요시설을 무력화하기 위하여 일제 히 공격할 것으로 판단된다[18]. 장사정포 공격 대응방안 으로는 발사체를 요격하는 방식과 발사 플랫폼에 대해 직 접 타격하는 방식으로 구분할 수 있다. 전자의 경우 사드 나 패트리어트로 요격이 가능하나, 비용 대 효과상 비효율 적인 대응 방안으로 고려대상이 아니다.

현재까지 장사정포의 공격에 대응하는 방식은 장사정 포 진지를 직접 타격하여 사전에 무력화 시키거나 아군이 공격을 받으면 가용 무기체계를 이용하여 대응사격을 하 는 방식이다[14]. 그러나, 이러한 대응방식은 개전 초에 북 한의 갱도화 된 포병진지를 선제타격 하더라도 무력화를 보장할 수 없기 때문에, 이스라엘의 아이언 돔과 유사한 한국형 장사정포 요격체계 개발을 추진하고 있다[25]. 한 국형 장사정포 요격체계는 무력화 되지 않은 적 장사정포 병이 수도권에 대하여 일제히 사격을 가할 때 돔 형태의 방어막을 형성하여 아군의 피해를 상당수 줄이는 개념이 다[6].

이러한 한국형 장사정포 요격체계 개발을 위해서는 하 드웨어와 더불어 최단시간 내에 효과적으로 사격할 수 있 도록 표적을 할당해 주는 무기표적할당 알고리즘 등 소프 트웨어 개발이 필수적이다. 특히, 한반도 전장 환경 특성 상, 적 장사정포 진지와 수도권은 매우 근거리이기 때문 에, 최단시간 내 대응할 수 있는 무기체계 교전알고리즘이 매우 중요하다.

기존의 장사정포 대응방법은 요격 유도탄 운용자의 판 단에 의해서 대응하는 방법으로 대응 시간의 차이가 발생 하고, 피폭 받는 아군측 자산의 가치, 아군측의 포탄 재고, 적군의 추정 포탄 재고 등 전장의 상황에 따라 공격의 대 응에 영향을 주는 제반 요소의 변화를 반영하지 않고 고정 된 대응방법을 가진다는 제한점이 상존한다.

따라서, 한국형 장사정포 요격체계를 개발할 때, 요격이 가능한 시간 안에 실시간 전장 상황을 반영하여 우수한 교전 효과를 도출할 수 있는 무기 표적 할당의 수립이 가 능한지를 살펴보는 것은 매우 중요하다. 현재까지 연구된 휴리스틱 알고리즘기반의 무장할당 방법은 주어진 시간 내에 정확한 최적해를 산출하는 것이 불가능하여 강화학 습 기반의 개략 최적해를 구하는 무장 할당 알고리즘 적용 이 필수적이다.

본 논문에서는 기존 장사정포와 성능이 한층 개량된 장 사정포를 혼합하여 발사하는 전술을 사용하는 경우, 강화 학습 기반의 알고리즘들을 적용하였을 때, 무기 표적 할당 의 결과가 우수한 지를 시뮬레이션을 실행하여 살펴보고, 알고리즘의 실행 시간을 기록하여 실제 상황에서 사용 가 능한 지 알아본다. 본 논문의 구성은 다음과 같다. 제2장에 서는 관련 연구를 요약하고, 제3장에서는 문제 정의와 방 법론을 설명한다. 제4장에서는 시뮬레이션 내용 및 결과 를 요약하고 분석하며, 제5장에서 결론을 맺는다.

2. 관련연구

무기 표적 할당(WTA, Weapon Target Assignment) 문제 는 다수의 표적에 가용 무기 자원을 적절히 할당함으로써 보호하고자 하는 자산의 생존 가치를 높이거나, 표적의 생 존 가치를 낮추는 문제이다. 무기 표적 할당 문제는 크게 정적(static) 무기표적할당 문제와 동적(dynamic) 무기 표 적 할당 문제로 구분한다[9]. 정적 무기 할당 문제에서는 한번에 모든 무기를 목표에 할당하는 반면, 동적 무기 표 적 할당 문제에서는 연속적인 여러 단계에 걸쳐 의사결정 을 실행한다.

무기 표적 할당 문제에서는, 최적해를 찾기 위한 알고리 즘에 관한 연구가 무기와 표적의 수가 증가함에 따라 계산 시간이 오래 걸리기 때문에, 최근에는 신속한 의사결정을 위해, 모형을 선형화 하거나[11], 유전자 알고리즘[13], 개 미군집 알고리즘[16] 등과 같은 휴리스틱 알고리즘을 활 용한 근사 해를 찾는 연구가 활발히 진행되고 있다.

Naeem et al.[19]은 동적 무기 표적 할당문제를 실시간 스케줄링 문제의 특별한 사례로 보고, 특정 제약조건하에 서 무기와 표적을 각각 기계와 처리되어야 하는 작업으로 가정하여 접근하였다. 이때 안정된 결혼 알고리즘(Stable Marriage Algorithm)을 변형하여 표적의 위협을 계산하고 무기-표적을 할당하는 2단계 접근방식을 사용하였다. Cha et al.[4]은 포병 부대의 표적 할당 및 사격일정계획 수립을 위하여 동적계획법으로 표적-포병부대를 할당하고 분기 한정 알고리즘을 사용하여 포병부대의 사격 스케줄을 결 정하는 2단계 휴리스틱 알고리즘을 제안하였다. 하지만 불확실한 교전상황이 존재하는 동적 무기 표적 할당에 스 케줄링 알고리즘을 적용한 연구는 문제 특성과 시간효율 성을 충족시키기 위해 제약조건을 단순화하는 등 조건에 따라 모든 사례에 적용하기 어렵다는 한계점이 있다[12]. Jung et al.[12]은 동적으로 무기를 할당하고, 교전계획을 작성하는 휴리스틱 기반의 Rolling-Horizon 스케줄링 알고 리즘을 제안하였으며, 기존의 SLS 전략보다 우수한 해를 도출할 수 있음을 보여 주었다.

Bertsekas et al.[1]은 강화학습 기반의 알고리즘을 동적 무기 표적 할당 문제에 적용한 최초의 논문으로, 미사일 방어 문제에서 현재의 표적에 몇 발의 무기를 배정하고, 이후 공격에 대비하기 위하여 얼마의 재고를 남겨야 하는 문제를 다루었다. 논문에서 제시한 neuro-dynamic programming은 최적 함수를 근사화 하기 위하여 인공신경망 과 시뮬레이션을 활용 하였다. Davis et al.[7]은 감시 위성 의 발달에 따라 공격하고자 하는 자산의 파괴 정도를 공격 측에서도 실시간으로 파악하고 있다고 가정 하였다. 아울 러 공격 측은 공격 하고자 하는 자산의 실시간 가치를 반 영하여 확률적으로 공격하며, 방어 측에서도 방어 자산의 실시간 가치를 파악하고 있다고 가정하여 현대전의 기술 발달을 반영하였다. 저자들은 4가지 미사일 방어 시나리 오에 대한 동적 무기 표적 할당 문제를 ADP(Approximate Dynamic Programming) 알고리즘을 적용한 시뮬레이션 결 과가 최적해에 비하여 8%~22% 차이를 보였음을 보고 하 였다. Summers et al.[24]은 교전 기간, 요격 유도탄의 종류 등을 다양화한 시나리오에 대하여 공격 미사일 방어를 위 한 동적 무기 표적 할당 문제를 ADP 알고리즘을 적용한 해가 테스트한 모든 시나리오에서 운용자에 의한 SSL (Shoot-Shoot-Look) 발사방법보다 우수함을 제시하였다.

대부분의 동적 무기 할당 문제에 관한 연구는 미사일 방어 문제를 다루고 있다. 미사일 방어는 한 번의 공격에 수 발의 미사일 발사를 가정한다. 이와는 달리 한 번의 공 격에 수십 발의 포탄을 발사할 수 있는 장사정포 방어체계 에 대한 연구는 초기 단계이다[15]. 이와 관련된 연구로, 탄도탄에 대한 비행궤적의 정확한 예측이 요격 유도탄 할 당에 가장 중요한 요소이므로[5, 8, 26], Im et al.[10]은 이를 바탕으로 장사정포 발사체의 궤적의 분류에 따른 규칙기반 의 할당 방법론을 제안하였다. Shin et al.[23]은 교전 상황 중 실시간 무기표적 할당을 위한 멀티 에이전트 강화학습 모델을 제시하였다. 제시된 모델은 표적과 발사대 수가 증 가함에 따라 학습 차원이 증가하는 문제를 평균 필드 게임 이론을 이용하여 완화시켰으며, 기존의 할당 기법과 달리 표적 수에 관계없이 일정 시간으로 할당함을 확인하였다. 이 논문의 테스트 시나리오에서 장사정포에 대한 언급은 없으나, 표적 수를 증가시키면 장사정포 공격 시나리오와 유사할 것으로 보인다. Lee et al.[15]은 장사정포 공격에 대한 방어를 언급한 최초의 동적 무기 할당 연구로, 요격 탄도탄의 재고 수준에 따른 3가지 시나리오를 시뮬레이션 을 실행한 결과, 강화학습 기반의 알고리즘을 적용한 해가 SSL 발사방법보다 4%~11% 우수함을 보여 주었다.

3. 방법론

3.1 문제정의

본 논문에서 아군은 가치가 다른 여러 자산을 방어하기 위하여 다 수의 요격 포대를 배치하고 있으며, 한 포대는 여러 자산을 방어할 수 있다. 자산이 피폭을 받으면 피폭한 포탄의 발수에 비례하여 가치가 감소하며, 자산의 실시간 가치는 적군과 아군 모두 실시간으로 파악하고 있다. 요격 포대는 초기에 포탄 재고를 가지고 있으며, 재고가 소진되 면 더 이상 포탄의 보충은 없다. 적군은 여러 종류의 장사정 포를 가지고 있다. 적군은 아군 자산의 가치에 비례하여 확률적으로 자산을 향하여 포탄을 발사한다. 적군의 포탄 재고는 파악되지 않으므로, 아군 자산의 가치가 0이 될 때까 지 계속 공격하는 것으로 가정한다. 아군은 적군의 연속적 인 공격으로부터 최대한 자산 가치를 방어한다.

3.2 MDP 모형

MDP(Markov Decision Process) 모형은 각 의사결정 시 점에서의 상태(state), 행동(action), 전이확률(transition probability), 보상(reward), 할인인자(discount factor)의 5가지 항목에 의해 정의되며 다음과 같이 요약된다[22].

의사결정시점: 의사 결정이 내려지는 한 시점으로 시간 t로 나타낸다. T = 1 ,2, ⋯, T , T ≤ ∞ 는 의사결정시점의 집합이다.
상태: 모든 가능한 시스템의 상태들의 집합은 S 로 나 타내며, t시점에서의 시스템의 상태는 S_t로 나타 낸다.
행동: t시점에서 시스템의 상태가 S_t 일 때 의사 결정자 가 결정하는 행동으로 보통 a_t로 나타낸다. 이 행 동으로 시스템의 상태를 변화시켜 t+1 시점에서 의 시스템의 상태가 새롭게 된다.
보상: t시점에서 시스템의 상태가 S_t 일 때 의사 결정자 가 결정하는 행동 a_t으로 인해 받는 보상으로 실 수 값을 갖는 함수 C ( S_t, a_t )로 표현된다.
전이확률: t시점에서 시스템의 상태가 S_t 일 때 의사 결 정자가 결정하는 행동 a_t으로 t시점에서 각 새로운 상태별로 변하게 되는 확률을 의미한 다.
할인인자: 현재 얻게 되는 보상이 미래에 얻게 될 보상 보다 얼마나 더 중요한지를 나타내는 값으 로, γϵ[0,1]로 나타낸다.

이상은 일반적인 MDP 모형에 관한 설명으로, 본 논문 에서 다루는 동적 무기 표적 할당 문제를 표현하기 위하여 다음의 기호들을 사용한다.

의사 결정 시점 t에서 요격 포대의 유도탄 재고는 $R_{t} = {(R_{t i})}_{(i \in A)} \equiv (R_{t 1}, R_{t 2}, \dots, R_{t | A |})$ 로 나타내며, 여기에서 $R_{t i} \in {0, 1, \dots, r_{i}}$ 이다. R_ti는 t에서의 A에 속하는 i에 위 치한 요격 포대의 재고다.

요격 포대가 방어하는 자산의 상태는 A_t로 나타내며 $A_{t} = {(A_{t i})}_{i \in A} \equiv (A_{t 1}, A_{t 2}, \dots, A_{t | A |}) A = {1, 2, \dots, | A |}$ 는 모든 자산의 집합이고, 0 ≤ A_ti ≤ 1이다. A_ti는 의사결정 시점 t에서 A에 속한 자산 i의 상태를 나타내며, 자산의 몇 퍼센트가 장사정포로부터 피해를 입지 않고 남아있는 지를 보여준다.

장사정포의 공격 벡터는 ${\hat{M}}_{t} = {(\hat{M_{t i j}})}_{i \in A, j \in J}$ 로서 표현되 며, $\hat{M_{t i j}} \subseteq {\hat{M}}_{t j}$ 는 t에서의 자산 i∈A를 표적으로 삼는 j∈J 형태의 장사정포 공격이다.

이러한 구성요소를 사용하여, t시점에서의 시스템의 상 태는 각 자산의 상태, 각 요격 포대의 유도탄 재고, 장사정 포의 공격 벡터로 나타내며, $S_{t} = (A_{t}, R_{t}, {\hat{M}}_{t}) \in S =$ 로 표현 한다. $x_{t i j k} \in N_{0}$ 는 t시점에서 $k \in {\hat{M}}_{t i j}$ 의 장사정포탄을 향 하여 자산 i∈A를 방어하기 위하여 요격 포탄의 수라고 하자.

의사 결정 벡터 $x_{t} = {(x_{t i j k})}_{i \in A, j \in J, k \in \hat{M_{t i j}})} =$ 는 t시점에서 장사정포 공격에 대한 요격포의 할당을 나타내는 요격 유 도탄 벡터다. 그러면, 방어 측의 모든 가능한 행동들의 집 합은 다음과 같다.

X_{S_{t}} = {x_{t} : \sum_{j \in J} \sum_{k \in \hat{M_{t i j}}} x_{t i j k} \leq min {R_{t i}, x^{m a x}}, \forall i \in A}

(1)

위 식에서 x^max는 적군의 공격을 방어하기 위하여 한 시점에서 연속해서 발사할 수 있는 유도탄의 최대치를 나 타낸다.

시스템 상태의 전이를 나타내는 함수는 $S_{t + 1} = S^{M} (S_{t}, x_{t}, W_{t + 1})$ 로 표현하며, $W_{t + 1} = (\hat{A_{t + 1}}, \hat{M_{t + 1}})$ 는 확률 변수다. $\hat{A_{t + 1}}$ 은 t에서 ${\hat{M}}_{t}$ 와 x_t에 의해 결정되는 확률 변수다.

유도탄의 재고 는 아래 식과 같다.

R_{t + 1, i} = R_{t, i} - \sum_{j \in J} \sum_{k \in \hat{M_{t i j}}} x_{t i j k}, \forall i \in A

(2)

t시점에서 즉각적인 자산 가치의 손실은 식 (3)과 같이 확률적으로 표현된다.

\hat{C} (S_{t}, x_{t}, {\hat{A}}_{t + 1, i}) = \sum_{i \in A} υ_{i} (A_{t i} - {\hat{A}}_{t + 1, i})

(3)

식 (3)에서 υ_i는 자산 i∈A의 가치다. 비용 함수를 현재 의 상태와 요격 유도탄 벡터의 함수로 표현하면 식 (4)와 같다.

C (S_{t}, x_{t}) = E [\sum_{i \in A} υ_{i} (A_{t i} - {\hat{A}}_{t + 1, i}) | S_{t}, x_{t}]

(4)

MDP 모형에서는 알고리즘을 통해 미래의 피해를 최소 화할 수 있는 요격 유도탄 벡터(즉, 행동)를 결정한다. $X^{π} (S_{t})$ 를 요격 유도탄 벡터를 결정하는 정책이라 하면 MDP의 목적함수는 다음과 같다.

min_{π \in Π} E^{π} [E^{T} [\sum_{t = 1}^{T} C (S_{t}, X^{π} (S_{t}))]]

(5)

자산이 오래 보전되면 보상이 커지도록 하기 위하여 할 인인자를 사용하여 목적함수를 다시 쓰면 다음과 같다.

min_{π \in Π} E^{π} [\sum_{t = 1}^{\infty} γ^{t - 1} C (S_{t}, X^{π} (S_{t}))]

(6)

t시점에서의 상태의 가치를 J ( S_t )라 하면 최적의 정책 은 Bellman 방정식이라 부르는 다음과 같은 식으로 표현 된다.

J (S_{t}) = min_{x_{t} \in X_{t}} (C (S_{t}, x_{t}) + γ E [J (S_{t + 1}) | S_{t}, x_{t}])

(7)

이 Bellman 방정식의 해는 다음과 같다.

X^{π} (S_{t}) = \underset{x_{t \in X_{t}}}{arg min} (C (S_{t}, x_{t}) + γ E [J (S_{t + 1}) | S_{t}, x_{t}])

(8)

3.3 강화학습 기반의 근사모형

DWTA(Dynamic Weapon Target Assignment) 문제를 MDP 모형으로 표현한 후에 Bellman 방정식을 이용하여 정확한 최적해를 구할 수 있다. 그러나, 이러한 방법을 실 제 문제에 적용하여 최적해를 구할 때는 두 가지 문제가 발생하며, 각 문제점과 그 해결방안을 살펴보자[20].

첫째, MDP로 모형화 하면 소규모의 문제에서는 계산이 가능하나, 문제의 크기가 커지면 계산이 불가능 하거나 너 무 오랜 시간이 걸린다는 사실에 있다[20]. 예를 들어 한번 공격할 때마다 적의 장사정포가 1번에 12발 단위로 동시 에 최대 3번 발사할 수 있다고 가정하자. 12발씩 10번 발 사가 가능한 유도탄 재고를 가진 요격 포대가 4곳 있으며, 방어할 자산이 4곳이며, 장사정포 1발이 자산에 피격되면 자산의 최초 가치를 0.025배씩 감소시킨다고 가정하자. 이 경우 |S_t|는 최대 1.4×10¹²가 된다. 여기에 |T |를 곱해야 전 체 시스템 상태의 크기 |S |가 나온다. 이 사례는 DWTA 문제의 크기가 커지면 정확한 해를 구하는 방법은 사용하 기 어렵다는 사실을 보여준다.

Powell[20]은 시스템 상태의 수를 줄이는 방법으로 의사 결정 직후(post-decision) 상태라는 개념을 제안했다. DWTA 문제에서 의사결정 직후 상태는 요격 벡터를 결정 한 직후이면서 새로운 정보 W_t+1는 도착하기 직전의 상태 를 나타낸다. 의사결정 직후 상태를 $S_{t}^{x}$ 로 나타내면, 시스 템 상태의 전이를 나타내는 함수 $S_{t + 1} = S^{M} (S_{t}, x_{t}, W_{t + 1})$ 는 다음과 같이 나누어 표현 할 수 있다.

S_{t}^{x} = S^{M, x} (S_{t}, x_{t})

(9)

S_{t + 1} = S^{M, W} (S_{t}^{x}, W_{t + 1})

(10)

<Figure 1>은 t = 0일 때와 t = 1일 때, 이러한 관계를 보 여준다. 따라서 의사결정 직후 상태를 사용하여 시스템 상 태를 표현하면 크기가 $1 / | {\hat{M}}_{t} |$ 배로 줄어든다. 앞에서 예로 든 문제에 대하여 의사 결정 직후 상태 $S_{t}^{x}$ 의 크기는 시스 템 상태 S_t보다1/35배가 된다. 그러나, 상태의 크기가 축소 되었지만 정확한 해를 구하기 어려울 정도로 여전히 크다.

둘째, MDP 모형에서는 가치 J (S_t )를 정확하게 계산하 기 위해서는 식 (7)에 의거하여 S_t로부터 t시점이후 모든 시간에 대해 전이가 가능한 모든 상태의 가치를 정확하게 알고 있어야 한다. 그러므로 대부분의 DWTA 문제에서 J (S_t )를 정확하게 계산하는 것은 많은 시간이 소요된다. 이와는 대조적으로 강화학습 기반의 알고리즘에서는 가치 를 근사적으로 구하는 함수를 사용하여 계산하며, 샘플로 모집단의 통계치를 추정할 때 샘플의 수를 조정하는 것처 럼, 가치 함수를 추정할 때 입력으로 사용하는 S_t의 샘플 의 크기를 사용자가 조절할 수 있다. 이와 같이 |S_t|보다 훨씬 적은 샘플을 취하여 계산함으로써 매우 빠른 시간 내에 근사치 추정이 가능해진다.

의사결정 직후 상태의 가치를 $J^{x} (S_{t}^{x})$ 라 하면 상태의 가 치와 의사결정 직후 상태의 가치의 관계는 다음과 같다 [20, 21].

J (S_{t}) = min_{x_{t} \in X_{t}} (C (S_{t}, x_{t}) + γ J^{x} (S_{t}^{x}))

(11)

J^{x} (S_{t}^{x}) = E [J (S_{t + 1}) | S_{t}^{x}]

(12)

상태의 가치와 의사결정 직후 상태의 가치의 관계를 나 타내는 식 (11)을 $J^{x} (S_{t - 1}^{x})$ 에 대입하여 계산하면 의사결정 직후 상태에 대한 다음과 같은 방정식을 얻는다.

J^{x} (S_{t - 1}^{x}) = E [min_{x_{t} \in X_{t}} (C (S_{t}, x_{t}) + γ J^{x} (S_{t}^{x})) | S_{(t - 1)}^{x}]

(13)

이 식에서 J가 선형 기저 함수에 의해 결정된다고 가정 하자. 이 가정 하에서 의사결정 직후 상태의 가치를 계산 하면, 정확한 값을 추정하지는 못하지만, 빠른 시간 안에 근사해를 구하는 장점을 가진다. 의사결정 직후 상태의 가 치를 추정하기 위하여 선택된 기저 함수를 ϕ_f ( S_t ), fϵF 라 하자. 이때, 기저 함수들의 집합 F 는 시스템 변수의 차원 을 |F |로 줄여 관심있는 요소들로 표현할 수 있다. 그러면, 의사결정 직후 상태의 가치를 $({\bar{J}}^{x}) (S_{t}^{x})$ 라 할 때, 다음과 같이 선형식으로 나타낼 수 있다.

({\bar{J}}^{x}) (S_{t}^{x}) = \sum_{f \in F} θ_{f} ϕ_{f} (S_{t}^{x})

(14)

의사결정 직후 상태의 가치를 나타내는 위 식에서 θ_f는 파라미터 벡터다. 식 (13)에서 $J^{x} (S_{t}^{x})$ 및 $J^{x} (S_{t - 1}^{x})$ 대신에 의사결정 직후 상태의 가치를 나타내는 선형 회귀식 (14) 를 사용하여 다시 쓰면 다음과 같다.

{\bar{J}}^{x} (S_{t - 1}^{x}) = E [min_{x_{t} \in X_{t}} (C (S_{t}, x_{t}) + γ \sum_{f \in F} θ_{f} ϕ_{f} (S_{t}^{x}) | S_{t - 1}^{x})]

(15)

강화학습에서는 API(Approximate Policy Iteration)라는 전략을 통하여 식 (7)의 Bellman 방정식에 대한 해로서 식 (8)을 사용하는 대신에, 의사결정 직후 상태의 가치를 나 타내는 식 (15)를 이용한 시뮬레이션을 통하여 근사해를 얻는다. API 전략은 정책 평가를 정해진 수만큼 반복한 후, 그 결과를 정책 개선에 반영하는 방법을 반복적으로 실행한다. 강화학습의 API 중에 LSTD(Least Square Time Difference) 알고리즘과 LSPE(Least Square Policy Evaluation) 알고리즘은 서로 비슷한 성능을 낸다고 알려져 있 으므로[2, 3], 본 논문에서는 이 두 알고리즘을 사용하여 해를 구하고, 그 성능을 비교한다.

<Figure 2>의 API-LSTD 알고리즘은 정책 개선을 N번 실행하며, 각 정책 개선 루프 안에 K번의 정책 평가를 한 다. 먼저 θ⁰를 초기화한 후에 정책 평가 루프에서 샘플링 된 K개의 의사 결정 직후 상태에 대하여 기저 함수 $ϕ (S_{t - 1, 1}^{x})$ 및 $ϕ (S_{t, 1}^{x})$ 와 Cost를 기록한다. 정책 개선 루프에 서는, 기록된 기저 함수 행렬과 Cost 벡터를 이용하여 θ¹ 를 계산한다. θ¹을 이용하여 정책 평가 루프를 실행한 후 θ²를 구한다. 이런 방법으로 정책 개선 루프를 N번 실행하 여 θ^N 을 구한 다음 $X^{π} (S_{t} | θ^{N})$ 을 계산함으로써 알고리즘 을 마치게 된다. 각 알고리즘의 정책 개선 루프의 마지막 행에서 새로운 θ를 구하기 위한 수식에서 사용된 기저 함 수 행렬과 Cost 벡터는 다음과 같다.

Φ_{t - 1} ≜ [\begin{array}{l} ϕ {(S_{t - 1, 1}^{x})}^{T} \\ ⋮ \\ ϕ {(S_{t - 1, K}^{x})}^{T} \end{array}], Φ_{t} ≜ [\begin{array}{l} ϕ {(S_{t, 1}^{x})}^{T} \\ ⋮ \\ ϕ {(S_{t, K}^{x})}^{T} \end{array}], C_{t} ≜ [\begin{array}{l} C (S_{t, 1}, x_{t}) \\ ⋮ \\ C (S_{t, K}, x_{t}) \end{array}]

(16)

<Figure 3>의 API-LSPE 알고리즘은 정책 개선 루프와 각 정책 개선 루프 안에 정책 평가를 정해진 횟수만큼 반복한 다는 점에서는 API-LSTD 알고리즘과 동일하다. 차이점은 LSTD 알고리즘은 근사함수에 사용하는 기저함수에서 한 시점의 의사결정 직후 상태와 그 다음 시점의 의사결정 직후 상태를 이용하는 반면에, LSPE 알고리즘은 기저 함수 가 한 시점의 의사결정 직후 상태를 사용한다는데 있다.

4. 시뮬레이션 및 결과분석

4.1 시뮬레이션 시나리오

북한은 아군의 대응에 혼란을 주기 위하여 정점고도가 다른 여러 종류의 방사포를 섞어 쏘는 전술을 구사한다. 따라서 이러한 경우에 적 장사정포 공격시 API-LSTD 및 API-LSPE 알고리즘을 활용한 표적할당의 계산시간이 단 시간에 이루어지는지 시뮬레이션을 통하여 확인하며, 계 산 결과로 얻어진 근사해가 우수한 해인지를 판단하기 위 하여 기존의 SSL 발사방법을 적용한 해와 비교한다.

<Figure 4>에 적군 및 아군의 배치가 요약되어 있다. 아 군은 3개의 자산을 방어하며, 각 자산의 가치는 (1, 10, 5) 로 가정한다. 요격 포대는 2개의 장소에 배치되어 있으며, 포대 1은 자산 1, 2를 방어하고 포대 2는 자산 2, 3을 방어 한다. 요격 포대는 한 번의 방어에 최대 4회의 유도탄을 사용할 수 있으며, 각 요격 포대는 적 장사정포 포대의 1회 공격에 대하여 최대 2회 방어한다고 가정한다. 포탄 1 단 위는 12발로 한다. 1회의 요격 유도탄은 소구경 장사정포 1회(24발)공격에 대하여 포탄 2 단위를 사용하여 요격하 며, 대구경 장사정포 1회(12발)에 공격에 대하여 포탄 1 단위를 사용하여 요격한다. 대구경 장사정포에 대한 유도 탄의 명중률은 70%이며, 소구경 장사정포에 대한 유도탄 의 명중률은 90%이다.

장사정포 공격은 한 번의 공격에 최대 3문의 장사정포 를 사용하여 공격할 수 있다. 소구경 장사정포는 2문을 보 유하고 있으며, 한 번 공격에 각 24발을 발사하며, 1 발이 자산에 떨어질 때 마다 최초 가치의 2.5%씩 자산의 가치 가 감소한다. 대구경 장사정포는 1문을 보유하고 있으며, 한 번 공격에 12발을 발사하며, 1 발이 자산에 떨어지면 최초 가치의 5% 만큼 자산의 가치가 감소한다. 각 장사정 포의 1회 공격시 하나의 자산을 향하여 공격한다. 한 번의 공격에 동원하는 장사정포의 문 수는 1, 2, 3문중 하나이며 동일한 확률로 사용한다. 적군은 아군 자산의 잔존 가치에 따른 다항분포에 의거하여 자산을 선택하여 공격한다. 예 를 들어 자산의 잔존가치가 (1, 8, 5)이면 (1/14, 8/14, 5/14) 의 매개변수를 갖는 다항분포에 의하여 공격할 자산을 선 택하며, 자산의 잔존가치가 (0.5, 5.5, 2)이면 (0.5/8, 5.5/8, 2/8)의 매개변수를 갖는 다항분포에 의하여 자산을 선택하 여 공격한다.

LSTD 및 LSPE 알고리즘에서 시점에서의 의사결정 직 후 상태의 가치를 추정할 때 사용하는 기저함수로는 $ϕ_{0} (S_{t}^{x}) = 1, ϕ_{1} (S_{t}^{x}) = A_{t}, ϕ_{2} (S_{t}^{x}) = R_{t}^{x}, ϕ_{3} (S_{t}^{x}) = A_{t}^{x}$ 를 사용 하였으며, α는 1, γ는 0.8을 사용하였다. 두 알고리즘에서 정책평가는 매 정책개선 루프마다 50번 실행하며, 정책개 선 루프는 15번 실행하였다.

4.2 시뮬레이션 결과

본 연구에서는 요격 유도탄 재고에 따라 2개의 시나리 오를 만들어 시뮬레이션을 실행하였다. 시나리오 1에서 = R_t (4,4), 시나리오 2에서 R_t = (8,8)로 설정하였다. 모든 경우 A_t = (1,1,1)로 하였다. 모든 시나리오에서 두 알고 리즘으로 시뮬레이션을 실행하면 1초 이내에 결과를 얻 었다.

4.2.1 시나리오 1: R_t = (4,4)

<Table 1>은 아군의 2개 방어포대에 각 4단위(48발)의 유도탄 재고가 있는 경우, 공격 벡터 별로 두 알고리즘을 적용한 의사결정 결과와 SSL 발사방법을 적용한 결과를 보여준다. <Table 1>에서 공격 벡터는 6자리 숫자로 구성 되어 있다. 6자리 숫자 중 첫 3자리 숫자는 대구경 장사정 포가 자산 1, 2, 3에 대하여 공격하는지 여부를 1과 0으로 나타내며, 나머지 3자리 숫자는 소구경 장사정포가 자산 1, 2, 3에 대하여 몇 회 공격하는지를 나타낸다. 이 시나리 오를 적용하여 시뮬레이션을 한 결과, API-LSTD 알고리 즘을 적용 했을 때의 자산가치 손실이 SSL 발사방법을 적 용 했을 때의 자산 가치의 손실보다, 공격 벡터의 공격 확 률을 고려한 가중평균치가 18.6% 작았다. API-LSPE 알고 리즘을 적용한 경우, SSL 발사방법을 사용하는 경우보다 자산 손실의 가중평균이 17.9% 작았다. API-LSTD 알고리 즘을 적용한 경우, API-LSPE 알고리즘을 적용한 경우보다 자산 손실이 0.9% 작았다. 따라서, 시나리오 1에 대한 두 알고리즘의 우열은 가릴 수 없다. 아울러 어떤 종류의 공 격 벡터에 대해서도 강화학습 기반의 알고리즘들은 SSL 발사방법에 비하여 자산 손실이 작은 결과를 가져왔다.

4.2.2 시나리오 2: R_t = (8,8)

<Table 2>는 아군의 2개 방어 포대에 각 8 단위(48 발)의 유도탄 재고가 있는 경우, 장사정포의 공격 벡터 에 따른 두 알고리즘을 적용한 의사결정 결과와 SSL 발 사방법을 적용한 결과를 보여준다. API-LSTD 알고리즘 을 적용 했을 때의 자산가치 손실이 SSL 발사방법을 적 용 했을 때의 자산 가치의 손실보다 평균 27.7% 작았 다. API-LSPE 알고리즘을 적용한 경우, SSL 발사방법을 취하는 경우보다 손실이 평균 22.4% 작았다. API-LSTD 알고리즘을 적용한 경우, API-LSPE 알고리즘을 적용한 경우보다 자산 손실이 평균 6% 작았다. 따라서, 시나리 오 2에 대해서는 API-LSTD 알고리즘이 API-LSPE 알고 리즘을 적용하는 경우보다 우수한 결과를 가져왔다. 아 울러 어떤 종류의 공격 벡터에 대해서도 강화학습 기반 의 알고리즘은 SSL 발사방법보다 자산 손실이 작은 결 과를 가져왔다.

4.3 시뮬레이션 분석

이상의 두 시나리오에 대한 시뮬레이션의 결과는 다음 과 같이 요약 할 수 있다.

첫째, MDP의 경우 주어진 문제의 크기가 클수록 최적 화를 위해 기하급수적으로 많은 시간이 소요되는 것으 로 알려져 있으나, 강화학습 기반의 알고리즘을 사용할 경우 매우 빠른 시간 안에 근사 해를 구할 수 있음을 확 인하였다.

둘째, 강화학습 기반의 알고리즘을 적용하는 경우 공격 벡터 및 유도탄의 재고에 따라 요격 전략을 유연하게 사용 하므로, 공격 벡터 및 유도탄의 재고 수준에 관계없이 고 정적으로 대응하는 SSL 발사방법보다 자산 가치의 손실 이 항상 작았다.

셋째, 두 시나리오에 대한 알고리즘을 적용한 결과, API-LSTD 알고리즘을 적용한 경우가 API-LSPE 알고리 즘을 적용한 경우보다 자산 손실이 작은 결과를 가져왔다. 이는 의사결정 직후 상태의 가치를 추정할 때 사용하는 기저함수 행렬이 API-LSTD 알고리즘은 두 시점을 사용하 고, API-LSPE 알고리즘을 한 시점의 기저함수 행렬을 사 용하기 때문인 것으로 보인다.

5. 결 론

본 논문에서는 파괴력과 요격률이 다른 여러 구경의 장 사정포 공격에 대하여 무기를 할당하는 문제에 강화학습 기반의 API-LSTD 및 API-LSPE 알고리즘을 적용하여 해 를 구하는 시뮬레이션을 수행하였다. 두 알고리즘은 매우 짧은 시간에 복잡한 MDP 문제의 근사해를 산출하였으며, 산출된 근사해가 SSL 발사방법을 적용하여 구한 해보다 훨씬 우수하여 여러 구경의 장사정포에 의한 공격의 대응 에 효과적으로 사용할 수 있음을 확인하였다.

이로써 본 논문의 학문적 공헌은 적용이 검증된 방법론 을 장사정포 전체 위협 도메인에 적용을 통하여 적용범위 를 확대하여도 좋은 방법론임을 검증하였고, 실제사례와 근접한 시뮬레이션을 보여준데 있다.

본 연구의 결과를 장사정포 위협에 대비한 방어 요격체 계 개발에 적용한다면 기존의 SSL 발사방법보다 효과적 인 방공망 설계에 기여할 수 있을 것으로 판단된다. 추후 연구 과제로, 요격 포대의 수, 각 포대별 커버리지 범위 및 유도탄 재고 수준, 방어 자산의 가치 등의 값을 바꾸어 가며 시뮬레이션을 한다면, 장사정포 공격의 대비에 필요 한 여러 자원의 양적 및 질적 수준 확보에 도움이 될 것으 로 보인다. 아울러, 다양한 탄도탄을 섞어 쏘는 공격에 대 비한 다층 방어망을 구축할 때 방어의 효과를 검증하기 위한 도구로서 본 논문의 방법론을 확장하여 사용 가능할 것으로 추정된다.

Acknowledgement

This study was partially supported by 2022 Industry- Academic Research Program of Hannam University and Hanwha systems.

Figure

<Figure 1>.

Example of a Sequence of Decisions as a MDP with Post-decision State Variable (from Fig. 2 in [22])

<Figure 2>.

API-LSTD Algorithm [7, 17, 24]

<Figure 3>.

API-LSPE Algorithm [24]

<Figure 4>.

Scenario Layout

Table

<Table 1>.

Policy Comparison for the Scenario 1

<Table 2>.

Policy Comparison for the Scenario 2

Reference

Bertsekas, D., Homer, M., Logan, D., Patek, S., and Sandell, N., Missile Defense and Interceptor Allocation by Neuro-Dynamic Programming, IEEE Transactions on Systems, Man, and Cybernetics, Part A: Systems and Humans, 2000, Vol. 30, No. 1, pp. 42-51.
Bertsekas, D.P., Approximate Policy Iteration: A Survey and Some New Methods, Journal of Control Theory and Applications, 2011, Vol. 9, pp. 310-335.
Bertsekas, D.P., Dynamic Programming and Optimal Control: Approximate Dynamic Programming, 4th Edition, 2012, Athena Scientific, Belmont, MA.
Cha, Y.H. and Jeong, B., Exact Algorithm for the Weapon Target Assignment and Fire Scheduling Problem, Journal of the Society of Korea Industrial and Systems Engineering, 2019, Vol. 42, No. 1, pp. 143- 150.
Choi, B.W., Yoo, B.C., Kim, J.H., and Yim, D.S., A Study on the Flight Trajectory Prediction Method of Ballistic Missiles, 2020 Autumn Conference on Journal of Korean Society of Systems Engineering, 2020, pp. 131-140.
Chosun Media, https://www.chosun.com/ politics/ diplomacy- defense/2022/04/10/3AQITBNGDZHBFGU I4WFTS3A4RA/ (accessed 2022/08/30)
Davis, M.T., Robbins, M.J., and Lunday, B.J., Approximate Dynamic Programming for Missile Defense Interceptor Fire Control, European Journal of Operational Research, 2017, Vol. 259, pp. 873-886.
Hong, D.W., Yim, D.S., and Choi, B.W., Application and Determination of Defended Footprint Using a Simulation Model for Ballistic Missile Trajectory, Journal of the Korea Institute of Military Science and Technology, 2018, Vol. 21, No. 4, pp. 551-561.
Hosein, P.A., A Class of Dynamic Nonlinar Resource Allocation Problems, [Ph. D. Dissertation], Massachusetts Institute of Technology, 1989.
Im, J.S., Yoo, B.C., Kim, J.H., and Choi, B.W., A Study of Multi-to-Majority Response on Threat Assessment and Weapon Assignment Algorithm: by Adjusting Ballistic Missiles and Long-Range Artillery Threat, Journal of Korean Society of Industrial and systems Engineering, 2021, Vol. 44, N0. 4, pp. 43-52.
Jang, J.G., Kim, K., Choi, B.W., and Suh, J.J., A Linear Approximation Model for an Asset-based Weapon Target Assignment Problem, Journal Society of Korea Industrial and System Engineering, 2015, Vol. 38, No. 3, pp. 108-116.
Jung, J.K., Uhm, H.S., and Lee, Y.H., Rolling-Horizon Scheduling Algorithm for Dynamic Weapon-Target Assignment in Air Defense Engagement, Journal of the Korean Institute of Industrial Engineering, 2020, Vol. 46, No. 1, pp. 11-24.
Kim, J.H., Kim, K., Choi, B.W., and Suh, J.J., An Application of Quantum-inspired Genetic Algorithm for Weapon Target Assignment Problem, Journal Society of Korea Industrial and System Engineering, 2017, Vol. 40, No. 4, pp. 260-267.
Kim, T., Yun, N., Kim, Y.J., Park, I., and Shim, D., Effect Analysis of Long-range Artillery Intercept System According to its Component Arrangement, Journal of Korean Society Industrial and System Engineering, 2022, Vol. 45, No. 1, pp. 41~52.
Lee, C., Kim, J.-H., Choi, B.W., and Kim, K., Approximate Dynamic Programming Based Interceptor Fire Control and Effectiveness Analysis for M-to-M Engagement, Journal of the Korean Society for Aeronautical & Space Science, 2022, Vol. 50, No. 4, pp. 287-295.
Lee, Z.J., Lee, C.Y., and Su, S.F., An Immunity Based Ant Colony Optimization Algorithm for Solving Weapon-Target Assignment Problem, Applied Soft Computing, 2002, Vol. 2, No. 1, pp. 39-47.
McKenna, R.S., Robbins, M.J., Lunday, B.J., and McCormack, I.M., Approximate Dynamic Programming for the Military Inventory Routing Problem, Annals of Operational Research, 2020, Vol. 288, No. 1, pp. 391-416.
Ministry of National Defense, 2020 Defense White Paper, 2020, Seoul, Ministry of National Defense.
Naeem, H. and Masood, A., An Optimal Dynamic Threat Evaluation and Weapon Scheduling Technique, Knowledge-Based Systems, 2010, Vol. 23, No. 4, pp. 337-342.
Powell, W.B., Approximate Dynamic Programming: Solving the Curse of Dimensionality, Second Edition, 2011, John Wiley & Sons, Hoboken, NJ.
Powell, W. B., Perspectives of Approximate Dynamic Programming, Annals of Operations Research, 2012, Vol 13, No. 2, pp. 1-38.
Rempel, M. and Bai, J., A Review of Approximate Dynamic Programming Applications within Military Operations Research, Operational Research Perspectives, 2021, Vol. 8, 100204.
Shin, M.K., Park, S.-S., Lee, D., and Choi, H.-L., “Mean Field Game based Reinforcement Learning for Weapon-Target Assignment”, Journal of the Korea Institute of Military Science and Technology, 2020, Vol. 23, No. 4, pp. 337-345.
Summers, D.S., Robbins, M.J., and Lunday, B.J., An Approximate Dynamic Programming for Comparing Firing Policies in a Networked Air Defense Environment, Computers & Operations Research, 2020, Vol. 117, 104890.
Yonhapnews, https://www.yna.co.kr/view/AKR202204 10019151504 (accessed 2022/08/30)
Yoo, B.C., Kim, J.H., Kwon, Y.S., and Choi, B.W., A Study on the Flight Trajectory Prediction Method of Ballistic Missiles, Journal of Korean Society of Systems Engineering, 2020, Vol. 16, No. 2, pp. 131-140.