TY - GEN
T1 - Scalable decision-theoretic planning in open and typed multiagent systems
AU - Eck, Adam
AU - Shah, Maulik
AU - Doshi, Prashant
AU - Soh, Leen Kiat
N1 - Publisher Copyright:
Copyright © 2020, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.
PY - 2020
Y1 - 2020
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85106663138&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85106663138&partnerID=8YFLogxK
U2 - 10.1609/aaai.v34i05.6200
DO - 10.1609/aaai.v34i05.6200
M3 - Conference contribution
AN - SCOPUS:85106663138
T3 - AAAI 2020 - 34th AAAI Conference on Artificial Intelligence
SP - 7127
EP - 7134
BT - AAAI 2020 - 34th AAAI Conference on Artificial Intelligence
PB - AAAI Press
T2 - 34th AAAI Conference on Artificial Intelligence, AAAI 2020
Y2 - 7 February 2020 through 12 February 2020
ER -