Case-based reasoning networks are machine-learning models that make predictions based on similarity between the input and prototypical parts of training samples, called prototypes. Such models are able to explain each decision by pointing to the prototypes that contributed the most to the final outcome. As the explanation is a core part of the prediction, they are often qualified as "interpretable by design". While promising, we show that such explanations are sometimes misleading, which hampers their usefulness in safety-critical contexts. In particular, several instances may lead to different predictions and yet have the same explanation. Drawing inspiration from the field of formal eXplainable AI (formal XAI), we propose Abductive Latent Explanations (ALEs), a formalism to express sufficient conditions on the intermediate (latent) representation of the instance that imply the prediction. Our approach combines the inherent interpretability of case-based reasoning models and the guarantees provided by formal XAI. We propose a solver-free and scalable algorithm for generating ALEs based on three distinct paradigms, compare them, and present the feasibility of our approach on diverse datasets for both standard and fine-grained image classification.

Automated planning involves finding a sequence of actions that changes the world from an initial state to a final state with goals satisfied. The general problem is PSPACE-hard. Nevertheless, many restricted variants are NP-complete or even in P. Existing complexity work focuses mostly on plan existence, or plan with minimal plan length. Little is known about optimization variants that aim to satisfy as many goal conditions as possible. In this paper, we aim to fill this gap by providing a first inapproximability study of goal-maximization using the classical STRIPS formalism. For MAXPLANSAT and its length-bounded counterpart MAXPLANSAT(K), we prove tight constant-factor lower bounds. More specifically, through performing L-reductions from MAXE3SAT and MAX3DM, we show several of these problems are inapproximable by a constant factor, unless P=NP.

Hardness of modeling a planning domain is a major obstacle for making automated planning techniques accessible. We developed a tool that helps modelers correct domains based on available information such as the known feasibility or infeasibility of certain plans. Designing model repair strategies that are capable of repairing flawed planning domains automatically has been explored in previous work to use positive plans (invalid in the given (flawed) domain but feasible in the ``true'' domain). In this work, we highlight the importance of and study counter-example negative plans (valid in the given (flawed) domain but infeasible in the ``true'' domain). Our approach automatically corrects a domain by finding an optimal repair set to the domain which turns all negative plans into non-solutions, in addition to making all positive plans solutions. Experiments indicate strong performance in the fast-downward benchmark suite with random errors. A handcrafted benchmark with domain flaws inspired by some practical applications also motivates the method's efficacy.

Multi-agent pathfinding MAPF is a problem where multiple autonomous agents must find paths to their respective destinations without colliding. Decisional MAPF on undirected graphs can be solved in polynomial time; Several optimization MAPF variants however are NP-complete. The directed graph variant (diMAPF) is more complex, with its decisional version already being NP-complete. This paper examines the computational approximability of optimal MAPF problems (i.e., minimizing makespan for agent travel distance and maximizing the total number of agents reaching their goals), providing a first set of several inapproximability results for these problems. The results reveal an inherent limitation in approximating optimal solutions for MAPFs, provide a deeper understanding regarding their computational intractability, thus offer foundational references for future research.

This paper introduces a counter-example based approach for solving probabilistic conformant planning (PCP) problems. Our algorithm incrementally generates candidate plans and identifies counter-examples until it finds a plan for which the probability of success is above the specified threshold. We prove that the algorithm is sound and complete. We further propose a variation of our algorithm that uses hitting sets to accelerate the generation of candidate plans. Experimental results show that our planner is particularly suited for problems with a high probability threshold.

In this paper, we address the problem of finding the part of the observations that is useful for the diagnosis. We define a sub-observation as an abstraction of the observations. We then argue that a sub-observation is sufficient if it allows a diagnoser to derive the same minimal diagnosis as the original observations; and we define critical observations as a maximally abstracted sufficient sub-observation. We show how to compute a critical observation, and discuss a number of algorithmic improvements that also shed light on the theory of critical observations. Finally, we illustrate this framework on both state-based and event-based observations.

Designing a planning domain is a difficult task in AI planning. Assisting tools are thus required if we want planning to be used more broadly. In this paper, we are interested in automatically correcting a flawed domain. In particular, we are concerned with the scenario where a domain contradicts a plan that is known to be valid. Our goal is to repair the domain so as to turn the plan into a solution. Specifically, we consider both grounded and lifted representations support for negative preconditions and show how to explore the space of repairs to find the optimal one efficiently. As an evidence of the efficiency of our approach, the experiment results show that all flawed domains except one in the benchmark set can be repaired optimally by our approach within one second.

