FoM: Field-of-View-Aware Graph Neural Learning for Min–Max Multi-Robot Patrol Path Planning

Abstract

Multi-robot patrol path planning is conventionally formulated as the min-max multiple traveling salesman problem (min-max mTSP). Existing formulations typically assume robots must physically visit each target, overlooking their visual perception capabilities. However, in many scenarios, targets are considered covered once they fall within a robot's field-of-view (FOV). To exploit this, we introduce a novel variant, the min-max mTSP with FOV, incorporating viewing directions into the optimization process. To efficiently solve this, we propose FoM, a sequential planning framework powered by a graph neural network (GNN) trained via reinforcement learning (RL). Instead of optimizing paths from scratch for each specific instance, FoM functions as a sequential decision-maker that iteratively selects nodes and sensing directions, achieving robust zero-shot generalization to unseen maps without retraining. Evaluations on synthetic and real-world maps demonstrate that FoM achieves remarkable performance, highlighting its practical effectiveness for multi-robot coordination.