Pushing the Envelope: From Discrete to Continuous Movements in
Multi-Agent Path Finding via Lazy Encodings
- URL: http://arxiv.org/abs/2004.13477v1
- Date: Sat, 25 Apr 2020 13:21:32 GMT
- Title: Pushing the Envelope: From Discrete to Continuous Movements in
Multi-Agent Path Finding via Lazy Encodings
- Authors: Pavel Surynek
- Abstract summary: We introduce a novel solving approach for obtaining makespan optimal solutions called SMT-CBS$mathcalR$ based on em satisfiability modulo theories (SMT)
The new algorithm combines collision resolution known from conflict-based search (CBS) with previous generation of incomplete SAT encodings on top of a novel scheme for selecting decision variables in a potentially uncountable search space.
- Score: 15.99072005190786
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Multi-agent path finding in continuous space and time with geometric agents
MAPF$^\mathcal{R}$ is addressed in this paper. The task is to navigate agents
that move smoothly between predefined positions to their individual goals so
that they do not collide. We introduce a novel solving approach for obtaining
makespan optimal solutions called SMT-CBS$^\mathcal{R}$ based on {\em
satisfiability modulo theories} (SMT). The new algorithm combines collision
resolution known from conflict-based search (CBS) with previous generation of
incomplete SAT encodings on top of a novel scheme for selecting decision
variables in a potentially uncountable search space. We experimentally compare
SMT-CBS$^\mathcal{R}$ and previous CCBS algorithm for MAPF$^\mathcal{R}$.
Related papers
- Optimal and Bounded Suboptimal Any-Angle Multi-agent Pathfinding [13.296796764344169]
We present the first optimal any-angle multi-agent pathfinding algorithm.
Our planner is based on the Continuous Conflict-based Search (CCBS) algorithm and an optimal any-angle variant of the Safe Interval Path Planning (TO-AA-SIPP)
We adapt two techniques from classical MAPF to the any-angle setting, namely Disjoint Splitting and Multi-Constraints.
arXiv Detail & Related papers (2024-04-25T07:41:47Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
We study the Shortest Path (SSP) problem with a linear mixture transition kernel.
An agent repeatedly interacts with a environment and seeks to reach certain goal state while minimizing the cumulative cost.
Existing works often assume a strictly positive lower bound of the iteration cost function or an upper bound of the expected length for the optimal policy.
arXiv Detail & Related papers (2024-02-14T07:52:00Z) - Decentralized Monte Carlo Tree Search for Partially Observable
Multi-agent Pathfinding [49.730902939565986]
Multi-Agent Pathfinding problem involves finding a set of conflict-free paths for a group of agents confined to a graph.
In this study, we focus on the decentralized MAPF setting, where the agents may observe the other agents only locally.
We propose a decentralized multi-agent Monte Carlo Tree Search (MCTS) method for MAPF tasks.
arXiv Detail & Related papers (2023-12-26T06:57:22Z) - Monte-Carlo Tree Search for Multi-Agent Pathfinding: Preliminary Results [60.4817465598352]
We introduce an original variant of Monte-Carlo Tree Search (MCTS) tailored to multi-agent pathfinding.
Specifically, we use individual paths to assist the agents with the the goal-reaching behavior.
We also use a dedicated decomposition technique to reduce the branching factor of the tree search procedure.
arXiv Detail & Related papers (2023-07-25T12:33:53Z) - LaCAM: Search-Based Algorithm for Quick Multi-Agent Pathfinding [5.025654873456756]
We propose a novel complete algorithm for multi-agent pathfinding (MAPF) called lazy constraints addition search for MAPF (LaCAM)
LaCAM uses a two-level search to find solutions quickly, even with hundreds of agents or more.
Our experiments reveal that LaCAM is comparable to or outperforms state-of-the-art sub-optimal MAPF algorithms in a variety of scenarios.
arXiv Detail & Related papers (2022-11-24T06:27:18Z) - Multi-block-Single-probe Variance Reduced Estimator for Coupled
Compositional Optimization [49.58290066287418]
We propose a novel method named Multi-block-probe Variance Reduced (MSVR) to alleviate the complexity of compositional problems.
Our results improve upon prior ones in several aspects, including the order of sample complexities and dependence on strongity.
arXiv Detail & Related papers (2022-07-18T12:03:26Z) - Kernel Packet: An Exact and Scalable Algorithm for Gaussian Process
Regression with Mat\'ern Correlations [23.560067934682294]
We develop an exact and scalable algorithm for one-dimensional Gaussian process regression with Mat'ern correlations.
The proposed algorithm is significantly superior to the existing alternatives in both the computational time and predictive accuracy.
arXiv Detail & Related papers (2022-03-07T03:30:35Z) - Randomized Exploration for Reinforcement Learning with General Value
Function Approximation [122.70803181751135]
We propose a model-free reinforcement learning algorithm inspired by the popular randomized least squares value iteration (RLSVI) algorithm.
Our algorithm drives exploration by simply perturbing the training data with judiciously chosen i.i.d. scalar noises.
We complement the theory with an empirical evaluation across known difficult exploration tasks.
arXiv Detail & Related papers (2021-06-15T02:23:07Z) - Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
We investigate the active pure exploration problem in Markov Decision Processes.
Agent sequentially selects actions and, from the resulting system trajectory, aims at the best as fast as possible.
arXiv Detail & Related papers (2021-06-05T09:16:28Z) - Multi-Goal Multi-Agent Path Finding via Decoupled and Integrated Goal
Vertex Ordering [15.99072005190786]
We introduce multi-goal multi agent path finding (MAPF$MG$) which generalizes the standard discrete multi-agent path finding (MAPF) problem.
We suggest two novel algorithms using different paradigms to address MAPF$MG$: a search-based search algorithm called Hamiltonian-CBS (HCBS) and a compilation-based algorithm built using the SMT paradigm, called SMT-Hamiltonian-CBS (SMT-HCBS)
arXiv Detail & Related papers (2020-09-10T22:27:18Z)
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.