[학위논문]계획사격 상황하에서의 표적할당 및 사격순서 결정에 관한 연구 : Algorithms for Weapon Target Assignment and Fire Scheduling Problem in Planned Artillery Attack Operations원문보기
본 논문에서는 군사작전 중 포병무기체계를 활용한 계획사격 상황하에서 발생하는 제반 문제를 다루고 있다. 포병의 계획사격은 식별된 다수의 적 위협에 대하여 아군의 무기체계를 각 표적에 할당하고 사격순서를 결정하여 아군의 피해를 최소화 하는데 그 목적이 있다. 본 연구에서는 아군의 피해를 최소화 하는 수단으로써, 적이 반응하기 이전에 최대한 신속히 계획된 사격을 완료하기 위한 알고리듬 개발과 사격 종료 후 적이 아군에게 미치는 위협치의 합을 최소화하는 알고리듬 개발을 목표로 하였다. 군사작전에서는 인간정보, 무인정찰기, 인공위성등과 같은 감시자산에 의해 식별된 표적첩보들은 적절한 분석과정을 거쳐 정보로 가공되어 타격부대 (예: 포병, MLRS, 공군, 육군항공 등)에 할당되어 사격이 이루어지게 된다. 본 연구에서는 다양한 무기체계 가운데, 포병부대에 초점을 두도록 한다. 포병부대 무기체계(105mm 견인포, 155mm 견인/자주포, 8인치 등)가 다양하기 때문에 통합된 화력계획수립을 위해 5분단위 사격계획을 가정하였다. 계획사격의 실행까지는 크게 표적할당과 사격순서 결정이라는 두 단계로 나누어진다. 할당단계에서는 무기체계를 표적에 효율적으로 할당하여 해당 작전이 종료되었을 때 생존한 표적이 가지는 위협치를 최소화시키는데 이런 문제를 전통적으로 표적할당문제(WTAP: ...
본 논문에서는 군사작전 중 포병무기체계를 활용한 계획사격 상황하에서 발생하는 제반 문제를 다루고 있다. 포병의 계획사격은 식별된 다수의 적 위협에 대하여 아군의 무기체계를 각 표적에 할당하고 사격순서를 결정하여 아군의 피해를 최소화 하는데 그 목적이 있다. 본 연구에서는 아군의 피해를 최소화 하는 수단으로써, 적이 반응하기 이전에 최대한 신속히 계획된 사격을 완료하기 위한 알고리듬 개발과 사격 종료 후 적이 아군에게 미치는 위협치의 합을 최소화하는 알고리듬 개발을 목표로 하였다. 군사작전에서는 인간정보, 무인정찰기, 인공위성등과 같은 감시자산에 의해 식별된 표적첩보들은 적절한 분석과정을 거쳐 정보로 가공되어 타격부대 (예: 포병, MLRS, 공군, 육군항공 등)에 할당되어 사격이 이루어지게 된다. 본 연구에서는 다양한 무기체계 가운데, 포병부대에 초점을 두도록 한다. 포병부대 무기체계(105mm 견인포, 155mm 견인/자주포, 8인치 등)가 다양하기 때문에 통합된 화력계획수립을 위해 5분단위 사격계획을 가정하였다. 계획사격의 실행까지는 크게 표적할당과 사격순서 결정이라는 두 단계로 나누어진다. 할당단계에서는 무기체계를 표적에 효율적으로 할당하여 해당 작전이 종료되었을 때 생존한 표적이 가지는 위협치를 최소화시키는데 이런 문제를 전통적으로 표적할당문제(WTAP: weapon target assignment problem)라고 한다. 이 할당 결과를 보면, 각 무기체계 별로 다수의 표적이 할당된 경우가 발생하는데 이 때 설정된 목표 달성을 위한 사격순서결정단계가 필요하게 되고 이런 문제를 본 연구에서는 사격순서결정문제(FSP: fire sequencing problem)로 부르기로 한다. 소주제 1에서는 표적할당이 이미 완료가 되었다는 가정하에 사격순서를 결정하는 스케쥴링 문제를 다루었다. 본 소주제에서는 표적들이 고정되어 있으며 계획기간 (planninghorizon)동안 움직이지 않는 것으로 가정하고 있다. 최적해의 성질 (optimal solution property), 상한 (upper bound) 및 하한 (lower bound) 계산 방법을 개발하고 이를 이용하는 분지한계법 (branch-and-bound algorithm)을 제시하였다. 소주제 2에서는 소주제 1과 동일하게 표적할당은 이미 완료되었다는 가정하에 사격순서를 결정하는 문제를 다루었다. 본 연구에서는 표적들이 고정되어있지 않고, 최초사격이 실시된 이후 상황전파체계에 의하여 표적들이 회피기동을 하는 상황을 고려했다. 표적들이 회피하는 상황을 파괴확률이 경과시간에 비례해서 선형적으로 감소한다고 가정하였으며, 이에 기반한 비선형 목적식을 도출하였다. 본 소주제에서도 최적해의 성질, 상한 및 하한 계산 방법을 개발하고 이를 이용하는 분지한계법을 제시하였다. 소주제 3에서는 표적할당문제와 사격순서결정문제를 동시에 해결하는 문제를 다루었다. 우선 동적계획법 (dynamic programming)을 활용한 최적해 알고리듬을 2개 내지 3개 무기체계를 가지는 문제에 대하여 제시하였다. 4개 이상의 무기체계를 가지는 문제에 대해서는 위에서 제시된 동적계획법을 활용한 휴리스틱 알고리듬과 건설적휴리스틱 알고리듬 (constructive heuristic algorithm)을 제시하였다. 제시된 알고리듬의 성능분석을 위하여 실전상황을 고려하여 생성된 실험 문제를 생성하였으며, 제시된 알고리듬과 상용패키지인 CPLEX 11.0을 활용하여 비교분석을 실시하였다. 실험결과, 제안된 알고리듬은 논문에서 다루고 있는 문제에 대한 합리적인 시간 내에 최적해 내지는 우수한 해를 찾아낼 수 있음을 확인하였다. 현재 육군에서는 포병대대급에 대대전술지휘시스템 (Battalion Tactical Command System, BTCS)이 개발되어 운영 중이며 군단급에는 육군전술지휘시스템 (Army Tactical Command Information System, ATCIS)이 개발되어 운영 중에 있다. 이러한 시스템은 포병작전에 대한 계획-실시-평가 단계를 전산화하여 전제대에 걸쳐 정보를 공유하는 시스템이다. 본 연구에서 제안하는 운영 알고리듬은 실제 포병계획사격 작전 시 신속한 무기체계-표적 할당 및 최단시간 내에 사격을 완료할 수 있도록 사격계획을 제공하게 된다. 현재의 무기체계-표적 할당 및 사격계획수립은 비과학적인 방법으로 수행되는 바, 효율적인 측면과 최적화 측면에서도 많은 맹점이 있지만 본 연구에서 제안 하는 알고리듬을 위에서 소개한 시스템에 탑재할 경우 불필요한 포탄의 소요를 최소화 할 수 있고, 신속한 작전 수행을 가능하게 할 것으로 예상된다. 또한 본 연구결과는 야전포병부대에서 수립한 화력계획에 대한 검증을 가능하게 한다. 동일한 성격을 가진 표적에 대하여 화력계획을 수립할 때, 동일한 무기체계를 가진 부대라 할지라도 상이한 포탄 할당을 하는 경우가 많은데 이러한 불합리한 계획을 수정 및 보완할 수 있을 것으로 판단된다.
본 논문에서는 군사작전 중 포병무기체계를 활용한 계획사격 상황하에서 발생하는 제반 문제를 다루고 있다. 포병의 계획사격은 식별된 다수의 적 위협에 대하여 아군의 무기체계를 각 표적에 할당하고 사격순서를 결정하여 아군의 피해를 최소화 하는데 그 목적이 있다. 본 연구에서는 아군의 피해를 최소화 하는 수단으로써, 적이 반응하기 이전에 최대한 신속히 계획된 사격을 완료하기 위한 알고리듬 개발과 사격 종료 후 적이 아군에게 미치는 위협치의 합을 최소화하는 알고리듬 개발을 목표로 하였다. 군사작전에서는 인간정보, 무인정찰기, 인공위성등과 같은 감시자산에 의해 식별된 표적첩보들은 적절한 분석과정을 거쳐 정보로 가공되어 타격부대 (예: 포병, MLRS, 공군, 육군항공 등)에 할당되어 사격이 이루어지게 된다. 본 연구에서는 다양한 무기체계 가운데, 포병부대에 초점을 두도록 한다. 포병부대 무기체계(105mm 견인포, 155mm 견인/자주포, 8인치 등)가 다양하기 때문에 통합된 화력계획수립을 위해 5분단위 사격계획을 가정하였다. 계획사격의 실행까지는 크게 표적할당과 사격순서 결정이라는 두 단계로 나누어진다. 할당단계에서는 무기체계를 표적에 효율적으로 할당하여 해당 작전이 종료되었을 때 생존한 표적이 가지는 위협치를 최소화시키는데 이런 문제를 전통적으로 표적할당문제(WTAP: weapon target assignment problem)라고 한다. 이 할당 결과를 보면, 각 무기체계 별로 다수의 표적이 할당된 경우가 발생하는데 이 때 설정된 목표 달성을 위한 사격순서결정단계가 필요하게 되고 이런 문제를 본 연구에서는 사격순서결정문제(FSP: fire sequencing problem)로 부르기로 한다. 소주제 1에서는 표적할당이 이미 완료가 되었다는 가정하에 사격순서를 결정하는 스케쥴링 문제를 다루었다. 본 소주제에서는 표적들이 고정되어 있으며 계획기간 (planning horizon)동안 움직이지 않는 것으로 가정하고 있다. 최적해의 성질 (optimal solution property), 상한 (upper bound) 및 하한 (lower bound) 계산 방법을 개발하고 이를 이용하는 분지한계법 (branch-and-bound algorithm)을 제시하였다. 소주제 2에서는 소주제 1과 동일하게 표적할당은 이미 완료되었다는 가정하에 사격순서를 결정하는 문제를 다루었다. 본 연구에서는 표적들이 고정되어있지 않고, 최초사격이 실시된 이후 상황전파체계에 의하여 표적들이 회피기동을 하는 상황을 고려했다. 표적들이 회피하는 상황을 파괴확률이 경과시간에 비례해서 선형적으로 감소한다고 가정하였으며, 이에 기반한 비선형 목적식을 도출하였다. 본 소주제에서도 최적해의 성질, 상한 및 하한 계산 방법을 개발하고 이를 이용하는 분지한계법을 제시하였다. 소주제 3에서는 표적할당문제와 사격순서결정문제를 동시에 해결하는 문제를 다루었다. 우선 동적계획법 (dynamic programming)을 활용한 최적해 알고리듬을 2개 내지 3개 무기체계를 가지는 문제에 대하여 제시하였다. 4개 이상의 무기체계를 가지는 문제에 대해서는 위에서 제시된 동적계획법을 활용한 휴리스틱 알고리듬과 건설적휴리스틱 알고리듬 (constructive heuristic algorithm)을 제시하였다. 제시된 알고리듬의 성능분석을 위하여 실전상황을 고려하여 생성된 실험 문제를 생성하였으며, 제시된 알고리듬과 상용패키지인 CPLEX 11.0을 활용하여 비교분석을 실시하였다. 실험결과, 제안된 알고리듬은 논문에서 다루고 있는 문제에 대한 합리적인 시간 내에 최적해 내지는 우수한 해를 찾아낼 수 있음을 확인하였다. 현재 육군에서는 포병대대급에 대대전술지휘시스템 (Battalion Tactical Command System, BTCS)이 개발되어 운영 중이며 군단급에는 육군전술지휘시스템 (Army Tactical Command Information System, ATCIS)이 개발되어 운영 중에 있다. 이러한 시스템은 포병작전에 대한 계획-실시-평가 단계를 전산화하여 전제대에 걸쳐 정보를 공유하는 시스템이다. 본 연구에서 제안하는 운영 알고리듬은 실제 포병계획사격 작전 시 신속한 무기체계-표적 할당 및 최단시간 내에 사격을 완료할 수 있도록 사격계획을 제공하게 된다. 현재의 무기체계-표적 할당 및 사격계획수립은 비과학적인 방법으로 수행되는 바, 효율적인 측면과 최적화 측면에서도 많은 맹점이 있지만 본 연구에서 제안 하는 알고리듬을 위에서 소개한 시스템에 탑재할 경우 불필요한 포탄의 소요를 최소화 할 수 있고, 신속한 작전 수행을 가능하게 할 것으로 예상된다. 또한 본 연구결과는 야전포병부대에서 수립한 화력계획에 대한 검증을 가능하게 한다. 동일한 성격을 가진 표적에 대하여 화력계획을 수립할 때, 동일한 무기체계를 가진 부대라 할지라도 상이한 포탄 할당을 하는 경우가 많은데 이러한 불합리한 계획을 수정 및 보완할 수 있을 것으로 판단된다.
This dissertation focuses on scheduling problems arising in the military. In planned artillery attack operations, a large number of threatening enemy targets should be destroyed effectively to minimize fatal loss to the friendly forces. We consider a situation in which the number of available weapon...
This dissertation focuses on scheduling problems arising in the military. In planned artillery attack operations, a large number of threatening enemy targets should be destroyed effectively to minimize fatal loss to the friendly forces. We consider a situation in which the number of available weapons is smaller than the number of targets and the available weapons are not identical. Therefore, it is required to develop new scheduling methodologies that coordinate heterogeneous weapon types to achieve specific objectives such as minimizing the latest completion time of firing operations (makespan) and minimizing total threat of the targets after engagement is finished. In this dissertation, we develop scheduling algorithms for the fire scheduling problem (FSP) with given assignment results, and then, we develop a methodology combining both assignment and scheduling decision for the entire planned artillery attack operation. First, we address the minimization of the makespan criterion for the FSP, in which the sequence of targets to be fired at is determined. In this environment, we assume that there are m available weapons to fire at n targets (>m) and the weapons are already allocated to targets. One target can be fired by not only a weapon but also multiple weapons, and these fire operations should start simultaneously regardless of the weapons while the finish time of them may be different. We develop several dominance properties and a lower bound for the problem, and suggest a branch and bound algorithm exploiting them. Also, we introduce several local search methods and compare the solutions with the optimal solutions obtained from the branch and bound algorithm. Secondly, we consider the situation in which targets may move and hence the probability that a target is destroyed by a firing attack decreases as time passes. We present a branch and bound algorithm for the FSP with the objective of minimizing total threat of the targets, which is expressed as a function of the target destruction probabilities. Finally, we address the problem of allocating weapons to identified targets and scheduling firing operations for the objective of minimizing the makespan for given set of required firing operations. The problem is composed of two subproblems; the weapon target assignment problem (WTAP), in which the targets are to be assigned to the weapons, and the FSP, in which the start and completion times of each firing operation are to be determined, both of which are proved to be NP-hard. An exact algorithm is developed for two- and three-weapon WTAP based on dynamic programming (DP) approach. We present heuristic algorithms including a DP based heuristic and constructive algorithms to concurrently solve the two subproblems. Performances of the suggested algorithms are evaluated through series of computational tests on test problems which reflects the real engagement situation relatively well. Results of the computational tests show that the algorithms suggested in this dissertation give very good solutions in reasonable amount of computation time. Also, the algorithms suggested in this dissertation can be used in real artillery attack operations if they are modified slightly to cope with the practical situations.
This dissertation focuses on scheduling problems arising in the military. In planned artillery attack operations, a large number of threatening enemy targets should be destroyed effectively to minimize fatal loss to the friendly forces. We consider a situation in which the number of available weapons is smaller than the number of targets and the available weapons are not identical. Therefore, it is required to develop new scheduling methodologies that coordinate heterogeneous weapon types to achieve specific objectives such as minimizing the latest completion time of firing operations (makespan) and minimizing total threat of the targets after engagement is finished. In this dissertation, we develop scheduling algorithms for the fire scheduling problem (FSP) with given assignment results, and then, we develop a methodology combining both assignment and scheduling decision for the entire planned artillery attack operation. First, we address the minimization of the makespan criterion for the FSP, in which the sequence of targets to be fired at is determined. In this environment, we assume that there are m available weapons to fire at n targets (>m) and the weapons are already allocated to targets. One target can be fired by not only a weapon but also multiple weapons, and these fire operations should start simultaneously regardless of the weapons while the finish time of them may be different. We develop several dominance properties and a lower bound for the problem, and suggest a branch and bound algorithm exploiting them. Also, we introduce several local search methods and compare the solutions with the optimal solutions obtained from the branch and bound algorithm. Secondly, we consider the situation in which targets may move and hence the probability that a target is destroyed by a firing attack decreases as time passes. We present a branch and bound algorithm for the FSP with the objective of minimizing total threat of the targets, which is expressed as a function of the target destruction probabilities. Finally, we address the problem of allocating weapons to identified targets and scheduling firing operations for the objective of minimizing the makespan for given set of required firing operations. The problem is composed of two subproblems; the weapon target assignment problem (WTAP), in which the targets are to be assigned to the weapons, and the FSP, in which the start and completion times of each firing operation are to be determined, both of which are proved to be NP-hard. An exact algorithm is developed for two- and three-weapon WTAP based on dynamic programming (DP) approach. We present heuristic algorithms including a DP based heuristic and constructive algorithms to concurrently solve the two subproblems. Performances of the suggested algorithms are evaluated through series of computational tests on test problems which reflects the real engagement situation relatively well. Results of the computational tests show that the algorithms suggested in this dissertation give very good solutions in reasonable amount of computation time. Also, the algorithms suggested in this dissertation can be used in real artillery attack operations if they are modified slightly to cope with the practical situations.
AI-Helper
※ AI-Helper는 부적절한 답변을 할 수 있습니다.