Optimal Monitoring of Multiple Agents via Time Sequence-Based Modeling

Abstract

Control of multi-agent systems is one of the central problems in control theory. In this paper, we study the optimal monitoring (surveillance) problem over a graph. This problem is to find trajectories of multiple agents that travel each node as evenly as possible, and can be applied to several applications such as city safety management and disaster rescue. In our previous work, the finite-time optimal monitoring problem was formulated, and was reduced to a mixed integer linear programming (MILP) problem. Based on the policy of model predictive control, an optimal trajectory is generated by solving the MILP problem at each discrete time. However, the computation time for solving the MILP problem is frequently long. In this paper, to reduce the computation time, we introduce the policy of time sequence-based modeling. In the proposed method, the adjacency relation of a given graph is time varying depending on the current locations of agents. Since the unnecessary arcs are eliminated, the computation time is improved. The effectiveness of the proposed method is demonstrated by numerical examples.

Keywords

• mixed logical dynamical system
• model predictive control
• multi-agent systems
• optimal monitoring
• time sequence-based modeling