United Kingdom

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&#39;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.

AAMAS 2021

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

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 

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.

poster

We study a variant of the continuous multi-armed bandits problem, where the objective is to estimate the sensitivity threshold for an unknown psychometric function ¶si. This setting models the conduct of a psychometric experiment, which aims at quantifying human perception. We show that this setting is akin to hierarchical multi-armed bandits and Black-box optimization of noisy functions, with both significant similarities and key differences. We introduce a new algorithm, DOS, for Dichotomous Optimistic Search, that efficiently solves this task, and show that DOS outperforms recent methods from both Psychophysics and Global Optimization for non Gaussian Psychometric functions in our experiments.

Quantifying Human Perception with Multi-Armed Bandits

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

In service robot applications, planning is often integrated with task allocation.  Linear Temporal Logic (LTL) as an expressive high-level formalism is widely used for task specification, and allows for formalised restrictions on temporal sequences of tasks.   In multiagent planning, a Multi-Objective Markov Decision Process extends the standard model with vector rewards capturing possibly conflicting planning objectives. Such objectives include the success rates of accomplishing individual tasks, and the cost budgets for individual agents. In this paper, we consider the problem of concurrently allocating LTL task sequences to a team of agents and calculating optimal task schedulers simultaneously, satisfying cost and probability thresholds. We reduce this problem to multi-objective scheduler synthesis for a team MDP structure, whose size is linear in the number of agents. Our preliminary experiment demonstrates the scalability of our approach.

Multiagent Task Allocation and Planning with Multi-Objective Requirements

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

In this paper, we study the problem of learning to satisfy temporal logic specifications with a group of agents in an unknown environment, which may exhibit probabilistic behaviour. From a learning perspective these specifications provide a rich formal language with which to capture tasks or objectives, while from a logic and automated verification perspective the introduction of learning capabilities allows for practical applications in large, stochastic, unknown environments. The existing work in this area is, however, limited. Of the frameworks that consider full linear temporal logic or have correctness guarantees, all methods thus far consider only the case of a single temporal logic specification and a single agent. In order to overcome this limitation, we develop the first multi-agent reinforcement learning technique for temporal logic specifications, which is also novel in its ability to handle multiple specifications. We provide correctness and convergence guarantees for our main algorithm – ALMANAC (Automaton/Logic Multi-Agent Natural Actor-Critic) – even when using function approximation. Alongside our theoretical results, we further demonstrate the applicability of our technique via a set of preliminary experiments.

Multi-Agent Reinforcement Learning with Temporal Logic Specifications

A robust testing program is necessary for containing the spread of COVID-19 infections before a vaccine becomes available. However, due to an acute shortage of testing kits (especially in low-resource developing countries), designing an optimal testing program/strategy is a challenging problem to solve. Prior literature on testing strategies suffers from two major limitations: (i) it does not account for the trade-off between testing of symptomatic and asymptomatic individuals, and (ii) it primarily focuses on static testing strategies, which leads to significant shortcomings in the testing program's effectiveness. In this paper, we address these limitations by making five novel contributions. (i) We formally define the optimal testing problem and propose the DOCTOR POMDP model to tackle it. (ii) We solve the DOCTOR POMDP using a scalable Monte Carlo tree search based algorithm. (iii) We provide a rigorous experimental analysis of DOCTOR's testing strategies against static baselines - our results show that when applied to the city of Santiago in Panama, DOCTOR's strategies result in approximately 40% fewer COVID-19 infections (over one month) as compared to state-of-the-art static baselines. (iv) In addition, we analyze DOCTOR's testing policy to derive insights about the reasons behind the optimality of DOCTOR's testing policy. (v) Finally, we characterize conditions (of the real world) under which DOCTOR's optimization would be of most benefit to government policy makers, and thus requires significant attention from researchers in this area. Our work complements the growing body of research on COVID-19, and serves as a proof-of-concept that illustrates the benefit of having an AI-driven adaptive testing strategy for COVID-19.

Let the DOCTOR Decide Whom to Test: Adaptive Testing Strategies to Tackle the COVID-19 Pandemic

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

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.

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

Next from AAMAS 2021

Quantifying Human Perception with Multi-Armed Bandits

Similar lecture

Aggregating Bipolar Opinions

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES