Multi-objective Conflict-based Search for Multi-agent Path Finding

• URL: http://arxiv.org/abs/2101.03805v2
• Date: Tue, 23 Mar 2021 06:19:25 GMT
• Title: Multi-objective Conflict-based Search for Multi-agent Path Finding
• Authors: Zhongqiang Ren, Sivakumar Rathinam and Howie Choset
• Abstract summary: Multi-objective path planners typically compute an ensemble of paths while optimizing a single objective, such as path length. This article presents an approach named Multi-objective Conflict-based Search (MO-CBS) that bypasses this so-called curse of dimensionality.
• Score: 10.354181009277623
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Conventional multi-agent path planners typically compute an ensemble of paths while optimizing a single objective, such as path length. However, many applications may require multiple objectives, say fuel consumption and completion time, to be simultaneously optimized during planning and these criteria may not be readily compared and sometimes lie in competition with each other. Naively applying existing multi-objective search algorithms to multi-agent path finding may prove to be inefficient as the size of the space of possible solutions, i.e., the Pareto-optimal set, can grow exponentially with the number of agents (the dimension of the search space). This article presents an approach named Multi-objective Conflict-based Search (MO-CBS) that bypasses this so-called curse of dimensionality by leveraging prior Conflict-based Search (CBS), a well-known algorithm for single-objective multi-agent path finding, and principles of dominance from multi-objective optimization literature. We prove that MO-CBS is able to compute the entire Pareto-optimal set. Our results show that MO-CBS can solve problem instances with hundreds of Pareto-optimal solutions which the standard multi-objective A* algorithms could not find within a bounded time.

Related papers

• Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
  We introduce a novel greedy-style subset selection algorithm for batch acquisition. Our experiments on the red fluorescent proteins show that our proposed method achieves the baseline performance in 1.69x fewer queries.
  arXiv  Detail & Related papers  (2024-06-21T05:57:08Z)
• UCB-driven Utility Function Search for Multi-objective Reinforcement Learning [75.11267478778295]
  In Multi-objective Reinforcement Learning (MORL) agents are tasked with optimising decision-making behaviours. We focus on the case of linear utility functions parameterised by weight vectors w. We introduce a method based on Upper Confidence Bound to efficiently search for the most promising weight vectors during different stages of the learning process.
  arXiv  Detail & Related papers  (2024-05-01T09:34:42Z)
• MGCBS: An Optimal and Efficient Algorithm for Solving Multi-Goal Multi-Agent Path Finding Problem [5.580214316179672]
  The MG-MAPF problem requires each agent to visit pre-assigned multiple goal points at least once without conflict. We propose the Multi-Goal Conflict-Based Search (MGCBS), which is based on Decoupling the goal Safe interval visiting order search and the Single-agent pathfinding. Our method can consistently obtain optimal results and execute up to 7 times faster than the state-of-the-art method in our evaluation.
  arXiv  Detail & Related papers  (2024-04-30T12:49:54Z)
• Factorization of Multi-Agent Sampling-Based Motion Planning [72.42734061131569]
  Modern robotics often involves multiple embodied agents operating within a shared environment. Standard sampling-based algorithms can be used to search for solutions in the robots' joint space. We integrate the concept of factorization into sampling-based algorithms, which requires only minimal modifications to existing methods. We present a general implementation of a factorized SBA, derive an analytical gain in terms of sample complexity for PRM*, and showcase empirical results for RRG.
  arXiv  Detail & Related papers  (2023-04-01T15:50:18Z)
• A Scale-Independent Multi-Objective Reinforcement Learning with Convergence Analysis [0.6091702876917281]
  Many sequential decision-making problems need optimization of different objectives which possibly conflict with each other. We develop a single-agent scale-independent multi-objective reinforcement learning on the basis of the Advantage Actor-Critic (A2C) algorithm. A convergence analysis is then done for the devised multi-objective algorithm providing a convergence-in-mean guarantee.
  arXiv  Detail & Related papers  (2023-02-08T16:38:55Z)
• Multi-Objective Quality Diversity Optimization [2.4608515808275455]
  We propose an extension of the MAP-Elites algorithm in the multi-objective setting: Multi-Objective MAP-Elites (MOME) Namely, it combines the diversity inherited from the MAP-Elites grid algorithm with the strength of multi-objective optimizations. We evaluate our method on several tasks, from standard optimization problems to robotics simulations.
  arXiv  Detail & Related papers  (2022-02-07T10:48:28Z)
• Multi-objective Conflict-based Search Using Safe-interval Path Planning [10.354181009277623]
  We present a new multi-objective conflict-based search (MO-CBS) approach that relies on a novel multi-objective safe interval path planning (MO-SIPP) algorithm for its low-level search. We present extensive numerical results to show that there is an order of magnitude improvement in the average low level search time. We also provide a case study to demonstrate the potential application of the proposed algorithms for construction site planning.
  arXiv  Detail & Related papers  (2021-08-02T09:42:08Z)
• Subdimensional Expansion for Multi-objective Multi-agent Path Finding [10.354181009277623]
  Multi-agent path planners typically determine a path that optimize a single objective, such as path length. Many applications, however, may require multiple objectives, say time-to-completion and fuel use, to be simultaneously optimized in the planning process. This paper presents an approach that bypasses this so-called curse of dimensionality by leveraging our prior multi-agent work with a framework called subdimensional expansion.
  arXiv  Detail & Related papers  (2021-02-02T06:58:28Z)
• Provable Multi-Objective Reinforcement Learning with Generative Models [98.19879408649848]
  We study the problem of single policy MORL, which learns an optimal policy given the preference of objectives. Existing methods require strong assumptions such as exact knowledge of the multi-objective decision process. We propose a new algorithm called model-based envelop value (EVI) which generalizes the enveloped multi-objective $Q$-learning algorithm.
  arXiv  Detail & Related papers  (2020-11-19T22:35:31Z)
• Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal Constraints [52.58352707495122]
  We present a multi-robot allocation algorithm that decouples the key computational challenges of sequential decision-making under uncertainty and multi-agent coordination. We validate our results over a wide range of simulations on two distinct domains: multi-arm conveyor belt pick-and-place and multi-drone delivery dispatch in a city.
  arXiv  Detail & Related papers  (2020-05-27T01:10:41Z)
• Pareto Multi-Task Learning [53.90732663046125]
  Multi-task learning is a powerful method for solving multiple correlated tasks simultaneously. It is often impossible to find one single solution to optimize all the tasks, since different tasks might conflict with each other. Recently, a novel method is proposed to find one single Pareto optimal solution with good trade-off among different tasks by casting multi-task learning as multiobjective optimization.
  arXiv  Detail & Related papers  (2019-12-30T08:58:40Z)

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.