GRIP: Latent Field-Guided Graph Policy for Budget-Constrained Multi-Agent Routing
Yujiao Hu, Zuyu Chen, MengJie Lee, Jinchao Chen, Meng Shen, Hailun Zhang, Wei Li, Yan Pan
Abstract
Subset selection under budget constraints is critical in applications like multi-robot patrolling, crime deterrence, and targeted marketing, where multiple agents must jointly select targets and plan feasible routes. We formalize this challenge as Multi-Subset Selection with Budget-Constrained Routing (MSS-BCR), involving complex, non-additive cost structures that defy traditional methods. We propose GRIP, a graph-based framework integrating spatial reward fields and policy learning to enable coordinated, budget-aware target selection and routing. GRIP uses attention-based embeddings and constraint-triggered pruning with utility recovery to produce high-quality, feasible solutions. Experiments based on multiple synthetic and real-world datasets show GRIP outperforms baselines in reward efficiency and scalability across varied scenarios.
BibTeX
@inproceedings{aaai2026_griplatentfieldg,
title = {GRIP: Latent Field-Guided Graph Policy for Budget-Constrained Multi-Agent Routing},
author = {Yujiao Hu and Zuyu Chen and MengJie Lee and Jinchao Chen and Meng Shen and Hailun Zhang and Wei Li and Yan Pan},
booktitle = {AAAI 2026},
year = {2026}
}