International Journal on Artificial Intelligence Tools

Please refer to full text.

We introduce, study, and evaluate a novel algorithm in the context of qualitative constraint-based spatial and temporal reasoning that is based on the idea of variable elimination, a simple and general exact inference approach in probabilistic graphical models. Given a qualitative constraint network $\mathcal{N}$, our algorithm utilizes a particular directional local consistency, which we denote by $\stackrel{\overleftarrow{\diamond }}{G}$-consistency, in order to efficiently decide the satisfiability of $\mathcal{N}$. Our discussion is restricted to distributive subclasses of relations, i.e., sets of relations closed under converse, intersection, and weak composition and for which weak composition distributes over non-empty intersections for all of their relations. We demonstrate that enforcing $\stackrel{\overleftarrow{\diamond }}{G}$-consistency in a given qualitative constraint network defined over a distributive subclass of relations allows us to decide its satisfiability, and obtain similar useful results for the problems of minimal labelling and redundancy. Further, we present a generic method that allows extracting a scenario from a satisfiable network, i.e., an atomic satisfiable subnetwork of that network, in a very simple and effective manner. The experimentation that we have conducted with random and real-world qualitative constraint networks defined over a distributive subclass of relations of the Region Connection Calculus and the Interval Algebra, shows that our approach exhibits unparalleled performance against state-of-the-art approaches for checking the satisfiability of such constraint networks.

Constraint programming (CP) is a powerful paradigm for various types of hard combinatorial problems. Constraint propagation techniques, such as arc consistency (AC), are used within solvers to prune inconsistent values from the domains of the variables and narrow down the search space. Local consistencies stronger than AC have the potential to prune the search space even more, but they are not widely used because they incur a high run time penalty in cases where they are unsuccessful. All constraint propagation techniques are sequential by nature, and thus they cannot be scaled up to modern multicore machines. For this reason, research on parallelizing constraint propagation is very limited. Contributing towards this direction, we exploit the parallelization possibilities of modern CPUs in tandem with strong local propagation methods in a novel way. Instead of trying to parallelize constraint propagation algorithms, we propose two search algorithms that apply different propagation methods in parallel. Both algorithms consist of a master search process, which is a typical CP solver, and a number of slave processes, with each one implementing a strong propagation method. The first algorithm runs the different propagators synchronously at each node of the search tree explored in the master process, while the second one can run them asynchronously at different nodes of the search tree. Preliminary experimental results on well-established benchmarks display the promise of our research by illustrating that our algorithms have execution times equal to those of serial solvers, in the worst case, while being faster in most cases.

In the late 1990s, Constrained Programming (CP) promised to separate the declaration of a problem from the process to solve it. This work attempts to serve this direction, by implementing and presenting a modular way to define search methods that seek solutions to arbitrary Constraint Satisfaction Problems (CSPs). The user just declares their CSP, and it can be solved using a portfolio of search methods already in place. Apart from the pluggable search methods framework for any CSP, we also introduce pluggable heuristics for our search methods. We found an efficient stochastic heuristics’ paradigm that smoothly combines randomness with normal heuristics. We consider a factor of disobedience to normal heuristics, and we fine-tune it each time, according to our estimation of normal heuristics’ reliability (confidence). We prove mathematically that while the disobedience factor decreases, the stochastic heuristics approximate deterministic normal heuristics. Our algebraic evidence is supported by empirical evaluations on real life problems: A new search method, namely PoPS, that exploits this heuristics’ paradigm, can outperform regular well-known constructive search methods.

Evolutionary algorithms have been long established as an essential field of research in Computational Intelligence. Differential Evolution is placed among the most successful algorithms of this type. However, it has proved to be highly sensitive on its parameters. For this purpose, offline and online parameter-control methods have been proposed. Recently, a grid-based parameter adaptation procedure was introduced and successfully applied on Differential Evolution. Despite the generality of the method, the resulting algorithm was capable to compete with already tuned adaptive algorithms on high-dimensional test problems without any additional preprocessing. The present work extends the experimental study of this approach on the state-of-the-art CEC-2013 test suite. Two variants of the algorithm are considered and different initial conditions are tested to shed light on its performance aspects. Comparisons with other algorithms as well as between the proposed approaches are reported. The results verify the potential of the grid-based parameter adaptation method as a general-purpose alternative for parameter setting.

This paper investigates the use of reinforcement learning for the navigation of an over-actuated, i.e. more control inputs than degrees of freedom, marine platform in unknown environment. The proposed approach uses an online least-squared policy iteration scheme for value function approximation in order to estimate optimal policy, in conjunction with a low-level control system that controls the magnitude of the linear velocity, and the orientation of the platform. Primary goal of the proposed scheme is the reduction of the consumed energy. To that end, we propose a variable reward function that depends on the energy consumption of the platform. We evaluate our approach in a complex and realistic simulation environment and report results concerning its performance on estimating optimal navigation policies under different environmental disturbances, and position GPS measurement noise. The proposed framework is compared, in terms of energy consumption, to a baseline approach based on virtual potential fields. The results show that the marine platform successfully discovers the target point following a sub-optimal path, maintaining reduced energy consumption.

Data clustering is an unsupervised learning task that has found many applications in various scientific fields. The goal is to find subgroups of closely related data samples (clusters) in a set of unlabeled data. A classic clustering algorithm is the so-called k-Means. It is very popular, however, it is also unable to handle cases in which the clusters are not linearly separable. Kernel k-Means is a state of the art clustering algorithm, which employs the kernel trick, in order to perform clustering on a higher dimensionality space, thus overcoming the limitations of classic k-Means regarding the non-linear separability of the input data. With respect to the challenges of Big Data research, a field that has established itself in the last few years and involves performing tasks on extremely large amounts of data, several adaptations of the Kernel k-Means have been proposed, each of which has different requirements in processing power and running time, while also incurring different trade-offs in performance. In this paper, we present several issues and techniques involving the usage of Kernel k-Means for Big Data clustering and how the combination of each component in a clustering framework fares in terms of resources, time and performance. We use experimental results, in order to evaluate several combinations and provide a recommendation on how to approach a Big Data clustering problem.

This paper studies the problem of automatic categorization of Arabic normative provisions. An automatic categorization approach based on a semantic annotation model is proposed. Coupling a taxonomy of Arabic normative provisions’ categories, an Arabic normative terminological base and a rule-based semantic annotator, the proposed semantic annotation model enables the automatic categorization of normative provisions in Arabic legal texts. The robustness and the language independency of the proposed approach are also studied. Robustness is measured with the comparison of the constructed model against Machine Learning (ML) approaches. The language independency level is evaluated through the adaptation of the proposed model to the French language. The performance of the approach is evaluated in terms of Precision, Recall and F-score. The obtained results for the different experiments are very promising.