Author name cluster

Sara Bernardini

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.

24 papers

2 author rows

AAMAS Conference 2025 Conference Paper

Speed vs Accuracy in Goal Recognition for Time-Sensitive Applications: A Game-Theoretic Approach

Sara Bernardini
Fabio Fagnani
Santiago Franco

This work addresses a specific instance of Goal Recognition (GR), termed time-sensitive GR, where a malicious actor (the attacker) seeks to reach and damage one of several sensitive targets, while the observer (the defender) must identify the attacker’s target and allocate limited resources to protect it. Focusing on real-world physical and cyber security scenarios, the defender faces a tradeoff between acting early, with limited information, or waiting for more data but risking insufficient time to defend. Our contributions include introducing a game-theoretic formulation of this instance of GR, which captures the time-sensitive nature of these scenarios, and providing an efficient method to compute Nash equilibria using the fictitious play learning scheme. Experimental results confirm that our method equips the defender with robust policies, outperforming less adaptable strategies.

PDF

SoCS Conference 2024 Conference Paper

Lazy Evaluation of Negative Preconditions in Planning Domains (Extended Abstract)

Santiago Franco
Jamie O. Roberts
Sara Bernardini

AI planning technology faces performance issues with large-scale problems with negative preconditions. In this extended abstract, we show how to leverage the power of the Finite Domain Representation (FDR) used by the popular Fast Downward planner for such domains. FDR improves scalability thanks to its use of multi-valued state variables. However, it scales poorly when dealing with negative preconditions. We propose an alternative hybrid approach that evaluates negative preconditions on the fly during search but only when strictly needed. This is compared to the traditional use of domain-specific PDDL bookmark predicates, increasing memory usage, and automated transformations to Positive Normal Form, further escalating memory consumption.

Details

AIJ Journal 2024 Journal Article

Optimizing pathfinding for goal legibility and recognition in cooperative partially observable environments

Sara Bernardini
Fabio Fagnani
Alexandra Neacsu
Santiago Franco

In this paper, we perform a joint design of goal legibility and recognition in a cooperative, multi-agent pathfinding setting with partial observability. More specifically, we consider a set of identical agents (the actors) that move in an environment only partially observable to an observer in the loop. The actors are tasked with reaching a set of locations that need to be serviced in a timely fashion. The observer monitors the actors' behavior from a distance and needs to identify each actor's destination based on the actor's observable movements. Our approach generates legible paths for the actors; namely, it constructs one path from the origin to each destination so that these paths overlap as little as possible while satisfying budget constraints. It also equips the observer with a goal-recognition mapping between unique sequences of observations and destinations, ensuring that the observer can infer an actor's destination by making the minimum number of observations (legibility delay). Our method substantially extends previous work, which is limited to an observer with full observability, showing that optimizing pathfinding for goal legibility and recognition can be performed via a reformulation into a classical minimum cost flow problem in the partially observable case when the algorithms for the fully observable case are appropriately modified. Our empirical evaluation shows that our techniques are as effective in partially observable settings as in fully observable ones.

Details DOI

ICAPS Conference 2023 Conference Paper

Exploiting Geometric Constraints in Multi-Agent Pathfinding

Dor Atzmon
Sara Bernardini
Fabio Fagnani
David L. Fairbairn

In tackling the multi-agent pathfinding problem (MAPF), we study a specific class of paths that are constructed by taking the agents’ shortest paths from the start to the goal locations and adding safe delays at the beginning of the paths, which guarantee that they are non-conflicting. Safe delays are calculated by exploiting a set of fundamental geometric constraints among the distances between all agents’ start and goal locations. Those constraints are simple, but the MAPF problem reformulated in terms of them remains computationally hard. Nonetheless, based on safe delays, we devise a new, fast and lightweight algorithm, called Delayed Shortest Path (DSP), to find solutions to the MAPF problem. Via an extensive experimental evaluation on standard benchmarks, we show that, in many cases, our technique runs several orders of magnitudes faster than related methods while addressing problems with thousands of agents and returning low-cost solutions.

Details

IJCAI Conference 2023 Conference Paper

Helpful Information Sharing for Partially Informed Planning Agents

Sarah Keren
David Wies
Sara Bernardini

