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

作     者：Kim, Gwang Jeong, Yoonjea 

作者机构：Chosun Univ Div Business Adm Gwangju South Korea Pukyong Natl Univ Div Syst Management & Safety Engn Busan 48513 South Korea 

出 版 物：《FLEXIBLE SERVICES AND MANUFACTURING JOURNAL》 (Flexible Serv Manuf J)

年 卷 期：2025年

页      面：1-27页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 0802[工学-机械工程] 

基　　金：Chosun University 

主　　题：Mobile multi-agent systems Monitoring problem Route planning Nonlinear programming Submodularity 

摘      要：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.