skip to main content


Title: Group Evacuation on a Line by Agents with Different Communication Abilities
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
Award ID(s):
1813940
NSF-PAR ID:
10384006
Author(s) / Creator(s):
; ; ; ; ; ; ;
Date Published:
Journal Name:
32nd International Symposium on Algorithms and Computation (ISAAC 2021)
Volume:
212
Page Range / eLocation ID:
57:1 - 57:24
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract

    Successful language use requires accurate intention recognition. However, sometimes this can be undermined because communication occurs within an interpersonal context. In this research, I used a relatively large set of speech acts (n= 32) and explored how variability in their inherent face‐threat influences the extent to which they are successfully recognized by a recipient, as well as the confidence of senders and receivers in their communicative success. Participants in two experiments either created text messages (senders) designed to perform a specific speech act (e.g., agree) or interpreted those text messages (receivers) in terms of the specific speech act being performed. The speech acts were scaled in terms of their degree of face threat. In both experiments, speech acts that were more threatening were less likely to be correctly recognized than those that were less threatening. Additionally, the messages of the more threatening speech acts were longer and lower in clout than the less threatening speech acts. Senders displayed greater confidence in communicative success than receivers, but judgments of communicative success (for both senders and receivers) were unrelated to actual communicative success. The implications of these results for our understanding of actual communicative episodes are discussed.

     
    more » « less
  2. null (Ed.)
    Justified communication equilibrium (JCE) is an equilibrium refinement for signaling games with cheap-talk communication. A strategy profile must be a JCE to be a stable outcome of nonequilibrium learning when receivers are initially trusting and senders play many more times than receivers. In the learning model, the counterfactual “speeches” that have been informally used to motivate past refinements are messages that are actually sent. Stable profiles need not be perfect Bayesian equilibria, so JCE sometimes preserves equilibria that existing refinements eliminate. Despite this, it resembles the earlier refinements D1 and NWBR, and it coincides with them in co-monotonic signaling games. (JEL C70, D82, D83, J23, M51) 
    more » « less
  3. This paper considers a planar multi-agent coordination problem. Unlike other related works, we explicitly consider a globally shared wireless communication channel where individual agents must choose both a frequency and power to transmit their messages at. This problem is motivated by the pressing need for algorithms that are able to efficiently and reliably operate on overcrowded wireless networks or otherwise poor-performing RF environments. We develop a self-triggered coordination algorithm that guarantees convergence to the desired set of states with probability 1. The algorithm is developed by using ideas from event/self-triggered coordination and allows agents to autonomously decide for themselves when to broadcast information, at which frequency and power, and how to move based on information received from other agents in the network. Simulations illustrate our results. 
    more » « less
  4. Online matching markets (OMMs) are commonly used in today’s world to pair agents from two parties (whom we will call offline and online agents) for mutual benefit. However, studies have shown that the algorithms making decisions in these OMMs often leave disparities in matching rates, especially for offline agents. In this article, we propose online matching algorithms that optimize for either individual or group-level fairness among offline agents in OMMs. We present two linear-programming (LP) based sampling algorithms, which achieve competitive ratios at least 0.725 for individual fairness maximization and 0.719 for group fairness maximization. We derive further bounds based on fairness parameters, demonstrating conditions under which the competitive ratio can increase to 100%. There are two key ideas helping us break the barrier of 1-1/𝖾~ 63.2% for competitive ratio in online matching. One is boosting , which is to adaptively re-distribute all sampling probabilities among only the available neighbors for every arriving online agent. The other is attenuation , which aims to balance the matching probabilities among offline agents with different mass allocated by the benchmark LP. We conduct extensive numerical experiments and results show that our boosted version of sampling algorithms are not only conceptually easy to implement but also highly effective in practical instances of OMMs where fairness is a concern. 
    more » « less
  5. Several recent works have found the emergence of grounded com-positional language in the communication protocols developed bymostly cooperative multi-agent systems when learned end-to-endto maximize performance on a downstream task. However, humanpopulations learn to solve complex tasks involving communicativebehaviors not only in fully cooperative settings but also in scenar-ios where competition acts as an additional external pressure forimprovement. In this work, we investigate whether competitionfor performance from an external, similar agent team could actas a social influence that encourages multi-agent populations todevelop better communication protocols for improved performance,compositionality, and convergence speed. We start fromTask &Talk, a previously proposed referential game between two coopera-tive agents as our testbed and extend it intoTask, Talk & Compete,a game involving two competitive teams each consisting of twoaforementioned cooperative agents. Using this new setting, we pro-vide an empirical study demonstrating the impact of competitiveinfluence on multi-agent teams. Our results show that an externalcompetitive influence leads to improved accuracy and generaliza-tion, as well as faster emergence of communicative languages thatare more informative and compositional. 
    more » « less