More Like this

1. Group Evacuation on a Line by Agents with Different Communication Abilities

   Czyzowicz, J; Killick R.; Kranakis, E.; Krizanc, D.; Narayanan, L.; Opatrny, J.; Pankratov, D.; Shende, S. (January 2021, 32nd International Symposium on Algorithms and Computation (ISAAC 2021))

   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
2. Incorporating impact of hazardous and toxic environments on the guidance of mobile sensor networks used for the cooperative estimation of spatially distributed processes

   https://doi.org/10.1109/CDC.2018.8619588  

   Demetriou, Michael A. (December 2018, 2018 IEEE Conference on Decision and Control (CDC))

   This work incorporates the effects that hazardous environments have on sensing devices, in the guidance of mobile platforms with onboard sensors. Mobile sensors are utilized in the state reconstruction of spatiotemporally varying processes, often described by advection-diffusion PDEs. A typical sensor guidance policy is based on a gradient ascent scheme which repositions the sensors to spatial regions that have larger state estimation errors. If the cumulative measurements of the spatial process are used as a means to represent the effects of hazardous environments on the sensors, then the sensors are considered inoperable the instance the cumulative measurements exceed a device-specific tolerance level. A binary guidance policy considered earlier repositioned the sensors to regions of larger values of the state estimation errors thus implementing an information-sensitive policy. The policy switched to an information-averse guidance the instance the cumulative effects exceeded a certain tolerance level. Such a binary policy switches the sensor velocity abruptly from a positive to a negative value. To alleviate these discontinuity effects, a ternary guidance policy is considered and which inserts a third guidance policy, the information-neutral policy, that smooths out the transitions from information-sensitive to information-averse guidance. A novelty in this ternary guidance has to do with the level-set approach which changes from a guidance towards large values of the state estimation error towards level sets of the state estimation error and eventually towards reduced values of the state estimation error. An example on an advection-diffusion PDE in 2D employing a single interior mobile sensor using both the binary and ternary guidance policies is used to demonstrate the effects of hazardous environments on both the sensor life expectancy and the performance of the state estimator. 

   more » « less
3. Multi-agent Modeling of Human Traffic Dynamics for Rapid Response to Public Emergency in Spatial Networks

   https://doi.org/10.1109/CASE59546.2024.10711522  

   Shi, Xiaoru; Lee, Hankang; Yang, Hui (August 2024, IEEE)

   Public emergencies pose catastrophic casualties and financial losses in densely populated areas, rendering communities such as cities, towns, and universities particularly susceptible due to their intricate environments and high pedestrian traffic. While simulation analysis offers a flexible and cost-effective approach to evaluating evacuation procedures, conventional evacuation models are often limited to specific scenarios and communities, overlooking the diverse range of emergencies and evacuee behaviors. Thus, there is an urgent need for an evacuation model capable of capturing complex structures of communities and modeling evacuee responses to various emergencies. This paper presents a novel approach to simulating responsive evacuation behaviors for multiple emergency situations in public communities through spatial network modeling and multi-agent modeling. Leveraging a community network framework adaptable to different community layouts based on map data, the proposed model employs a multi-agent approach to characterize responsive and decentralized evacuation decision-making. Experimental results show the model’s efficacy in representing pedestrian flow and pedestrians’ reactive behavior across various campuses based on real-world map data. Additionally, the case study highlights the potential of the proposed model to simulate pedestrian dynamics for a variety of heterogeneous emergencies. The proposed community evacuation model holds strong promise for evaluating evacuation policies and providing insights into resilient plans during public emergencies, thereby enhancing community safety. 

   more » « less
4. Allocating Public Goods via Dynamic Max-Min Fairness: Long-Run Behavior and Competitive Equilibria

   https://doi.org/10.1145/3711695  

   Onyeze, Chido; Banerjee, Siddhartha; Fikioris, Giannis; Tardos, Éva (March 2025, Proceedings of the ACM on Measurement and Analysis of Computing Systems)

   Dynamic max-min fair allocation (DMMF) is a simple and popular mechanism for the repeated allocation of a shared resource among competing agents: in each round, each agent can choose to request or not for the resource, which is then allocated to the requesting agent with the least number of allocations received till then. Recent work has shown that under DMMF, a simple threshold-based request policy enjoys surprisingly strong robustness properties, wherein each agent can realize a significant fraction of her optimal utility irrespective of how other agents' behave. While this goes some way in mitigating the possibility of a 'tragedy of the commons' outcome, the robust policies require that an agent defend against arbitrary (possibly adversarial) behavior by other agents. This however may be far from optimal compared to real world settings, where other agents are selfish optimizers rather than adversaries. Therefore, robust guarantees give no insight on how agents behave in an equilibrium, and whether outcomes are improved under one. Our work aims to bridge this gap by studying the existence and properties of equilibria under DMMF. To this end, we first show that despite the strong robustness guarantees of the threshold based strategies,no Nash equilibrium existswhen agents participate in DMMF, each using some fixed threshold-based policy. On the positive side, however, we show that for the symmetric case, a simple data-driven request policy guarantees that no agent benefits from deviating to a different fixed threshold policy. In our proposed policy agents aim to match the historical allocation rate with a vanishing drift towards the rate optimizing overall welfare for all users. Furthermore, the resulting equilibrium outcome can be significantly better compared to what follows from the robustness guarantees. Our results are built on a complete characterization of the steady-state distribution under DMMF, as well as new techniques for analyzing strategic agent outcomes under dynamic allocation mechanisms; we hope these may prove of independent interest in related problems. 

   more » « less
5. Distributed Q-Learning with State Tracking for Multi-agent Networked Control

   Wang, Hang; Lin, Sen; Jafarkhani, Hamid; Zhang, Junshan (May 2021, AAMAS '21: Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent SystemsMay 2021)

   This paper studies distributed Q-learning for Linear Quadratic Regulator (LQR) in a multi-agent network. The existing results often assume that agents can observe the global system state, which may be infeasible in large-scale systems due to privacy concerns or communication constraints. In this work, we consider a setting with unknown system models and no centralized coordinator. We devise a state tracking (ST) based Q-learning algorithm to design optimal controllers for agents. Specifically, we assume that agents maintain local estimates of the global state based on their local information and communications with neighbors. At each step, every agent updates its local global state estimation, based on which it solves an approximate Q-factor locally through policy iteration. Assuming a decaying injected excitation noise during the policy evaluation, we prove that the local estimation converges to the true global state, and establish the convergence of the proposed distributed ST-based Q-learning algorithm. The experimental studies corroborate our theoretical results by showing that our proposed method achieves comparable performance with the centralized case. 

   more » « less