An official website of the United States government
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
Collective Progress: Dynamics of Exit Waves
We introduce a framework for studying collective search by teams. Discoveries are correlated over time and governed by a Brownian path, where search speed is jointly controlled. Agents individually choose when to cease search and implement their best discovery. We characterize equilibrium and optimal policies. Search speeds are constant within active alliances and depend on complementarities between members. A drawdown stopping boundary governs each agent’s search termination. The consequent exit waves, whereby possibly heterogeneous agents cease search simultaneously, exhibit deterministic sequencing but stochastic timing. We highlight environments with lower than optimal equilibrium speeds and search durations, and different exit waves.
more »
« less
- Award ID(s):
- 1949381
- PAR ID:
- 10521062
- Publisher / Repository:
- Journal of Political Economy
- Date Published:
- Journal Name:
- Journal of Political Economy
- Volume:
- 131
- Issue:
- 9
- ISSN:
- 0022-3808
- Page Range / eLocation ID:
- 2402 to 2450
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Objective: Semi-active exoskeletons combining lightweight, low powered actuators and passive-elastic elements are a promising approach to portable robotic assistance during locomotion. Here, we introduce a novel semi-active hip exoskeleton concept and evaluate human walking performance across a range of parameters using a tethered robotic testbed. Methods : We emulated semi-active hip exoskeleton (exo) assistance by applying a virtual torsional spring with a fixed rotational stiffness and an equilibrium angle established in terminal swing phase (i.e., via pre-tension into stance). We performed a 2-D sweep of spring stiffness x equilibrium position parameters (30 combinations) across walking speed (1.0, 1.3, and 1.6 m/s) and measured metabolic rate to identify device parameters for optimal metabolic benefit. Results : At each speed, optimal exoskeleton spring settings provided a ∼10% metabolic benefit compared to zero-impedance (ZI). Higher walking speeds required higher exoskeleton stiffness and lower equilibrium angle for maximal metabolic benefit. Optimal parameters tuned to each individual (user-dependent) provided significantly larger metabolic benefit than the average-best settings (user-independent) at all speeds except the fastest (p = 0.021, p = 0.001, and p = 0.098 at 1.0, 1.3, and 1.6 m/s, respectively). We found significant correlation between changes in user's muscle activity and changes in metabolic rate due to exoskeleton assistance, especially for muscles crossing the hip joint. Conclusion : A semi-active hip exoskeleton with spring-parameters personalized to each user could provide metabolic benefit across functional walking speeds. Minimizing muscle activity local to the exoskeleton is a promising approach for tuning assistance on-line on a user-dependent basis.more » « less
-
null (Ed.)Mechanisms with money are commonly designed under the assumption that agents are quasi-linear, meaning they have linear disutility for spending money. We study the implications when agents with non-linear (specifically, convex) disutility for payments participate in mechanisms designed for quasi-linear agents. We first show that any mechanism that is truthful for quasi-linear buyers has a simple best response function for buyers with non-linear disutility from payments, in which each bidder simply scales down her value for each potential outcome by a fixed factor, equal to her target return on investment (ROI). We call such a strategy ROI-optimal. We prove the existence of a Nash equilibrium in which agents use ROI-optimal strategies for a general class of allocation problems. Motivated by online marketplaces, we then focus on simultaneous second-price auctions for additive bidders and show that all ROI-optimal equilibria in this setting achieve constant-factor approximations to suitable welfare and revenue benchmarks.more » « less
-
In the Multi-Agent Meeting problem (MAM), the task is to find a meeting location for multiple agents, as well as a path for each agent to that location. In this paper, we introduce MM*, a Multi-Directional Heuristic Search algorithm that finds the optimal meeting location under different cost functions. MM* generalizes the Meet in the Middle (MM) bidirectional search algorithm to the case of finding an optimal meeting location for multiple agents. Several admissible heuristics are proposed, and experiments demonstrate the benefits of MM*.more » « less
-
null (Ed.)We study a sequence of many-agent exit time stochastic control problems, parameterized by the number of agents, with risk-sensitive cost structure. We identify a fully characterizing assumption, under which each such control problem corresponds to a risk-neutral stochastic control problem with additive cost, and sequentially to a risk-neutral stochastic control problem on the simplex that retains only the distribution of states of agents, while discarding further specific information about the state of each agent. Under some additional assumptions, we also prove that the sequence of value functions of these stochastic control problems converges to the value function of a deterministic control problem, which can be used for the design of nearly optimal controls for the original problem, when the number of agents is sufficiently large.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1086/724321
