Towards Scalable Planning in Partially Observable, Multi-Agent Environments

Abstract

Artificial intelligence (AI) continues to push the boundaries of what is possible for autonomous systems. However, there remains many tasks which AI is still unable or too unreliable to perform. Many of these require the execution of long sequences of actions in uncertain environments involving partial observability, stochasticity, and the presence of other agents. This thesis tackles critical challenges in this domain, focusing on developing methods for improving planning in partially observable, multi-agent environments.

A leading theoretical framework for modeling the other agents in partially observable environments is the Interactive-Partially Observable Markov Decision Process (I-POMDP). However, the computational demands of I-POMDPs have historically limited their applicability. The first contribution of this thesis is a novel online planning method, Interactive Nested Tree Monte-Carlo Planning (I-NTMCP), which improves the scalability and efficiency of planning in I-POMDPs. Our experimental evaluation shows I-NTMCP significantly outperforms existing state-of-the-art offline solvers, and is able to plan effectively to deeper nested reasoning levels than was previously possible.

Another core challenge for multi-agent systems research is the design of autonomous agents that can interact effectively with other agents without prior coordination. Type-based reasoning methods achieve this by maintaining a belief over a set of possible behaviours for the other agent. The second contribution of this thesis is the Partially Observable Type-based Meta Monte-Carlo Planning (POTMMCP) algorithm, which uses a novel meta-policy for guiding search during planning. We prove that POTMMCP converges to the optimal solution in the limit, given the model of the other agents is accurate. Furthermore, through empirical evaluations we demonstrate POTMMCP's ability to adapt online to diverse types of other agents across a range of environments, outperforming previous state-of-the-art methods in terms of efficiency and final performance.

An alternative method for tackling sequential decision-making problems is reinforcement learning (RL). Seamless integration of planning and RL promises to bring the best of both model-driven and data-driven worlds to multi-agent decision-making. The third contribution of this thesis is an in-depth empirical investigation of existing state-of-the-art planning methods and a method which combines planning and RL in the type-based reasoning setting. Our findings highlight the benefit of integrating planning and RL in partially observable, multi-agent domains, while also serving to highlight several important directions for future research.

A key driver of progress in AI research is the availability of high quality, open-source benchmark environments. The final contribution of this thesis is the creation of POSGGym: a library for facilitating planning and RL research in partially observable, multi-agent domains. It provides a diverse collection of discrete and continuous environments, complete with their dynamics models and a reference set of policies that can be used for evaluation. POSGGym assimilates the various environments used throughout this thesis, and more, into an integrated Python library with the goal of aiding future research in planning and RL.

In summary, this thesis addresses the problem of optimal decision-making in partially observable, multi-agent environments. It presents algorithmic innovations, improvements, insights, and tools for planning in highly uncertain environments. Much work remains if we are to create autonomous agents with the ability to plan which are capable, robust, and safe. We hope the contribution of this thesis will help along this path.