This workshop focuses on models and algorithms for multiagent interaction without prior coordination (MIPC). Interaction between agents is the defining attribute of multiagent systems, encompassing problems of planning in a decentralized setting, learning other agent models, composing teams with high task performance, and selected resource-bounded communication and coordination. There is significant variety in methodologies used to solve such problems, including symbolic reasoning about negotiation and argumentation, distributed optimization methods, machine learning methods such as multiagent reinforcement learning, etc. The majority of these well studied methods depends on some form of prior coordination. Often, the coordination is at the level of problem definition. For example, learning algorithms may assume that all agents share a common learning method or prior beliefs, distributed optimization methods may assume specific structural constraints regarding the partition of state space or cost/rewards, and symbolic methods often make strong assumptions regarding norms and protocols. In realistic problems, these assumptions are easily violated — calling for new models and algorithms that specifically address the case of ad hoc interactions. Similar issues are also becoming increasingly more pertinent in human-machine interactions, where there is a need for intelligent adaptive behaviour and assumptions regarding prior knowledge and communication are problematic.
Effective MIPC is most likely to be achieved as we bring together work from many different areas, including work on intelligent agents, machine learning, game theory, and operations research. For instance, game theorists have considered what happens to equilibria when common knowledge assumptions must be violated, agent designers are faced with mixed teams of humans and agents in open environments and developing variations on planning methods in response to this, etc. The goal of this workshop is to bring together these diverse viewpoints in an attempt to consolidate the common ground and identify new lines of attack.
The workshop will discuss research related to multiagent interaction without prior coordination, as outlined in the workshop description above. A non-exclusive list of relevant topics includes:
| 09:00 - 10:30 | Session 1 (Chair: Stefano Albrecht) |
| 09:00 - 09:30 | Invited Talk — Subramanian Ramamoorthy: Ad Hoc Human-Machine Interaction: A Categorization-based Approach |
| 09:30 - 09:50 | Xing Su, Minjie Zhang, Quan Bai and Dayong Ye: A Dynamic Coordination Approach for Task Allocation in Disaster Environments under Spatial and Communicational Constraints |
| 09:50 - 10:10 | Samuel Barrett and Peter Stone: Cooperating with Unknown Teammates in Robot Soccer |
| 10:10 - 10:30 | Patrick Lavictoire, Benja Fallenstein, Eliezer Yudkowsky, Mihaly Barasz, Paul Christiano and Marcello Herreshoff: Program Equilibrium in the Prisoner's Dilemma via Löb's Theorem |
| 10:30 - 11:00 | Coffee Break |
| 11:00 - 12:30 | Session 2 (Chair: Samuel Barrett) |
| 11:00 - 11:30 | Invited Talk — Peter Stone: Ad Hoc Autonomous Agent Teams: Collaboration without Pre-Coordination |
| 11:30 - 11:50 | Kyle Wray and Benjamin Thompson: A Distributed Communication Architecture for Dynamic Multiagent Systems |
| 11:50 - 12:10 | Elizabeth Jensen, Ernesto Nunes and Maria Gini: Communication-Restricted Exploration for Robot Teams |
| 12:10 - 12:30 | Itsuki Noda: Robustness of Optimality of Exploration Ratio against Agent Population in Multiagent Learning for Nonstationary Environments |
| 12:30 - 14:00 | Lunch |
| 14:00 - 15:30 | Session 3 (Chair: Jacob Crandall) |
| 14:00 - 14:30 | Invited Talk — Manuela Veloso: Synergy Graphs to Train and Form Ad-Hoc Teams |
| 14:30 - 14:50 | Jianye Hao, Dongping Huang, Yi Cai and Ho-Fung Leung: Reinforcement Social Learning of Coordination in Networked Cooperative Multiagent Systems |
| 14:50 - 15:10 | Kyle Wray and Benjamin Thompson: An Application of Multiagent Learning in Highly Dynamic Environments |
| 15:30 - 16:00 | Coffee Break |
| 16:00 - 17:00 | Expert Panel (Chair: Stefano Albrecht) |
| The panel will consist of: This is an interactive session, questions from the audience are welcome. |
|
Subramanian Ramamoorthy School of Informatics The University of Edinburgh Website |
Ad Hoc Human-Machine Interaction: A Categorization-based Approach
Abstract:
Agents that must interact with others, especially when the others are human co-workers, must learn to coordinate with the unknown, quickly and robustly despite substantial variability in plans and strategies. The intractability of this problem is often alleviated by categorisation, wherein the agent conceptualises the domain in terms of abstractions, enabling a general class of practicable algorithms.
Motivated thus, I will present the Harsanyi-Bellman Ad Hoc Coordination (HBA) model and algorithm that combines Harsanyi's concept of types in Bayesian games with Bellman's concept of optimal control. I will briefly outline some ways in which policy types can be defined in principled ways, extracted from data through unsupervised learning and sometimes provided by human experts as weak and imperfect domain knowledge. In a genuinely unknown interaction, all of these are error-prone in that the hypothesised model is unlikely to exactly match the behaviour of other agents in a novel task instance. I will present some analytical results that characterise the performance of the HBA algorithm under these conditions of mis-specification. If time permits, I will also present some results from human subject experiments involving the HBA algorithm.
|
Peter Stone Co-chair of AAAI-14 Department of Computer Science The University of Texas at Austin Website |
Ad Hoc Autonomous Agent Teams: Collaboration without Pre-Coordination
Abstract:
As autonomous agents proliferate in the real world, both in software and robotic settings, they will increasingly need to band together for cooperative activities with previously unfamiliar teammates. In such "ad hoc" team settings, team strategies cannot be developed a priori. Rather, an agent must be prepared to cooperate with many types of teammates: it must collaborate without pre-coordination. This talk considers ad hoc teamwork from both a game theoretical and empirical perspectives.
|
Manuela Veloso President of AAAI Computer Science Department Carnegie Mellon University Website |
Synergy Graphs to Train and Form Ad-Hoc Teams
Abstract:
Synergy Graphs were introduced by Liemhetcharat's PhD thesis to effectively capture the fact that agents perform tasks with other agents, not only based on their individual capabilities at the task, but also on their level of connection with other agents. The talk will review the contribution in terms of the representation and team formation algorithm. More recent work to be submitted for full publication, will be presented on improving a team by explicitly choosing which agents to train based on their synergy graph. As a workshop talk, comments and questions from the experts will be greatly appreciated and beneficial.
The workshop will include an expert panel with three researchers. The purpose of the panel is to hear their opinions on important issues and new developments in MIPC. This session will be interactive, questions from the audience are welcome.
The expert panel will include the following researchers:
|
Noa Agmon Department of Computer Science Bar-Ilan University Website |
|
Prashant Doshi Department of Computer Science The University of Georgia Website |
|
Michael Littman Department of Computer Science Brown University Website |