# Environment Optimization for Multi-Agent Navigation

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 37 references that are in the map.
- First posted on arXiv 22 Sep 2022.

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

- [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)
- [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)
- [ModGNN: Expert Policy Approximation in Multi-Agent Systems with a Modular Graph Neural Network Architecture](https://mlsanity.com/paper/2103.13446/) (2021)
- [Multi-Robot Path Deconfliction through Prioritization by Path Prospects](https://mlsanity.com/paper/1908.02361/) (2019)
- [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)

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

- [Online Control Barrier Functions for Decentralized Multi-Agent Navigation](https://mlsanity.com/paper/2303.04313/) (2023)
- [Constrained Environment Optimization for Prioritized Multi-Agent Navigation](https://mlsanity.com/paper/2305.11260/) (2023)
- [Co-Optimizing Reconfigurable Environments and Policies for Decentralized Multi-Agent Navigation](https://mlsanity.com/paper/2403.14583/) (2024)
- [Graph Neural Networks over the Air for Decentralized Tasks in Wireless Networks](https://mlsanity.com/paper/2302.08447/) (2023)
- [On the Trade-Off between Stability and Representational Capacity in Graph Neural Networks](https://mlsanity.com/paper/2312.02372/) (2023)
- [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 obvious influence of spatial constraints on agents' performance. Yet hand-designing improved environment layouts and structures 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 can be accounted for. We begin by proposing a novel environment optimization problem. We show, through formal proofs, under which conditions the environment can change while guaranteeing completeness (i.e., all agents reach their navigation goals). Our solution leverages a model-free reinforcement learning approach. In order to accommodate a broad range of implementation scenarios, we include both online and offline optimization, and both discrete and continuous environment representations. Numerical results corroborate our theoretical findings and validate our approach.