International Journal on Artificial Intelligence Tools

Distributed Constraint Optimization Problem (DCOP) is a powerful paradigm to model multi-agent systems through enabling multiple agents to coordinate with each other to solve a problem. These agents are often assumed to be cooperative, that is, they communicate with other agents in order to optimize a global objective. However, the communication times between all pairs of agents are assumed to be identical in the evaluation of most DCOP algorithms. This assumption is impractical in almost all real-world applications. In this paper, we study the impact of empirically evaluating a DCOP algorithm under the assumption that communication times between pairs of agents can vary. In addition, we evaluate a DCOP algorithm using ns-2, a discrete-event simulator that is widely used in the computer networking community, to simulate the communication times, as opposed to the standard DCOP simulators that are used to evaluate DCOP algorithms in the AI community. Furthermore, we propose heuristics that exploit the non-uniform communication times to speed up DCOP algorithms that operate on pseudo-trees. Our empirical results demonstrate that the proposed heuristics improve the runtime of those algorithms up to 20%. These heuristics are evaluated on different benchmarks such as scale-free graphs, random graphs, and an instance of the smart grid, Customer-Driven Microgrid (CDMG) application.

Process Discovery techniques, allowing to extract graph-like models from large process logs, are a valuable mean for grasping a summarized view of real business processes’ behaviors. If augmented with statistics on process performances (e.g., processing times), such models help study the evolution of process performances across different processing steps, and possibly detect bottlenecks and worst practices. However, when the process analyzed exhibits complex and heterogeneous behaviors, these techniques fail to yield good quality models, in terms of readability, accuracy and generality. In particular, the presence of deviant traces may lead to cumbersome models and misleading performance statistics. Current noise/outlier filtering solutions can alleviate this problem and help discover a better model for “normal” process executions, but they do not provide insight on the deviant ones. Then, difficult and expensive analyses are usually performed to extract interpretable and general enough patterns for deviant behaviors. The performance-oriented discovery approach proposed here is addressed to recognize and describe both a normal execution scenario and deviant ones for the process analyzed, by inducing different sub-models: (i) a collection of readable clustering rules (conjunctive patterns over trace attributes) defining the deviance scenarios; (ii) a performance model $M_0$ for the “normal” traces that do not fall in any deviant scenario; and (iii) a performance model (and a “difference” model emphasizing the differences in behaviors from the “normal” execution scenario), for each discovered deviance scenario. Technically, these models are discovered by exploiting a conceptual clustering method, embedded in an iterative optimization scheme where the current version of $M_0$ is replaced with the model extracted from the newly found normality cluster, in case the latter is more accurate than $M_0$; on the other hand, the clustering procedure is devised to greedily find groups of traces that maximally deviate from $M_0$. Tests on real-life logs confirmed the validity of this approach, and its capability to find good performance models, and to support the analysis of deviant process instances.

Fuzzy Cognitive Maps (FCMs) have become a suitable and proven knowledge-based methodology for systems modeling and simulation. This technique is especially attractive when modeling systems characterized by ambiguity, and/or non-trivial causalities among its variables. The rich literature that is found related to FCMs reports very clearly many successful studies solved through the use of FCMs; however, when it comes to software implementations, where domain experts can design FCM-based systems, run simulations or perform more advanced experiments, not much is found or documented. The few existing implementations are not proficient in providing options for experimentation. Therefore, we believe that a gap exists, specifically between the theoretical advances and the development of accurate, transparent and sound FCM-based systems; and we advocate for the creation of more complete and exible software products. The goal of this paper is to introduce “FCM Expert”, a software tool for fuzzy cognitive modeling, where we focus on scenario analysis and pattern classification. The main features of FCM Expert rely on Machine Learning algorithms to compute the parameters that might define a model, optimize its network topology and improve the system convergence without losing information. Also, FCM Expert allows performing WHAT-IF simulations and studying the system behavior through a friendly, intuitive and easy-to-use graphical user interface.

The θ-subsumption test is known to be a bottleneck in Inductive Logic Programming. The state-of-the-art learning systems in this field are hardly scalable. Last year, we have created a distributed θ-subsumption process based on an Actor Model, with the aim of being able to decide subsumption on very large clauses. This model was correct and complete, but was also very slow. This is why we introduce ANTS (Actor Network based Theta-Subsumption), a new model also based on an actor network, which is significantly faster than the previous one.

The human mobility is nowadays always organized in a multimodal context. However, the transport system has become more complex. Consequently, for the sake of helping passengers, building Advanced Travelers Information Systems (ATIS) has become a certain need. Since passengers tend to consider several other criteria than the travel time, an efficient routing system should incorporate a multi-objective analysis. Besides, the transport system may behave in an uncertain manner. Integrating uncertainty into routing algorithms may thus provide more robust itineraries. The main objective of this paper is to propose a Memetic Algorithm (MA) in which a Genetic Algorithm (GA) is combined with a Hill Climbing (HC) local search procedure in order to solve the multicriteria shortest path problem in stochastic multimodal networks. As transport modes, railway, bus, tram and metro are considered. As optimization criteria, stochastic travel time, travel cost, number of transfers and walking time are taken into account. Experimental results have been assessed by solving real life itinerary problems defined on the transport network of the city of Paris and its suburbs. Results indicate that unlike classical deterministic algorithms and pure GA and HC, the proposed MA is efficient enough to be integrated within real world journey-planning systems.

Principal Component Analysis (PCA) is a classical dimensionality reduction technique that computes a low rank representation of the data. Recent studies have shown how to compute this low rank representation from most of the data, excluding a small amount of outlier data. We show how to convert this problem into graph search, and describe an algorithm that solves this problem optimally by applying a variant of the A* algorithm to search for the outliers. The results obtained by our algorithm are optimal in terms of accuracy, and are shown to be more accurate than results obtained by the current state-of-the- art algorithms which are shown not to be optimal. This comes at the cost of running time, which is typically slower than the current state of the art. We also describe a related variant of the A* algorithm that runs much faster than the optimal variant and produces a solution that is guaranteed to be near the optimal. This variant is shown experimentally to be more accurate than the current state-of-the-art and has a comparable running time.

Feature selection is a common dimensionality reduction technique of fundamental importance in big data. A common approach for reducing the running time of feature selection is to perform it in two stages. In the first stage a fast and simple filter is applied to select good candidates. The number of candidates is further reduced in the second stage by an accurate algorithm that may run significantly slower. There are two main variants of feature selection: unsupervised and supervised. In the supervised variant features are selected for predicting labels, while the unsupervised variant does not use labels at all. We describe a general framework that can use an arbitrary off-the-shelf unsupervised algorithm for the second stage. The algorithm is applied to the selection obtained in the first stage weighted appropriately. Our main technical result is a method for calculating weights for the columns that need to be selected in the second stage. We show that these weights can be computed as the solution to a constrained quadratic optimization problem. The solution is deterministic, and improves on previously published studies that use probabilistic ideas to compute similar weights. To the best of our knowledge our approach is the first technique for converting a supervised feature selection problem into an unsupervised problem. Complexity analysis shows that the proposed technique is very fast, can be implemented in a single pass over the data, and can take advantage of data sparsity. Experimental results show that the accuracy of the proposed method is comparable to that of much slower techniques.

Cooperative games-based robot cooperation is analysed for reoccurring scenarios. It is shown that potential games can be used for robot coordination when the robots have a shared objective. By observing each others’ behaviour in similar scenarios, they estimate each other’s expected actions, which they use for their own choice of action. The resulting learning scheme can enable “tuning” of smooth cooperation by task allocation in teams of robots for various goals and in reoccurring scenarios of their environment. The theoretical results and methods are illustrated in simulation.