  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.
