AAAI-23MAPFWorkshop

Amanda Prorok
University of Cambridge

Learning-Based Methods for Multi-Agent Navigation

• Abstract: In this talk, I discuss our work on using Graph Neural Networks (GNNs) to solve multi-agent coordination problems. In my first case-study, I show how we use GNNs to find a decentralized solution by learning what the agents need to communicate to one another. This communication-based policy is able to achieve near-optimal performance; when combined with an attention mechanism, we can drastically improve generalization to very-large-scale systems. But instead of optimizing agent policies, what if we could modify the navigation environment, instead? I next introduce an environment optimization approach that guarantees the existence of complete solutions, improving agent navigation success rates over heuristic methods. Finally, I discuss challenges in the transfer of learned policies to the real world.
• Amanda Prorok is Professor of Collective Intelligence and Robotics in the Department of Computer Science and Technology at Cambridge University, and a Fellow of Pembroke College. She has been honoured by numerous research awards, including an ERC Starting Grant, an Amazon Research Award, the EPSRC New Investigator Award, the Isaac Newton Trust Early Career Award, and several Best Paper awards. Her PhD thesis was awarded the Asea Brown Boveri (ABB) prize for the best thesis at EPFL in Computer Science. She serves as Associate Editor for IEEE Robotics and Automation Letters (R-AL) and Associate Editor for Autonomous Robots (AURO). Prior to joining Cambridge, Amanda was a postdoctoral researcher at the General Robotics, Automation, Sensing and Perception (GRASP) Laboratory at the University of Pennsylvania, USA, where she worked with Prof. Vijay Kumar. She completed her PhD at EPFL, Switzerland, with Prof. Alcherio Martinoli"

Guillaume Sartoretti
National University of Singapore

Distributed Learning towards Scalable and Cooperative Multi-Agent Pathfinding

• Abstract: Multi-agent path finding (MAPF) is an indispensable component of large-scale robot deployments in numerous domains ranging from airport management to warehouse automation. However, as the number of agents (robots) in the system grows, so does the combinatorial complexity of coordinating them, drastically affecting the scalability of coupled planners and the solution quality of fully decoupled methods. As a new direction for research into scalable, high-quality MAPF, my work has embraced advances in distributed reinforcement learning (RL) to let multiple agents learn decentralized, collaborative policies in a time-efficient manner. In this talk, I will first introduce our recent AI-based frameworks for MAPF (PRIMAL) and lifelong MAPF (PRIMAL2), which combine deep RL with imitation learning from a complete, optimal planner. As a result, the policies learned by PRIMAL/PRIMAL2 naturally scale to near-arbitrary team sizes while exhibiting the type of coordinated behaviors usually only associated with coupled planners. The reactive nature of these policies is also particularly well suited for robotic deployments, especially in dynamic environments, as exhibited by our numerical and experimental results. I will then discuss our recent works, which focus on explicitly combining learning-based MAPF with conventional, complete planners towards highly scalable, yet provably complete MAPF. Finally, I will touch on some of our recent advances into communication learning, where, agents are tasked with learning a movement policy as well as a communication protocol, allowing them to identify, encode, and share relevant information about their environment/intention towards true team-level cooperation in MAPF. If time permits, I will also present preliminary results of our most recent, context-learning-based MAPF works, which aims at mitigating the effect of partial observability in decentralized, AI-based MAPF.
• Guillaume Sartoretti joined the Mechanical Engineering department at the National University of Singapore (NUS) as an Assistant Professor in 2019. He founded and is directing the Multi-Agent Robotic Motion (MARMot) lab. Before that, he was a Postdoctoral Fellow in the Robotics Institute at Carnegie Mellon University (USA), where he worked with Prof. Howie Choset. He received his Ph.D. in robotics from EPFL (Switzerland) in 2016 for his dissertation on "Control of Agent Swarms in Random Environments," under the supervision of Prof. Max-Olivier Hongler. He also holds a B.S. and an M.S. degree in Mathematics and Computer Science from the University of Geneva (Switzerland). His research focuses on the distributed/decentralized coordination of numerous agents, at the interface between stochastic modelling, conventional control, and artificial intelligence. Applications range from multi-robot systems, where independent robots and systems need to coordinate their actions to achieve a common goal, to high-DoF articulated robots, where joints need to be carefully coupled during locomotion in rough terrain. In 2018, he was awarded a Manufacturing Futures Initiative (MFI) postdoctoral fellowship for his recent work on scalable multi-agent path finding via distributed reinforcement learning.

Jingjin Yu
Rutgers University

Stack Rearrangement, Rubik Tables, and Multi-Robot Routing

• Abstract: In a basic Rubik table problem, there are $n$ item types, each with a multiplicity of $n$. These $n^2$ items are randomly placed in an $n x n$ table, one in each cell. In a shuffle, a row (resp., column) of the table may be permuted to achieve an arbitrary configuration of the items in that row (resp., column). The Rubik table problem asks how many shuffles are needed to sort the table so that type $i$ items occupies column $i$ of the table. Somewhat surprisingly, $2n$ shuffles suffice. Rubik tables and its many generalizations enables the successful tackling of difficult sequential combinatorial rearrangement problems, including stack rearrangement and multi-robot path planning, resulting in polynomial time algorithms for computing asymptotically optimal solutions that were previously not possible, to our knowledge. In particular, using Rubik table as a building block, we are able to achieve (1, 1.5] asymptotic makespan optimality for multi-robot path planning on grids in polynomial time, with high probability.
• Jingjin Yu is an Associate Professor in the Department of Computer Science, Rutgers University at New Brunswick. He received his B.S. from the University of Science and Technology of China, and obtained his M.S. in Computer Science and Ph.D. in Electrical and Computer Engineering, both from the University of Illinois, where he briefly stayed as a postdoctoral researcher. Before joining Rutgers, he was a postdoctoral researcher at the Massachusetts Institute of Technology. He is broadly interested in the area of algorithmic robotics, focusing on issues related to optimality, complexity, and the design of efficient decision-making methods. He is a recipient of the NSF CAREER award and an Amazon Research Award.