Subdimensional Expansion for Multi-objective Multi-agent Path Finding
- URL: http://arxiv.org/abs/2102.01353v1
- Date: Tue, 2 Feb 2021 06:58:28 GMT
- Title: Subdimensional Expansion for Multi-objective Multi-agent Path Finding
- Authors: Zhongqiang Ren, Sivakumar Rathinam and Howie Choset
- Abstract summary: 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.
- Score: 10.354181009277623
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Conventional multi-agent path planners typically determine a path that
optimizes 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. Often, these criteria may not
be readily compared and sometimes lie in competition with each other. Simply
applying standard multi-objective search algorithms to multi-agent path finding
may prove to be inefficient because 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 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. One example
of subdimensional expansion, when applied to A*, is called M* and M* was
limited to a single objective function. We combine principles of dominance and
subdimensional expansion to create a new algorithm named multi-objective M*
(MOM*), which dynamically couples agents for planning only when those agents
have to "interact" with each other. MOM* computes the complete Pareto-optimal
set for multiple agents efficiently and naturally trades off sub-optimal
approximations of the Pareto-optimal set and computational efficiency. Our
approach is able to find the complete Pareto-optimal set for problem instances
with hundreds of solutions which the standard multi-objective A* algorithms
could not find within a bounded time.
Related papers
- 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) - Scalable Mechanism Design for Multi-Agent Path Finding [87.40027406028425]
Multi-Agent Path Finding (MAPF) involves determining paths for multiple agents to travel simultaneously and collision-free through a shared area toward given goal locations.
Finding an optimal solution is often computationally infeasible, making the use of approximate, suboptimal algorithms essential.
We introduce the problem of scalable mechanism design for MAPF and propose three strategyproof mechanisms, two of which even use approximate MAPF algorithms.
arXiv Detail & Related papers (2024-01-30T14:26:04Z) - 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) - Enhanced Multi-Objective A* with Partial Expansion [22.45142249108214]
Multi-Objective Shortest Path Problem (MO-SPP), typically posed on a graph, determines a set of paths while optimizing multiple objectives.
To address this problem, several Multi-Objective A* (MOA*) algorithms were recently developed to quickly compute solutions with quality guarantees.
This work thus aims at reducing the high memory consumption of MOA* with little increase in the runtime.
arXiv Detail & Related papers (2022-12-06T05:48:11Z) - 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) - Pareto Navigation Gradient Descent: a First-Order Algorithm for
Optimization in Pareto Set [17.617944390196286]
Modern machine learning applications, such as multi-task learning, require finding optimal model parameters to trade-off multiple objective functions.
We propose a first-order algorithm that approximately solves OPT-in-Pareto using only gradient information.
arXiv Detail & Related papers (2021-10-17T04:07:04Z) - Multi-objective Conflict-based Search for Multi-agent Path Finding [10.354181009277623]
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.
arXiv Detail & Related papers (2021-01-11T10:42:38Z) - Online Model Selection for Reinforcement Learning with Function
Approximation [50.008542459050155]
We present a meta-algorithm that adapts to the optimal complexity with $tildeO(L5/6 T2/3)$ regret.
We also show that the meta-algorithm automatically admits significantly improved instance-dependent regret bounds.
arXiv Detail & Related papers (2020-11-19T10:00:54Z) - Decomposition in Decision and Objective Space for Multi-Modal
Multi-Objective Optimization [15.681236469530397]
Multi-modal multi-objective optimization problems (MMMOPs) have multiple subsets within the Pareto-optimal Set.
Prevalent multi-objective evolutionary algorithms are not purely designed to search for multiple solution subsets, whereas, algorithms designed for MMMOPs demonstrate degraded performance in the objective space.
This motivates the design of better algorithms for addressing MMMOPs.
arXiv Detail & Related papers (2020-06-04T03:18:47Z) - 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.