In many real-world settings, an autonomous agent may not have sufficient information or sensory capabilities to accomplish its goals, even when they are achievable. In some cases, the needed information can be provided by another agent, but information sharing might be costly due to limited communication bandwidth and other constraints. We address the problem of Helpful Information Sharing (HIS), which focuses on selecting minimal information to reveal to a partially informed agent in order to guarantee it can achieve its goal. We offer a novel compilation of HIS to a classical planning problem, which can be solved efficiently by any off-the-shelf planner. We provide guarantees of optimality for our approach and describe its extensions to maximize robustness and support settings in which the agent needs to decide which sensors to deploy in the environment. We demonstrate the power of our approaches on a set of standard benchmarks as well as on a novel benchmark.

PDF Details DOI

KR Conference 2023 Conference Paper

Learning Interpretable Heuristics for WalkSAT

Yannet Interian
Sara Bernardini

Local search algorithms are well-known methods for solving large, hard instances of the satisfiability problem (SAT). The performance of these algorithms crucially depends on heuristics for setting noise parameters and scoring variables. The optimal setting for these heuristics varies for different instance distributions. In this paper, we present an approach for learning effective variable scoring functions and noise parameters by using reinforcement learning. We consider satisfiability problems from different instance distributions and learn specialized heuristics for each of them. Our experimental results show improvements with respect to both a WalkSAT baseline and another local search learned heuristic.

PDF Details DOI

ICAPS Conference 2022 Conference Paper

A Network Flow Interpretation of Robust Goal Legibility in Path Finding

Sara Bernardini
Fabio Fagnani
Santiago Franco
Alexandra Neacsu

In this paper, we define goal legibility in a multi-agent path-finding setting. We consider a set of identical agents moving in an environment and tasked with reaching a set of locations that need to be serviced. An observer monitors their movements from a distance to identify their destinations as soon as possible. Our algorithm constructs a set of paths for the agents, one to each destination, that overlap as little as possible while satisfying a budget constraint. In this way, the observer, knowing the possible agents' destinations as well as the set of paths they might follow, is guaranteed to determine with certainty an agent's destination by looking at the shortest possible fragment of the agent's trajectory, regardless of when it starts observing. Our technique is robust because the observer's inference mechanism requires no coordination with the agents' motions. By reformulating legible path planning into a classical minimum cost flow problem, we can leverage powerful tools from combinatorial optimization, obtaining fast and scalable algorithms. We present experiments that show the benefits offered by our approach.

Details

IROS Conference 2022 Conference Paper

Hybrid Discrete-Continuous Path Planning for Lattice Traversal

Santiago Franco
Julius Sustarevas
Sara Bernardini

Lattice structures allow robotic systems to operate in complex and hazardous environments, e. g. construction, mining and nuclear plants, reliably and effectively. However, current navigation systems for these structures are neither realistic, as they assume simplistic motion primitives and obstacle-free workspaces, nor efficient as they rely solely on global discrete search in an attempt to leverage the modularity of lattices. This paper tackles this gap and studies how robots can navigate lattice structures efficiently. We present a realistic application environment where robots have to avoid obstacles and the structure itself to reach target locations. Our solution couples discrete optimal search, using a domain-dependent heuristic, and sampling-based motion planning to find feasible trajectories in the discrete search space and in the continuous joint space at the same time. We provide two search graph formulations and a path planning approach. Simulation experiments, based on structures and robots created for the Innovate UK Connect-R project, examine scalability to large grid spaces while maintaining performances close to optimal.

Details

AIJ Journal 2021 Journal Article

A unifying look at sequence submodularity

Sara Bernardini
Fabio Fagnani
Chiara Piacentini

Several real-world problems in engineering and applied science require the selection of sequences that maximize a given reward function. Optimizing over sequences as opposed to sets requires exploring an exponentially larger search space and can become prohibitive in most cases of practical interest. However, if the objective function is submodular (intuitively, it exhibits a diminishing return property), the optimization problem becomes more manageable. Recently, there has been increasing interest in sequence submodularity in connection with applications such as recommender systems and online ad allocation. However, mostly ad hoc models and solutions have emerged within these applicative contexts. In consequence, the field appears fragmented and lacks coherence. In this paper, we offer a unified view of sequence submodularity and provide a generalized greedy algorithm that enjoys strong theoretical guarantees. We show how our approach naturally captures several application domains, and our algorithm encompasses existing methods, improving over them.

Details DOI

ICAPS Conference 2021 Conference Paper

Autonomous Building of Structures in Unstructured Environments via AI Planning

Jamie O. Roberts
Santiago Franco
Adam A. Stokes
Sara Bernardini

