Arrow Research search

Author name cluster

Bruno Lacerda

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

43 papers
2 author rows

Possible papers

43

AAMAS Conference 2026 Conference Paper

Multi-Agent Pickup and Delivery with Heterogeneous Agents

  • Benedetta Flammini
  • Francesco Amigoni
  • Bruno Lacerda

The Multi-Agent Pickup and Delivery (MAPD) problem involves a team of agents that plan collision-free paths to perform tasks, which appear over time, consisting of picking up and delivering items. Usually, agentsareconsideredhomogeneous. Forexample, an agent can move everywhere in the environment and can complete any task. In this paper, we study the MAPD problem in a setting with heterogeneous agents, where different classes of agents have distinct capabilities and can operate in different areas of the environment. Unlike classical MAPD formulations, our setting requires cooperation across agent classes to complete tasks, possibly spanning multiple operable zones, which requires agents of different classes to exchange items through handovers at frontier locations betweentheiroperablezones. Toaddressthischallenge, wepropose atwo-levelplanningframeworkthatfirstcomputeshigh-levelpaths for items across zones, determining where exchanges should occur, and then determines which agents will transport items along these high-level paths while generating collision-free low-level paths for each transporting agent. This approach coordinates item transfers and agent movements while respecting their heterogeneous capabilities. We evaluate our approach in simulated environments inspired by practical real-world scenarios.

PDF

AAAI Conference 2026 Conference Paper

Scalable Solution Methods for Dec-POMDPs with Deterministic Dynamics

  • Yang You
  • Alex Schutz
  • Zhikun Li
  • Bruno Lacerda
  • Robert Skilton
  • Nick Hawes

Many high-level multi-agent planning problems, such as multi-robot navigation and path planning, can be modeled with deterministic actions and observations. In this work, we focus on such domains and introduce the class of Deterministic Decentralized POMDPs (Det-Dec-POMDPs)—a subclass of Dec-POMDPs with deterministic transitions and observations given the state and joint actions. We then propose a practical solver, Iterative Deterministic POMDP Planning (IDPP), based on the classic Joint Equilibrium Search for Policies framework, specifically optimized to handle large-scale Det-Dec-POMDPs that existing Dec-POMDP solvers cannot handle efficiently.

PDF Details DOI

AAMAS Conference 2026 Conference Paper

Think Fast! Learning to Control Online Reasoning in Stochastic Environments

  • Matthew Budd
  • Bruno Lacerda
  • Nick Hawes

When an autonomous agent’s decision-making has resource costs or incurs potential real-world consequences, its performance can be improved by reasoning about its own decision-making process. This is known as metareasoning, and is a key capability of rational agents. However, existing metareasoning methods have significant limitations. Most apply only to the offline setting, controlling only how long the agent should think before executing its current best solution. Few methods exist for online metareasoning, where the agent can interleave thinking and acting, and these make strong simplifying assumptions that limit their performance. It is rarer still for methods to be applicable to stochastic problems, or to consider the effects of the environment on the agent’s planning process. In this work we extend a learning-based metareasoning method for probabilistic planning to the online setting. The framework enables the agent to learn when, where and how to think in order to make better decisions in stochastic environments. We demonstrate our method outperforming several baselines across two domain distributions, each highlighting different benefits of online metareasoning.

PDF

IJCAI Conference 2025 Conference Paper

A Finite-State Controller Based Offline Solver for Deterministic POMDPs

  • Alex Schutz
  • Yang You
  • Matías Mattamala
  • Ipek Caliskanelli
  • Bruno Lacerda
  • Nick Hawes

Deterministic partially observable Markov decision processes (DetPOMDPs) often arise in planning problems where the agent is uncertain about its environmental state but can act and observe deterministically. In this paper, we propose DetMCVI, an adaptation of the Monte Carlo Value Iteration (MCVI) algorithm for DetPOMDPs, which builds policies in the form of finite-state controllers (FSCs). DetMCVI solves large problems with a high success rate, outperforming existing baselines for DetPOMDPs. We also verify the performance of the algorithm in a real-world mobile robot forest mapping scenario.

PDF Details DOI

NeurIPS Conference 2025 Conference Paper

Improving Regret Approximation for Unsupervised Dynamic Environment Generation

  • Harry Mead
  • Bruno Lacerda
  • Jakob Foerster
  • Nick Hawes

