Resource allocation for constrained multi-agent systems

Thesis

In this thesis, we explore the challenges of resource allocation in multi-agent systems. In particular, we consider resource allocation for multi-agent planning, where agents make a series of independent decisions to achieve their own goals. We focus on three main challenges: uncertain domains, differing resource types, and non-cooperative settings. In uncertain domains, stochasticity in the environment leads to agents who are uncertain about their future resource use, which can present challenges for a resource allocation mechanism. Different resource types have different challenges, and increasing the types of resources being allocated in one problem increases the space of possible resource allocations which must be searched. Finally, in non-cooperative settings, agents may compete for resources, and competition may lead to agents lying about their preferences. Lying can, in turn, cause challenges for a mechanism that seeks to optimise a global property.

We address these three challenges through the lens of two classical planning challenges, Multi-Agent Markov Decision Processes and Multi-Agent Path Finding. In the context of weakly-coupled Multi-Agent Markov Decision Processes, we consider the problem of chance-constrained resource allocation and present an auction based method which is applicable to non-cooperative settings. Next, we consider the problem of risk-constrained resource allocation in cooperative Multi-Agent Markov Decision Processes. Finally, we consider the problem of allocating many differing resources in non-cooperative, deterministic Multi-Agent Pathfinding settings. In all settings, we experimentally evaluate the performance of our methods compared to state-of-the-art techniques.

Authors: Gautier, A

• DOI: 10.5287/ora-breyaxazb
• Type of award: DPhil
• Level of award: Doctoral
• Awarding institution: University of Oxford
• Language: English
• Keywords: multi-agent systems; Markov Decision Processes; autonomous decision making; planning under uncertainty
• Subjects: multi-agent systems; planning