Constrained Environment Optimization for Prioritized Multi-Agent Navigation

• URL: http://arxiv.org/abs/2305.11260v1
• Date: Thu, 18 May 2023 18:55:06 GMT
• Title: Constrained Environment Optimization for Prioritized Multi-Agent Navigation
• Authors: Zhan Gao and Amanda Prorok
• Abstract summary: 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.
• Score: 11.473177123332281
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Co-Optimization of Environment and Policies for Decentralized Multi-Agent Navigation [14.533605727697775]
  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.
  arXiv  Detail & Related papers  (2024-03-21T17:37:43Z)
• End-to-End Learning for Fair Multiobjective Optimization Under Uncertainty [55.04219793298687]
  The Predict-Then-Forecast (PtO) paradigm in machine learning aims to maximize downstream decision quality. This paper extends the PtO methodology to optimization problems with nondifferentiable Ordered Weighted Averaging (OWA) objectives. It shows how optimization of OWA functions can be effectively integrated with parametric prediction for fair and robust optimization under uncertainty.
  arXiv  Detail & Related papers  (2024-02-12T16:33:35Z)
• 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)
• CAMEO: A Causal Transfer Learning Approach for Performance Optimization of Configurable Computer Systems [16.75106122540052]
  We propose CAMEO, a method that identifies invariant causal predictors under environmental changes. We demonstrate significant performance improvements over state-of-the-art optimization methods in MLperf deep learning systems, a video analytics pipeline, and a database system.
  arXiv  Detail & Related papers  (2023-06-13T16:28:37Z)
• 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)
• Multi-Objective Constrained Optimization for Energy Applications via Tree Ensembles [55.23285485923913]
  Energy systems optimization problems are complex due to strongly non-linear system behavior and multiple competing objectives. In some cases, proposed optimal solutions need to obey explicit input constraints related to physical properties or safety-critical operating conditions. This paper proposes a novel data-driven strategy using tree ensembles for constrained multi-objective optimization of black-box problems.
  arXiv  Detail & Related papers  (2021-11-04T20:18:55Z)
• Modeling the Second Player in Distributionally Robust Optimization [90.25995710696425]
  We argue for the use of neural generative models to characterize the worst-case distribution. This approach poses a number of implementation and optimization challenges. We find that the proposed approach yields models that are more robust than comparable baselines.
  arXiv  Detail & Related papers  (2021-03-18T14:26:26Z)
• Incremental Data-driven Optimization of Complex Systems in Nonstationary Environments [26.93254582875251]
  This paper proposes a data-driven optimization algorithm to deal with the challenges presented by the dynamic environments. First, a data stream ensemble learning method is adopted to train the surrogates so that each base learner of the ensemble learns the time-varying objective function in the previous environments. After that, a multi-task evolutionary algorithm is employed to simultaneously optimize the problems in the past environments assisted by the ensemble surrogate.
  arXiv  Detail & Related papers  (2020-12-14T02:55:42Z)
• Emergent Complexity and Zero-shot Transfer via Unsupervised Environment Design [121.73425076217471]
  We propose Unsupervised Environment Design (UED), where developers provide environments with unknown parameters, and these parameters are used to automatically produce a distribution over valid, solvable environments. We call our technique Protagonist Antagonist Induced Regret Environment Design (PAIRED) Our experiments demonstrate that PAIRED produces a natural curriculum of increasingly complex environments, and PAIRED agents achieve higher zero-shot transfer performance when tested in highly novel environments.
  arXiv  Detail & Related papers  (2020-12-03T17:37:01Z)
• Bilevel Optimization for Differentially Private Optimization in Energy Systems [53.806512366696275]
  This paper studies how to apply differential privacy to constrained optimization problems whose inputs are sensitive. The paper shows that, under a natural assumption, a bilevel model can be solved efficiently for large-scale nonlinear optimization problems.
  arXiv  Detail & Related papers  (2020-01-26T20:15:28Z)
• Optimizing Wireless Systems Using Unsupervised and Reinforced-Unsupervised Deep Learning [96.01176486957226]
  Resource allocation and transceivers in wireless networks are usually designed by solving optimization problems. In this article, we introduce unsupervised and reinforced-unsupervised learning frameworks for solving both variable and functional optimization problems.
  arXiv  Detail & Related papers  (2020-01-03T11:01:52Z)

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.