Improving Continuous-time Conflict Based Search

• URL: http://arxiv.org/abs/2101.09723v2
• Date: Tue, 2 Mar 2021 18:37:38 GMT
• Title: Improving Continuous-time Conflict Based Search
• Authors: Anton Andreychuk, Konstantin Yakovlev, Eli Boyarski and Roni Stern
• Abstract summary: 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.
• Score: 19.36475688888736
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Conflict-Based Search (CBS) is a powerful algorithmic framework for optimally solving classical multi-agent path finding (MAPF) problems, where time is discretized into the time steps. Continuous-time CBS (CCBS) is a recently proposed version of CBS that guarantees optimal solutions without the need to discretize time. However, the scalability of CCBS is limited because it does not include any known improvements of CBS. In this paper, we begin to close this gap and explore how to adapt successful CBS improvements, namely, prioritizing conflicts (PC), disjoint splitting (DS), and high-level heuristics, to the continuous time setting of CCBS. These adaptions are not trivial, and require careful handling of different types of constraints, applying a generalized version of the Safe interval path planning (SIPP) algorithm, and extending the notion of cardinal conflicts. We evaluate the effect of the suggested enhancements by running experiments both on general graphs and $2^k$-neighborhood grids. CCBS with these improvements significantly outperforms vanilla CCBS, solving problems with almost twice as many agents in some cases and pushing the limits of multiagent path finding in continuous-time domains.

Related papers

• Multi-agent Path Finding in Continuous Environment [11.325849006178737]
  A new Continuous Environment Conflict-Based Search (CE-CBS) algorithm is proposed in this work. CE-CBS combines conflict-based search (CBS) for the high-level search framework with RRT* for low-level path planning. Experimental results show that CE-CBS is competitive w.r.t. to other algorithms that consider continuous aspect in MAPF with continuous time.
  arXiv  Detail & Related papers  (2024-09-16T19:23:04Z)
• Last-Iterate Global Convergence of Policy Gradients for Constrained Reinforcement Learning [62.81324245896717]
  We introduce an exploration-agnostic algorithm, called C-PG, which exhibits global last-ite convergence guarantees under (weak) gradient domination assumptions. We numerically validate our algorithms on constrained control problems, and compare them with state-of-the-art baselines.
  arXiv  Detail & Related papers  (2024-07-15T14:54:57Z)
• Decision-focused Graph Neural Networks for Combinatorial Optimization [62.34623670845006]
  An emerging strategy to tackle optimization problems involves the adoption of graph neural networks (GNNs) as an alternative to traditional algorithms. Despite the growing popularity of GNNs and traditional algorithm solvers in the realm of CO, there is limited research on their integrated use and the correlation between them within an end-to-end framework. We introduce a decision-focused framework that utilizes GNNs to address CO problems with auxiliary support.
  arXiv  Detail & Related papers  (2024-06-05T22:52:27Z)
• ITA-ECBS: A Bounded-Suboptimal Algorithm for the Combined Target-Assignment and Path-Finding Problem [20.090818762687565]
  We introduce ITA-ECBS, the first bounded-suboptimal variant of ITA-CBS. We show that it runs faster than ECBS-TA in 87.42% of 54,033 test cases.
  arXiv  Detail & Related papers  (2024-04-08T06:36:42Z)
• On Pitfalls of Test-Time Adaptation [82.8392232222119]
  Test-Time Adaptation (TTA) has emerged as a promising approach for tackling the robustness challenge under distribution shifts. We present TTAB, a test-time adaptation benchmark that encompasses ten state-of-the-art algorithms, a diverse array of distribution shifts, and two evaluation protocols.
  arXiv  Detail & Related papers  (2023-06-06T09:35:29Z)
• Analysis Of The Anytime MAPF Solvers Based On The Combination Of Conflict-Based Search (CBS) and Focal Search (FS) [2.320417845168326]
  Conflict-Based Search (CBS) is a widely used algorithm for solving multi-agent pathfinding problems optimally. To trade-off optimality for running time different variants of bounded sub-optimal CBS were designed. We show that Focal Search on both levels of CBS can be beneficial in a wide range of setups.
  arXiv  Detail & Related papers  (2022-09-20T11:05:14Z)
• Doubly Robust Off-Policy Actor-Critic: Convergence and Optimality [131.45028999325797]
  We develop a doubly robust off-policy AC (DR-Off-PAC) for discounted MDP. DR-Off-PAC adopts a single timescale structure, in which both actor and critics are updated simultaneously with constant stepsize. We study the finite-time convergence rate and characterize the sample complexity for DR-Off-PAC to attain an $epsilon$-accurate optimal policy.
  arXiv  Detail & Related papers  (2021-02-23T18:56:13Z)
• Optimization Issues in KL-Constrained Approximate Policy Iteration [48.24321346619156]
  Many reinforcement learning algorithms can be seen as versions of approximate policy iteration (API) While standard API often performs poorly, it has been shown that learning can be stabilized by regularizing each policy update by the KL-divergence to the previous policy. Popular practical algorithms such as TRPO, MPO, and VMPO replace regularization by a constraint on KL-divergence of consecutive policies.
  arXiv  Detail & Related papers  (2021-02-11T19:35:33Z)
• EECBS: A Bounded-Suboptimal Search for Multi-Agent Path Finding [40.0986954496361]
  Explicit Estimation CBS (EECBS) is a bounded-suboptimal variant of CBS that uses online learning to obtain inadmissible estimates of the cost of the solution of each high-level node. EECBS runs significantly faster than the state-of-the-art bounded-suboptimal MAPF algorithms ECBS, BCP-7, and eMDD-SAT on a variety of MAPF instances.
  arXiv  Detail & Related papers  (2020-10-03T14:19:00Z)
• Multi Agent Path Finding with Awareness for Spatially Extended Agents [0.5156484100374058]
  Path finding problems involve identification of a plan for conflict free movement of agents over a common road network. In this paper, we consider spatially extended agents which have a size comparable to the length of the road on which they travel. An optimal multi agent path finding approach for spatially-extended agents was proposed in the eXtended Conflict Based Search (XCBS) algorithm.
  arXiv  Detail & Related papers  (2020-09-20T05:40:04Z)
• Bottom-Up Temporal Action Localization with Mutual Regularization [107.39785866001868]
  State-of-the-art solutions for TAL involve evaluating the frame-level probabilities of three action-indicating phases. We introduce two regularization terms to mutually regularize the learning procedure. Experiments are performed on two popular TAL datasets, THUMOS14 and ActivityNet1.3.
  arXiv  Detail & Related papers  (2020-02-18T03:59:13Z)

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.