# Constrained Environment Optimization for Prioritized Multi-Agent Navigation

arXiv: https://arxiv.org/abs/2305.11260 · HTML: https://mlsanity.com/paper/2305.11260/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 60 references that are in the map.
- First posted on arXiv 18 May 2023.

## Builds on (most cited first, 21 of 21)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [On Evaluation of Embodied Navigation Agents](https://mlsanity.com/paper/1807.06757/) (2018)
- [Recent Advances in Convolutional Neural Networks](https://mlsanity.com/paper/1512.07108/) (2015)
- [Reinforced Cross-Modal Matching and Self-Supervised Imitation Learning for Vision-Language Navigation](https://mlsanity.com/paper/1811.10092/) (2018)
- [Navigating to Objects in the Real World](https://mlsanity.com/paper/2212.00922/) (2022)
- [Graph Neural Networks for Decentralized Multi-Robot Path Planning](https://mlsanity.com/paper/1912.06095/) (2019)
- [Learning Decentralized Controllers for Robot Swarms with Graph Neural Networks](https://mlsanity.com/paper/1903.10527/) (2019)
- [Robotic Grasp Detection using Deep Convolutional Neural Networks](https://mlsanity.com/paper/1611.08036/) (2016)
- [Scalable Co-Optimization of Morphology and Control in Embodied Machines](https://mlsanity.com/paper/1706.06133/) (2017)
- [Prioritized Planning Algorithms for Trajectory Coordination of Multiple Mobile Robots](https://mlsanity.com/paper/1409.2399/) (2014)
- [Wide and Deep Graph Neural Network with Distributed Online Learning](https://mlsanity.com/paper/2107.09203/) (2021)
- [Adversarial Environment Generation for Learning to Navigate the Web](https://mlsanity.com/paper/2103.01991/) (2021)
- [Multi-Robot Path Deconfliction through Prioritization by Path Prospects](https://mlsanity.com/paper/1908.02361/) (2019)
- [Designing Environments Conducive to Interpretable Robot Behavior](https://mlsanity.com/paper/2007.00820/) (2020)
- [Decentralized Channel Management in WLANs with Graph Neural Networks](https://mlsanity.com/paper/2210.16949/) (2022)
- [Environment Optimization for Multi-Agent Navigation](https://mlsanity.com/paper/2209.11279/) (2022)
- [Double-Deck Multi-Agent Pickup and Delivery: Multi-Robot Rearrangement in Large-Scale Warehouses](https://mlsanity.com/paper/2304.14309/) (2023)
- [SDP-based Joint Sensor and Controller Design for Information-regularized Optimal LQG Control](https://mlsanity.com/paper/1503.01848/) (2015)
- [Sensing-Constrained LQG Control](https://mlsanity.com/paper/1709.08826/) (2017)
- [Standby-Based Deadlock Avoidance Method for Multi-Agent Pickup and Delivery Tasks](https://mlsanity.com/paper/2201.06014/) (2022)

## Built on by (most cited first, 6 of 6)

- [Co-Optimizing Reconfigurable Environments and Policies for Decentralized Multi-Agent Navigation](https://mlsanity.com/paper/2403.14583/) (2024)
- [A Principle of Targeted Intervention for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2510.17697/) (2025)
- [On the Trade-Off between Stability and Representational Capacity in Graph Neural Networks](https://mlsanity.com/paper/2312.02372/) (2023)
- [Attaining Human`s Desirable Outcomes in Human-AI Interaction via Structural Causal Games](https://mlsanity.com/paper/2405.16588/) (2024)
- [Scaling Multi-Agent Environment Co-Design with Diffusion Models](https://mlsanity.com/paper/2511.03100/) (2025)
- [ReCoDe: Reinforcement Learning-based Dynamic Constraint Design for Multi-Agent Coordination](https://mlsanity.com/paper/2507.19151/) (2025)

## Abstract (arXiv)

Traditional approaches to the design of multi-agent navigation algorithms consider the environment as a fixed constraint, despite the influence of spatial constraints on agents' performance. Yet hand-designing conducive environment layouts is inefficient and potentially expensive. The goal of this paper is to consider the environment as a decision variable in a system-level optimization problem, where both agent performance and environment cost are incorporated. Towards this end, we propose novel problems of unprioritized and prioritized environment optimization, where the former considers agents unbiasedly and the latter accounts for agent priorities. We show, through formal proofs, under which conditions the environment can change while guaranteeing completeness (i.e., all agents reach goals), and analyze the role of agent priorities in the environment optimization. We proceed to impose real-world constraints on the environment optimization and formulate it mathematically as a constrained stochastic optimization problem. Since the relation between agents, environment and performance is challenging to model, we leverage reinforcement learning to develop a model-free solution and a primal-dual mechanism to handle constraints. Distinct information processing architectures are integrated for various implementation scenarios, including online/offline optimization and discrete/continuous environment. Numerical results corroborate the theory and demonstrate the validity and adaptability of our approach.