Unsupervised Environment Design (UED) seeks to automatically generate training curricula for reinforcement learning (RL) agents, with the goal of improving generalisation and zero-shot performance. However, designing effective curricula remains a difficult problem, particularly in settings where small subsets of environment parameterisations result in significant increases in the complexity of the required policy. Current methods struggle with a difficult credit assignment problem and rely on regret approximations that fail to identify challenging levels, both of which are compounded as the size of the environment grows. We propose Dynamic Environment Generation for UED (DEGen) to enable a denser level generator reward signal, reducing the difficulty of credit assignment and allowing for UED to scale to larger environment sizes. We also introduce a new regret approximation, Maximised Negative Advantage (MNA), as a significantly improved metric to optimise for, that better identifies more challenging levels. We show empirically that MNA outperforms current regret approximations and when combined with DEGen, consistently outperforms existing methods, especially as the size of the environment grows. We have made all our code available here: \url{https: //github. com/HarryMJMead/Dynamic-Environment-Generation-for-UED}.

PDF Details

IROS Conference 2025 Conference Paper

Multi-Agent Pickup and Delivery with Mobile Pickups

  • Benedetta Flammini
  • Nick Hawes
  • Bruno Lacerda

In Multi-Agent Pickup and Delivery (MAPD), a team of agents must find collision-free paths to service an online stream of tasks, which are composed of pickup and delivery locations that have to be visited sequentially. This paper addresses the novel problem of MAPD with mobile pickups, which involves two types of agents, the suppliers and the deliverers. Suppliers are large robots that can transport many items, but cannot navigate tight spaces or manipulate objects, while deliverers can navigate to rooms to deliver items, but can only carry one item at a time. Deliverers have to collect items from the suppliers, and bring them to the assigned delivery locations. This introduces a new challenge which is not tackled in classical MAPD: deciding where and when the exchange of items should happen. We propose Token Passing with Exchange Locations (TP-EL), an extension of the widely used Token Passing (TP) algorithm with a task allocation mechanism that considers which supplier to pick items from, and when and where to do so. We experiment in several simulated domains, demonstrating the superiority of TP-EL over baselines that do not consider mobile pickups or use alternative methods to decide pickup locations.

Details

ICML Conference 2025 Conference Paper

Return Capping: Sample Efficient CVaR Policy Gradient Optimisation

  • Harry Mead
  • Clarissa Costen
  • Bruno Lacerda
  • Nick Hawes

When optimising for conditional value at risk (CVaR) using policy gradients (PG), current methods rely on discarding a large proportion of trajectories, resulting in poor sample efficiency. We propose a reformulation of the CVaR optimisation problem by capping the total return of trajectories used in training, rather than simply discarding them, and show that this is equivalent to the original problem if the cap is set appropriately. We show, with empirical results in an number of environments, that this reformulation of the problem results in consistently improved performance compared to baselines. We have made all our code available here: https: //github. com/HarryMJMead/cvar-return-capping.

Details

TAAS Journal 2024 Journal Article

A Framework for Simultaneous Task Allocation and Planning under Uncertainty

  • Fatma Faruq
  • Bruno Lacerda
  • Nick Hawes
  • David Parker

We present novel techniques for simultaneous task allocation and planning in multi-robot systems operating under uncertainty. By performing task allocation and planning simultaneously, allocations are informed by individual robot behaviour, creating more efficient team behaviour. We go beyond existing work by planning for task reallocation across the team given a model of partial task satisfaction under potential robot failures and uncertain action outcomes. We model the problem using Markov decision processes, with tasks encoded in co-safe linear temporal logic, and optimise for the expected number of tasks completed by the team. To avoid the inherent complexity of joint models, we propose an alternative model that simultaneously considers task allocation and planning, but in a sequential fashion. We then build a joint policy from the sequential policy obtained from our model, thus allowing for concurrent policy execution. Furthermore, to enable adaptation in the case of robot failures, we consider replanning from failure states and propose an approach to preemptively replan in an anytime fashion, replanning for more probable failure states first. Our method also allows us to quantify the performance of the team by providing an analysis of properties, such as the expected number of completed tasks under concurrent policy execution. We implement and extensively evaluate our approach on a range of scenarios. We compare its performance to a state-of-the-art baseline in decoupled task allocation and planning: sequential single-item auctions. Our approach outperforms the baseline in terms of computation time and the number of times replanning is required on robot failure.

Details DOI

ECAI Conference 2024 Conference Paper

Hierarchical Planning for Resource-Constrained Long-Term Monitoring Missions in Time-Varying Environments

  • Alex Stephens
  • Bruno Lacerda
  • Nick Hawes

We consider autonomous robots deployed on long-term monitoring missions in unknown environments. The planning objective is to maximise the value of observations obtained over the course of a mission, subject to resource constraints which demand periodic visits to depots where resources can be replenished. Effective planning in this setting requires reasoning over long horizons based on sparse observational data, and flexible management of the constrained resources. We present a hierarchical planning approach to this problem, using a spatiotemporal Gaussian process environment model at different levels of abstraction for short- and long-horizon planning. We empirically evaluate our approach on a series of synthetic domains, and a wildfire monitoring scenario based on real data.

Details

AAMAS Conference 2024 Conference Paper

JaxMARL: Multi-Agent RL Environments and Algorithms in JAX

  • Alexander Rutherford
  • Benjamin Ellis
  • Matteo Gallici
  • Jonathan Cook
  • Andrei Lupu
  • Garðar Ingvarsson
  • Timon Willi
  • Akbir Khan

Benchmarks play an important role in the development of machine learning algorithms, with reinforcement learning (RL) research having been heavily influenced by the available environments. However, RL environments are traditionally run on the CPU, limiting their scalability with typical academic compute. Recent advancements in JAX have enabled the wider use of hardware acceleration to overcome these computational hurdles, enabling massively parallel RL training pipelines and environments. This is particularly useful for multi-agent reinforcement learning (MARL) research. First of all, multiple agents must be considered at each environment step, adding computational burden, and secondly, the sample complexity is increased due to non-stationarity, decentralised partial observability, or other MARL challenges. In this paper, we present JaxMARL, the first open-source code base that combines ease-ofuse with GPU enabled efficiency, and supports a large number of commonly used MARL environments as well as popular baseline algorithms. When considering wall clock time, our experiments Proc. of the 23rd International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2024), N. Alechina, V. Dignum, M. Dastani, J. S. Sichman (eds.), May 6 – 10, 2024, Auckland, New Zealand. © 2024 International Foundation for Autonomous Agents and Multiagent Systems (www. ifaamas. org). This work is licenced under the Creative Commons Attribution 4. 0 International (CC-BY 4. 0) licence. show that per-run our JAX-based training pipeline is up to 12500x faster than existing approaches. We also introduce and benchmark SMAX, a vectorised, simplified version of the popular StarCraft Multi-Agent Challenge, which removes the need to run the Star- Craft II game engine. This not only enables GPU acceleration, but also provides a more flexible MARL environment, unlocking the potential for self-play, meta-learning, and other future applications in MARL. We provide code at https: //github. com/flairox/jaxmarl.

PDF

NeurIPS Conference 2024 Conference Paper

