Environment Optimization for Multi-Agent Navigation

Traditional approaches to the design of multiagent 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.

Authors

• Zhan Gao
• Amanda Prorok

Keywords

• Learning systems
• Costs
• Navigation
• Layout
• Reinforcement learning
• Information processing
• Numerical models
• Multi-agent Navigation
• Optimization Problem
• Goal Of This Paper
• Optimal Environment
• Formal Proof
• Model-free Reinforcement Learning
• Navigation Algorithm
• Objective Function
• Convolutional Neural Network
• Mild Conditions
• Cost Function
• Shortest Path
• Multilayer Perceptron
• Path Planning
• Heuristic Method
• Multi-agent Systems
• Graph Neural Networks
• Closest Distance
• Navigation Task
• Trajectory Planning
• Destination Regions
• Navigation Performance
• Online Optimization
• Movement Of Agents
• Trajectories Of Agents
• Efficient Path
• End Of Episode
• Optimization Criteria