Learning Minimalist Strategies for Decentralized Multi-Robot Patrolling
James Ward, Ryan McConville, Edmund R. Hunt · ACM SIGAPP Applied Computing Review · 2025
The problem of decentralized multi-robot patrol has previously been approached primarily with hand-designed strategies for minimization of "idleness" over the vertices of a graph-structured environment. These approaches often involve heuristic utility functions and complex inter-agent coordination mechanisms, which may introduce unnecessary complication or performance degradation due to inefficient utility function formulations. To examine this, we present two lightweight learned neural network-based strategies and show that they outperform existing strategies in both idleness minimization and against an intelligent intruder model, as well as presenting an examination of robustness to communication failure. We also present a minimal regression of these strategies, and show that performance comparable to leading literature strategies is achievable with an extremely simple controller. Our results indicate important considerations for strategy design and analysis of patrol systems, which we discuss in depth.