JaxMARL: Multi-Agent RL Environments and Algorithms in JAX

  • Alexander Rutherford
  • Benjamin Ellis
  • Matteo Gallici
  • Jonathan Cook
  • Andrei Lupu
  • Garðar Ingvarsson
  • Timon Willi
  • Ravi Hammond

Benchmarks are crucial in the development of machine learning algorithms, significantly influencing reinforcement learning (RL) research through the available environments. Traditionally, RL environments run on the CPU, which limits their scalability with the computational resources typically available in academia. However, recent advancements in JAX have enabled the wider use of hardware acceleration, enabling massively parallel RL training pipelines and environments. While this has been successfully applied to single-agent RL, it has not yet been widely adopted for multi-agent scenarios. In this paper, we present JaxMARL, the first open-source, easy-to-use code base that combines GPU-enabled efficiency with support for a large number of commonly used MARL environments and popular baseline algorithms. Our experiments show that, in terms of wall clock time, our JAX-based training pipeline is up to 12, 500 times faster than existing approaches. This enables efficient and thorough evaluations, potentially alleviating the evaluation crisis in the field. We also introduce and benchmark SMAX, a vectorised, simplified version of the popular StarCraft Multi-Agent Challenge, which removes the need to run the StarCraft II game engine. This not only enables GPU acceleration, but also provides a more flexible MARL environment, unlocking the potential for self-play, meta-learning, and other future applications in MARL. The code is available at https: //github. com/flairox/jaxmarl.

PDF Details DOI

AAMAS Conference 2024 Conference Paper

Multi-Robot Allocation of Assistance from a Shared Uncertain Operator

  • Clarissa Costen
  • Anna Gautier
  • Nick Hawes
  • Bruno Lacerda

Shared autonomy systems allow robots to either operate autonomously or request assistance from a human operator. In such settings, the human operator may exhibit sub-optimal behaviours, influenced by latent variables such as attention level or task proficiency. In this paper, we consider shared autonomy systems composed of multiple robots and one human. In this setting, we aim to synthesise a controller that selects, at each decision step, the actions to be taken by each robot and which (if any) robot the human operator should assist. To efficiently allocate the human operator to a robot at any given time, we propose a controller that reasons about the uncertainty over the latent variables impacting the human operator’s performance. To ensure scalability, we use an online bidding system, where each robot plans while considering its belief over the human’s performance, and bids according to the direct benefit of human assistance and how much information will be gained by the system about the human. We experiment on two domains, where we outperform approaches for allocation of human assistance that do not consider the human’s latent variables, and show that the performance of the overall system increases when robots consider the information gained by requesting human assistance when bidding.

PDF

NeurIPS Conference 2024 Conference Paper

No Regrets: Investigating and Improving Regret Approximations for Curriculum Discovery

  • Alex Rutherford
  • Michael Beukman
  • Timon Willi
  • Bruno Lacerda
  • Nick Hawes
  • Jakob Foerster

What data or environments to use for training to improve downstream performance is a longstanding and very topical question in reinforcement learning. In particular, Unsupervised Environment Design (UED) methods have gained recent attention as their adaptive curricula promise to enable agents to be robust to in- and out-of-distribution tasks. This work investigates how existing UED methods select training environments, focusing on task prioritisation metrics. Surprisingly, despite methods aiming to maximise regret in theory, the practical approximations do not correlate with regret but with success rate. As a result, a significant portion of an agent's experience comes from environments it has already mastered, offering little to no contribution toward enhancing its abilities. Put differently, current methods fail to predict intuitive measures of learnability. Specifically, they are unable to consistently identify those scenarios that the agent can sometimes solve, but not always. Based on our analysis, we develop a method that directly trains on scenarios with high learnability. This simple and intuitive approach outperforms existing UED methods in several binary-outcome environments, including the standard domain of Minigrid and a novel setting closely inspired by a real-world robotics problem. We further introduce a new adversarial evaluation procedure for directly measuring robustness, closely mirroring the conditional value at risk (CVaR). We open-source all our code and present visualisations of final policies here: https: //github. com/amacrutherford/sampling-for-learnability.

PDF Details DOI

IROS Conference 2024 Conference Paper

Planning for Long-Term Monitoring Missions in Time-Varying Environments

  • Alex Stephens
  • Bruno Lacerda
  • Nick Hawes

Recent years have seen autonomous robots deployed in long-term missions across an ever-increasing breadth of domains. We consider robots deployed over a sequence of finite-horizon missions in the same environment, with the objective of maximising the value from observations of some unknown spatiotemporal process. This work is motivated by applications such as ecological monitoring, in which a robot might be repeatedly deployed in the field over weeks or months with the task of modelling processes of scientific interest. We formalise the problem of long-term monitoring over multiple finite-horizon missions as a Markov decision process with a partially unknown state, and present an online planning approach to address it. Our approach uses a spatiotemporal Gaussian process to model the environment and make predictions about unvisited states, integrating this with a belief-based Monte Carlo tree search algorithm which decides where the robot should go next. We demonstrate the strengths of our framework empirically through a series of experiments using synthetic data as well as real acoustic data from monitoring of bioactivity in coral reefs.

Details

JAIR Journal 2024 Journal Article

Right Place, Right Time: Proactive Multi-Robot Task Allocation Under Spatiotemporal Uncertainty

  • Charlie Street
  • Bruno Lacerda
  • Manuel Mühlig
  • Nick Hawes

For many multi-robot problems, tasks are announced during execution, where task announcement times and locations are uncertain. To synthesise multi-robot behaviour that is robust to early announcements and unexpected delays, multi-robot task allocation methods must explicitly model the stochastic processes that govern task announcement. In this paper, we model task announcement using continuous-time Markov chains which predict when and where tasks will be announced. We then present a task allocation framework which uses the continuous-time Markov chains to allocate tasks proactively, such that robots are near or at the task location upon its announcement. Our method seeks to minimise the expected total waiting duration for each task, i.e. the duration between task announcement and a robot beginning to service the task. Our framework can be applied to any multi-robot task allocation problem where robots complete spatiotemporal tasks which are announced stochastically. We demonstrate the efficacy of our approach in simulation, where we outperform baselines which do not allocate tasks proactively, or do not fully exploit our task announcement models.

