×

Frequency-based multi-agent patrolling model and its area partitioning solution method for balanced workload. (English) Zbl 1511.90363

van Hoeve, Willem-Jan (ed.), Integration of constraint programming, artificial intelligence, and operations research. 15th international conference, CPAIOR 2018, Delft, The Netherlands, June 26–29, 2018. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10848, 530-545 (2018).
Summary: Multi-Agent Patrolling problem has received growing attention from many researchers due to its wide range of potential applications. In realistic environment, e.g., security patrolling, each location has different visitation requirement according to the required security level. Therefore, a patrolling system with non-uniform visiting frequency is preferable. The difference in visiting frequency generally causes imbalanced workload amongst agents leading to inefficiency. This paper, thus, aims at partitioning a given area to balance agents’ workload by considering that different visiting frequency and then generating route inside each sub-area. We formulate the problem of frequency-based multi-agent patrolling and propose its semi-optimal solution method, whose overall process consists of two steps – graph partitioning and sub-graph patrolling. Our work improve traditional \(k\)-means clustering algorithm by formulating a new objective function and combine it with simulated annealing – a useful tool for operations research. Experimental results illustrated the effectiveness and reasonable computational efficiency of our approach.
For the entire collection see [Zbl 1388.68011].

MSC:

90C27 Combinatorial optimization
PDFBibTeX XMLCite
Full Text: DOI