Deep learning is increasingly used to learn policies for planning problems, yet policies represented by neural networks are difficult to interpret, verify and trust. Existing formal approaches to post-hoc explanations provide concise reasons for a single decision made by an ML model. However, understanding planning policies require explaining sequences of decisions. In this paper, we formulate the problem of finding explanations for the sequence of decisions recommended by a learnt policy in a given state. We show that, under certain assumptions, a minimal explanation for a sequence can be computed by solving a number of single decision explanation problems which is linear in the length of the sequence. We present experimental results of our implementation of this approach for ASNet policies for classical planning domains.

This paper introduces three improvements to the conformant planner CPCES, which continuously searches candidate plans and counter-examples against the current candidate plan until a valid plan (no counter-example exists) is found. First, we identify and merge equivalent PDDL facts to accelerate candidate plan generation. Second, we warm-start CPCES by generating multiple carefully selected counter-examples at the beginning of the procedure, which reduces the number of calls to the classical planner. Third, we investigate the use Fast Downward (FD) as the candidate plan generator; in particular, we propose an incremental procedure to generate the SAS+ file used by FD. Our experimental results show significant improvements for each technique.

There has been increasing acceptance that agents must act in a way that is sensitive to ethical considerations. These considerations have been cashed out as constraints, such that some actions are permissible, while others are impermissible. In this paper, we claim that, in addition to only performing those actions that are permissible, agents should only perform those courses of action that are _unambiguously_ permissible. By doing so they signal normative compliance: they communicate their understanding of, and commitment to abiding by, the normative constraints in play. Those courses of action (or plans) that succeed in signalling compliance in this sense, we term 'acceptable'. The problem this paper addresses is how to compute plans that signal compliance, that is, how to find plans that are acceptable as well as permissible. We do this by identifying those plans such that, were an observer to see only part of its execution, that observer would infer the plan enacted was permissible. This paper provides a formal definition of compliance signalling within the domain of AI planning, describes an algorithm for computing compliance signalling plans, provides preliminary experimental results and discusses possible improvements. The signalling of compliance is vital for communication, coordination and cooperation in situations where the agent is partially observed. It is equally vital, therefore, to solve the computational problem of finding those plans that signal compliance. This is what this paper does.

In a counter-example based approach to conformant planning, choosing the right counter-example can improve performance. We formalise this observation by introducing the notion of “superiority” of a counter-example over another one, that holds whenever the superior counter-example exhibits more tags than the latter. We provide a theoretical explanation that supports the strategy of searching for maximally superior counter-examples, and we show how this strategy can be implemented. The empirical experiments validate our approach.

We present BRIGITTE, a new path-finding algorithm for 8-connected grids. It is based on the notion bridge that we define here, i.e., a high-level description of paths between all pairs of points from two convex regions that allows fast distance query and fast generation of the prefix and suffix of these paths. BRIGITTE uses a pre-processing step to first partition the map into convex regions and then compute a sufficient set of bridges between every pair of regions. Path-finding is then performed by looking up the regions of the source and target cells and then iterating over the bridges of the pair of regions to determine which one yields the shortest path. BRIGITTE competes favourably compared to CH-SG-R and Copp, although this currently comes at a price of an extensive pre-processing.

In this paper, we propose an approach to ensure the diagnosability of a partially controllable system. Given a model of correct and faulty behaviors of a partially observable discrete event system, equipped with a set of elementary actions that do not intertwine with autonomous events, we search a diagnosability plan, i.e., a sequence of applicable actions that leads the system from an initial belief state (a set of potentially current states) to a diagnosable belief state, in which the system is then left to run freely. This helps in reducing the diagnosis interaction with running systems and can be applied, e.g., on the output of a repair plan, like in power networks. The two successive stages of this approach keep diagnosability planning, including diagnosability tests, in PSpace in comparison to the Exptime test for the more complex active diagnosability used usually in such cases. For this, we propose to construct incrementally the twin plant structure of the given system and to exploit its parts already constructed while testing the candidate plans and constructing its next parts. This helps in pruning the twin plant constructions and many non-diagnosability plan tests. We have created a special benchmark and tested three proposed methods, according to the recycling level of twin plants construction, with one cost function used for plan optimality and an optional heuristics.

In this paper, we propose a method to diagnose faults in a discrete event system that only relies on past observed logs and not on any behavioural model of the system. Given a set of tagged logs produced by the system, the first objective is to extract from them a set of fault signatures. These fault signatures are represented with a set of critical observations that are the support of the diagnosis method. We first propose a method to compute the fault signatures from an initial log journal and follow with detail on how the signatures can then be updated when new logs are available.

