Learning to Efficiently Plan in Flexible Distributed Organizations

Teams of robots are expected to revolutionise industry and other other parts of society. However, decision making in such so-called multiagent systems (MASs) under uncertainty is computationally very complex. The decentralized partially observable Markov decision process (Dec-POMDP) framework facilitates principled formulation of such decision making problems, but currently there are no scalable solution methods that provide guarantees on task performance. To simplify coordination in MASs, agent organisations assign an abstracted, easier problem to each agent. Typically only the most rigid organisations, which completely decouple the agents, have led to clear computational benefits. However, these come at the expense of task performance: full decoupling means that agents can no longer collaborate to divide the workload.

This project will focus on flexible distributed organisations (FDOs) for Dec-POMDPs, which restrict considered interactions to spatially nearby agents without imposing full decoupling. Currently no scalable decision making methods with guarantees on task performance exist for FDOs: the main goal of the project is to develop such methods along with the theory that supports their formalisation. To accomplish this goal, it will investigate the use of deep learning techniques to learn representations of 'influence' in FDOs and use those representations to develop novel planning methods. If successful, this will provide the proof-of-concept that learned influence representations can enable principled decision making in large-scale MASs. This will be the basis for a larger research program investigating such influence representations for different forms of abstraction and will spark applied research that investigates deployment of the developed algorithms in real robotic teams.

This is a relatively short project that pursues basic research in the field of AI. As such, the expected short-term impact will mostly be in the form of knowledge (developed techniques), the scientific output (articles and software) and the influence on research questions picked up by peers (of which citations to those output are an indication). These academic impacts are a crucial link in the pathways to longer-term impact on society and economy. In particular, the project aims to make simulation-based planning dramatically more efficient, and thus more effective or even feasible in cases where it was not before. This could have a great mid-to-long-term impact since the potential of application of these methods is huge; they are advanced versions of model-predictive control (MPC) methods which are widely applied in industry. The recent application of simulation-based planning in the mastering of the game of Go is likely to attract attention in many areas.

Another reason that simulation-based planning methods have not seen more application yet is their large computational costs. However, this is precisely what we address for the class of problems that admit flexible distributed organizations. For such problems, the proposed research will have a crucial impact in terms of just making it feasible at all to apply simulation-based planning to these domains. For instance, we expect that this could be the case for robotic teams collaborating in future factories or warehouses, but also for other problems that can be modelled as spatial task allocation problems, such as dispatching of emergency vehicles, or for applications areas such as optimizing traffic control by simulating large traffic networks, optimizing routing policies by simulation of communication networks, optimizing UAV patrolling policies in security domains or for law enforcement, etc.

Therefore, a large part of the longer term impact will be of the economic kind (new companies, improved products and services) with, given the possible application areas, the potential to improve quality of life. The first companies to adopt these techniques will be logistics and manufacturing companies since these already are starting to use robotic teams. Many of the other aforementioned applications (UAV patrolling etc.) will probably need more time and are likely to be tackled by AI and robotics start-up companies. The discipline of high-performance computing (HPC) is involved in optimizing both hardware and software, e.g., to make simulations maximally efficient. The basic idea put forth in this proposal---that one can mostly use 'local model simulations' that consider only a small subset of the variables considered in 'full model' simulations, while still converging to the same behaviour---could potentially make an impact on this community, and thus may affect the design of computers dedicated to doing simulations.

I will contribute to the impact of the developed methods by contributing to awareness (interacting with potential industrial partners, as well as with academic peers, and organising a workshop), clarifying potential gains (an expected output of the research), and facilitating adoption by releasing open source software.