Various model-based diagnosis scenarios require the computation of the most preferred fault explanations. Existing algorithms that are sound (i.e., output only actual fault explanations) and complete (i.e., can return all explanations), however, require exponential space to achieve this task. As a remedy, to enable successful diagnosis on memory-restricted devices and for memory-intensive problem cases, we propose RBF-HS, a diagnostic search method based on Korf's well-known RBFS algorithm. RBF-HS can enumerate an arbitrary fixed number of fault explanations in best-first order within linear space bounds, without sacrificing the desirable soundness or completeness properties. Evaluations using real-world diagnosis cases show that RBF-HS, when used to compute minimum-cardinality fault explanations, in most cases saves substantial space (up to 98 %) while requiring only reasonably more or even less time than Reiter's HS-Tree, a commonly used and as generally applicable sound, complete and best-first diagnosis search.

This document describes the design and implementation of the Tabletop Games framework (TAG), a Java-based benchmark for developing modern board games for AI research. TAG provides a common skeleton for implementing tabletop games based on a common API for AI agents, a set of components and classes to easily add new games and an import module for defining data in JSON format. At present, this platform includes the implementation of seven different tabletop games that can also be used as an example for further developments. Additionally, TAG also incorporates logging functionality that allows the user to perform a detailed analysis of the game, in terms of action space, branching factor, hidden information, and other measures of interest for Game AI research. The objective of this document is to serve as a central point where the framework can be described at length. TAG can be downloaded at: https://github.com/GAIGResearch/TabletopGames

The theory of computation is one of the crown jewels of the computer science curriculum. It stretches from the discovery of mathematical problems, such as the halting problem, that cannot be solved by computers, to the most celebrated open problem in computer science today: the P vs. NP question. Since the founding of our discipline by Church and Turing in the 1930s, the theory of computation has addressed some of the most fundamental questions about computers: What does it mean to compute the solution to a problem? Which problems can be solved by computers? Which problems can be solved efficiently, in theory and in practice?

Japanese toy-maker MegaHouse Corp. said Wednesday it will launch the world's smallest working Rubik's Cube, weighing about 2 grams and measuring 0.99 centimeter on each side. On the same day, the Bandai Namco Holdings Inc. subsidiary started accepting orders for the product online. It is priced at ¥198,000 in Japan, including delivery costs. Delivery will start in late December. The Rubik's Cube, invented by Erno Rubik from Hungary in 1974, hit store shelves across the world in 1980. In Japan, MegaHouse has shipped out over 14 million cubes.

This paper introduces a blazingly fast, no-loss expert system for Tic Tac Toe using Decision Trees called T3DT, that tries to emulate human gameplay as closely as possible. It does not make use of any brute force, minimax or evolutionary techniques, but is still always unbeatable. In order to make the gameplay more human-like, randomization is prioritized and T3DT randomly chooses one of the multiple optimal moves at each step. Since it does not need to analyse the complete game tree at any point, T3DT is exceptionally faster than any brute force or minimax algorithm, this has been shown theoretically as well as empirically from clock-time analyses in this paper. T3DT also doesn't need the data sets or the time to train an evolutionary model, making it a practical no-loss approach to play Tic Tac Toe.

Algorithms can search the game trees to determine the best move to make from the current state. The most well known is called the Minimax algorithm. The minimax algorithm is a useful method for simple two-player games. It is a method for selecting the best move given an alternating game where each player opposes the other working toward a mutually exclusive goal. Each player knows the moves that are possible given a current game state, so for each move, all subsequent moves can be discovered.

Augmenting a base constraint model with additional constraints can strengthen the inferences made by a solver and therefore reduce search effort. We focus on the automatic addition of streamliner constraints, derived from the types present in an abstract Essence specification of a problem class of interest, which trade completeness for potentially very significant reduction in search. The refinement of streamlined Essence specifications into constraint models suitable for input to constraint solvers gives rise to a large number of modelling choices in addition to those required for the base Essence specification. Previous automated streamlining approaches have been limited in evaluating only a single default model for each streamlined specification. In this paper we explore the effect of model selection in the context of streamlined specifications. We propose a new best-first search method that generates a portfolio of Pareto Optimal streamliner-model combinations by evaluating for each streamliner a portfolio of models to search and explore the variability in performance and find the optimal model. Various forms of racing are utilised to constrain the computational cost of training.

Causal effect identification considers whether an interventional probability distribution can be uniquely determined from a passively observed distribution in a given causal structure. If the generating system induces context-specific independence (CSI) relations, the existing identification procedures and criteria based on do-calculus are inherently incomplete. We show that deciding causal effect non-identifiability is NP-hard in the presence of CSIs. Motivated by this, we design a calculus and an automated search procedure for identifying causal effects in the presence of CSIs. The approach is provably sound and it includes standard do-calculus as a special case. With the approach we can obtain identifying formulas that were unobtainable previously, and demonstrate that a small number of CSI-relations may be sufficient to turn a previously non-identifiable instance to identifiable.

Problems affecting the transport of people or goods are plentiful in industry and commerce and they also appear to be at the origin of much more complex problems. In recent years, the logistics and transport sector keeps growing supported by technological progress, i.e. companies to be competitive are resorting to innovative technologies aimed at efficiency and effectiveness. This is why companies are increasingly using technologies such as Artificial Intelligence (AI), Blockchain and Internet of Things (IoT). Artificial intelligence, in particular, is often used to solve optimization problems in order to provide users with the most efficient ways to exploit available resources. In this work we present an overview of our current research activities concerning the development of new algorithms, based on CLP techniques, for route planning problems exploiting the geometric information intrinsically present in many of them or in some of their variants. The research so far has focused in particular on the Euclidean Traveling Salesperson Problem (Euclidean TSP) with the aim to exploit the results obtained also to other problems of the same category, such as the Euclidean Vehicle Routing Problem (Euclidean VRP), in the future.

Path finding problems involve identification of a plan for conflict free movement of agents over a common road network. Most approaches to this problem handle the agents as point objects, wherein the size of the agent is significantly smaller than the road on which it travels. In this paper, we consider spatially extended agents which have a size comparable to the length of the road on which they travel. An optimal multi agent path finding approach for spatially-extended agents was proposed in the eXtended Conflict Based Search (XCBS) algorithm. As XCBS resolves only a pair of conflicts at a time, it results in deeper search trees in case of cascading or multiple (more than two agent) conflicts at a given location. This issue is addressed in eXtended Conflict Based Search with Awareness (XCBS-A) in which an agent uses awareness of other agents' plans to make its own plan. In this paper, we explore XCBS-A in greater detail, we theoretically prove its completeness and empirically demonstrate its performance with other algorithms in terms of variances in road characteristics, agent characteristics and plan characteristics. We demonstrate the distributive nature of the algorithm by evaluating its performance when distributed over multiple machines. XCBS-A generates a huge search space impacting its efficiency in terms of memory; to address this we propose an approach for memory-efficiency and empirically demonstrate the performance of the algorithm. The nature of XCBS-A is such that it may lead to suboptimal solutions, hence the final contribution of this paper is an enhanced approach, XCBS-Local Awareness (XCBS-LA) which we prove will be optimal and complete.