We want to compute geometric shortest paths in a collection of convex traversable polygons, also known as a navigation mesh. Simple to compute and easy to update, navigation meshes are widely used for pathfinding in computer games. When the mesh is static, shortest path problems can be solved exactly and very fast but only after a costly preprocessing step. When the mesh is dynamic, practitioners turn to online methods which typically compute only approximately shortest paths. In this work we present a new pathfinding algorithm which is compromise-free; i.e. it is simultaneously fast, online and optimal. Our method, Polyanya, extends and generalises Anya; a recent and related interval-based search technique developed for computing geometric shortest paths in grids. We show how that algorithm can be modified to support search over arbitrary sets of convex polygons and then evaluate its performance on a range of realistic and synthetic benchmark problems.

We propose a new method for conformant planning based on two ideas. First given a small sample of the initial belief state we reduce conformant planning for this sample to a classical planning problem, giving us a candidate solution. Second we exploit regression as a way to compactly represent necessary conditions for such a solution to be valid for the non-deterministic setting. If necessary, we use the resulting formula to extract a counter-example to populate our next sampling. Our experiments show that this approach is competitive on a class of problems that are hard for traditional planners, and also returns generally shorter plans. We are also able to demonstrate unsatisfiability of some problems.

Any-angle pathfinding is a fundamental problem in robotics and computer games. The goal is to find a shortest path between a pair of points on a grid map such that the path is not artificially constrained to the points of the grid. Prior research has focused on approximate online solutions. A number of exact methods exist but they all require super-linear space and pre-processing time. In this study, we describe Anya: a new and optimal any-angle pathfinding algorithm. Where other works find approximate any-angle paths by searching over individual points from the grid, Anya finds optimal paths by searching over sets of states represented as intervals. Each interval is identified on-the-fly. From each interval Anya selects a single representative point that it uses to compute an admissible cost estimate for the entire set. Anya always returns an optimal path if one exists. Moreover it does so without any offline pre-processing or the introduction of additional memory overheads. In a range of empirical comparisons we show that Anya is competitive with several recent (sub-optimal) online and pre-processing based techniques and is up to an order of magnitude faster than the most common benchmark algorithm, a grid-based implementation of A*.

We propose a new approach to diagnosis of hybrid systems. In this approach, questions about the behavior of the system are asked and translated into Satisfiability Modulo Theory (SMT) problems, which are then solved by an SMT solver. We show the reduction to SMT. We also discuss the benefits and the drawbacks of this approach and conclude with a number of research directions that will make this approach applicable to large systems.

Diagnosis of discrete event systems requires to decide whether the system model allows for certain types of executions to take place. Because this problem is hard, incomplete yet faster algorithms may be needed. This however can lead to a loss of precision. This paper presents a method to decide whether precision is maintained by such incomplete algorithms. To this end we define the Simulation, which is a modification of the model that simulates how the algorithm works. We then use the twin plant method to decide whether diagnosability is maintained despite the imprecision of the diagnostic algorithm. We illustrate the benefits of this approach on two diagnostic algorithms, namely Independent-Windows Algorithms and Chronicle-based Diagnosis.

We describe a pathfinding system based on Jump Point Search (JPS): a recent and very successful search strategy that performs symmetry breaking to speed up optimal pathfinding on grid maps. We first modify JPS for grid maps where corner-cutting moves are not allowed. We then describe JPS+: a new derivative search strategy that reformulates an input graph into an equivalent symmetry-reduced form that can be searched more efficiently. JPS and JPS+ were both submitted to the 2012 Grid-based Path Planning Competition.

Pathfinding in uniform-cost grid environments is a problem commonly found in application areas such as robotics and video games. The state-of-the-art is dominated by hierarchical pathfinding algorithms which are fast and have small memory overheads but usually return suboptimal paths. In this paper we present a novel search strategy, specific to grids, which is fast, optimal and requires no memory overhead. Our algorithm can be described as a macro operator which identifies and selectively expands only certain nodes in a grid map which we call jump points. Intermediate nodes on a path connecting two jump points are never expanded. We prove that this approach always computes optimal solutions and then undertake a thorough empirical analysis, comparing our method with related works from the literature. We find that searching with jump points can speed up A* by an order of magnitude and more and report significant improvement over the current state of the art.

We propose a SAT-based algorithm for incremental diagnosis of discrete-event systems. The monotonicity is ensured by a prediction window that uses the future observations to lead the current diagnosis. Experiments stress the impact of parameters tuning on the correctness and the efficiency of the approach.

We extend the decentralised/distributed approach of diagnosis of discrete-event systems modeled using automata. The goal is to avoid computing a global diagnosis, which is expensive, and to perform local diagnoses instead. To still ensure global consistency, we transform the topology of the system into a junction tree where each vertex represents a subsystem. Local consistency between the diagnoses of these subsystems ensures global consistency due to the tree structure. This technique will work best for systems whose natural structure is close to a tree structure, as the generated automata will be of reasonable size.