United Kingdom

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&#39;s probability of mission completion. An augmented stochastic framework is applied to evaluate a strategy&#39;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.

AAMAS 2021

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

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 

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.

poster

Agents can individually devise plans and coordinate to achieve common goals. Methods exist to factor planning problems into separate tasks and distribute the plan synthesis process, while reducing the overall planning complexity. Merging distributedly generated plans becomes computationally costly when task plans are tightly coupled, and conflicts arise due to dependencies between plan actions. New plan merging algorithms allow factoring and solving large problems with a growing number of agents and tasks, but are yet to be demonstrated in physical real-world systems.   This Demo presents an architecture that deploys plan merging algorithms in a physical multi-robot setting and emulates a First Response Domain.

Scalable Multiple Robot Task Planning with Plan Merging and Conflict Resolution

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

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

In safe Reinforcement Learning (RL), the agent attempts to find policies which maximize the expectation of accumulated rewards and guarantee its safety to remain above a given threshold. Hence, it is straightforward to formalize safe RL problems by both a reward function and a safety constraint. We define safety as the probability of survival in environments where taking risky actions could lead to early termination of the task. Although the optimization problem is already constrained by a safety threshold, reward signals related to unsafe terminal states influence the original maximization objective of the task. Selecting the appropriate value of these signals is often a time consuming and challenging reward engineering task, which requires expert knowledge of the domain.     This paper presents a safe RL algorithm, called Masked Constrained Policy Optimization (MCPO), in which the learning process is constrained by safety and excludes the risk reward signals. We develop MCPO as an extension of gradient-based policy search methods, in which the updates of the policy and the expected reward models are masked. Our method benefits from having a high probability of satisfying the given constraints for every policy in the learning process. We validate the proposed algorithm in two continuous tasks. Our findings prove the proposed algorithm is able to neglect risk reward signals, and thereby resolving the desired safety-performance trade-off without having the need for hand-tuning rewards.

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

Speakers

Next from AAMAS 2021

Scalable Multiple Robot Task Planning with Plan Merging and Conflict Resolution

Similar lecture

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