Co-Optimizing Reconfigurable Environments and Policies for Decentralized Multi-Agent Navigation

This work views the multiagent system and its surrounding environment as a coevolving system, where the behavior of one affects the other. The goal is to take both agent actions and environment configurations as decision variables, and optimize these two components in a coordinated manner to improve some measure of interest. Toward this end, we consider the problem of decentralized multiagent navigation in a cluttered environment, where we assume that the layout of the environment is reconfigurable. By introducing two subobjectives—multiagent navigation and environment optimization—we propose an agent-environment co-optimization problem and develop a coordinated algorithm that alternates between these subobjectives to search for an optimal synthesis of agent actions and environment configurations; ultimately, improving the navigation performance. Due to the challenge of explicitly modeling the relation between the agents, the environment and their performance therein, we leverage policy gradient to formulate a model-free learning mechanism within the coordinated framework. A formal convergence analysis shows that our coordinated algorithm tracks the local minimum solution of an associated time-varying nonconvex optimization problem. Experiments corroborate theoretical findings and show the benefits of co-optimization. Interestingly, the results also indicate that optimized environments can offer structural guidance to deconflict agents in motion.