United Kingdom

Multi-Agent Path Finding (MAPF) is an NP-hard problem that has important applications for distribution centers, traffic management and computer games, and it is still difficult for current solvers to solve large instances optimally. Bounded suboptimal solvers, such as Enhanced Conflict-Based Search (ECBS) and its variants, are more efficient than optimal solvers in finding a solution with suboptimality guarantees. ECBS is a tree search algorithm that expands the search tree by repeatedly selecting search tree nodes from a focal list. In this work, we propose to use machine learning (ML) to learn a node-selection strategy to speed up ECBS. In the first phase of our framework, we use imitation learning and curriculum learning to learn node-selection strategies iteratively for different numbers of agents from training instances. In the second phase, we deploy the learned models in ECBS and test their solving performance on unseen instances drawn from the same distribution as the training instances. We demonstrate that our solver, \ML, shows substantial improvement in terms of the success rates and runtimes over ECBS on five different types of grid maps from the MAPF benchmark.

AAMAS 2021

Learning Node-Selection Strategies in Bounded-Suboptimal Conflict-Based Search for Multi-Agent Path Finding

AAMAS is the largest and most influential conference in the area of agents and multiagent systems, bringing together researchers and practitioners in all areas of agent technology and providing and internationally renowned high-profile forum for publishing and finding out about the latest developments in the field. AAMAS is the flagship conference of the non-profit International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS).  

