Decision Making in Multi-Agent Systems

Abstract: Multi-agent path finding (MAPF) is an important decision problem for all multi-robot systems, but with a huge array of solvers, it is difficult to decide which solver to use. In this presentation, I will discuss our state-of-the-art MAPF algorithm selector that automatically chooses an optimal MAPF solver to use to solve any instance. I will also discuss our work in trying to understand what makes some MAPF instances hard to solve, which, in turn, can improve our algorithm selection.

Abstract: In ad hoc teamwork, multiple agents need to collaborate without having knowledge about their teammates or their plans a priori. A common assumption in this research area is that the agents cannot communicate. However, just as two random people may speak the same language, autonomous teammates may also happen to share a communication protocol. We consider how such a shared protocol can be leveraged, introducing a means to reason about Communication in Ad Hoc Teamwork (CAT). The goal of this work is enabling improved ad hoc teamwork by judiciously leveraging the ability of the team to communicate.

10:15-10:27a --- Data-Efficient Collaborative Decentralized Thermal-Inertial Odometry
10:27-10:39a --- Modular Value Function Factorization in Multi-Agent Reinforcement Learning
10:39-10:51a --- Asynchronous Actor-Critic for Multi-Agent Reinforcement Learning
10:51-11:03a --- Toward Capability-Aware Cooperation for Decentralized Planning
11:03-11:15a --- A Game-theoretic Utility Network for Multi-Agent Decisions in Adversarial Environments

Abstract: The coordination of robots and other agents becomes more and more important for industry. For example, on the order of one thousand robots already navigate autonomously in fulfillment centers to move inventory pods all the way from their storage locations to the picking stations that need the products they store (and vice versa). Optimal and, in some cases, even approximately optimal path planning for these robots is NP-hard, yet one must find high-quality collision-free paths for them in real-time. Algorithms for such multi-agent path-finding problems have been studied in robotics and theoretical computer science for a longer time but are insufficient since they are either fast but of insufficient solution quality or of good solution quality but too slow. In this talk, I will discuss both recent cool ideas for solving such multi-agent path-finding problems (including the roles of planning and machine learning) and several of their applications, including in warehousing. Our research on this topic has been funded by both NSF and Amazon Robotics.

Abstract: A challenge in cooperative multi-agent reinforcement learning is credit assignment, where it is often difficult to determine when an agent contributes to a shared reward. This problem is particularly hard for teams with many decentralized agents. In this talk, I will discuss common approaches for addressing this problem from the perspective of learning individual utility functions agents can use for decentralized decision making. I will then discuss our recent work in this growing body of literature and how we leverage successor features to achieve promising results.

Abstract: A major challenge of multiagent reinforcement learning (MARL) is the curse of multiagents, where the size of the joint action space scales exponentially with the number of agents. This remains to be a bottleneck for designing efficient MARL algorithms even in a basic scenario with finitely many states and actions. This paper resolves this challenge for the model of episodic Markov games. We design a new class of fully decentralized algorithms---V-learning, which provably learns Nash equilibria (in the two-player zero-sum setting), correlated equilibria and coarse correlated equilibria (in the multiplayer general-sum setting) in a number of samples that only scales with \max_i A_i, where A_i is the number of actions for the ith player. This is in sharp contrast to the size of the joint action space which is \prod_i A_i. V-learning (in its basic form) is a new class of single-agent RL algorithms that convert any adversarial bandit algorithm with suitable regret guarantees into a RL algorithm. Similar to the classical Q-learning algorithm, it performs incremental updates to the value functions. Different from Q-learning, it only maintains the estimates of V-values instead of Q-values. This key difference allows V-learning to achieve the claimed guarantees in the MARL setting by simply letting all agents run V-learning independently.

Abstract: Some important breakthroughs in artificial intelligence in recent years (such as Libratus and security games) can be attributed to the development of large-scale game solving technology in the past decade. However, game solving technology cannot handle large scale complex games, and the academic community began to use deep learning techniques to solve such complex games. The talk will discuss important progress in this direction in recent years and future directions.

Abstract: In general-sum games, the interaction of self-interested learning agents commonly leads to collectively worst-case outcomes, such as defect-defect in the iterated prisoner's dilemma (IPD). To overcome this, some methods, such as Learning with Opponent-Learning Awareness (LOLA), shape their opponents' learning process. However, these methods are myopic since only a small number of steps can be anticipated, are asymmetric since they treat other agents as naive learners, and require the use of higher-order derivatives, which are calculated through white-box access to an opponent's differentiable learning algorithm. In this talk I will first introduce Model-Free Opponent Shaping (M-FOS), which overcomes all of these limitations. M-FOS learns in a meta-game in which each meta-step is an episode of the underlying (``inner'') game. The meta-state consists of the inner policies, and the meta-policy produces a new inner policy to be used in the next episode. M-FOS then uses generic model-free optimisation methods to learn meta-policies that accomplish long-horizon opponent shaping. I will finish off the talk with our recent results for adversarial (or cooperative) cheap-talk: How can agents interfere with (or support) the learning process of other agents without being able to act in the environment?

Abstract: In this talk, I first discuss how we leverage machine learning methods to generate cooperative policies for multi-robot systems. I describe how we use Graph Neural Networks (GNNs) to learn effective communication strategies for decentralized coordination. I then show how our GNN-based policy is able to achieve near-optimal performance across a variety of problems, at a fraction of the real-time computational cost. Finally, I present some pioneering real-robot experiments that demonstrate the transfer of our methods to the physical world.