United Kingdom

Multi-Agent Path Finding (MAPF) is the challenging problem of computing collision-free paths for a cooperative team of moving agents. Algorithms for solving MAPF can be categorized on a spectrum. At one end are (bounded-sub)optimal algorithms that can find high-quality solutions for small problems. At the other end are unbounded-suboptimal algorithms (including prioritized and rule-based algorithms) that can solve very large practical problems but usually find low-quality solutions. In this paper, we consider a third approach that combines both advantages: anytime algorithms that quickly find an initial solution, including for large problems, and that subsequently improve the solution to near-optimal as time progresses. To improve the solution, we replan subsets of agents using Large Neighborhood Search, a popular meta-heuristic often applied in combinatorial optimization. Empirically, we compare our algorithm MAPF-LNS to the state-of-the-art anytime MAPF algorithm anytime BCBS and report significant gains in scalability, runtime to the first solution, and speed of improving solutions.

AAMAS 2021

Anytime Multi-Agent Path Finding via Large Neighborhood Search

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 

poster

The introduction of driver-less technologies can improve on-demand transport (ODT) systems and help make passenger transportation and logistics more efficient. Here, we aim to provide a generic model of the online ODT with autonomous vehicles problem and a multi-agent model specific to resource allocation and scheduling in vehicle fleets. Our model considers autonomous vehicles that communicate via peer-to-peer radio channels to meet passenger requirements and satisfy trip requests in an online ODT system. We experiment this model with several allocation mechanisms (mathematical programming, greedy heuristic, distributed constraint optimization, and auctions) and compare their performance on synthetic scenarios on a real-world city road network.

A Generic Multi-Agent Model for Resource Allocation Strategies in Online On-Demand Transport with Autonomous Vehicles

Graceful degradation is a desirable trait in applications that require coverage with real, failure-prone robots. Thus paper uses methods informed by Reliability Engineering to study the Reliability-Aware Multi-Agent Coverage Path Planning (RA-MCPP) problem. An augmented stochastic framework is applied to evaluate a strategy's probability of mission completion. An augmented stochastic framework is applied to evaluate a strategy's probability of mission completion (PoC) on 3D lattice graph environments. A Genetic Algorithm optimisation approach is then proposed to find RA-MCPP path plans which maximise PoC. It is shown that the GA provides good solutions at reasonable runtimes, complementing previous approaches which focused on global optimality guarantees at the cost of massive computation, especially for medium and large environments.

Reliability-Aware Multi-UAV Coverage Path Planning using a Genetic Algorithm

The Incomplete Distributed Constraint Optimization Problem (I-DCOP) extends the distributed constraint optimization problem, where constraint costs are allowed to be unspecified. A distributed variant of the Synchronous Branch-and-Bound (SyncBB) search algorithm has been proposed to solve I-DCOPs, where unspecified constraint costs are elicited during its execution. In this paper, we propose two heuristics that can be used in conjunction with SyncBB to solve I-DCOPs. Our proposed heuristics speed up the algorithm by pruning those parts of the search space whose solution quality is sub-optimal. Thus, our model and heuristics extend the state of the art in distributed constraint reasoning to better model and solve distributed agent-based applications with user preferences.

Branch-and-Bound Heuristics for Incomplete DCOPs

Plan recognition is the task of inferring the actual plan an observed agent is performing to achieve a goal, given domain theory and a partial, possibly noisy, sequence of observations. Applications include natural language processing, elder-care, multi-agent systems, collaborative problem-solving, epistemic problems, and more. Real-world plan recognition problems impose limitations on the quality and quantity of the observations, which may be missing or faulty from silent errors in the sensors. While recent approaches to goal and plan recognition have substantially improved performance under partial observability and noisy conditions, dealing with these problems remains a challenge. Recent work on goal and plan recognition use machine learning to assist planning-based approaches in modeling domains. Such techniques yield robust models capable of accurate predictions with missing or noisy data. Thus inspired, we develop a novel approach to solve both goal and plan recognition tasks simultaneously by combining planning and machine learning techniques to mitigate problems of low and faulty observability.

Combining LSTMs and Symbolic Approaches for Robust Plan Recognition

Narrative planning algorithms coordinate the virtual agents of interactive environments. Sabre is a single, centralized, omniscient decision maker that solves a multi-agent problem. It has a system-level author goal it must achieve, but every action taken by an agent must make sense according to that agent's individual intentions and limited, possibly wrong beliefs. We describe our motivation for solving such problems and the difficulties of comparing our planner to existing systems.

The Sabre Narrative Planner: Multi-Agent Coordination with Intentions and Beliefs

