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 manyagent system, and combines it with a generalization of Monte Carlo tree search to perform individual agent reasoning in manyagent 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 MultiAgent 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 partiallyobservable 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 casestudies and implement it in an autonomous vehicle simulator.
more »
« less
 Award ID(s):
 1652113
 NSFPAR ID:
 10508430
 Publisher / Repository:
 IEEE
 Date Published:
 Journal Name:
 Control Technology and Applications
 ISSN:
 27680770
 ISBN:
 9798350335446
 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 ecosystem (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 edgeweighted 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 colocated: when two agents meet, one can transfer part of its energy to the other. For an nnode path, we give an O(n+k) time algorithm that either nds an exploration strategy, or reports that one does not exist. For an nnode 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 energysharing agents is NPhard, even for 3regular 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 decisionmaking policies. This formal synthesis typically entails finding a policy which satisfies formal specifications in the form of some welldefined 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 decisionmaking policies which satisfy certain types of asymptotic behavior in general system models. In particular, we are interested in specifying constraints on the steadystate 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 steadystate planning problem that consists of deriving a decisionmaking policy for an agent such that constraints on its steadystate 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

Autonomous agents in a multiagent system work with each other to achieve their goals. However, In a partially observable world, current multiagent systems are often less effective in achieving their goals. This limitation is due to the agentsâ€™ lack of reasoning about other agents and their mental states. Another factor is the agentsâ€™ inability to share required knowledge with other agents. This paper addresses the limitations by presenting a general approach for autonomous agents to work together in a multiagent system. In this approach, an agent applies two main concepts: goal reasoning to determine what goals to pursue and share; Theory of mindto select an agent(s) for sharing goals and knowledge. We evaluate the performance of our multiagent system in a Marine Life Survey Domain and compare it to another multiagent system that randomly selects agent(s) to delegates its goals.more » « less