An official website of the United States government
Multi-Agent Path Finding (MAPF) is NP-hard to solve optimally, even on graphs, suggesting no polynomial-time algorithms can compute exact optimal solutions for them. This raises a natural question: How optimal can polynomial-time algorithms reach? Whereas algorithms for computing constant-factor optimal solutions have been developed, the constant factor is generally very large, limiting their application potential. In this work, among other breakthroughs, we propose the first low-polynomial-time MAPF algorithms delivering 1-1.5 (resp., 1-1.67) asymptotic makespan optimality guarantees for 2D (resp., 3D) grids for random instances at a very high 1/3 agent density, with high probability. Moreover, when regularly distributed obstacles are introduced, our methods experience no performance degradation. These methods generalize to support 100% agent density.Regardless of the dimensionality and density, our high-quality methods are enabled by a unique hierarchical integration of two key building blocks. At the higher level, we apply the labeled Grid Rearrangement Algorithm (GRA), capable of performing efficient reconfiguration on grids through row/column shuffles. At the lower level, we devise novel methods that efficiently simulate row/column shuffles returned by GRA. Our implementations of GRA-based algorithms are highly effective in extensive numerical evaluations, demonstrating excellent scalability compared to other SOTA methods. For example, in 3D settings, GRA-based algorithms readily scale to grids with over 370,000 vertices and over 120,000 agents and consistently achieve conservative makespan optimality approaching 1.5, as predicted by our theoretical analysis.
more »
« less
Coordinating the Motion of Labeled Discs with Optimality Guarantees under Extreme Density
We push the limit in planning collision-free motions for rout- ing uniform labeled discs in two dimensions. First, from a theoretical perspective, we show that the constant-factor time-optimal routing of labeled discs can be achieved using a polynomial-time algorithm with robot density over 50% in the limit (i.e., over half of the workspace may be occupied by the discs). Second, from a more practical standpoint, we provide a high performance algorithm that computes near-optimal (e.g., 1.x) solutions under the same density setting.
more »
« less
- PAR ID:
- 10111589
- Date Published:
- Journal Name:
- International Workshop on the Algorithmic Foundations of Robotics
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Let G = (V, E) be an m_1 \times \ldots \times m_k grid for some arbitrary constant k. We establish that O(\sum_{i=1}^km_i) (makespan) time-optimal labeled (i.e., each robot has a specific goal) multi-robot path planning can be realized on G in O(|V|^2) running time, even when vertices of G are fully occupied by robots. When all dimensions are of equal sizes, the running time approaches O(|V|). Using this base line algorithm, which provides average case O(1)-approximate (i.e., constant-factor) time-optimal solutions, we further develop a first worst case O(1)-approximate algorithm that again runs in O(|V|^2) time for two and three dimensions. We note that the problem has a worst case running time lower bound of \Omega(|V|^2).more » « less
-
ABSTRACT Stars embedded in active galactic nucleus (AGN) discs or captured by them may scatter onto the supermassive black hole (SMBH), leading to a tidal disruption event (TDE). Using the moving-mesh hydrodynamics simulations with arepo, we investigate the dependence of debris properties in in-plane TDEs in AGN discs on the disc density and the orientation of stellar orbits relative to the disc gas (pro- and retro-grade). Key findings are: (1) Debris experiences continuous perturbations from the disc gas, which can result in significant and continuous changes in debris energy and angular momentum compared to ‘naked’ TDEs. (2) Above a critical density of a disc around an SMBH with mass M• [ρcrit ∼ 10−8 g cm−3 (M•/106 M⊙)−2.5] for retrograde stars, both bound and unbound debris is fully mixed into the disc. The density threshold for no bound debris return, inhibiting the accretion component of TDEs, is $$\rho _{\rm crit,bound} \sim 10^{-9}{\rm g~cm^{-3}}(M_{\bullet }/10^{6}\, {\rm M}_{\odot })^{-2.5}$$. (3) Observationally, AGN-TDEs transition from resembling naked TDEs in the limit of ρdisc ≲ 10−2ρcrit,bound to fully muffled TDEs with associated inner disc state changes at ρdisc ≳ ρcrit,bound, with a superposition of AGN + TDE in between. Stellar or remnant passages themselves can significantly perturb the inner disc. This can lead to an immediate X-ray signature and optically detectable inner disc state changes, potentially contributing to the changing-look AGN phenomenon. (4) Debris mixing can enrich the average disc metallicity over time if the star’s metallicity exceeds that of the disc gas. We point out that signatures of AGN-TDEs may be found in large AGN surveys.more » « less
-
Quantum technologies are maturing by the day and their near-term applications are now of great interest. Deep-space optical communication involves transmission over the pure-state classical-quantum channel. For optimal detection, a joint measurement on all output qubits is required in general. Since this is hard to realize, current (sub-optimal) schemes perform symbol-by-symbol detection followed by classical post-processing. In this paper we focus on a recently proposed belief propagation algorithm by Renes that passes qubit messages on the factor graph of a classical error-correcting code. More importantly, it only involves single-qubit Pauli measurements during the process. For an example 5-bit code, we analyze the involved density matrices and calculate the error probabilities on this channel. Then we numerically compute the optimal joint detection limit using the Yuen-Kennedy-Lax conditions and demonstrate that the calculated error probabilities for this algorithm appear to achieve this limit. This represents a first step towards achieveing quantum communication advantage. We verify our analysis using Monte-Carlo simulations in practice.more » « less
-
Dyck-reachability is a fundamental formulation for program analysis, which has been widely used to capture properly-matched-parenthesis program properties such as function calls/returns and field writes/reads. Bidirected Dyck-reachability is a relaxation of Dyck-reachability on bidirected graphs where each edge u → ( i v labeled by an open parenthesis “( i ” is accompanied with an inverse edge v → ) i u labeled by the corresponding close parenthesis “) i ”, and vice versa. In practice, many client analyses such as alias analysis adopt the bidirected Dyck-reachability formulation. Bidirected Dyck-reachability admits an optimal reachability algorithm. Specifically, given a graph with n nodes and m edges, the optimal bidirected Dyck-reachability algorithm computes all-pairs reachability information in O ( m ) time. This paper focuses on the dynamic version of bidirected Dyck-reachability. In particular, we consider the problem of maintaining all-pairs Dyck-reachability information in bidirected graphs under a sequence of edge insertions and deletions. Dynamic bidirected Dyck-reachability can formulate many program analysis problems in the presence of code changes. Unfortunately, solving dynamic graph reachability problems is challenging. For example, even for maintaining transitive closure, the fastest deterministic dynamic algorithm requires O ( n 2 ) update time to achieve O (1) query time. All-pairs Dyck-reachability is a generalization of transitive closure. Despite extensive research on incremental computation, there is no algorithmic development on dynamic graph algorithms for program analysis with worst-case guarantees. Our work fills the gap and proposes the first dynamic algorithm for Dyck reachability on bidirected graphs. Our dynamic algorithms can handle each graph update ( i.e. , edge insertion and deletion) in O ( n ·α( n )) time and support any all-pairs reachability query in O (1) time, where α( n ) is the inverse Ackermann function. We have implemented and evaluated our dynamic algorithm on an alias analysis and a context-sensitive data-dependence analysis for Java. We compare our dynamic algorithms against a straightforward approach based on the O ( m )-time optimal bidirected Dyck-reachability algorithm and a recent incremental Datalog solver. Experimental results show that our algorithm achieves orders of magnitude speedup over both approaches.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
