This study proposes the creation of maritime search patterns using the Sequential Greedy Algorithm (SGA) based on probabilistic maps generated from pre-existing information. Additionally, it presents an efficient target search and task allocation strategy that combines the SGA with the Hungarian Algorithm for multi-agent task assignment. The paper describes techniques for the movement of multiple agents in various scenarios that may be encountered during initial maritime search missions, proposing a pattern for conducting search missions based on probabilistic maps with the SGA technique, considering the asymmetry of the given information. The paper introduces the Hungarian Algorithm for rescue missions and a cost-based allocation algorithm for one-to-one matching of agents and targets, planning task assignments with differentiated cost functions according to scenarios, thereby ensuring flexibility. This approach presents an algorithm for the overall mission execution of unmanned forces, offering an advantage by conducting searches based on probabilistic patterns derived from information. It was confirmed that knowing the changes in the probabilistic map from the beginning and performing tasks according to environmental changes in the map allows for rapid decision-making in the movement of multiple agents, and simulation results have shown that this can significantly reduce the time required for search missions. Furthermore, the study successfully connects the different nature of search and rescue mission planning through problem definition, achieving the goal of performing overall missions. It also confirms that the Hungarian Algorithm, extended with task weights and sorting based on these weights, can solve the allocation problem quickly, even when the number of tasks and agents does not match.
본 연구는 사전에 생성된 정보로부터 생성된 확률적 지도를 기반으로 순차 탐욕 알고리즘(SGA : Sequential Greedy Algorithm)을 사용한 해상 검색 패턴 생성을 제안한다. 또한 SGA와 헝가리 알고리즘을 활용한 다중 에이전트 작업 할당 기술을 결합한 효율적인 대상 검색 및 작업 할당 전략을 제시한다. 초기 단계에서 해상에서 탐색 임무를 실시할 때 마주할 수 있는 여러 가지 상황을 가정하여 다중 에이전트의 움직임에 대한 기법을 기술하며, 주어진 정보의 비대칭성을 고려한 SGA기법 확률적 지도를 기반으로 탐색임무를 수행하는 패턴을 제안한다. 본 논문에서는 구조 임무를 위한 헝가리 알고리즘을 제시하며 기존 에이전트와 목표물의 1대1 매칭을 위한 비용 기반 할당 알고리즘을 수행 대비 경우에 따른 비용함수 차등화를 통한 할당 임무를 수행하도록 계획하여 유연성을 보장하는 알고리즘을 제안한다. 이는 무인 전력의 전반적인 임무 수행을 위한 알고리즘을 제시하는 한편 기존 수행해 왔던 탐색 패턴을 확률 기반으로 탐색을 진행함으로써 정보에 기반한 탐색 패턴을 제시하고 임무를 수행한다는 장점이 있다. 또한, 처음부터 확률 맵의 변화를 알고 있는 경우와 맵의 환경 변화에 따른 임무 수행 모두 다수 에이전트의 움직임을 빠르게 결정할 수 있음을 확인하였고, 시뮬레이션 결과를 통해 탐색 임무에서 중요한 시간적 소요를 줄일 수 있음을 확인하였다. 또한, 서로 다른 성향의 임무 계획인 탐색과 구조 임무를 위한 할당 문제를 문제 정의를 통해 연결하여 전반적인 임무를 수행하는 목표를 달성하였으며, 헝가리안 알고리즘에 임무 가중치와 가중치에 따른 정렬을 통해 임무-에이전트 간 동수가 아니어도 기존 알고리즘에서 확장하여 빠른 시간 내 할당 문제를 해결할 수 있음을 확인하였다.
