skip to main content


Title: Priority Evacuation from a Disk Using Mobile Robots
We introduce and study a new search-type problem with ( 𝑛+1 )-robots on a disk. The searchers (robots) all start from the center of the disk, have unit speed, and can communicate wirelessly. The goal is for a distinguished robot (the queen) to reach and evacuate from an exit that is hidden on the perimeter of the disk in as little time as possible. The remaining n robots (servants) are there to facilitate the queen’s objective and are not required to reach the hidden exit. We provide upper and lower bounds for the time required to evacuate the queen. Namely, we propose an algorithm specifying the trajectories of the robots which guarantees evacuation of the queen in time always better than 2+4(\sqrt{2}-1)\pi/n for 𝑛β‰₯4 servants. We also demonstrate that for 𝑛β‰₯4 servants the queen cannot be evacuated in time less than 2 + \pi/n + 2/n^2.  more » « less
Award ID(s):
1813940
NSF-PAR ID:
10092714
Author(s) / Creator(s):
; ; ; ; ; ; ;
Date Published:
Journal Name:
Lecture notes in computer science
Volume:
11085
ISSN:
0302-9743
Page Range / eLocation ID:
392 - 407
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Queen Daniela of Sardinia is asleep at the center of a round room at the top of the tower in her castle. She is accompanied by her faithful servant, Eva. Suddenly, they are awakened by cries of "Fire". The room is pitch black and they are disoriented. There is exactly one exit from the room somewhere along its boundary. They must find it as quickly as possible in order to save the life of the queen. It is known that with two people searching while moving at maximum speed 1 anywhere in the room, the room can be evacuated (i.e., with both people exiting) in 1 + (2 pi)/3 + sqrt{3} ~~ 4.8264 time units and this is optimal [Czyzowicz et al., DISC'14], assuming that the first person to find the exit can directly guide the other person to the exit using her voice. Somewhat surprisingly, in this paper we show that if the goal is to save the queen (possibly leaving Eva behind to die in the fire) there is a slightly better strategy. We prove that this "priority" version of evacuation can be solved in time at most 4.81854. Furthermore, we show that any strategy for saving the queen requires time at least 3 + pi/6 + sqrt{3}/2 ~~ 4.3896 in the worst case. If one or both of the queen's other servants (Biddy and/or Lili) are with her, we show that the time bounds can be improved to 3.8327 for two servants, and 3.3738 for three servants. Finally we show lower bounds for these cases of 3.6307 (two servants) and 3.2017 (three servants). The case of n >= 4 is the subject of an independent study by Queen Daniela's Royal Scientific Team. 
    more » « less
  2. null (Ed.)
    Multiple silicon solar cell technologies have surpassed or are close to surpassing 26% efficiency. Dielectric and amorphous silicon-based passivation layers combined with minimal metal/silicon contact areas were responsible for reducing the surface saturation current density below 3 fA cm βˆ’2 . At open-circuit, in passivated contact solar cells, the recombination is mainly from fundamental mechanisms (Auger and radiative) representing over 3/4 of the total recombination. At the maximum power point, the fundamental recombination fraction can drop to half, as surface and bulk Shockley–Read–Hall step in. As a result, to further increase the performance at the operating point, it is paramount to reduce the bulk dependence and secure proper surface passivation. Bulk recombination can be mitigated either by reducing bulk defect density or by reducing the wafer thickness. We demonstrate that for commercially-viable solar-grade silicon, thinner wafers and surface saturation current densities below 1 fA cm βˆ’2 , are required to significantly increase the practical efficiency limit of solar cells up to 0.6% absolute. For a high-quality n-type bulk silicon minority-carrier lifetime of 10 ms, the optimum wafer thickness range is 40–60 ΞΌm, a very different value from 110 ΞΌm previously calculated assuming undoped substrates and solely Auger and radiative recombination. In this thickness range surface saturation current densities near 0.1 fA cm βˆ’2 are required to narrow the gap towards the fundamental efficiency limit. We experimentally demonstrate surface saturation currents below 0.5 fA cm βˆ’2 on pi/CZ/in structures across different wafer thicknesses (35–170 ΞΌm), with potential to reach open-circuit voltages close to 770 mV and bandgap-voltage offsets near 350 mV. Finally, we use the bandgap-voltage offset as a metric to compare the quality of champion experimental solar cells in the literature, for the most commercially-relevant photovoltaic cell absorbers and architectures. 
    more » « less
  3. We consider evacuation of a group of n β‰₯ 2 autonomous mobile agents (or robots) from an unknown exit on an infinite line. The agents are initially placed at the origin of the line and can move with any speed up to the maximum speed 1 in any direction they wish and they all can communicate when they are co-located. However, the agents have different wireless communication abilities: while some are fully wireless and can send and receive messages at any distance, a subset of the agents are senders, they can only transmit messages wirelessly, and the rest are receivers, they can only receive messages wirelessly. The agents start at the same time and their communication abilities are known to each other from the start. Starting at the origin of the line, the goal of the agents is to collectively find a target/exit at an unknown location on the line while minimizing the evacuation time, defined as the time when the last agent reaches the target. We investigate the impact of such a mixed communication model on evacuation time on an infinite line for a group of cooperating agents. In particular, we provide evacuation algorithms and analyze the resulting competitive ratio (CR) of the evacuation time for such a group of agents. If the group has two agents of two different types, we give an optimal evacuation algorithm with competitive ratio CR = 3+2√2. If there is a single sender or fully wireless agent, and multiple receivers we prove that CR ∈ [2+√5,5], and if there are multiple senders and a single receiver or fully wireless agent, we show that CR ∈ [3,5.681319]. Any group consisting of only senders or only receivers requires competitive ratio 9, and any other combination of agents has competitive ratio 3. 
    more » « less
  4. Abstract We report on the internal distribution of star formation efficiency in IRAS 08339+6517 (hereafter IRAS08), using ∼200 pc resolution CO(2 βˆ’ 1) observations from NOEMA. The molecular gas depletion time changes by 2 orders-of-magnitude from disk-like values in the outer parts to less than 10 8 yr inside the half-light radius. This translates to a star formation efficiency per freefall time that also changes by 2 orders-of-magnitude, reaching 50%–100%, different than local spiral galaxies and the typical assumption of constant, low star formation efficiencies. Our target is a compact, massive disk galaxy that has a star formation rate 10Γ— above the z = 0 main sequence; Toomre Q β‰ˆ 0.5βˆ’0.7 and high gas velocity dispersion ( Οƒ mol β‰ˆ 25 km s βˆ’1 ). We find that IRAS08 is similar to other rotating, starburst galaxies from the literature in the resolved Ξ£ SFR ∝ Ξ£ mol N relation. By combining resolved literature studies we find that the distance from the main sequence is a strong indicator of the Kennicutt-Schmidt power-law slope, with slopes of N β‰ˆ 1.6 for starbursts from 100 to 10 4 M βŠ™ pc βˆ’2 . Our target is consistent with a scenario in which violent disk instabilities drive rapid inflows of gas. It has low values of Toomre- Q , and also at all radii, the inflow timescale of the gas is less than the depletion time, which is consistent with the flat metallicity gradients in IRAS08. We consider these results in light of popular star formation theories; in general observations of IRAS08 find the most tension with theories in which star formation efficiency is a constant. Our results argue for the need of high-spatial-resolution CO observations for a larger number of similar targets. 
    more » « less
  5. Given a set P of n weighted points and a set S of m disks in the plane, the hitting set problem is to compute a subset 𝑃′ of points of P such that each disk contains at least one point of 𝑃′ and the total weight of all points of 𝑃′ is minimized. The problem is known to be NP-hard. In this paper, we consider a line-constrained version of the problem in which all disks are centered on a line β„“. We present an 𝑂((π‘š+𝑛)log(π‘š+𝑛)+πœ…logπ‘š) time algorithm for the problem, where πœ… is the number of pairs of disks that intersect. For the unit-disk case where all disks have the same radius, the running time can be reduced to 𝑂((𝑛+π‘š)log(π‘š+𝑛)). In addition, we solve the problem in 𝑂((π‘š+𝑛)log(π‘š+𝑛)) time in the 𝐿∞ and 𝐿1 metrics, in which a disk is a square and a diamond, respectively. 
    more » « less