LEARNING-BASED METAREASONING FOR MULTI-AGENT DIFFERENTIAL GAMES

Abstract

Multi-agent systems operating in adversarial environments must continuously make decisions regarding coordination, strategy selection, and the use of limited computational resources. Within the broader framework of differential games, reach-avoid and pursuit-evasion problems provide canonical settings for studying these challenges. In reach-avoid games, agents must ensure that certain targets are reached while avoiding unsafe regions, whereas pursuit-evasion games focus on the dynamic interaction between pursuers and evaders with opposing objectives. These settings are closely related but introduce distinct coordination and computational demands, particularly when scaling to multiple agents and maintaining real-time responsiveness. This dissertation investigates how metareasoning can improve the efficiency and effectiveness of decision making in multi-agent pursuit-evasion problems through the integration of game-theoretic reasoning, structured coordination methods, and machine learning. The first contribution investigates metareasoning for selecting coordination strategies in perimeter defense and pursuit-evasion games. In perimeter defense, the work compares maximum matching and local-game-region decomposition methods and develops data-driven policies that select the more effective algorithm from the initial game configuration. In pursuit-evasion, centralized and decentralized metareasoning policies select among predefined pursuer roles, including chaser, interceptor, and sitter behaviors, as the game evolves. The results show that learned metareasoning policies can adapt strategy selection to the current interaction state and, in several cases, improve upon fixed strategy combinations without exhaustively evaluating all alternatives. The second contribution addresses the problem of determining when computationally expensive assignment computations should be performed in multi-agent pursuit-evasion games. Hamilton-Jacobi reachability analysis is used to compute value functions and control laws for one-versus-one and two-versus-one pursuit-evasion sub-games. These sub-game solutions are combined through a mixed-integer assignment formulation to coordinate larger teams. Heuristic and graph-based metareasoning policies determine whether the assignment should be recomputed or retained at each decision point. Experimental results show that assignment computations can be reduced substantially while maintaining performance close to that of continuous reassignment. The third contribution explores tactical reasoning in large-scale multi-agent combat environments using professional StarCraft II replay data. A reachability-guided labeling framework combines geometric tactical priors, command information, trajectory features, and temporal smoothing to infer tactical pseudo-labels from expert demonstrations. These labels are used to train centralized temporal graph-based tactical models, while a teacher-student distillation framework is formulated for decentralized execution. The experimental results demonstrate that broad tactical categories can be learned more reliably than fine-grained tactics, but they also reveal substantial challenges caused by pseudo-label noise, severe class imbalance, and distribution shift across held-out replays. Collectively, the contributions of this dissertation demonstrate that metareasoning can support multi-agent decision making at several levels: selecting coordination algorithms, determining when to invoke costly structured computations, and representing higher-level tactical behavior. The results highlight both the value of combining learning with interpretable structured reasoning and the remaining challenges involved in scaling these approaches to complex multi-agent systems.