In this paper, we offer a novel AI planning representation, based on a Cartesian coordinate system, for enabling the autonomous operations of Multi-Robot Systems in 3D environments. Each robot in the system has to conform to unique actuation and connection constraints that create a complex set of valid configurations. Our approach allows Multi-Robot Systems to self-assemble themselves into larger structures via AI planning, with the overarching goal of providing structural capabilities in harsh and uncertain environments. In comparing four different PDDL (Planning Domain Definition Language) domain representations, we show that our novel formulation satisfies the practical requirements emerging from robot deployment in the real world, resulting in an AI planning system that is accurate and efficient. We scale up performance by implementing direct FDR (Finite Domain Representation) generation based on the best performing PDDL model, bypassing the PDDL-to-FDR translation used by the majority of modern planners. The proposed approach is general and can be applied to a broad range of AI problems involving reasoning in 3D spaces.

Details

ICAPS Conference 2021 Conference Paper

vPlanSim: An Open Source Graphical Interface for the Visualisation and Simulation of AI Systems

Jamie O. Roberts
Georgios Mastorakis
Brad Lazaruk
Santiago Franco
Adam A. Stokes
Sara Bernardini

We introduce vPlanSim, an open source tool to aid in AI PDDL development. This tool is primarily aimed at researchers and developers who need a visual representation of their planning problem so that they can make useful insights into the performance of their system, and also to naturally convey their system to others. It is an open-source tool which allows a user to quickly and easily visualise a target environment to generate the problem files and also to visualise a plan. It is particularly well suited to spatial planning problems. This paper will demonstrate vPlanSim on 2D and 3D planning problems. vPlanSim is based on a small and carefully considered set of dependencies such as VTK and PyQt. It can be set up on different platforms and compiled from source with minimal effort. The code is and maintained via a clear code review mechanism. We welcome contributions from the open-source community.

Details

KR Conference 2020 Conference Paper

An Optimization Approach to Robust Goal Obfuscation

Sara Bernardini
Fabio Fagnani
Santiago Franco

In this paper, we present a set of strategies to underpin the behavior of an agent that wants to arrive as close as possible to its destination without revealing it to an observer, which monitors its progress in the environment. This problem is an instance of goal obfuscation (GO), which has lately received significant attention in the AI community. With different variants of GO being proposed, the field lacks coherence and characterization from first principles. In addition, existing techniques are not robust to possible attempts of the observer to learn the agent's strategy. To fill this gap, we provide here a foundational study of GO and offer robust techniques to ensure that the agent can protect its privacy as much as possible regardless of the observer's behavior. We cast GO as an optimization problem, offer a complete theoretical analysis of it and introduce efficient algorithms to find exact solutions.

PDF Details DOI

IROS Conference 2020 Conference Paper

Intelligent Exploration and Autonomous Navigation in Confined Spaces

Aliakbar Akbari
Puneet S. Chhabra
Ujjar Bhandari
Sara Bernardini

Autonomous navigation and exploration in confined spaces are currently setting new challenges for robots. The presence of narrow passages, flammable atmosphere, dust, smoke, and other hazards makes the mapping and navigation tasks extremely difficult. To tackle these challenges, robots need to make intelligent decisions, maximising information while maintaining the safety of the system and their surroundings. In this paper, we present a suite of reasoning mechanisms along with a software architecture for exploration tasks that can be used to underpin the behavior of a broad range of robots operating in confined spaces. We present an autonomous navigation module that allows the robot to safely traverse known areas of the environment and extract features of the unknown frontier regions. An exploration component, by reasoning about these frontiers, provides the robot with the ability to venture into new spaces. From low-level sensory input and contextual information, the robot incrementally builds a semantic network that represents known and unknown parts of the environment and then uses a logic-based, high-level reasoner to interrogate such a network and decide the best course of actions. We evaluate our approach against several mine-like challenging scenarios with different characteristics using a small drone. The experimental results indicate that our method allows the robot to make informed decisions on how to best explore the environment while preserving safety.

Details

KR Conference 2020 Conference Paper

Reasoning About Plan Robustness Versus Plan Cost for Partially Informed Agents

Sarah Keren
Sara Bernardini
Kofi Kwapong
David C. Parkes

A common approach to planning with partial information is replanning: compute a plan based on assumptions about unknown information and replan if these assumptions are refuted during execution. To date, most planners with incomplete information have been designed to provide guarantees on completeness and soundness for the generated plans. Switching focus to performance, we measure the robustness of a plan, which quantiﬁes the plan’s ability to avoid failure. Given a plan and an agent’s belief, which describes the set of states it deems as possible, robustness counts the number of world states in the belief from which the plan will achieve the goal without the need to replan. We formally describe the trade-off between robustness and plan cost and offer a solver that is guaranteed to produce plans that satisfy a required level of robustness. By evaluating our approach on a set of standard benchmarks, we demonstrate how it can improve the performance of a partially informed agent.

PDF Details DOI

ICAPS Conference 2020 Conference Paper

Through the Lens of Sequence Submodularity

Sara Bernardini
Fabio Fagnani
Chiara Piacentini

Details

JAIR Journal 2019 Journal Article

Autonomous Target Search with Multiple Coordinated UAVs

Chiara Piacentini
Sara Bernardini
J. Christopher Beck

Search and tracking is the problem of locating a moving target and following it to its destination. In this work, we consider a scenario in which the target moves across a large geographical area by following a road network and the search is performed by a team of unmanned aerial vehicles (UAVs). We formulate search and tracking as a combinatorial optimization problem and prove that the objective function is submodular. We exploit this property to devise a greedy algorithm. Although this algorithm does not offer strong theoretical guarantees because of the presence of temporal constraints that limit the feasibility of the solutions, it presents remarkably good performance, especially when several UAVs are available for the mission. As the greedy algorithm suffers when resources are scarce, we investigate two alternative optimization techniques: Constraint Programming (CP) and AI planning. Both approaches struggle to cope with large problems, and so we strengthen them by leveraging the greedy algorithm. We use the greedy solution to warm start the CP model and to devise a domain-dependent heuristic for planning. Our extensive experimental evaluation studies the scalability of the different techniques and identifies the conditions under which one approach becomes preferable to the others.

PDF Details DOI

AIJ Journal 2018 Journal Article

Extracting mutual exclusion invariants from lifted temporal planning domains

Sara Bernardini
Fabio Fagnani
David E. Smith

We present a technique for automatically extracting mutual exclusion invariants from temporal planning instances. It first identifies a set of invariant templates by inspecting the lifted representation of the domain and then checks these templates against properties that assure invariance. Our technique builds on other approaches to invariant synthesis presented in the literature but departs from their limited focus on instantaneous actions by addressing temporal domains. To deal with time, we formulate invariance conditions that account for the entire temporal structure of the actions and the possible concurrent interactions between them. As a result, we construct a more comprehensive technique than previous methods, which is able to find not only invariants for temporal domains but also a broader set of invariants for sequential domains. Our experimental results provide evidence that our domain analysis is effective at identifying a more extensive set of invariants, which results in the generation of fewer multi-valued state variables. We show that, in turn, this reduction in the number of variables reflects positively on the performance of the temporal planners that use a variable/value representation.

Details DOI

ICAPS Conference 2017 Conference Paper

Boosting Search Guidance in Problems with Semantic Attachments

Sara Bernardini
Maria Fox 0001
Derek Long
Chiara Piacentini

Most applications of planning to real problems involve complex and often non-linear equations, including matrix operations. PDDL is ill-suited to express such calculations since it only allows basic operations between numeric fluents. To remedy this restriction, a generic PDDL planner can be connected to a specialised advisor, which equips the planner with the ability to carry out sophisticated mathematical operations. Unlike related techniques based on semantic attachment, our planner is able to exploit an approximation of the numeric information calculated by the advisor to compute informative heuristic estimators. Guided by both causal and numeric information, our planning framework outperforms traditional approaches, especially against problems with numeric goals. We provide evidence of the power of our solution by successfully solving four completely different problems.

Details

AAAI Conference 2017 Conference Paper

Deterministic versus Probabilistic Methods for Searching for an Evasive Target

Sara Bernardini
Maria Fox
Derek Long
Chiara Piacentini

Several advanced applications of autonomous aerial vehicles in civilian and military contexts involve a searching agent with imperfect sensors that seeks to locate a mobile target in a given region. Effectively managing uncertainty is key to solving the related search problem, which is why all methods devised so far hinge on a probabilistic formulation of the problem and solve it through branch-and-bound algorithms, Bayesian ﬁltering or POMDP solvers. In this paper, we consider a class of hard search tasks involving a target that exhibits an intentional evasive behaviour and moves over a large geographical area, i. e. , a target that is particularly difﬁcult to track down and uncertain to locate. We show that, even for such a complex problem, it is advantageous to compile its probabilistic structure into a deterministic model and use standard deterministic solvers to ﬁnd solutions. In particular, we formulate the search problem for our uncooperative target both as a deterministic automated planning task and as a constraint programming task and show that in both cases our solution outperforms POMDPs methods.

