Multi-Agent Goal Recognition with Team- and Goal-Conditioned Reinforcement Learning and Factorized Branch-and-Bound

Researchers introduce MAGR-BB, a novel algorithm that identifies which agents work together and what goals they pursue by analyzing trajectory data alone. The method uses branch-and-bound search with a shared policy model, achieving order-of-magnitude improvements in efficiency while maintaining accuracy comparable to exhaustive search.

Multi-agent goal recognition represents a fundamental challenge in AI systems requiring real-time decision-making without explicit communication protocols. The MAGR-BB approach tackles the combinatorial explosion inherent in inferring both team compositions and objectives simultaneously—a problem that grows exponentially with agent count. By leveraging a shared team- and goal-conditioned reinforcement learning policy as a scoring mechanism within a factorized branch-and-bound framework, the researchers achieve dramatic computational savings while preserving solution quality.

This work builds on established techniques in planning and multi-agent reinforcement learning, but innovates by factorizing the search space to avoid materializing the full hypothesis set. The controlled Blocksworld benchmark demonstrates theoretical soundness, but the practical motivation emerges from real-world applications like autonomous drone swarms and collaborative robotic systems where explicit communication may be impossible or undesirable. These domains frequently operate under strict computational and latency constraints.

The efficiency gains translate directly to deployment feasibility in time-sensitive environments. Reducing hypothesis materialization by orders of magnitude means systems can scale to larger agent populations without proportional computational overhead. The maintenance of exhaustive search quality validates that the factorized approach doesn't sacrifice accuracy for speed—a critical requirement for safety-critical applications.

Future work likely involves testing on more complex benchmarks beyond Blocksworld and examining robustness to partial observability and noisy trajectory data. Integration with real robotic systems would demonstrate practical viability and reveal performance bottlenecks in production environments.

• →MAGR-BB achieves exhaustive-search-level accuracy while reducing computational overhead by orders of magnitude through factorized branch-and-bound search.
• →The method uses a shared reinforcement learning policy as a scoring model to rank team-goal hypotheses from trajectory data alone.
• →Algorithm directly addresses real-world applications like drone surveillance and collaborative robotics without requiring explicit agent communication.
• →Factorized search space design prevents combinatorial explosion that would otherwise limit scalability to multi-agent systems.
• →Blocksworld validation demonstrates theoretical correctness, but robustness to noisy real-world data remains an open question.