Search

We consider evacuation of a group of $n \geq 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 \sqrt{2}$. If there is a single sender or fully wireless agent, and multiple receivers we prove that $CR \in [2+\sqrt{5},5]$, and if there are multiple senders and a single receiver or fully wireless agent, we show that $CR \in [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.

Assume that $m \geq 1$ autonomous mobile agents and $0 \leq b \leq m$ single-agent transportation devices (called {\em bikes}) are initially placed at the left endpoint $0$ of the unit interval $[0,1]$. The agents are identical in capability and can move at speed one. The bikes cannot move on their own, but any agent riding bike $i$ can move at speed $v_i > 1$. An agent may ride at most one bike at a time. The agents can cooperate by sharing the bikes; an agent can ride a bike for a time, then drop it to be used by another agent, and possibly switch to a different bike. We study two problems. In the \BS problem, we require all agents and bikes starting at the left endpoint of the interval to reach the end of the interval as soon as possible. In the \RBS problem, we aim to minimize the arrival time of the agents; the bikes can be used to increase the average speed of the agents, but are not required to reach the end of the interval. Our main result is the construction of a polynomial time algorithm for the \BS problem that creates an arrival-time optimal schedule for travellers and bikes to travel across the interval. For the \RBS problem, we give an algorithm that gives an optimal solution for the case when at most one of the bikes can be abandoned.

Two robots stand at the origin of the infinite line and are tasked with searching collaboratively for an exit at an unknown location on the line. They can travel at maximum speed $b$ and can change speed or direction at any time. The two robots can communicate with each other at any distance and at any time. The task is completed when the last robot arrives at the exit and evacuates. We study time-energy tradeoffs for the above evacuation problem. The evacuation time is the time it takes the last robot to reach the exit. The energy it takes for a robot to travel a distance $x$ at speed $s$ is measured as $xs^2$. The total and makespan evacuation energies are respectively the sum and maximum of the energy consumption of the two robots while executing the evacuation algorithm. Assuming that the maximum speed is $b$, and the evacuation time is at most $cd$, where $d$ is the distance of the exit from the origin, we study the problem of minimizing the total energy consumption of the robots. We prove that the problem is solvable only for $bc \geq 3$. For the case $bc=3$, we give an optimal algorithm, and give upper bounds on the energy for the case $bc>3$. We also consider the problem of minimizing the evacuation time when the available energy is bounded by $\Delta$. Surprisingly, when $\Delta$ is a constant, independent of the distance $d$ of the exit from the origin, we prove that evacuation is possible in time $O(d^{3/2}\log d)$, and this is optimal up to a logarithmic factor. When $\Delta$ is linear in $d$, we give upper bounds on the evacuation time., Comment: This is the full version of the paper with the same title which will appear in the proceedings of the 26th International Colloquium on Structural Information and Communication Complexity (SIROCCO'19) L'Aquila, Italy during July 1-4, 2019

Consider two robots that start at the origin of the infinite line in search of an exit at an unknown location on the line. The robots can only communicate if they arrive at the same location at exactly the same time, i.e. they use the so-called face-to-face communication model. The group search time is defined as the worst-case time as a function of $d$, the distance of the exit from the origin, when both robots can reach the exit. It has long been known that for a single robot traveling at unit speed, the search time is at least $9d-o(d)$. It was shown recently that $k\geq2$ robots traveling at unit speed also require at least $9d$ group search time. We investigate energy-time trade-offs in group search by two robots, where the energy loss experienced by a robot traveling a distance $x$ at constant speed $s$ is given by $s^2 x$. Specifically, we consider the problem of minimizing the total energy used by the robots, under the constraints that the search time is at most a multiple $c$ of the distance $d$ and the speed of the robots is bounded by $b$. Motivation for this study is that for the case when robots must complete the search in $9d$ time with maximum speed one, a single robot requires at least $9d$ energy, while for two robots, all previously proposed algorithms consume at least $28d/3$ energy. When the robots have bounded memory, we generalize existing algorithms to obtain a family of optimal (and in some cases nearly optimal) algorithms parametrized by pairs of $b,c$ values that can solve the problem for the entire spectrum of these pairs for which the problem is solvable. We also propose a novel search algorithm, with unbounded memory, that simultaneously achieves search time $9d$ and consumes energy $8.42588d$. Our result shows that two robots can search on the line in optimal time $9d$ while consuming less total energy than a single robot within the same search time., Comment: This is the full version of the paper with the same title which will appear in the proceedings of the 46th International Colloquium on Automata, Languages and Programming 8-12 July 2019, Patras, Greece

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 + \frac{2\pi}{3} + \sqrt{3} \approx 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 \approx 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\geq 4$ is the subject of an independent study by Queen Daniela's Royal Scientific Team., Comment: 33 pages, 8 Figures. This is the full version of the paper with the same title which will appear in the proceedings of the 9th International Conference on Fun with Algorithms, (FUN'18), June 13--15, 2018, La Maddalena, Maddalena Islands, Italy

A set of mobile robots (represented as points) is distributed in the Cartesian plane. The collection contains an unknown subset of byzantine robots which are indistinguishable from the reliable ones. The reliable robots need to gather, i.e., arrive to a configuration in which at the same time, all of them occupy the same point on the plane. The robots are equipped with GPS devices and at the beginning of the gathering process they communicate the Cartesian coordinates of their respective positions to the central authority. On the basis of this information, without the knowledge of which robots are faulty, the central authority designs a trajectory for every robot. The central authority aims to provide the trajectories which result in the shortest possible gathering time of the healthy robots. The efficiency of a gathering strategy is measured by its competitive ratio, i.e., the maximal ratio between the time required for gathering achieved by the given trajectories and the optimal time required for gathering in the offline case, i.e., when the faulty robots are known to the central authority in advance. The role of the byzantine robots, controlled by the adversary, is to act so that the gathering is delayed and the resulting competitive ratio is maximized. The objective of our paper is to propose efficient algorithms when the central authority is aware of an upper bound on the number of byzantine robots. We give optimal algorithms for collections of robots known to contain at most one faulty robot. When the proportion of byzantine robots is known to be less than one half or one third, we provide algorithms with small constant competitive ratios. We also propose algorithms with bounded competitive ratio in the case where the proportion of faulty robots is arbitrary., Comment: 14 pages, 6 figures

An RF ion-funnel technique has been developed to extract ions from a high-pressure (10 bar) noble-gas environment into vacuum ($10^{-6}$ mbar). Detailed simulations have been performed and a prototype has been developed for the purpose of extracting $^{136}$Ba ions from Xe gas with high efficiency. With this prototype, ions have been extracted for the first time from high-pressure xenon gas and argon gas. Systematic studies have been carried out and compared to the simulations. This demonstration of extraction of ions with mass comparable to that of the gas generating the high-pressure into vacuum has applications to Ba tagging from a Xe-gas time-projection chamber (TPC) for double beta decay as well as to the general problem of recovering trace amounts of an ionized element in a heavy (m$>40$ u) carrier gas.

The Standard Model Higgs boson may be mixed with another scalar that does not couple to fermions. The electroweak quantum numbers of such an additional scalar can be determined by measuring the quartic Higgs-Higgs-vector-vector couplings, which contribute---along with the coveted triple Higgs coupling---to double Higgs production in $e^+e^-$ collisions. We show that simultaneous sensitivity to the quartic Higgs-Higgs-vector-vector coupling and the triple Higgs coupling can be obtained using measurements of the double Higgs production cross section at two different e+e- center-of-mass energies. Kinematic distributions of the two Higgs bosons in the final state could provide additional discriminating power., Comment: 9 pages, 5 figures. v2 : refs added, footnote 3 on septet model added, v3 : refs added/updated, figures 3,4 and 5 improved, final version to be published in PRD