PDF Details DOI

AAAI Conference 2024 Conference Paper

Stop! Planner Time: Metareasoning for Probabilistic Planning Using Learned Performance Profiles

  • Matthew Budd
  • Bruno Lacerda
  • Nick Hawes

The metareasoning framework aims to enable autonomous agents to factor in planning costs when making decisions. In this work, we develop the first non-myopic metareasoning algorithm for planning with Markov decision processes. Our method learns the behaviour of anytime probabilistic planning algorithms from performance data. Specifically, we propose a novel model for metareasoning, based on contextual performance profiles that predict the value of the planner's current solution given the time spent planning, the state of the planning algorithm's internal parameters, and the difficulty of the planning problem being solved. This model removes the need to assume that the current solution quality is always known, broadening the class of metareasoning problems that can be addressed. We then employ deep reinforcement learning to learn a policy that decides, at each timestep, whether to continue planning or start executing the current plan, and how to set hyperparameters of the planner to enhance its performance. We demonstrate our algorithm's ability to perform effective metareasoning in two domains.

PDF Details DOI

NeurIPS Conference 2023 Conference Paper

Monte Carlo Tree Search with Boltzmann Exploration

  • Michael Painter
  • Mohamed Baioumy
  • Nick Hawes
  • Bruno Lacerda

Monte-Carlo Tree Search (MCTS) methods, such as Upper Confidence Bound applied to Trees (UCT), are instrumental to automated planning techniques. However, UCT can be slow to explore an optimal action when it initially appears inferior to other actions. Maximum ENtropy Tree-Search (MENTS) incorporates the maximum entropy principle into an MCTS approach, utilising Boltzmann policies to sample actions, naturally encouraging more exploration. In this paper, we highlight a major limitation of MENTS: optimal actions for the maximum entropy objective do not necessarily correspond to optimal actions for the original objective. We introduce two algorithms, Boltzmann Tree Search (BTS) and Decaying ENtropy Tree-Search (DENTS), that address these limitations and preserve the benefits of Boltzmann policies, such as allowing actions to be sampled faster by using the Alias method. Our empirical analysis shows that our algorithms show consistent high performance across several benchmark domains, including the game of Go.

PDF Details

AAAI Conference 2023 Conference Paper

Multi-Unit Auctions for Allocating Chance-Constrained Resources

  • Anna Gautier
  • Bruno Lacerda
  • Nick Hawes
  • Michael Wooldridge

Sharing scarce resources is a key challenge in multi-agent interaction, especially when individual agents are uncertain about their future consumption. We present a new auction mechanism for preallocating multi-unit resources among agents, while limiting the chance of resource violations. By planning for a chance constraint, we strike a balance between worst-case approaches, which under-utilise resources, and expected-case approaches, which lack formal guarantees. We also present an algorithm that allows agents to generate bids via multi-objective reasoning, which are then submitted to the auction. We then discuss how the auction can be extended to non-cooperative scenarios. Finally, we demonstrate empirically that our auction outperforms state-of-the-art techniques for chance-constrained multi-agent resource allocation in complex settings with up to hundreds of agents.

PDF Details DOI

NeurIPS Conference 2023 Conference Paper

One Risk to Rule Them All: A Risk-Sensitive Perspective on Model-Based Offline Reinforcement Learning

  • Marc Rigter
  • Bruno Lacerda
  • Nick Hawes

Offline reinforcement learning (RL) is suitable for safety-critical domains where online exploration is not feasible. In such domains, decision-making should take into consideration the risk of catastrophic outcomes. In other words, decision-making should be risk-averse. An additional challenge of offline RL is avoiding distributional shift, i. e. ensuring that state-action pairs visited by the policy remain near those in the dataset. Previous offline RL algorithms that consider risk combine offline RL techniques (to avoid distributional shift), with risk-sensitive RL algorithms (to achieve risk-aversion). In this work, we propose risk-aversion as a mechanism to jointly address both of these issues. We propose a model-based approach, and use an ensemble of models to estimate epistemic uncertainty, in addition to aleatoric uncertainty. We train a policy that is risk-averse, and avoids high uncertainty actions. Risk-aversion to epistemic uncertainty prevents distributional shift, as areas not covered by the dataset have high epistemic uncertainty. Risk-aversion to aleatoric uncertainty discourages actions that are risky due to environment stochasticity. Thus, by considering epistemic uncertainty via a model ensemble and introducing risk-aversion, our algorithm (1R2R) avoids distributional shift in addition to achieving risk-aversion to aleatoric risk. Our experiments show that 1R2R achieves strong performance on deterministic benchmarks, and outperforms existing approaches for risk-sensitive objectives in stochastic domains.

PDF Details

AAAI Conference 2023 Conference Paper

Planning with Hidden Parameter Polynomial MDPs

  • Clarissa Costen
  • Marc Rigter
  • Bruno Lacerda
  • Nick Hawes