![](https://assets.underline.io/uploads/markdown_image/1/image/ce4604bd54468a006164d16e080204fb.jpg)

Please click on the button below to register for this event.

If you are registered and see this page please check the account email you are logged in with. It must be the same as for the registration.

If you still have trouble accessing the contact please contact support at aamas2021@underline.io 

technical paper

We advocate the development of a discipline of interacting with and extracting information from models, both mathematical (e.g. game-theoretic ones) and computational (e.g. agent-based models). We outline some directions for the development of a such a discipline: - the development of logical frameworks for the systematic formal specification of stylized facts and social mechanisms in (mathematical and computational) social science. Such frameworks would bring to attention new issues, such as <i>phase transitions</i>, i.e. dramatical changes in the validity of the stylized facts beyond some critical values in parameter space. We argue that such statements are useful for those logical frameworks describing properties of ABM. - the adaptation of tools from the theory of reactive systems (such as bisimulation) to obtain practically relevant notions of two systems "having the same behavior". - the systematic development of an adversarial theory of model perturbations, that investigates the robustness of conclusions derived from models of social behavior to variations in several features of the social dynamics. These may include: activation order, the underlying social network, individual agent behavior.

Models We Can Trust: Toward a Systematic Discipline of (Agent-Based) Model Interpretation and Validation (Blue Sky Ideas Track)

We investigate a repeated two-player game setting where the column player is also a designer of the system, and has full control over payoff matrices. In addition, we assume that the row player uses a no-regret algorithm to efficiently learn how to adapt their strategy to the column player's behaviour over time. The goal of the column player is to guide her opponent into picking a mixed strategy which is preferred by the system designer. Therefore, she needs to: (i) design appropriate payoffs for both players; and (ii) strategically interact with the row player during a sequence of plays in order to guide her opponent to converge to the desired mixed strategy. To design appropriate payoffs, we propose a novel zero-sum game construction whose unique minimax solution contains the desired behaviour. We also propose another construction in which only the minimax strategy of the row player is unique. Finally, we propose a new game playing algorithm for the system designer and show that it can guide the row player to its minimax strategy, under the assumption that the row player adopts a stable  no-regret algorithm.

How to Guide a Non-Cooperative Learner to Cooperate: Exploiting No-Regret Algorithms in System Design

In this work, we consider the problem of multi-agent reinforcement learning in directed social networks with a large number of agents. Network dependencies among user activities impact the reward for individual actions and need to be incorporated into policy learning, however, directed interactions entail that the network is partially observable to each user. When estimating policies locally, the insufficient state information makes it challenging for users to effectively learn network dependencies. To address this, we use parameter sharing and ego-network extrapolation in a decentralized policy learning and execution framework. This is in contrast to previous work on social RL that assumes a centralized controller to capture inter-agent dependencies for joint policy learning. We evaluate our proposed approach on Twitter datasets and show that our decentralized learning approach achieves performance nearly equivalent to that of centralized learning approach and superior performance to other baselines.

Towards Decentralized Social Reinforcement Learning via Ego-Network Extrapolation

Artificial agents trained by deep reinforcement learning will likely encounter novel situations after deployment that were never seen during training. Our agent must be 
 to handle such situations well. However, if we cannot rely on the average training or validation reward as a metric, then how can we effectively evaluate robustness? We take inspiration from the practice of 
 in software engineering. Specifically, we suggest that when designing AI agents that collaborate with humans, designers should search for potential edge cases in 
 and 
 and write tests which check that the behavior of the agent in these edge cases is reasonable. We apply this methodology to build a suite of unit tests for the Overcooked-AI environment, and use this test suite to evaluate three proposals for improving robustness. We find that the test suite provides significant insight into the effects of these proposals that were generally not revealed by looking solely at the average validation reward. For our full paper, see https://arxiv.org/abs/2101.05507 arxiv.org/abs/2101.05507

Evaluating the Robustness of Collaborative Agents

In recent work, Gourvès, Lesca, and Wilczynski propose a variant of the classic housing markets model where the matching between agents and objects evolves through Pareto-improving swaps between pairs of adjacent agents in a social network. To explore the swap dynamics of their model, they pose several basic questions concerning the set of reachable matchings. In their work and other follow-up works, these questions have been studied for various classes of graphs: stars, paths, generalized stars (i.e., trees where at most one vertex has degree greater than two), trees, and cliques. For generalized stars and trees, it remains open whether a Pareto-efficient reachable matching can be found in polynomial time.

Object Allocation Over a Network of Objects: Mobile Agents with Strict Preferences

In this work we present the Hanabi Open Agent Dataset (HOAD)— meant to address the current lack of Hanabi datasets, HOAD is an easily extensible, open-sourced, and comprehensive collection of existing Hanabi playing agents, all ported to the Hanabi Learning Environment (HLE). We give a description and analysis of each agent’s strategy, and we also show cross-play performance between all the agents, demonstrating both their high quality and diversity of strategy. These properties make HOAD especially well suited to studies involving meta-learning and transfer learning. Finally, we describe in detail an easy way to add new agents to HOAD regardless of the origin codebase of the agent and make our code and dataset publicly available at https://github.com/aronsar/hoad.

HOAD: The Hanabi Open Agent Dataset

We present a scalable tree search planning algorithm for large multi-agent sequential decision problems that require dynamic collaboration. Teams of agents need to coordinate decisions in many domains, but naive approaches fail due to the exponential growth of the joint action space with the number of agents. We circumvent this complexity through an anytime approach that allows us to trade computation for approximation quality and also dynamically coordinate actions. Our algorithm comprises three elements: online planning with Monte Carlo Tree Search (MCTS), factored representations of local agent interactions with coordination graphs, and the iterative Max-Plus method for joint action selection. We evaluate our approach on the benchmark SysAdmin domain with static coordination graphs and achieve comparable performance with much lower computation cost than our MCTS baselines. We also introduce a multi-drone delivery domain with dynamic, i.e., state-dependent coordination graphs, and demonstrate how our approach scales to large problems on this domain that are intractable for other MCTS methods. We provide an open-source implementation of our algorithm at https://github.com/JuliaPOMDP/FactoredValueMCTS.jl.

Scalable Anytime Planning for Multi-Agent MDPs

Consider a typical organization whose worker agents seek to collectively cooperate for its general betterment. However, each individual agent simultaneously seeks to act to secure a larger chunk than its co-workers of the annual increment in compensation, which usually comes from a fixed pot. As such, the agents in an organization must cooperate and compete. Another feature of many organizations is that a worker receives a bonus, which is often a fraction of previous year’s total profit. As such, the agent derives a reward that is also partly dependent on historical performance. How should the individual agent decide to act in this context? Few methods for the mixed cooperative-competitive setting have been presented in recent years, but these are challenged by problem domains whose reward functions additionally depend on historical information. Recent deep multi-agent reinforcement learning (MARL) methods using long short-term memory (LSTM) may be used, but these adopt a joint perspective to the interaction or require explicit exchange of information among the agents to promote cooperation, which may not be possible under competition. In this paper, we first show that the agent’s decision-making problem can be modeled as an interactive partially observable Markov decision process (I-POMDP) that captures the dynamic of a history-dependent reward. We present an interactive advantage actor-critic method (IA2C+), which combines the independent advantage actor-critic network with a belief filter that maintains a belief distribution over other agents’ models. Empirical results show that IA2C+ learns the optimal policy faster and more robustly than several baselines.

Cooperative-Competitive Reinforcement Learning with History-Dependent Rewards

We study several fairness notions in allocating indivisible chores (i.e., items with non-positive values): envy-freeness and its relaxations. For allocations under each fairness criterion, we establish their approximation guarantees for other fairness criteria. Under the setting of additive cost functions, our results show strong connections between these fairness criteria and, at the same time, reveal intrinsic differences between goods allocation and chores allocation. Furthermore, we investigate the efficiency loss under these fairness constraints and establish their prices of fairness.

Connections between Fairness Criteria and Efficiency for Allocating Indivisible Chores

In the facility location problem with continuous demands, where customers are continuously distributed on an area, a planner wants to locate the facilities and allocate the customers to their closest facilities under the proximity rule. In this work, we focus on the fairness and system efficiency from the facility's perspective. Each facility is assumed to have a preference (represented as valuation function) over the subsets of customers. For the fairness of facilities, we provide approximation guarantees for the proportionality and envy-freeness. For the efficiency, we study the utilitarian and egalitarian social welfare. In addition, we are interested in quantifying the possible trade-offs between meeting the fairness criteria and maximizing social welfare, measured by the price of fairness.

Learning Node-Selection Strategies in Bounded-Suboptimal Conflict-Based Search for Multi-Agent Path Finding

Downloads

Next from AAMAS 2021

Models We Can Trust: Toward a Systematic Discipline of (Agent-Based) Model Interpretation and Validation (Blue Sky Ideas Track)

Similar lecture

Modelling Cooperation in Network Games with Spatio-Temporal Complexity

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES