Author name cluster

Anna Gautier

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.

7 papers

2 author rows

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

ICRA Conference 2024 Conference Paper

Robust MITL planning under uncertain navigation times

Alexis Linard
Anna Gautier
Daniel Duberg
Jana Tumova

In environments like offices, the duration of a robot’s navigation between two locations may vary over time. For instance, reaching a kitchen may take more time during lunchtime since the corridors are crowded with people heading the same way. In this work, we address the problem of routing in such environments with tasks expressed in Metric Interval Temporal Logic (MITL) – a rich robot task specification language that allows us to capture explicit time requirements. Our objective is to find a strategy that maximizes the temporal robustness of the robot’s MITL task. As the first step towards a solution, we define a Mixed-integer linear programming approach to solving the task planning problem over a Varying Weighted Transition System, where navigation durations are deterministic but vary depending on the time of day. Then, we apply this planner to optimize for MITL temporal robustness in Markov Decision Processes, where the navigation durations between physical locations are uncertain, but the time-dependent distribution over possible delays is known. Finally, we develop a receding horizon planner for Markov Decision Processes that preserves guarantees over MITL temporal robustness. We show the scalability of our planning algorithms in simulations of robotic tasks.

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

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

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

AAMAS Conference 2022 Conference Paper

Non-Cooperative Multi-Robot Planning Under Shared Resources

Anna Gautier

As more and more single-use robots are introduced to private and public spaces, it will become essential to mediate the interaction between robots. In particular, we consider the problem of resource sharing in non-cooperative multi-robot systems. We discuss the motivation for different types of shared resources and share how we used auctions to address the non-cooperative multi-agent pathfinding problem. We summarize those result, which are presented in full in a separate paper. Finally, we discuss some avenues for future work, including the application of auctions to allocate multi-unit chance-constrained resources under the presence of uncertainty.

PDF

IS Journal 2022 Journal Article

Understanding Mechanism Design—Part 3 of 3: Mechanism Design in the Real World: The VCG Mechanism

Anna Gautier
Michael Wooldridge

In the first two parts of this short series, we learned how mechanism design can be used in theory to engineer systems that achieve desirable properties by anticipating how rational agents will act, and then designing the rules accordingly. In particular, we focused on the Vickrey–Clarke–Groves (VCG) mechanism that results in a welfare maximizing outcome by incentivizing agents to tell the truth about how much they prefer each outcome. Now, let's explore how the VCG mechanisms may be used to solve real-world problems.

Details DOI