For many applications of Markov Decision Processes (MDPs), the transition function cannot be specified exactly. Bayes-Adaptive MDPs (BAMDPs) extend MDPs to consider transition probabilities governed by latent parameters. To act optimally in BAMDPs, one must maintain a belief distribution over the latent parameters. Typically, this distribution is described by a set of sample (particle) MDPs, and associated weights which represent the likelihood of a sample MDP being the true underlying MDP. However, as the number of dimensions of the latent parameter space increases, the number of sample MDPs required to sufficiently represent the belief distribution grows exponentially. Thus, maintaining an accurate belief in the form of a set of sample MDPs over complex latent spaces is computationally intensive, which in turn affects the performance of planning for these models. In this paper, we propose an alternative approach for maintaining the belief over the latent parameters. We consider a class of BAMDPs where the transition probabilities can be expressed in closed form as a polynomial of the latent parameters, and outline a method to maintain a closed-form belief distribution for the latent parameters which results in an accurate belief representation. Furthermore, the closed-form representation does away with the need to tune the number of sample MDPs required to represent the belief. We evaluate two domains and empirically show that the polynomial, closed-form, belief representation results in better plans than a sampling-based belief representation.

PDF Details DOI

ECAI Conference 2023 Conference Paper

Reinforcement Learning for Bandits with Continuous Actions and Large Context Spaces

  • Paul Duckworth
  • Katherine A. Vallis
  • Bruno Lacerda
  • Nick Hawes

We consider the challenging scenario of contextual bandits with continuous actions and large context spaces. This is an increasingly important application area in personalised healthcare where an agent is requested to make dosing decisions based on a patient’s single image scan. In this paper, we first adapt a reinforcement learning (RL) algorithm for continuous control to outperform contextual bandit algorithms specifically hand-crafted for continuous action spaces. We empirically demonstrate this on a suite of standard benchmark datasets for vector contexts. Secondly, we demonstrate that our RL agent can generalise problems with continuous actions to large context spaces, providing results that outperform previous methods on image contexts. Thirdly, we introduce a new contextual bandits test domain with multi-dimensional continuous action space and image contexts which existing tree-based methods cannot handle. We provide initial results with our RL agent.

Details

AAMAS Conference 2023 Conference Paper

Risk-Constrained Planning for Multi-Agent Systems with Shared Resources

  • Anna Gautier
  • Marc Rigter
  • Bruno Lacerda
  • Nick Hawes
  • Michael Wooldridge

Planning under uncertainty requires complex reasoning about future events, and this complexity increases with the addition of multiple agents. One problem faced when considering multi-agent systems under uncertainty is the handling of shared resources. Adding a resource constraint limits the actions that agents can take, forcing collaborative decision making on who gets to use what resources. Prior work has considered different formulations, such as satisfying a resource constraint in expectation or ensuring that a resource constraint is met some percent of the time. However, these formulations of constrained planning ignore important distributional information about resource usage. Namely, they do not consider how bad the worst cases can get. In this paper, we formulate a risk-constrained shared resource problem and aim to limit the risk of excessive use of such resources. We focus on optimising for reward while constraining the Conditional Value-at-Risk (CVaR) of the shared resource. While CVaR is well studied in the single-agent setting, we consider the challenges that arise from the state and action space explosion in the multi-agent setting. In particular, we exploit risk contributions, a measure introduced in finance research which quantifies how much individual agents affect the joint risk. We present an algorithm that uses risk contributions to iteratively update single-agent policies until the joint risk constraint is satisfied. We evaluate our algorithm on two synthetic domains.

PDF

AAMAS Conference 2022 Conference Paper

Context-Aware Modelling for Multi-Robot Systems Under Uncertainty

  • Charlie Street
  • Bruno Lacerda
  • Michal Staniaszek
  • Manuel Mühlig
  • Nick Hawes

Formal models of multi-robot behaviour are fundamental to planning, simulation, and model checking techniques. However, existing models are invalidated by strong assumptions that fail to capture execution-time multi-robot behaviour, such as simplistic duration models or synchronisation constraints. In this paper we propose a novel multi-robot Markov automaton formulation which models asynchronous multi-robot execution in continuous time. Robot dynamics are captured using phase-type distributions over action durations. Moreover, we explicitly model the effects of robot interactions, as they are a key factor for the duration of action execution. We also present a scalable discrete-event simulator which yields realistic statistics over execution-time robot behaviour by sampling through the Markov automaton. We validate our model and simulator against a Gazebo simulation in a range of multi-robot navigation scenarios, demonstrating that our model accurately captures highlevel multi-robot behaviour.

PDF

AAMAS Conference 2022 Conference Paper

Negotiated Path Planning for Non-Cooperative Multi-Robot Systems

  • Anna Gautier
  • Alex Stephens
  • Bruno Lacerda
  • Nick Hawes
  • Michael Wooldridge

As autonomous systems are deployed at a large scale in both public and private spaces, robots owned and operated by competing organisations will be required to interact. Interactions in such settings will be inherently non-cooperative. In this paper, we address the problem of non-cooperative multi-agent path finding. We design an auction mechanism that allows a group of agents to reach their goals whilst minimising the total cost of the system. In particular, we aim to design a mechanism such that rational agents are incentivised to participate. Our privileged knowledge auction consists of a modified combinatorial Vickrey-Clarke-Groves auction. Our approach limits the initial number of bids in the Vickrey-Clarke-Groves auction, then uses the privileged knowledge of the auctioneer to identify and solve path conflicts. In order to maintain agent autonomy in the non-cooperative system, individual agents are provided with final say over paths. The mechanism provides a heuristic method to maximise social welfare whilst remaining computationally efficient. We also consider single-agent bid generation and propose a similarity metric to use in dissimilar shortest path generation. We then show this bid generation method increases the success likelihood of both the limited-bid VCG auction and our novel approach on synthetic data. Our experiments with synthetic data outperform existing work on the non-cooperative problem.

PDF

ICAPS Conference 2022 Conference Paper

Planning for Risk-Aversion and Expected Value in MDPs

  • Marc Rigter
  • Paul Duckworth
  • Bruno Lacerda
  • Nick Hawes

Planning in Markov decision processes (MDPs) typically optimises the expected cost. However, optimising the expectation does not consider the risk that for any given run of the MDP, the total cost received may be unacceptably high. An alternative approach is to find a policy which optimises a riskaverse objective such as conditional value at risk (CVaR). However, optimising the CVaR alone may result in poor performance in expectation. In this work, we begin by showing that there can be multiple policies which obtain the optimal CVaR. This motivates us to propose a lexicographic approach which minimises the expected cost subject to the constraint that the CVaR of the total cost is optimal. We present an algorithm for this problem and evaluate our approach on four domains. Our results demonstrate that our lexicographic approach improves the expected cost compared to the state of the art algorithm, while achieving the optimal CVaR.

Details

IROS Conference 2022 Conference Paper

Probabilistic Planning for AUV Data Harvesting from Smart Underwater Sensor Networks

  • Matthew Budd
  • Georgios Salavasidis
  • Izzat Karnarudzaman
  • Catherine A. Harris
  • Alexander B. Phillips
  • Paul Duckworth
  • Nick Hawes
  • Bruno Lacerda

Harvesting valuable ocean data, ranging from climate and marine life analysis to industrial equipment monitoring, is an extremely challenging real-world problem. Sparse underwater sensor networks are a promising approach to scale to larger and deeper environments, but these have difficulty offloading their data without external assistance. Traditionally, offloading data has been achieved by costly, fixed communication infrastructure. In this paper, we propose a planning under uncertainty method that enables an autonomous underwater vehicle (AUV) to adaptively collect data from smart sensor networks in underwater environments. Our novel solution exploits the ability of sensor nodes to provide the AUV with time-of-flight acoustic localisation, and is able to prioritise nodes with the most valuable data. In both simulated experiments and a real-world field trial, we demonstrate that our method outperforms the type of hand-designed behaviours that has previously been used in the context of underwater data harvesting.

Details

NeurIPS Conference 2022 Conference Paper

RAMBO-RL: Robust Adversarial Model-Based Offline Reinforcement Learning

  • Marc Rigter
  • Bruno Lacerda
  • Nick Hawes

Offline reinforcement learning (RL) aims to find performant policies from logged data without further environment interaction. Model-based algorithms, which learn a model of the environment from the dataset and perform conservative policy optimisation within that model, have emerged as a promising approach to this problem. In this work, we present Robust Adversarial Model-Based Offline RL (RAMBO), a novel approach to model-based offline RL. We formulate the problem as a two-player zero sum game against an adversarial environment model. The model is trained to minimise the value function while still accurately predicting the transitions in the dataset, forcing the policy to act conservatively in areas not covered by the dataset. To approximately solve the two-player game, we alternate between optimising the policy and adversarially optimising the model. The problem formulation that we address is theoretically grounded, resulting in a probably approximately correct (PAC) performance guarantee and a pessimistic value function which lower bounds the value function in the true environment. We evaluate our approach on widely studied offline RL benchmarks, and demonstrate that it outperforms existing state-of-the-art baselines.

PDF Details

IJCAI Conference 2022 Conference Paper

Shared Autonomy Systems with Stochastic Operator Models

  • Clarissa Costen
  • Marc Rigter
  • Bruno Lacerda
  • Nick Hawes

We consider shared autonomy systems where multiple operators (AI and human), can interact with the environment, e. g. by controlling a robot. The decision problem for the shared autonomy system is to select which operator takes control at each timestep, such that a reward specifying the intended system behaviour is maximised. The performance of the human operator is influenced by unobserved factors, such as fatigue or skill level. Therefore, the system must reason over stochastic models of operator performance. We present a framework for stochastic operators in shared autonomy systems (SO-SAS), where we represent operators using rich, partially observable models. We formalise SO-SAS as a mixed-observability Markov decision process, where environment states are fully observable and internal operator states are hidden. We test SO-SAS on a simulated domain and a computer game, empirically showing it results in better performance compared to traditional formulations of shared autonomy systems.

PDF Details DOI

ICRA Conference 2021 Conference Paper

Active Inference for Integrated State-Estimation, Control, and Learning

  • Mohamed Baioumy
  • Paul Duckworth
  • Bruno Lacerda
  • Nick Hawes

This work presents an approach for control, state-estimation and learning model (hyper)parameters for robotic manipulators. It is based on the active inference framework, prominent in computational neuroscience as a theory of the brain, where behaviour arises from minimizing variational free-energy. First, we show there is a direct relationship between active inference controllers, and classic methods such as PID control. We demonstrate its application for adaptive and robust behaviour of a robotic manipulator that rivals state-of-the-art. Additionally, we show that by learning specific hyperparameters, our approach can deal with unmodeled dynamics, damps oscillations, and is robust against poor initial parameters. The approach is validated on the ‘Franka Emika Panda’ 7 DoF manipulator. Finally, we highlight limitations of active inference controllers for robotic systems.

Details

AAAI Conference 2021 Conference Paper

Minimax Regret Optimisation for Robust Planning in Uncertain Markov Decision Processes

  • Marc Rigter
  • Bruno Lacerda
  • Nick Hawes

The parameters for a Markov Decision Process (MDP) often cannot be specified exactly. Uncertain MDPs (UMDPs) capture this model ambiguity by defining sets which the parameters belong to. Minimax regret has been proposed as an objective for planning in UMDPs to find robust policies which are not overly conservative. In this work, we focus on planning for Stochastic Shortest Path (SSP) UMDPs with uncertain cost and transition functions. We introduce a Bellman equation to compute the regret for a policy. We propose a dynamic programming algorithm that utilises the regret Bellman equation, and show that it optimises minimax regret exactly for UMDPs with independent uncertainties. For coupled uncertainties, we extend our approach to use options to enable a trade off between computation and solution quality. We evaluate our approach on both synthetic and real-world domains, showing that it significantly outperforms existing baselines.

PDF Details

NeurIPS Conference 2021 Conference Paper

Risk-Averse Bayes-Adaptive Reinforcement Learning

  • Marc Rigter
  • Bruno Lacerda
  • Nick Hawes