PDF Details

ICAPS Conference 2016 Conference Paper

Leveraging Probabilistic Reasoning in Deterministic Planning for Large-Scale Autonomous Search-and-Tracking

Sara Bernardini
Maria Fox 0001
Derek Long
Chiara Piacentini

Search-And-Tracking (SaT) is the problem of searching for a mobile target and tracking it once it is found. Since SaT platforms face many sources of uncertainty and operational constraints, progress in the field has been restricted to simple and unrealistic scenarios. In this paper, we propose a new hybrid approach to SaT that allows us to successfully address large-scale and complex SaT missions. The probabilistic structure of SaT is compiled into a deterministic planning model and Bayesian inference is directly incorporated in the planning mechanism. Thanks to this tight integration between automated planning and probabilistic reasoning, we are able to exploit the power of both approaches. Planning provides the tools to efficiently explore big search spaces, while Bayesian inference, by readily combining prior knowledge with observable data, allows the planner to make more informed and effective decisions. We offer experimental evidence of the potential of our approach.

Details

ICAPS Conference 2014 Conference Paper

Planning the Behaviour of Low-Cost Quadcopters for Surveillance Missions

Sara Bernardini
Maria Fox 0001
Derek Long

Micro Aerial Vehicles (MAVs) are increasingly regarded as a valid low-cost alternative to UAVs and ground robots in surveillance missions and a number of other civil and military applications. Research on autonomous MAVs is still in its infancy and has focused almost exclusively on integrating control and computer vision techniques to achieve reliable autonomous flight. In this paper, we describe our approach to using automated planning in order to elicit high-level intelligent behaviour from autonomous MAVs engaged in surveillance applications. Planning offers effective tools to handle the unique challenges faced by MAVs that relate to their fast and unstable dynamics as well as their low endurance and small payload capabilities. We demonstrate our approach by focusing on the "Parrot AR. Drone2. 0" quadcopter and Search-and-Tracking missions, which involve searching for a mobile target and tracking it after it is found.

Details

ICAPS Conference 2013 Conference Paper

Autonomous Search and Tracking via Temporal Planning

Sara Bernardini
Maria Fox 0001
Derek Long
John Bookless

Search And Tracking (SAT) is the problem of searching for a mobile target and tracking it after it is found. As this problem has important applications in search-and-rescue and surveillance operations, recently there has been increasing interest in equipping unmanned aerial vehicles (UAVs) with autonomous SAT capabilities. State-of-the-art approaches to SAT rely on estimating the probability density function of the target's state and solving the search control problem in a greedy fashion over a short planning horizon (typically, a one-step lookahead). These techniques suffer high computational cost, making them unsuitable for complex problems. In this paper, we propose a novel approach to SAT, which allows us to handle big geographical areas, complex target motion models and long-term operations. Our solution is to track the target reactively while it is in view and to plan a recovery strategy that relocates the target every time it is lost, using a high-performing automated planning tool. The planning problem consists of deciding where to search and which search patterns to use in order to maximise the likelihood of recovering the target. We show experimental results demonstrating the potential of our approach.

Details

ICAPS Conference 2013 Conference Paper

Planning-Based Social Partners for Children with Autism

Sara Bernardini
Kaska Porayska-Pomsta

This paper describes the design and implementation of a planning-based socially intelligent agent built to help young children with Autism Spectrum Conditions acquire social communication skills. We explain how planning technology allowed us to satisfy the requirements relating to the agent's design that we identified through our consultations with children and carers as well as our review of best practices for autism intervention. We discuss the design principles we implemented, the engineering challenges we faced and the lessons we learned in building the pedagogical agent. We conclude by presenting extensive experimental results concerning the agent's efficacy.

Details

SAT Conference 2004 Conference Paper

Incremental Compilation-to-SAT Procedures

Marco Benedetti
Sara Bernardini

We focus on incremental compilation-to-SAT procedures (iCTS), a promising way to push the standard CTS approaches beyond their limits. We propose the first comprehensive framework that encompasses all the aspects of an incremental decision procedure, from the encoding to the incremental solver. We apply our guidelines to a real-world CTS approach (Bounded Model Checking) and show how to modify both the generation mechanism of a real BMC tool (NuSMV) and the solving engine of a public-domain SAT solver (SIM). Related approaches and experimental results are discussed as well.

Details