Multi-Agent Surveillance Based on Travel Cost Minimization
Summary :
The multi-agent surveillance problem is to find optimal trajectories of multiple agents that patrol a given area as evenly as possible. In this paper, we consider the multi-agent surveillance problem based on travel cost minimization. The surveillance area is given by an undirected graph. The penalty for each agent is introduced to evaluate the surveillance performance. Through a mixed logical dynamical system model, the multi-agent surveillance problem is reduced to a mixed integer linear programming (MILP) problem. In model predictive control, trajectories of agents are generated by solving the MILP problem at each discrete time. Furthermore, a condition that the MILP problem is always feasible is derived based on the Chinese postman problem. Finally, the proposed method is demonstrated by a numerical example.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E107-A No.1 pp.25-30
- Publication Date
- 2024/01/01
- Publicized
- 2023/07/19
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.2023KEP0015
- Type of Manuscript
- Special Section PAPER (Special Section on Circuits and Systems)
- Category
Authors
Kyohei MURAKATA
Hokkaido University
Koichi KOBAYASHI
Hokkaido University
Yuh YAMASHITA
Hokkaido University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Kyohei MURAKATA, Koichi KOBAYASHI, Yuh YAMASHITA, "Multi-Agent Surveillance Based on Travel Cost Minimization" in IEICE TRANSACTIONS on Fundamentals,
vol. E107-A, no. 1, pp. 25-30, January 2024, doi: 10.1587/transfun.2023KEP0015.
Abstract: The multi-agent surveillance problem is to find optimal trajectories of multiple agents that patrol a given area as evenly as possible. In this paper, we consider the multi-agent surveillance problem based on travel cost minimization. The surveillance area is given by an undirected graph. The penalty for each agent is introduced to evaluate the surveillance performance. Through a mixed logical dynamical system model, the multi-agent surveillance problem is reduced to a mixed integer linear programming (MILP) problem. In model predictive control, trajectories of agents are generated by solving the MILP problem at each discrete time. Furthermore, a condition that the MILP problem is always feasible is derived based on the Chinese postman problem. Finally, the proposed method is demonstrated by a numerical example.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.2023KEP0015/_p
Copy
@ARTICLE{e107-a_1_25,
author={Kyohei MURAKATA, Koichi KOBAYASHI, Yuh YAMASHITA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Multi-Agent Surveillance Based on Travel Cost Minimization},
year={2024},
volume={E107-A},
number={1},
pages={25-30},
abstract={The multi-agent surveillance problem is to find optimal trajectories of multiple agents that patrol a given area as evenly as possible. In this paper, we consider the multi-agent surveillance problem based on travel cost minimization. The surveillance area is given by an undirected graph. The penalty for each agent is introduced to evaluate the surveillance performance. Through a mixed logical dynamical system model, the multi-agent surveillance problem is reduced to a mixed integer linear programming (MILP) problem. In model predictive control, trajectories of agents are generated by solving the MILP problem at each discrete time. Furthermore, a condition that the MILP problem is always feasible is derived based on the Chinese postman problem. Finally, the proposed method is demonstrated by a numerical example.},
keywords={},
doi={10.1587/transfun.2023KEP0015},
ISSN={1745-1337},
month={January},}
Copy
TY - JOUR
TI - Multi-Agent Surveillance Based on Travel Cost Minimization
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 25
EP - 30
AU - Kyohei MURAKATA
AU - Koichi KOBAYASHI
AU - Yuh YAMASHITA
PY - 2024
DO - 10.1587/transfun.2023KEP0015
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E107-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 2024
AB - The multi-agent surveillance problem is to find optimal trajectories of multiple agents that patrol a given area as evenly as possible. In this paper, we consider the multi-agent surveillance problem based on travel cost minimization. The surveillance area is given by an undirected graph. The penalty for each agent is introduced to evaluate the surveillance performance. Through a mixed logical dynamical system model, the multi-agent surveillance problem is reduced to a mixed integer linear programming (MILP) problem. In model predictive control, trajectories of agents are generated by solving the MILP problem at each discrete time. Furthermore, a condition that the MILP problem is always feasible is derived based on the Chinese postman problem. Finally, the proposed method is demonstrated by a numerical example.
ER -
English