In this work, we address risk-averse Bayes-adaptive reinforcement learning. We pose the problem of optimising the conditional value at risk (CVaR) of the total return in Bayes-adaptive Markov decision processes (MDPs). We show that a policy optimising CVaR in this setting is risk-averse to both the epistemic uncertainty due to the prior distribution over MDPs, and the aleatoric uncertainty due to the inherent stochasticity of MDPs. We reformulate the problem as a two-player stochastic game and propose an approximate algorithm based on Monte Carlo tree search and Bayesian optimisation. Our experiments demonstrate that our approach significantly outperforms baseline approaches for this problem.

PDF Details

ICAPS Conference 2020 Conference Paper

Convex Hull Monte-Carlo Tree-Search

  • Michael Painter
  • Bruno Lacerda
  • Nick Hawes

This work investigates Monte-Carlo planning for agents in stochastic environments, with multiple objectives. We propose the Convex Hull Monte-Carlo Tree-Search (CHMCTS) framework, which builds upon Trial Based Heuristic Tree Search and Convex Hull Value Iteration (CHVI), as a solution to multi-objective planning in large environments. Moreover, we consider how to pose the problem of approximating multi-objective planning solutions as a contextual multi-armed bandits problem, giving a principled motivation for how to select actions from the view of contextual regret. This leads us to the use of Contextual Zooming for action selection, yielding Zooming CHMCTS. We evaluate our algorithm using the Generalised Deep Sea Treasure environment, demonstrating that Zooming CHMCTS can achieve a sublinear contextual regret and scales better than CHVI on a given computational budget.

Details

IROS Conference 2020 Conference Paper

Long-Run Multi-Robot Planning under Uncertain Action Durations for Persistent Tasks

  • Carlos Azevedo
  • Bruno Lacerda
  • Nick Hawes
  • Pedro U. Lima

This paper presents an approach for multi-robot long-term planning under uncertainty over the duration of actions. The proposed methodology takes advantage of generalized stochastic Petri nets with rewards (GSPNR) to model multi-robot problems. A GSPNR allows for unified modeling of action selection, uncertainty on the duration of action execution, and for goal specification through the use of transition rewards and rewards per time unit. Our approach relies on the interpretation of the GSPNR model as an equivalent embedded Markov reward automaton (MRA). We then build on a state-of-the-art method to compute the long-run average reward over MRAs, extending it to enable the extraction of the optimal policy. We provide an empirical evaluation of the proposed approach on a simulated multi-robot monitoring problem, evaluating its performance and scalability. The results show that the synthesized policy outperforms a policy obtained from an infinite horizon discounted reward formulation as well as a carefully hand-crafted policy.

Details

IROS Conference 2020 Conference Paper

Markov Decision Processes with Unknown State Feature Values for Safe Exploration using Gaussian Processes

  • Matthew Budd
  • Bruno Lacerda
  • Paul Duckworth
  • Andrew West
  • Barry Lennox
  • Nick Hawes

When exploring an unknown environment, a mobile robot must decide where to observe next. It must do this whilst minimising the risk of failure, by only exploring areas that it expects to be safe. In this context, safety refers to the robot remaining in regions where critical environment features (e. g. terrain steepness, radiation levels) are within ranges the robot is able to tolerate. More specifically, we consider a setting where a robot explores an environment modelled with a Markov decision process, subject to bounds on the values of one or more environment features which can only be sensed at runtime. We use a Gaussian process to predict the value of the environment feature in unvisited regions, and propose an estimated Markov decision process, a model that integrates the Gaussian process predictions with the environment model transition probabilities. Building on this model, we propose an exploration algorithm that, contrary to previous approaches, considers probabilistic transitions and explicitly reasons about the uncertainty over the Gaussian process predictions. Furthermore, our approach increases the speed of exploration by selecting locations to visit further away from the currently explored area. We evaluate our approach on a real-world gamma radiation dataset, tackling the challenge of a nuclear material inspection robot exploring an a priori unknown area.

Details

IJCAI Conference 2019 Conference Paper

Multi-Robot Planning Under Uncertain Travel Times and Safety Constraints

  • Masoumeh Mansouri
  • Bruno Lacerda
  • Nick Hawes
  • Federico Pecora

We present a novel modelling and planning approach for multi-robot systems under uncertain travel times. The approach uses generalised stochastic Petri nets (GSPNs) to model desired team behaviour, and allows to specify safety constraints and rewards. The GSPN is interpreted as a Markov decision process (MDP) for which we can generate policies that optimise the requirements. This representation is more compact than the equivalent multi-agent MDP, allowing us to scale better. Furthermore, it naturally allows for asynchronous execution of the generated policies across the robots, yielding smoother team behaviour. We also describe how the integration of the GSPN with a lower-level team controller allows for accurate expectations on team performance. We evaluate our approach on an industrial scenario, showing that it outperforms hand-crafted policies used in current practice.

PDF Details

IROS Conference 2018 Conference Paper

Simultaneous Task Allocation and Planning Under Uncertainty

  • Fatma Faruq
  • David Parker 0001
  • Bruno Lacerda
  • Nick Hawes

We propose novel techniques for task allocation and planning in multi-robot systems operating in uncertain environments. Task allocation is performed simultaneously with planning, which provides more detailed information about individual robot behaviour, but also exploits independence between tasks to do so efficiently. We use Markov decision processes to model robot behaviour and linear temporal logic to specify tasks and safety constraints. Building upon techniques and tools from formal verification, we show how to generate a sequence of multi-robot policies, iteratively refining them to reallocate tasks if individual robots fail, and providing probabilistic guarantees on the performance (and safe operation) of the team of robots under the resulting policy. We implement our approach and evaluate it on a benchmark multi-robot example.

Details

