skip to main content


Title: 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
Award ID(s):
1734419 1617744
NSF-PAR ID:
10111589
Author(s) / Creator(s):
; ;
Date Published:
Journal Name:
International Workshop on the Algorithmic Foundations of Robotics
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. 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
  2. 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
  3. A great number of robotics applications demand the rearrangement of many mobile objects, for example, organizing products on store shelves, shuffling containers at shipping ports, reconfiguring fleets of mobile robots, and so on. To boost the efficiency/throughput in systems designed for solving these rearrangement problems, it is essential to minimize the number of atomic operations that are involved, for example, the pick-n-places of individual objects. However, this optimization task poses a rather difficult challenge due to the complex inter-dependency between the objects, especially when they are tightly packed together. In this work, in tackling the aforementioned challenges, we have developed a novel algorithmic tool, called Rubik Tables, that provides a clean abstraction of object rearrangement problems as the proxy problem of shuffling items stored in a table or lattice. In its basic form, a Rubik Table is an n × n table containing n2items. We show that the reconfiguration of items in such a Rubik Table can be achieved using at most n column and n row shuffles in the partially labeled setting, where each column (resp., row) shuffle may arbitrarily permute the items stored in a column (resp., row) of the table. When items are fully distinguishable, additional n shuffles are needed. Rubik Tables allow many generalizations, for example, adding an additional depth dimension or extending to higher dimensions. Using Rubik Table results, we have designed a first constant-factor optimal algorithm for stack rearrangement problems where items are stored in stacks, accessible only from the top. We show that, for nd items stored in n stacks of depth d each, using one empty stack as the swap space, O( nd) stack pop-push operations are sufficient for an arbitrary reconfiguration of the stacks where [Formula: see text] for arbitrary fixed m > 0. Rubik Table results also allow the development of constant-factor optimal solutions for solving multi-robot motion planning problems under extreme robot density. These algorithms based on Rubik Table results run in low-polynomial time.

     
    more » « less
  4. 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
  5. null (Ed.)
    ABSTRACT We investigate mass ejection from accretion discs formed in mergers of black holes (BHs) and neutron stars (NSs). The third observing run of the LIGO/Virgo interferometers provided BH–NS candidate events that yielded no electromagnetic (EM) counterparts. The broad range of disc configurations expected from BH–NS mergers motivates a thorough exploration of parameter space to improve EM signal predictions. Here we conduct 27 high-resolution, axisymmetric, long-term hydrodynamic simulations of the viscous evolution of BH accretion discs that include neutrino emission/absorption effects and post-processing with a nuclear reaction network. In the absence of magnetic fields, these simulations provide a lower limit to the fraction of the initial disc mass ejected. We find a nearly linear inverse dependence of this fraction on disc compactness (BH mass over initial disc radius). The dependence is related to the fraction of the disc mass accreted before the ouflow is launched, which depends on the disc position relative to the innermost stable circular orbit. We also characterize a trend of decreasing ejected fraction and decreasing lanthanide/actinide content with increasing disc mass at fixed BH mass. This trend results from a longer time to reach weak freezout and an increasingly dominant role of neutrino absorption at higher disc masses. We estimate the radioactive luminosity from the disc outflow alone available to power kilonovae over the range of configurations studied, finding a spread of two orders of magnitude. For most of the BH–NS parameter space, the disc outflow contribution is well below the kilonova mass upper limits for GW190814. 
    more » « less