Clique Analysis and Bypassing in Continuous-Time Conflict-Based Search
- URL: http://arxiv.org/abs/2312.16106v1
- Date: Tue, 26 Dec 2023 16:21:15 GMT
- Title: Clique Analysis and Bypassing in Continuous-Time Conflict-Based Search
- Authors: Thayne T. Walker, Nathan R. Sturtevant and Ariel Felner
- Abstract summary: This paper studies symmetry-breaking enhancements for Continuous-Time Conflict-Based Search (CCBS)
We adapt known enhancements from unit-cost domains for CCBS: bypassing, which resolves cost symmetries and biclique constraints which resolve spatial conflict symmetries.
We show empirically that these enhancements yield a statistically significant performance improvement versus previous state of the art, solving problems for up to 10% or 20% more agents in the same amount of time on dense graphs.
- Score: 19.1809369667358
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: While the study of unit-cost Multi-Agent Pathfinding (MAPF) problems has been
popular, many real-world problems require continuous time and costs due to
various movement models. In this context, this paper studies symmetry-breaking
enhancements for Continuous-Time Conflict-Based Search (CCBS), a solver for
continuous-time MAPF. Resolving conflict symmetries in MAPF can require an
exponential amount of work. We adapt known enhancements from unit-cost domains
for CCBS: bypassing, which resolves cost symmetries and biclique constraints
which resolve spatial conflict symmetries. We formulate a novel combination of
biclique constraints with disjoint splitting for spatial conflict symmetries.
Finally, we show empirically that these enhancements yield a statistically
significant performance improvement versus previous state of the art, solving
problems for up to 10% or 20% more agents in the same amount of time on dense
graphs.
Related papers
- Multi-Source and Test-Time Domain Adaptation on Multivariate Signals using Spatio-Temporal Monge Alignment [59.75420353684495]
Machine learning applications on signals such as computer vision or biomedical data often face challenges due to the variability that exists across hardware devices or session recordings.
In this work, we propose Spatio-Temporal Monge Alignment (STMA) to mitigate these variabilities.
We show that STMA leads to significant and consistent performance gains between datasets acquired with very different settings.
arXiv Detail & Related papers (2024-07-19T13:33:38Z) - Dimension-free Relaxation Times of Informed MCMC Samplers on Discrete Spaces [5.075066314996696]
We develop general mixing time bounds for Metropolis-Hastings algorithms on discrete spaces.
We establish sufficient conditions for a class of informed Metropolis-Hastings algorithms to attain relaxation times independent of the problem dimension.
arXiv Detail & Related papers (2024-04-05T02:40:45Z) - TFMQ-DM: Temporal Feature Maintenance Quantization for Diffusion Models [52.454274602380124]
Diffusion models heavily depend on the time-step $t$ to achieve satisfactory multi-round denoising.
We propose a Temporal Feature Maintenance Quantization (TFMQ) framework building upon a Temporal Information Block.
Powered by the pioneering block design, we devise temporal information aware reconstruction (TIAR) and finite set calibration (FSC) to align the full-precision temporal features.
arXiv Detail & Related papers (2023-11-27T12:59:52Z) - A Multi-Scale Decomposition MLP-Mixer for Time Series Analysis [14.40202378972828]
We propose MSD-Mixer, a Multi-Scale Decomposition-Mixer, which learns to explicitly decompose and represent the input time series in its different layers.
We demonstrate that MSD-Mixer consistently and significantly outperforms other state-of-the-art algorithms with better efficiency.
arXiv Detail & Related papers (2023-10-18T13:39:07Z) - Robust Detection of Lead-Lag Relationships in Lagged Multi-Factor Models [61.10851158749843]
Key insights can be obtained by discovering lead-lag relationships inherent in the data.
We develop a clustering-driven methodology for robust detection of lead-lag relationships in lagged multi-factor models.
arXiv Detail & Related papers (2023-05-11T10:30:35Z) - Beyond Exponentially Fast Mixing in Average-Reward Reinforcement
Learning via Multi-Level Monte Carlo Actor-Critic [61.968469104271676]
We propose an RL methodology attuned to the mixing time by employing a multi-level Monte Carlo estimator for the critic, the actor, and the average reward embedded within an actor-critic (AC) algorithm.
We experimentally show that these alleviated restrictions on the technical conditions required for stability translate to superior performance in practice for RL problems with sparse rewards.
arXiv Detail & Related papers (2023-01-28T04:12:56Z) - Continual Learning In Environments With Polynomial Mixing Times [13.533984338434106]
We study the effect of mixing times on learning in continual reinforcement learning.
We propose a family of model-based algorithms that speed up learning by directly optimizing for the average reward.
arXiv Detail & Related papers (2021-12-13T23:41:56Z) - Pairwise Symmetry Reasoning for Multi-Agent Path Finding Search [43.40580211016752]
Multi-Agent Path Finding (MAPF) is a challenging problem that asks us to plan collision-free paths for a team of cooperative agents.
We show that one of the reasons why MAPF is so hard to solve is due to a phenomenon called pairwise symmetry.
We propose a variety of reasoning techniques that detect the symmetries efficiently as they arise and resolve them by using specialized constraints.
arXiv Detail & Related papers (2021-03-12T07:27:35Z) - Improving Continuous-time Conflict Based Search [19.36475688888736]
Conflict-Based Search (CBS) is a powerful framework for optimally solving multi-agent path finding (MAPF) problems.
Continuous-time CBS (CCBS) is a recently proposed version of CBS that guarantees optimal solutions without the need to discretize time.
We show how to adapt successful CBS improvements, namely, prioritizing conflicts (PC), disjoint splitting (DS), and high-levelagents, to the continuous time setting of CCBS.
arXiv Detail & Related papers (2021-01-24T14:34:25Z) - Global Convergence of Policy Gradient for Linear-Quadratic Mean-Field
Control/Game in Continuous Time [109.06623773924737]
We study the policy gradient method for the linear-quadratic mean-field control and game.
We show that it converges to the optimal solution at a linear rate, which is verified by a synthetic simulation.
arXiv Detail & Related papers (2020-08-16T06:34:11Z) - Upper Confidence Primal-Dual Reinforcement Learning for CMDP with
Adversarial Loss [145.54544979467872]
We consider online learning for episodically constrained Markov decision processes (CMDPs)
We propose a new emphupper confidence primal-dual algorithm, which only requires the trajectories sampled from the transition model.
Our analysis incorporates a new high-probability drift analysis of Lagrange multiplier processes into the celebrated regret analysis of upper confidence reinforcement learning.
arXiv Detail & Related papers (2020-03-02T05:02:23Z)
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.