An approximation algorithm for mobile multi-agent monitoring and routing problem

In this study, we present a monitoring scheme with a group of agents, that is considered a practical challenge in operations management. In particular, mobile multi-agents, such as drones, can facilitate the implementation of monitoring tasks in more efficient and flexible manners. However, comparing to a monitoring system with stationary agents, a monitoring problem with mobile multi-agents must incorporate the routing plan of agents together. Accordingly, this study provides a monitoring (patrolling) and routing model coupled with mobile agents. The focal interest of the paper is to obtain the optimal routes of agents such that the total utilities from the monitoring process are maximized over a specific duration of the planning horizon. To reflect a real-world situation, we examine a three-dimensional space along with a stochastic process of event occurrence. The corresponding model is formulated based on an integer programming model with a nonlinear objective function, also known as an NP-hard problem. In addition, we show the mathematical formulation based on a submodular maximization problem and propose a heuristic algorithm in light of submodularity to guarantee sub-optimal solutions along with the efficiency of the algorithm via numerical experiments.