The European Journal on Artificial Intelligence

Neighbourhood singleton arc consistency (NSAC) is a type of singleton arc consistency (SAC) in which the subproblem formed by variables adjacent to a variable with a singleton domain is made arc consistent. This paper describes two extensions to neighbourhood SAC. The first is a generalization from NSAC to k-NSAC, where k is the maximum length of the shortest path between the singleton variable and any variable in the subgraph. The second is an extension of k-NSAC to problems with n-ary constraints, which retains the basic definition of a k-neighbourhood subgraph. To establish such consistencies a suite of algorithms is considered based on various SAC algorithms including SAC-1, SACQ, SAC-SDS, and SAC-3. In analyzing these different algorithms it was found useful to distinguish between “light-weight” and “heavy-weight” SAC algorithms, based on the complexity of data structures and procedures needed to carry out the task of establishing (N)SAC. Under this classification, SAC-1 and SACQ are light-weight; the other two (and SAC-2) are heavy-weight. It was found that only light-weight algorithms can be readily and effectively transformed into efficient NSAC algorithms. In contrast, because of their specialized procedures, it was necessary to modify heavy-weight algorithms significantly, which also compromised performance. Extensive experimental analysis shows that with a spectrum of neighbourhood consistencies and attendant algorithms, one can finesse the fundamental tradeoff between efficiency and effectiveness across a greater range of problems than with SAC and NSAC algorithms alone. This work serves to enlarge the scope of SAC-based consistency maintenance as well as defining the various niches that light-weight and heavy-weight algorithms are best suited for.

In this paper a new discrete Differential Evolution algorithm for the Permutation Flowshop Scheduling Problem with the total flowtime and makespan criteria is proposed. The core of the algorithm is the distance-based differential mutation operator defined by means of a new randomized bubble sort algorithm. This mutation scheme allows the Differential Evolution to directly navigate the permutations search space. Experiments were held on a well known benchmarks suite and they show that the proposal reaches very good performances compared to other state-of-the-art algorithms. The results are particularly satisfactory on the total flowtime criterion where also new upper bounds that improve on the state-of-the-art have been found.

Research literature on Probabilistic Model Checking (PMC) encompasses a well-established set of algorithmic techniques whereby probabilistic models can be analyzed. In the last decade, owing to the increasing availability of effective tools, PMC has found applications in many domains, including computer networks, computational biology and robotics. In this paper, we evaluate PMC tools – namely comics, mrmc and prism – to investigate safe reinforcement learning in robots, i.e., to establish safety of policies learned considering feedback signals received upon acting in partially unknown environments. Introduced in previous contributions of ours, this application is a challenging domain wherein PMC tools act as back-engines of an automated methodology aimed to verify and repair control policies. We present an evaluation of the current state-of-the-art PMC tools to assess their potential on various case studies, including both real and simulated robots accomplishing navigation, manipulation and reaching tasks.

Immunization strategies are significant in many real scale-free networks, e.g. Internet or communication systems, to prevent virus infections. Several centralized and distributed strategies have been proposed in the last few years. They are efficient but they share the same major limitation: they need to know in advance the network topology and the size of the network or the number of nodes that must be immunized. These requirements make those strategies unsuitable for application to real and dynamic networks. In this paper, we propose an immunization strategy based on distributed autonomous entities that self-regulate their diffusion in the network where they are deployed. Experiments show that the proposed approach produces a population that is able to self regulate in many widely accepted benchmarks while achieving different target coverage rates.

We provide a systematic analysis of levels of integration between discrete high-level reasoning and continuous low-level feasibility checks to address hybrid planning problems in robotic applications. We identify four distinct strategies for such an integration: (i) low-level checks are done for all possible cases in advance and the results are used during plan generation; (ii) low-level checks are done exactly when they are needed during the search for a plan; (iii) low-level checks are done after a plan is computed, and if the plan is found infeasible then a new plan is computed; (iv) similar to the previous strategy but the results of previous low-level checks are used during computation of a new plan. We analyze the usefulness of these strategies and their combinations by experiments on hybrid planning problems in different robotic application domains, in terms of computational efficiency and plan quality (relative to its feasibility).

