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.

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.

With the fast development of offshore wind farms as renewable energy sources, maintaining them efficiently and safely becomes necessary. The high costs of operation and maintenance (O&M) are due to the length of turbine downtime and the logistics for human technician transfer. To reduce such costs, we propose a comprehensive multi-robot system that includes unmanned aerial vehicles (UAV), autonomous surface vessels (ASV), and inspection-and-repair robots (IRR). Our system, which is capable of co-managing the farms with human operators located onshore, brings down costs and significantly reduces the Health and Safety (H&S) risks of O&M by assisting human operators in performing dangerous tasks. In this paper, we focus on using AI temporal planning to coordinate the actions of the different autonomous robots that form the multi-robot system. We devise a new, adaptive planning approach that reduces failures and replanning by performing data-driven goal and domain refinement. Our experiments in both simulated and real-world scenarios prove the effectiveness and robustness of our technique. The success of our system marks the first-step towards a large-scale, multirobot solution for wind farm O&M.

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.

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.

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.

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.

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.

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.

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 quantifies 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.

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.

Abstract 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.

This article examines the educational efficacy of a learning environment in which children diagnosed with Autism Spectrum Conditions (ASC) engage in social interactions with an artificially intelligent (AI) virtual agent and where a human practitioner acts in support of the interactions. A multi-site intervention study in schools across the UK was conducted with 29 children with ASC and learning difficulties, aged 4--14 years old. For reasons related to data completeness and amount of exposure to the AI environment, data for 15 children was included in the analysis. The analysis revealed a significant increase in the proportion of social responses made by ASC children to human practitioners. The number of initiations made to human practitioners and to the virtual agent by the ASC children also increased numerically over the course of the sessions. However, due to large individual differences within the ASC group, this did not reach significance. Although no evidence of transfer to the real-world post-test was shown, anecdotal evidence of classroom transfer was reported. The work presented in this article offers an important contribution to the growing body of research in the context of AI technology design and use for autism intervention in real school contexts. Specifically, the work highlights key methodological challenges and opportunities in this area by leveraging interdisciplinary insights in a way that (i) bridges between educational interventions and intelligent technology design practices, (ii) considers the design of technology as well as the design of its use (context and procedures) on par with one another, and (iii) includes design contributions from different stakeholders, including children with and without ASC diagnosis, educational practitioners, and researchers.

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 filtering 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 difficult 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 find 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.

The development of social communication skills in children relies on multimodal aspects of communication such as gaze, facial expression, and gesture. We introduce a multimodal learning environment for social skills which uses computer vision to estimate the children's gaze direction, processes gestures from a large multi-touch screen, estimates in real time the affective state of the users, and generates interactive narratives with embodied virtual characters. We also describe how the structure underlying this system is currently being extended into a general framework for the development of interactive multimodal systems.