Missed connections at transit airports are a source of both poor customer experience   and reduced airline operational efficiency. Airlines typically handle missed connections by rebooking customers. Recently, airlines have started holding departing flights for some time in a rule-based manner to avoid missed connections. However, rule-based heuristics typically use information local to a flight and do not learn in a globally informed way across the entire network. We complement existing approaches by learning a policy for holding a flight to avoid misconnections, using reinforcement learning (RL). The state presented to the RL agent uses forecasted flight-specific context; and measured network-wide context. The reward uses components that trade off the decrease in on-time performance due to the hold decisions, for a decrease in missed connections. We attribute the global rewards to individual local hold actions through a novel delay tree that approximates the network interactions. Multiple flights are handled through the same instance of the agent handling them in sequence with varying state information. We evaluate our approach for two different airlines with training and testing over a microsimulator that uses real-world data for calibration. Across different algorithms (DQN, AC, A2C, DDPG), we find that the best performing RL-based agent is able to reduce significantly more (up to 50%) missed connections for a minimal decrease (~5%) in on-time performance; when compared with a current rule-based heuristic. Further, the approach is tunable and able to transfer learn across different airlines.

To hold or not to hold? - Reducing Passenger Missed Connections in Airlines using Reinforcement Learning

Open-world AI requires artificial agents to cope with novelties that arise during task performance, i.e., they must (1) detect novelties, (2) characterize them, in order to (3) accommodate them, especially in cases where sudden changes to the environment make task accomplishment impossible without utilizing the novelty. We present a formal framework and implementation thereof in a cognitive agent for novelty handling and demonstrate the efficacy of the proposed methods for detecting and handling a large set of novelties in a crafting task in a simulated environment. We discuss the success of the proposed knowledge-based methods and propose heuristic extensions that will further improve novelty handling in open-worlds tasks.

A Novelty-Centric Agent Architecture for Changing Worlds

Human gaze is known to be an intention-revealing signal in human demonstrations of tasks. In this work, we use gaze cues from human demonstrators to enhance the performance of agents trained via three popular imitation learning methods    behavioral cloning (BC), behavioral cloning from observation (BCO), and Trajectory-ranked Reward EXtrapolation (T-REX). Based on similarities between the attention of reinforcement learning agents and human gaze, we propose a novel approach for utilizing gaze data in a computationally efficient manner, as part of an auxiliary loss function, which guides a network to have higher activations in image regions where the human’s gaze fixated. This work is a step towards augmenting any existing convolutional imitation learning agent's training with auxiliary gaze data. Our auxiliary coverage-based gaze loss (CGL) guides learning toward a better reward function or policy, without adding any additional learnable parameters and without requiring gaze data at test time. We find that our proposed approach improves the performance by 95% for BC, 343% for BCO, and 390% for TREX, averaged over 20 different Atari games. We also find that compared to a prior state-of-the-art imitation learning method assisted by human gaze (AGIL), our method achieves better performance, and is more efficient in terms of learning with fewer demonstrations. We further interpret trained CGL agents with a saliency map visualization method to explain their performance. At last, we show that CGL can help alleviate a well-known causal confusion problem in imitation learning.

Efficiently Guiding Imitation Learning Agents with Human Gaze

This paper presents an intelligent and adaptive agent that employs deception to recognize a cyber adversary's intent on a honeypot host. Unlike previous approaches to cyber deception, which mainly focus on delaying or confusing the attackers, we focus on engaging with them to learn their intent. We model cyber deception as a sequential decision-making problem in a two-agent context. We introduce factored finitely-nested interactive POMDPs (I-POMDP X ) and use this framework to model the problem with multiple attacker types. Our approach models cyber attacks on a single honeypot host across multiple phases from the attacker's initial entry to reaching its adversarial objective. The defending I-POMDP X -based agent uses decoys to engage with the attacker at multiple phases to form increasingly accurate predictions of the attacker’s behavior and intent. The use of I-POMDPs also enables us to model the adversary's mental state and investigate how deception affects their beliefs. Our experiments in both simulation and with the agent deployed on a host system show that the I-POMDP X -based agent performs significantly better at intent recognition than commonly used deception strategies on honeypots. This emerging application of autonomous agents offers a new approach that contrasts with the traditional action-reaction dynamic that has defined interactions between cyber attackers and defenders for years.

Cyber Attack Intent Recognition and Active Deception using Factored Interactive POMDPs

Crowd movement guidance has been a fascinating problem in various fields, such as easing traffic congestion in unusual events and evacuating people from an emergency-affected area. To grab the reins of crowds, there has been considerable demand for a decision support system that can answer a typical question: "what will be the outcomes of each of the possible options in the current situation". In this paper, we consider the problem of estimating the effects of crowd movement guidance from past data. To cope with limited amount of available data biased by past decision-makers, we leverage two recent techniques in deep representation learning for spatial data analysis and causal inference. We use a spatial convolutional operator to extract effective spatial features of crowds from a small amount of data and use balanced representation learning based on the integral probability metrics to mitigate the selection bias and missing counterfactual outcomes. To evaluate the performance on estimating the treatment effects of possible guidance, we use a multi-agent simulator to generate realistic data on evacuation scenarios in a crowded theater, since there are no available datasets recording outcomes of all possible crowd movement guidance. The results of three experiments demonstrate that our proposed method reduces the estimation error by at most 56% from state-of-the-art methods.

Next from AAMAS 2021

A Generic Multi-Agent Model for Resource Allocation Strategies in Online On-Demand Transport with Autonomous Vehicles

Similar lecture

Anytime Multi-Agent Path Finding via Large Neighborhood Search