An official website of the United States government
In open agent systems, the set of agents that are cooperating or competing changes over time and in ways that are nontrivial to predict. For example, if collaborative robots were tasked with fighting wildfires, they may run out of suppressants and be temporarily unavailable to assist their peers. We consider the problem of planning in these contexts with the additional challenges that the agents are unable to communicate with each other and that there are many of them. Because an agent's optimal action depends on the actions of others, each agent must not only predict the actions of its peers, but, before that, reason whether they are even present to perform an action. Addressing openness thus requires agents to model each other's presence, which becomes computationally intractable with high numbers of agents. We present a novel, principled, and scalable method in this context that enables an agent to reason about others' presence in its shared environment and their actions. Our method extrapolates models of a few peers to the overall behavior of the many-agent system, and combines it with a generalization of Monte Carlo tree search to perform individual agent reasoning in many-agent open environments. Theoretical analyses establish the number of agents to model in order to achieve acceptable worst case bounds on extrapolation error, as well as regret bounds on the agent's utility from modeling only some neighbors. Simulations of multiagent wildfire suppression problems demonstrate our approach's efficacy compared with alternative baselines.
more »
« less
Quantifying Faulty Assumptions in Heterogeneous Multi-Agent Systems *
We study the problem of analyzing the effects of inconsistencies in perception, intent prediction, and decision making among interacting agents. When accounting for these effects, planning is akin to synthesizing policies in uncertain and potentially partially-observable environments. We consider the case where each agent, in an effort to avoid a difficult planning problem, does not consider the inconsistencies with other agents when computing its policy. In particular, each agent assumes that other agents compute their policies in the same way as it does, i.e., with the same objective and based on the same system model. While finding policies on the composed system model, which accounts for the agent interactions, scales exponentially, we efficiently provide quantifiable performance metrics in the form of deltas in the probability of satisfying a given specification. We showcase our approach using two realistic autonomous vehicle case-studies and implement it in an autonomous vehicle simulator.
more »
« less
- PAR ID:
- 10508430
- Publisher / Repository:
- IEEE
- Date Published:
- Journal Name:
- Control Technology and Applications
- ISSN:
- 2768-0770
- ISBN:
- 979-8-3503-3544-6
- Page Range / eLocation ID:
- 1115 to 1121
- Subject(s) / Keyword(s):
- Measurement Computational modeling Decision making Model checking Reliability engineering Probabilistic logic Planning
- Format(s):
- Medium: X
- Location:
- Bridgetown, Barbados
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We study the problem of designing cyber insurance policies in an interdependent network, where the loss of one agent (a primary party) depends not only on his own effort, but also on the investments and efforts of others (third parties) in the same eco-system (i.e., externalities). In designing cyber insurance policies, the conventional wisdom is to avoid insuring dependent parties for two reasons. First, simultaneous loss incidents threaten the insurer's business and capital. Second, when a loss incident can be attributed to a third party, the insurer of the primary party can get compensation from the insurer of the third party in order to reduce its own risk exposure. In this work, we analyze an interdependent network model in order to understand whether an insurer should avoid or embrace risks interdependencies. We focus on two interdependent agents, where the risk of one agent (primary party) depends on the other agent (third party), but not the other way around. We consider two potential scenarios: one in which an insurer only insures a primary party, and another one in which the insurer of the primary party further insures the third party agent. We show that it is in fact profitable for the primary party's insurer to insure both agents. Further, we show that insuring both agents not only provides higher profit for the insurer, but also reduces the collective risk.more » « less
-
null (Ed.)We consider the problem of collective exploration of a known n- node edge-weighted graph by k mobile agents that have limited energy but are capable of energy transfers. The agents are initially placed at an arbitrary subset of nodes in the graph, and each agent has an initial, possibly different, amount of energy. The goal of the exploration problem is for every edge in the graph to be traversed by at least one agent. The amount of energy used by an agent to travel distance x is proportional to x. In our model, the agents can share energy when co-located: when two agents meet, one can transfer part of its energy to the other. For an n-node path, we give an O(n+k) time algorithm that either nds an exploration strategy, or reports that one does not exist. For an n-node tree with l leaves, we give an O(n+lk^2) algorithm that finds an exploration strategy if one exists. Finally, for the general graph case, we show that the problem of deciding if exploration is possible by energy-sharing agents is NP-hard, even for 3-regular graphs. In addition, we show that it is always possible to find an exploration strategy if the total energy of the agents is at least twice the total weight of the edges; moreover, this is asymptotically optimal.more » « less
-
The planning domain has experienced increased interest in the formal synthesis of decision-making policies. This formal synthesis typically entails finding a policy which satisfies formal specifications in the form of some well-defined logic. While many such logics have been proposed with varying degrees of expressiveness and complexity in their capacity to capture desirable agent behavior, their value is limited when deriving decision-making policies which satisfy certain types of asymptotic behavior in general system models. In particular, we are interested in specifying constraints on the steady-state behavior of an agent, which captures the proportion of time an agent spends in each state as it interacts for an indefinite period of time with its environment. This is sometimes called the average or expected behavior of the agent and the associated planning problem is faced with significant challenges unless strong restrictions are imposed on the underlying model in terms of the connectivity of its graph structure. In this paper, we explore this steady-state planning problem that consists of deriving a decision-making policy for an agent such that constraints on its steady-state behavior are satisfied. A linear programming solution for the general case of multichain Markov Decision Processes (MDPs) is proposed and we prove that optimal solutions to the proposed programs yield stationary policies with rigorous guarantees of behavior.more » « less
-
Abstract Connected autonomous intelligent agents (AIA) can improve intersection performance and resilience for the transportation infrastructure. An agent is an autonomous decision maker whose decision making is determined internally but may be altered by interactions with the environment or with other agents. Implementing agent-based modeling techniques to advance communication for more appropriate decision making can benefit autonomous vehicle technology. This research examines vehicle to vehicle (V2V), vehicle to infrastructure (V2I), and infrastructure to infrastructure (I2I) communication strategies that use gathered data to ensure these agents make appropriate decisions under operational circumstances. These vehicles and signals are modeled to adapt to the common traffic flow of the intersection to ultimately find an traffic flow that will minimizes average vehicle transit time to improve intersection efficiency. By considering each light and vehicle as an agent and providing for communication between agents, additional decision-making data can be transmitted. Improving agent based I2I communication and decision making will provide performance benefits to traffic flow capacities.more » « less
