Co-Optimization of Environment and Policies for Decentralized Multi-Agent Navigation
- URL: http://arxiv.org/abs/2403.14583v1
- Date: Thu, 21 Mar 2024 17:37:43 GMT
- Title: Co-Optimization of Environment and Policies for Decentralized Multi-Agent Navigation
- Authors: Zhan Gao, Guang Yang, Amanda Prorok,
- Abstract summary: This work views the multi-agent system and its surrounding environment as a co-evolving system, where the behavior of one affects the other.
We develop an algorithm that alternates between sub-objectives to search for an optimal of agent actions and obstacle configurations in the environment.
- Score: 14.533605727697775
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This work views the multi-agent system and its surrounding environment as a co-evolving 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. Towards this end, we consider the problem of decentralized multi-agent navigation in cluttered environments. By introducing two sub-objectives of multi-agent navigation and environment optimization, we propose an $\textit{agent-environment co-optimization}$ problem and develop a $\textit{coordinated algorithm}$ that alternates between these sub-objectives to search for an optimal synthesis of agent actions and obstacle configurations in the environment; ultimately, improving the navigation performance. Due to the challenge of explicitly modeling the relation between agents, environment and performance, 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 trajectory of an associated time-varying non-convex optimization problem. Extensive numerical results corroborate theoretical findings and show the benefits of co-optimization over baselines. Interestingly, the results also indicate that optimized environment configurations are able to offer structural guidance that is key to de-conflicting agents in motion.
Related papers
- Efficient Adaptation in Mixed-Motive Environments via Hierarchical Opponent Modeling and Planning [51.52387511006586]
We propose Hierarchical Opponent modeling and Planning (HOP), a novel multi-agent decision-making algorithm.
HOP is hierarchically composed of two modules: an opponent modeling module that infers others' goals and learns corresponding goal-conditioned policies.
HOP exhibits superior few-shot adaptation capabilities when interacting with various unseen agents, and excels in self-play scenarios.
arXiv Detail & Related papers (2024-06-12T08:48:06Z) - Evolutionary Algorithms for Optimizing Emergency Exit Placement in Indoor Environments [0.0]
A cellular-automaton model is used to simulate the behavior of pedestrians in such scenarios.
A metric is proposed to determine how successful or satisfactory an evacuation was.
Two metaheuristic algorithms, namely an iterated greedy and an evolutionary algorithm (EA) are proposed to solve the problem.
arXiv Detail & Related papers (2024-05-28T16:50:42Z) - Solving Expensive Optimization Problems in Dynamic Environments with Meta-learning [32.41025515064283]
We propose a simple yet effective meta-learning-based optimization framework for solving expensive dynamic optimization problems.
This framework is flexible, allowing any off-the-shelf continuously differentiable surrogate model to be used in a plug-in manner.
Experiments demonstrate the effectiveness of the proposed algorithm framework compared to several state-of-the-art algorithms.
arXiv Detail & Related papers (2023-10-19T07:42:51Z) - Federated Multi-Level Optimization over Decentralized Networks [55.776919718214224]
We study the problem of distributed multi-level optimization over a network, where agents can only communicate with their immediate neighbors.
We propose a novel gossip-based distributed multi-level optimization algorithm that enables networked agents to solve optimization problems at different levels in a single timescale.
Our algorithm achieves optimal sample complexity, scaling linearly with the network size, and demonstrates state-of-the-art performance on various applications.
arXiv Detail & Related papers (2023-10-10T00:21:10Z) - Constrained Environment Optimization for Prioritized Multi-Agent
Navigation [11.473177123332281]
This paper aims to consider the environment as a decision variable in a system-level optimization problem.
We propose novel problems of unprioritized and prioritized environment optimization.
We show, through formal proofs, under which conditions the environment can change while guaranteeing completeness.
arXiv Detail & Related papers (2023-05-18T18:55:06Z) - Environment Optimization for Multi-Agent Navigation [11.473177123332281]
The goal of this paper is to consider the environment as a decision variable in a system-level optimization problem.
We show, through formal proofs, under which conditions the environment can change while guaranteeing completeness.
In order to accommodate a broad range of implementation scenarios, we include both online and offline optimization, and both discrete and continuous environment representations.
arXiv Detail & Related papers (2022-09-22T19:22:16Z) - Optimizing Indoor Navigation Policies For Spatial Distancing [8.635212273689273]
In this paper, we focus on the modification of policies that can lead to movement patterns and directional guidance of occupants.
We show that within our framework, the simulation-optimization process can help to improve spatial distancing between agents.
arXiv Detail & Related papers (2022-06-04T21:57:22Z) - MetaAlign: Coordinating Domain Alignment and Classification for
Unsupervised Domain Adaptation [84.90801699807426]
This paper proposes an effective meta-optimization based strategy dubbed MetaAlign.
We treat the domain alignment objective and the classification objective as the meta-train and meta-test tasks in a meta-learning scheme.
Experimental results demonstrate the effectiveness of our proposed method on top of various alignment-based baseline approaches.
arXiv Detail & Related papers (2021-03-25T03:16:05Z) - Distributed Multi-agent Meta Learning for Trajectory Design in Wireless
Drone Networks [151.27147513363502]
This paper studies the problem of the trajectory design for a group of energyconstrained drones operating in dynamic wireless network environments.
A value based reinforcement learning (VDRL) solution and a metatraining mechanism is proposed.
arXiv Detail & Related papers (2020-12-06T01:30:12Z) - Decentralized MCTS via Learned Teammate Models [89.24858306636816]
We present a trainable online decentralized planning algorithm based on decentralized Monte Carlo Tree Search.
We show that deep learning and convolutional neural networks can be employed to produce accurate policy approximators.
arXiv Detail & Related papers (2020-03-19T13:10:20Z) - Dynamic Federated Learning [57.14673504239551]
Federated learning has emerged as an umbrella term for centralized coordination strategies in multi-agent environments.
We consider a federated learning model where at every iteration, a random subset of available agents perform local updates based on their data.
Under a non-stationary random walk model on the true minimizer for the aggregate optimization problem, we establish that the performance of the architecture is determined by three factors, namely, the data variability at each agent, the model variability across all agents, and a tracking term that is inversely proportional to the learning rate of the algorithm.
arXiv Detail & Related papers (2020-02-20T15:00:54Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.