Search papers, labs, and topics across Lattice.
This paper introduces a bi-level optimization framework that co-optimizes agent trajectories and environment configurations for safe multi-agent navigation. They leverage KKT conditions and the Implicit Function Theorem to differentiate agent trajectories with respect to environment parameters, enabling gradient-based optimization of both. Experiments in warehouse logistics and urban transportation scenarios demonstrate that optimized environments improve both agent safety and efficiency.
Optimizing the environment itself, alongside agent actions, unlocks safer and more efficient multi-agent navigation.
The environment plays a critical role in multi-agent navigation by imposing spatial constraints, rules, and limitations that agents must navigate around. Traditional approaches treat the environment as fixed, without exploring its impact on agents' performance. This work considers environment configurations as decision variables, alongside agent actions, to jointly achieve safe navigation. We formulate a bi-level problem, where the lower-level sub-problem optimizes agent trajectories that minimize navigation cost and the upper-level sub-problem optimizes environment configurations that maximize navigation safety. We develop a differentiable optimization method that iteratively solves the lower-level sub-problem with interior point methods and the upper-level sub-problem with gradient ascent. A key challenge lies in analytically coupling these two levels. We address this by leveraging KKT conditions and the Implicit Function Theorem to compute gradients of agent trajectories w.r.t. environment parameters, enabling differentiation throughout the bi-level structure. Moreover, we propose a novel metric that quantifies navigation safety as a criterion for the upper-level environment optimization, and prove its validity through measure theory. Our experiments validate the effectiveness of the proposed framework in a variety of safety-critical navigation scenarios, inspired from warehouse logistics to urban transportation. The results demonstrate that optimized environments provide navigation guidance, improving both agents' safety and efficiency.
