An official website of the United States government
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
God Save the Queen
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
- Award ID(s):
- 1813940
- PAR ID:
- 10092807
- Date Published:
- Journal Name:
- 9th International Conference on Fun with Algorithms
- Volume:
- 100
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Two experiments test how college students use nonbinary they to refer to a single and specific person whose pronouns are they/them, e.g., “Alex played basketball on the neighborhood court. At one point they made a basket,” compared to matched stories about characters with binary (she/her or he/him) pronouns. Experiment 1 shows that for both types of pronouns, people use pronouns more in a one-person than a two-person context. In both experiments, people produce nonbinary they at least as frequently as binary pronouns, suggesting that any difficulty does not result in pronoun avoidance in spoken language, even though it does in written language (Arnold et al., 2022). Nevertheless, there is evidence that nonbinary they is somewhat difficult, in that people made gender errors on about 9% of trials, and they used a more acoustically prominent and disfluent-sounding pronunciation for nonbinary pronouns than binary pronouns. However, exposure to they in the context of the experiment had no effect on frequency, accuracy, or pronunciation of pronouns. This provides the first evidence of how nonbinary they is used in a naturalistic storytelling context and shows that while it poses some minor difficulties, it can be used successfully in a supportive context.more » « less
-
We consider a social choice setting in which agents and alternatives are represented by points in a metric space, and the cost of an agent for an alternative is the distance between the corresponding points in the space. The goal is to choose a single alternative to (approximately) minimize the social cost (cost of all agents) or the maximum cost of any agent, when only limited information about the preferences of the agents is given. Previous work has shown that the best possible distortion one can hope to achieve is 3 when access to the ordinal preferences of the agents is given, even when the distances between alternatives in the metric space are known. We improve upon this bound of 3 by designing deterministic mechanisms that exploit a bit of cardinal information. We show that it is possible to achieve distortion 1+sqrt(2) by using the ordinal preferences of the agents, the distances between alternatives, and a threshold approval set per agent that contains all alternatives for whom her cost is within an appropriately chosen factor of her cost for her most-preferred alternative. We show that this bound is the best possible for any deterministic mechanism in general metric spaces, and also provide improved bounds for the fundamental case of a line metric.more » « less
-
During emergencies like fire and smoke or active shooter events, there is a need to address the vulnerability and assess plans for evacuation. With the recent improvements in technology for smartphones, there is an opportunity for geo-visual environments that offer experiential learning by providing spatial analysis and visual communication of emergency-related information to the user. This paper presents the development and evaluation of the mobile augmented reality application (MARA) designed specifically for acquiring spatial analysis, situational awareness, and visual communication. The MARA incorporates existing permanent features such as room numbers and signages in the building as markers to display the floor plan of the building and show navigational directions to the exit. Through visualization of integrated geographic information systems and real-time data analysis, MARA provides the current location of the person, the number of exits, and user-specific personalized evacuation routes. The paper also describes a limited user study that was conducted to assess the usability and effectiveness of the MARA application using the widely recognized System Usability Scale (SUS) framework. The results show the effectiveness of our situational awareness-based MARA in multilevel buildings for evacuations, educational, and navigational purposes.more » « less
-
Honey bees (Apis mellifera L.) localize the queen and aggregate into a swarm by forming a collective scenting network to directionally propagate volatile pheromone signals. Previous experiments show the robustness of this communication strategy in the presence of physical obstacles that partially block pheromone flow and the path to the queen. Specifically, there is a delay in the formation of the scenting network and aggregation compared to a simple environment without perturbations. To better understand the effect of obstacles beyond temporal dynamics, we use the experimental results as inspiration to explore how the behavioral parameter space of collective scenting responds to obstacle. We extend an agent-based model previously developed for a simple environment to account for the presence of physical obstacles. We study how individual agents with simple behavioral rules for scenting and following concentration gradients can give rise to collective localization and swarming. We show that the bees are capable of navigating the more complex environment with a physical obstacle to localize the queen and aggregate around her, but their range of behavioral parameters is more limited and less flexible as a result of the spatial density heterogeneity in the bees imposed by the obstacle.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
