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

We explore the class of problems where a central planner needs to select a subset of agents, each with different quality and cost. The planner wants to maximize its utility while ensuring that the average quality of the selected agents is above a certain threshold. When the agents' quality is known, we formulate our problem as an integer linear program (ILP) and propose a deterministic algorithm, namely \dpss\ that provides an exact solution to our ILP.

A Multi-Arm Bandit Approach To Subset Selection Under Constraints

Robots need task planning to sequence and execute actions toward achieving their goals. On the other hand, Behavior Trees provide a mathematical model for specifying plan execution in an intrinsically composable, reactive, and robust way. PDDL (Planning Domain Definition Language) has become the standard description language for most planners. In this paper, we present a novel algorithm to systematically create behavior trees from PDDL plans to execute them. This approach uses the execution graph of the plan to generate a behavior tree. The most remarkable contribution of this approach is the algorithm to build a Behavior Tree that optimizes its execution by paralyzing actions, applicable to any plan, taking into account the actions' causal relationships. We demonstrate the improvement in the execution of plans in mobile robots using the ROS2 Planning System framework.

Optimized Execution of PDDL Plans using Behavior Trees

The paper summarises a systematic literature review (SLR) over logic-based technologies for MAS.

Logic-based Technologies for Multi-agent Systems: Summary of a Systematic Literature Review (JAAMAS Track)

When agents independently learn knowledge, such as ontologies, about their environment, it may be diverse, incorrect or incomplete. This knowledge heterogeneity could lead agents to disagree, thus hindering their cooperation. Existing approaches usually deal with this interaction problem by relating ontologies, without modifying them, or, on the contrary, by focusing on building common knowledge. Here, we consider agents adapting ontologies learned from the environment in order to agree with each other when cooperating. In this scenario, fundamental questions arise: Do they achieve successful interaction? Can this process improve knowledge correctness? Do all agents end up with the same ontology? To answer these questions, we design a two-stage experiment. First, agents learn to take decisions about the environment by classifying objects and the learned classifiers are turned into ontologies. In the second stage, agents interact with each other to agree on the decisions to take and modify their ontologies accordingly. We show that agents indeed reduce interaction failure, most of the time they improve the accuracy of their knowledge about the environment, and they do not necessarily opt for the same ontology.

Knowledge Improvement and Diversity under Interaction-Driven Adaptation of Learned Ontologies

BDI agents act in response to external inputs and their internal plan library. Understanding the root cause of BDI agent action is often difficult, and in this paper we present a dialogue based approach for explaining the behaviour of a BDI agent. We consider two dialogue participants who may have different views regarding the beliefs, plans and external events which drove agent action (encoded via traces). These participants make utterances which incrementally reveal their traces to each other, allowing them to identify divergences in the traces, or to conclude that their traces agree. In practice, we envision a human taking on the role of a dialogue participant, with the BDI agent itself acting as the other participant. The dialogue then facilitates explanation, understanding and debugging of BDI agent behaviour. After presenting our formalism and its properties, we describe our implementation of the system and provide an example of its use in a simple scenario.

Explaining BDI Agent Behaviour through Dialogue

Communication improves the efficiency and convergence of multi-agent learning. Existing study of agent communication has been limited on predefined fixed connections. While an attention mechanism exists and is useful for scheduling the communication between agents, it, however, largely ignores the dynamical nature of communication and thus the correlation between agents' connections. In this work, we adopt a normalizing flow to encode correlation between agents interactions. The dynamical communication topology is directly learned by maximizing the agent rewards. In our end-to-end formulation, the communication structure is learned by considering it as a hidden dynamical variable. We realize centralized training of critics and graph reasoning policy, and decentralized execution from local observation and message that are received through the learned dynamical communication topology. Experiments on cooperative navigation in the particle world and adaptive traffic control tasks demonstrate the effectiveness of our method.

Learning Correlated Communication Topology in Multi-Agent Reinforcement learning

A key problem for Belief-Desire-Intention (BDI) agents is <i>intention progression, i.e., which plans should be selected and how the execution of these plans should be interleaved so as to achieve the agent's goals. Monte-Carlo Tree Search (MCTS) has been shown to be a promising approach to the intention progression problem, out-performing other approaches in the literature. However, MCTS relies on runtime simulation of possible interleavings of the plans in each intention, which may be computationally costly. In this paper, we introduce the notion of quantitative summary information</i> which can be used to estimate the likelihood of conflicts between an agent's intentions. We show how offline simulation can be used to precompute quantitative summary information prior to execution of the agent's program, and how the precomputed summary information can be used at runtime to guide the expansion of the MCTS search tree and avoid unnecessary runtime simulation. We compare the performance of our approach with standard MCTS in a range of scenarios of increasing difficulty. The results suggest our approach can significantly improve the efficiency of MCTS in terms of the number of runtime simulations performed.

Intention Progression using Quantitative Summary Information

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

Designing autonomous agents that act collaboratively to achieve a common set of goals has been a major goal for Artificial Intelligence research for many years. Collaborative Privacy-Preserving Planning (cppp) is a multi-agent planning task in which agents need to achieve a common set of goals without revealing certain private information [2]. In particular, in cppp an individual agent may have a set of private facts and actions that it does not share with the other agents. cppp has important motivating examples, such as planning for organizations that outsource some of their tasks, and has recently received considerable attention from the academic community.

Partial Disclosure of Private Dependencies in Privacy Preserving Planning

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.

Anytime Multi-Agent Path Finding via Large Neighborhood Search

Next from AAMAS 2021

A Multi-Arm Bandit Approach To Subset Selection Under Constraints

Similar lecture

An Abstraction-based Method to Check Multi-Agent Deep Reinforcement-Learning Behaviors

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES