How to efficiently route agents with conflicting goals?
A Convex Formulation of Game-theoretic Hierarchical Routing
This paper proposes a method for optimizing routes for multiple vehicles (e.g., aircraft) while accounting for their individual trajectories and interactions. It formulates this as a bilevel optimization problem, where the high level assigns routes (like deciding which waypoints each vehicle should visit) and the low level optimizes the detailed trajectories of each vehicle, considering their dynamics and potential collisions or cooperative formations. A key innovation is a convex reformulation of the problem, allowing efficient solutions using branch-and-bound algorithms. Experiments demonstrate its application in formation flight, where aircraft adapt their routes and trajectories to maintain desired spacing.
For LLM-based multi-agent systems, this research is relevant because it provides a structured approach to coordinating agents with complex dynamics and interactions. The high-level route planning could be analogous to task assignment by an LLM, while the low-level trajectory optimization resembles individual agent decision-making based on their capabilities and local information. The convex reformulation suggests potential for efficient solutions even with a large number of agents and complex interactions, which is crucial for scalable multi-agent applications. The focus on game-theoretic aspects at the low level could also inform how LLMs manage competition or cooperation among agents.