Approximation algorithms for mobile multi-agent sensing problem

Abstract

Multi-agent systems are generally applicable in a wide diversity of domains, such as robot engineering, computer science, the military, and smart cities. In particular, the mobile multi-agent sensing problem can be defined as a problem of detecting events occurring in a large number of nodes using moving agents. In this thesis, we introduce a mobile multi-agent sensing problem and present a mathematical formulation. The model can be represented as a submodular maximization problem under a partition matroid constraint, which is NP-hard in general. The optimal solution of the model can be considered computationally intractable. Therefore, we propose two approximation algorithms based on the greedy approach, which are global greedy and sequential greedy algorithms, respectively. We present new approximation ratios of the sequential greedy algorithm and prove tightness of the ratios. Moreover, we show that the sequential greedy algorithm is competitive with the global greedy algorithm and has advantages of computation times. Finally, we demonstrate the performances of our results through numerical experiments.

다중 에이전트 시스템은 일반적으로 로봇 공학, 컴퓨터 과학, 군사 및 스마트 도시와 같은 다양한 분야에 적용할 수 있다. 특히, 모바일 다중 에이전트 감지 문제는 움직이는 에이전트를 이용해 많은 수의 노드에서 발생하는 이벤트를 감지하는 문제로 정의할 수 있다. 본 논문에서는 모바일 다중 에이전트 감지 문제의 수학적 공식을 제안한다. 이 문제는 일반적으로 NP-난해 문제인 분할 매트로이드 제약 하에서 하위 모듈 함수의 최대화 문제로 표현할 수 있다. 문제의 최적해는 입력 데이터의 크기가 커질수록 보통 합리적인 시간 이내에 계산하기 어렵다. 따라서 본 논문에서는 탐욕적 접근 방식에 기초한 두 가지 근사 알고리즘 (전역 탐욕 알고리즘, 순차 탐욕 알고리즘)을 제안한다. 또한, 순차 탐욕 알고리즘의 새로운 근사 비율을 증명하고 근사 비율에 정확하게 일치하는 인스턴스를 제시한다. 또한, 수치 실험 결과로 순차 탐욕 알고리즘은 효과적인 해를 찾아줄 뿐 아니라, 전역 탐욕 알고리즘과 비교해 계산 시간의 이점을 가지고 있음을 확인한다.