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.
; ; ; ; ; ; ;
Award ID(s):
Publication Date:
Journal Name:
Lecture notes in computer science
Page Range or eLocation-ID:
392 - 407
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 themore »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.« less
  2. 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.more »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.« less
  3. 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 violentmore »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.« less
  4. 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 competitivemore »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.« less
  5. Recently, over 200 molecules have been detected in the interstellar medium (ISM), with about one third being complex organic molecules (COMs), molecules containing six or more atoms. Over the last few decades, astrophysical laboratory experiments have shown that several COMs are formed via interaction of ionizing radiation within ices deposited on interstellar dust particles at 10 K (H 2 O, CH 3 OH, CO, CO 2 , CH 4 , NH 3 ). However, there is still a lack of understanding of the chemical complexity that is available through individual ice constituents. The present research investigates experimentally the synthesis of carbon, hydrogen, and oxygen bearing COMs from interstellar ice analogues containing carbon monoxide (CO) and methane (CH 4 ), ethane (C 2 H 6 ), ethylene (C 2 H 4 ), or acetylene (C 2 H 2 ) exposed to ionizing radiation. Utilizing online and in situ techniques, such as infrared spectroscopy and tunable photoionization reflectron time-of-flight mass spectrometry (PI-ReTOF-MS), specific isomers produced could be characterized. A total of 12 chemically different groups were detected corresponding to C 2 H n O ( n = 2, 4, 6), C 3 H n O ( n = 2, 4, 6, 8),more »C 4 H n O ( n = 4, 6, 8, 10), C 5 H n O ( n = 4, 6, 8, 10), C 6 H n O ( n = 4, 6, 8, 10, 12, 14), C 2 H n O 2 ( n = 2, 4), C 3 H n O 2 ( n = 4, 6, 8), C 4 H n O 2 ( n = 4, 6, 8, 10), C 5 H n O 2 ( n = 6, 8), C 6 H n O 2 ( n = 8, 10, 12), C 4 H n O 3 ( n = 4, 6, 8), and C 5 H n O 3 ( n = 6, 8). More than half of these isomer specifically identified molecules have been identified in the ISM, and the remaining COMs detected here can be utilized to guide future astronomical observations. Of these isomers, three groups – alcohols, aldehydes, and molecules containing two of these functional groups – displayed varying degrees of unsaturation. Also, the detection of 1-propanol, 2-propanol, 1-butanal, and 2-methyl-propanal has significant implications as the propyl and isopropyl moieties (C 3 H 7 ), which have already been detected in the ISM via propyl cyanide and isopropyl cyanide, could be detected in our laboratory studies. General reaction mechanisms for their formation are also proposed, with distinct follow-up studies being imperative to elucidate the complexity of COMs synthesized in these ices.« less