Show simple item record

dc.contributor.advisorRamamoorthy, Subramanian
dc.contributor.advisorRovatsos, Michael
dc.contributor.authorAlbrecht, Stefano Vittorino
dc.date.accessioned2016-08-29T08:39:15Z
dc.date.available2016-08-29T08:39:15Z
dc.date.issued2015-11-26
dc.identifier.urihttp://hdl.handle.net/1842/16199
dc.description.abstractThis thesis is concerned with the ad hoc coordination problem. Therein, the goal is to design an autonomous agent which can achieve high flexibility and efficiency in a multiagent system that admits no prior coordination between the designed agent and the other agents. Flexibility describes the agent’s ability to solve its task with a variety of other agents in the system; efficiency is the relation between the agent’s payoffs and time needed to solve the task; and no prior coordination means that the agent does not a priori know how the other agents behave. This problem is relevant for a number of practical applications, including human-machine interaction tasks, such as adaptive user interfaces, robotic elderly care, and automated trading agents. Motivated by this problem, the central idea studied in this thesis is to utilise a set of policies, or types, to characterise the behaviour of other agents. Specifically, the idea is to reduce the complexity of the interaction problem by assuming that the other agents draw their latent type from some known or hypothesised space of types, and that the assignment of types is governed by an unknown distribution. Based on the current interaction history, we can form posterior beliefs about the relative likelihood of types. These beliefs, combined with the future predictions of the types, can then be used in a planning procedure to compute optimal responses. The aim of this thesis is to study the potential and limitations of this idea in the context of ad hoc coordination. We formulate the ad hoc coordination problem using a game-theoretic model called the stochastic Bayesian game. Based on this model, we derive a canonical algorithmic description of the idea outlined above, called Harsanyi-Bellman Ad Hoc Coordination (HBA). The practical potential of HBA is demonstrated in two case studies, including a human-machine experiment and a simulated logistics domain. We formulate basic ways to incorporate evidence (i.e. observed actions) into posterior beliefs and analyse the conditions under which the posterior beliefs converge to the true distribution of types. Furthermore, we study the impact of prior beliefs over types (that is, before any actions are observed) on the long-term performance of HBA, and show empirically that automatic methods can compute prior beliefs with consistent performance effects. For hypothesised (i.e. “guessed”) type spaces, we analyse the relations between hypothesised and true type spaces under which HBA is still guaranteed to solve its task, despite inaccuracies in hypothesised types. Finally, we show how HBA can perform an automatic statistical analysis to decide whether to reject its behavioural hypothesis, i.e. the combination of posterior beliefs and types.en
dc.contributor.sponsorotheren
dc.language.isoenen
dc.publisherThe University of Edinburghen
dc.relation.hasversionS.V. Albrecht, S. Ramamoorthy. Are You Doing What I Think You Are Doing? Criticising Uncertain Agent Models. In Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence, Amsterdam, Netherlands, 2015.en
dc.relation.hasversionS.V. Albrecht, J.W. Crandall, S. Ramamoorthy. An Empirical Study on the Practical Impact of Prior Beliefs over Policy Types. In Proceedings of the 29th AAAI Conference on Artificial Intelligence, Austin, Texas, USA, 2015.en
dc.relation.hasversionS.V. Albrecht, S. Ramamoorthy. On Convergence and Optimality of Best-Response Learning with Policy Types in Multiagent Systems. In Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence, Quebec City, Canada, 2014.en
dc.relation.hasversionS.V. Albrecht, S. Ramamoorthy. A Game-Theoretic Model and Best-Response Learning Method for Ad Hoc Coordination in Multiagent Systems (Extended Abstract). In Proceedings of the 12th International Conference on Autonomous Agents and Multiagent Systems, St. Paul, Minnesota, USA, 2013.en
dc.relation.hasversionS.V. Albrecht, J.W. Crandall, S. Ramamoorthy. E-HBA: Using Action Policies for Expert Advice and Agent Typification. In Proceedings of the AAAI-15 Workshop on Multiagent Interaction without Prior Coordination, Austin, Texas, USA, 2015.en
dc.relation.hasversionS.V. Albrecht, S. Ramamoorthy. Comparative Evaluation of MAL Algorithms in a Diverse Set of Ad Hoc Team Problems. In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems, Valencia, Spain, 2012.en
dc.subjectartificial intelligenceen
dc.subjectmultiagent systemsen
dc.subjecttype-based methoden
dc.titleUtilising policy types for effective ad hoc coordination in multiagent systemsen
dc.typeThesis or Dissertationen
dc.type.qualificationlevelDoctoralen
dc.type.qualificationnamePhD Doctor of Philosophyen


Files in this item

This item appears in the following Collection(s)

Show simple item record