ICAPS Conference 2017 Conference Paper

Multi-Objective Policy Generation for Mobile Robots under Probabilistic Time-Bounded Guarantees

  • Bruno Lacerda
  • David Parker 0001
  • Nick Hawes

We present a methodology for the generation of mobile robot controllers which offer probabilistic time-bounded guarantees on successful task completion, whilst also trying to satisfy soft goals. The approach is based on a stochastic model of the robot’s environment and action execution times, a set of soft goals, and a formal task specification in co-safe linear temporal logic, which are analysed using multi-objective model checking techniques for Markov decision processes. For efficiency, we propose a novel two-step approach. First, we explore policies on the Pareto front for minimising expected task execution time whilst optimising the achievement of soft goals. Then, we use this to prune a model with more detailed timing information, yielding a time-dependent policy for which more fine-grained probabilistic guarantees can be provided. We illustrate and evaluate the generation of policies on a delivery task in a care home scenario, where the robot also tries to engage in entertainment activities with the patients.

Details

ECAI Conference 2016 Conference Paper

Partial Order Temporal Plan Merging for Mobile Robot Tasks

  • Lenka Mudrová
  • Bruno Lacerda
  • Nick Hawes

For many mobile service robot applications, planning problems are based on deciding how and when to navigate to certain locations and execute certain tasks. Typically, many of these tasks are independent from one another, and the main objective is to obtain plans that efficiently take into account where these tasks can be executed and when execution is allowed. In this paper, we present an approach, based on merging of partial order plans with durative actions, that can quickly and effectively generate a plan for a set of independent goals. This plan exploits some of the synergies of the plans for each single task, such as common locations where certain actions should be executed. We evaluate our approach in benchmarking domains, comparing it with state-of-the-art planners and showing how it provides a good trade-off between the approach of sequencing the plans for each task (which is fast but produces poor results), and the approach of planning for a conjunction of all the goals (which is slow but produces good results).

Details

ICRA Conference 2015 Conference Paper

Now or later? Predicting and maximising success of navigation actions from long-term experience

  • Jaime Pulido Fentanes
  • Bruno Lacerda
  • Tomás Krajník
  • Nick Hawes
  • Marc Hanheide

In planning for deliberation or navigation in real-world robotic systems, one of the big challenges is to cope with change. It lies in the nature of planning that it has to make assumptions about the future state of the world, and the robot's chances of successively accomplishing actions in this future. Hence, a robot's plan can only be as good as its predictions about the world. In this paper, we present a novel approach to specifically represent changes that stem from periodic events in the environment (e. g. a door being opened or closed), which impact on the success probability of planned actions. We show that our approach to model the probability of action success as a set of superimposed periodic processes allows the robot to predict action outcomes in a long-term data obtained in two real-life offices better than a static model. We furthermore discuss and showcase how this knowledge gathered can be successfully employed in a probabilistic planning framework to devise better navigation plans. The key contributions of this paper are (i) the formation of the spectral model of action outcomes from non-uniform sampling, the (ii) analysis of its predictive power using two long-term datasets, and (iii) the application of the predicted outcomes in an MDP-based planning framework.

Details

IJCAI Conference 2015 Conference Paper

Optimal Policy Generation for Partially Satisfiable Co-Safe LTL Specifications

  • Bruno Lacerda
  • David Parker
  • Nick Hawes

We present a method to calculate cost-optimal policies for task specifications in co-safe linear temporal logic over a Markov decision process model of a stochastic system. Our key contribution is to address scenarios in which the task may not be achievable with probability one. We formalise a task progression metric and, using multi-objective probabilistic model checking, generate policies that are formally guaranteed to, in decreasing order of priority: maximise the probability of finishing the task; maximise progress towards completion, if this is not possible; and minimise the expected time or cost required. We illustrate and evaluate our approach in a robot task planning scenario, where the task is to visit a set of rooms that may be inaccessible during execution.

PDF Details

IROS Conference 2014 Conference Paper

Optimal and dynamic planning for Markov decision processes with co-safe LTL specifications

  • Bruno Lacerda
  • David Parker 0001
  • Nick Hawes

We present a method to specify tasks and synthesise cost-optimal policies for Markov decision processes using co-safe linear temporal logic. Our approach incorporates a dynamic task handling procedure which allows for the addition of new tasks during execution and provides the ability to re-plan an optimal policy on-the-fly. This new policy minimises the cost to satisfy the conjunction of the current tasks and the new one, taking into account how much of the current tasks has already been executed. We illustrate our approach by applying it to motion planning for a mobile service robot.

Details

AAMAS Conference 2011 Conference Paper

Designing Petri Net Supervisors for Multi-Agent Systems from LTL Specifications

  • Bruno Lacerda
  • Pedro U. Lima

In this paper, we use LTL to specify acceptable/desirable behaviours for a system modelled as a Petri net, and create a Petri net realization of a supervisor that is guaranteed to enforce them, by appropriately restricting the uncontrolled behaviour of the system. We illustrate the method with an application to the specification of coordination requirements between the members of a team of simulated soccer robots.

PDF

IROS Conference 2011 Conference Paper

LTL-based decentralized supervisory control of multi-robot tasks modelled as Petri nets

  • Bruno Lacerda
  • Pedro U. Lima

We present a decentralized methodology to control multi-robot systems, where each robot behaviour is modelled as a Petri net (PN) and a set of coordination rules between the robots is given as linear temporal logic (LTL) formulas describing safety properties for the system. The LTL formulas are used to define the events and changes in state that must be communicated between robots and to augment the individual PN model of each robot so that it can handle the incoming communications. These augmented PNs are then used, in conjunction with the LTL formulas, to build PN realizations of local supervisors, based on discrete event system theory, that enforce the LTL specifications by construction. The methodology is illustrated through a simulated application example.

Details
v2026.09.13