Similarly to Maximum Satisfiability (MaxSAT), Minimum Satisfiability (MinSAT) is an optimization extension of the Boolean Satisfiability (SAT) decision problem. In recent years, both problems have been studied in terms of exact and approximation algorithms. In addition, the MaxSAT problem has been characterized in terms of Maximal Satisfiable Subsets (MSSes) and Minimal Correction Subsets (MCSes), as well as Minimal Unsatisfiable Subsets (MUSes) and minimal hitting set dualization. However, and in contrast with MaxSAT, no such characterizations exist for MinSAT. This paper addresses this issue by casting the MinSAT problem in a more general framework. The paper studies Maximal Falsifiability, the problem of computing a subset-maximal set of clauses that can be simultaneously falsified, and shows that MinSAT corresponds to the complement of a largest subset-maximal set of simultaneously falsifiable clauses, i.e. the solution of the Maximum Falsifiability (MaxFalse) problem. Additional contributions of the paper include novel algorithms for Maximum and Maximal Falsifiability, as well as minimal hitting set dualization results for the MaxFalse problem. Moreover, the proposed algorithms are validated on practical instances.

In theory, an algorithm exists for solving non-binary Constraint Satisfaction Problems (CSPs) by using a Generalized Hypertree Decomposition (GHD). However in practice, this algorithm called GLS (due to Gottlob et al.) which is based on the Join Acyclic Solving (JAS) algorithm is inefficient when dealing with large instances because of memory fault or time out problem. In our research works, several approaches have been developed in order to exploit GHD for a practical resolution of extensional non-binary CSPs. One of them, called Forward-Checking based on Generalized Hypertree Decomposition (FC-GHD) algorithm, combines both the merits of an enumerative search algorithm which is memory efficient with those of the Generalized Hypertree Decomposition which is time efficient. In this present article, compressed table constraints are used with FC-GHD in order to study the benefit of such a technique for large CSPs. The resulting algorithm called CFC-GHD is described in this paper together with two improved extended versions of it called CFC-GHD+NG (for structural NoGoods) and CFC-GHD+NG+DR (for Dynamic Reordering of subtrees). Although the new algorithms present computation times comparable to those obtained with the non compressed versions of the algorithms, the new approach is a better candidate for solving optimization problems and more specifically multi-objective ones which involve taking decisions over several possible solutions.

Databases often contain missing values caused in different scenarios. Even though many methods are available to treat such missing values, they are specific to only certain types of missingness and are not commonly applicable to all scenarios. To address this issue, this thesis proposes a novel technique called Bayesian Genetic Algorithm (BAGEL) which combines both Bayesian principles and Genetic Algorithm to impute values in different kinds of missing scenarios and different kinds of attributes in mixed attribute datasets.

Integrating a web application into an automated business process requires to design wrappers that get user queries as input and map them onto the search forms that the application provides. Such wrappers build on automatic navigators which are responsible for navigating to the pages that provide the information required to answer the original user queries. A navigator relies on a web page classifier that discerns which pages provide the information and which do not. In the literature, there are many proposals to classify web pages, but none of them fulfills the requirements for a web page classifier in a navigator context. We address the problem of designing an unsupervised web page classifier that builds solely on the information provided by the URLs and does not require extensive crawling of the site being analysed. Our contribution is CALA, a new automated proposal to generate URL-based web page classifiers. Its salient features are that it does not need to previously crawl the complete web site, it is unsupervised, it does not require to download a page before classifying it, and it is computationally tractable. It has been validated by a number of experiments using real-world, top-visited web sites.

This thesis is focused on the study of the Autonomic Computing (AC) paradigm within the scope of Multimedia Communication Systems (MCSs). Specifically, it analyzes the set of autonomic properties and identifies the properties that can be observed in MCSs, specially those suitable to be implemented in a synchronous e-learning platform. Based on this analysis, the aim of this thesis is to design a self-managed multimedia distribution platform for developing synchronous e-learning activities, providing an efficient data delivery service and minimizing the required human intervention. The self-healing and self-optimization techniques of this platform use heuristics to select optimal data distribution paths is spite of failures and member joining and leaving.

Reasoning and change over inconsistent ontologies (i-ont(s)) is of utmost relevance in sciences like medicine and law. Argumentation may be an appropriate formalism to cope with both problems: (reasoning) through an Argumentation Framework ( AF ) constructed from the i-ont, and (change) by handling the dynamics of its arguments. We propose a new family of abstract AF s referred as generalized ( GenAF ), due to its ability of adapting to different representation languages. Afterwards, we propose a possible instantiation of the GenAF ’s abstract language for arguments to the basic ALC description logic for reasoning over i-onts. For dynamics of arguments, a revision operation modifies the graph of arguments in an AF for provoking the argumentation semantics to accept an argument. Thus, revising an ALC - GenAF would introduce a novel methodology for handling evolution of i-onts. To such end, we propose a revision operation by relying upon classic belief revision theory, although contrary to it, consistency restoration is avoided in order to handle evolution with inconsistency tolerance.