ABSTRACT. Many approaches exploiting Generalized Hypertree Decomposition are proposed in the literature for solving extensional Constraint Satisfaction Problems on finite domains. The most recent one, called FC-GHD, combines both the merits of an enumerative search algorithm which is memory efficient with those of the Hypertree Decomposition which is time efficient. Although FC-GHD is proved to be efficient, some large instances, however, remain unresolved because of the memory fault problem. This present article proposes to enhance the FC-GHD method with the notion of compressed table constraints to deal with memory explosion problems. This leads to a new compressed enumerative algorithm called CFC-GHD powerful when processing generalized hypertree decompositions. This paper describes this algorithm and presents the results obtained with this new approach. The experiments which were carried out validate the method from a practical viewpoint.

ABSTRACT. 'Simplifying' problems, by removing values or combinations of values, has been a primary approach to combinatorial complexity in constraint satisfaction problems. This paper provides a unifying framework for much of this previous work, and in the process presents new opportunities. It extends a framework for CSP properties provided by Bordeaux, Cadoli, and Mancini. New forms of substitutability and subproblem extraction are introduced. An algorithm for one form of substitutability, neighbourhood replaceability (called "removeability" by Bordeaux et al.), is presented along with preliminary experimental results.

ABSTRACT. This paper reports extensions and further analysis of a new form of singleton arc consistency, called neighbourhood SAC (NSAC), where a subproblem adjacent to the variable with a reduced domain (the "focal variable") is made arc consistent.

The first part of the paper presents two important extensions: (1) NSAC is generalized to k-NSAC, where k is the longest path between the focal variable and any variable in the subgraph. In this framework, the original NSAC becomes 1-NSAC; but in addition, we can have 2-NSAC, 3-NSAC, etc. up to a point where there is no difference from full SAC. In this work we will only consider the just-named forms. Obviously, there is an associated dominance hierarchy with respect to level of consistency, with k-NSAC < (k+1)-NSAC until full SAC is reached. (2) NSAC can be extended in a relatively straightforward way to handle n-ary constraints, although there are some subtleties, which are discussed.

The second part presents some studies of hybrid search techniques based on NSAC and SAC, using a variety of problems. Comparisons are made using the domain/degree and the domain/weighted degree variable ordering heuristics. In some cases, higher levels of consistency maintenance outperform MAC by several orders of magnitude, although with weighted degree the best tradeoff is obtained when SAC-based consistency is restricted to preprocessing.

ABSTRACT. Monte-Carlo Tree Search (MCTS) is a heuristic to search in large trees. We apply it to argumentation with regard to concept learning where MCTS pursues the best argumentation meant to account for a possibly inconsistent set of training examples. We provide experimental results of our approach with the search variant Upper Confidence Bounds on Tree (UCT)

ABSTRACT. In the last decade, thanks to the ability of analyzing probabilistic models given specifications in temporal logics, Probabilistic Model Checking (PMC) has become a widely used methodology in several application domains, e.g., communication protocols, planning and scheduling, and robotics. Moreover, the availability of effective PMC tools enables automated analysis in such complex real-world scenarios.

In this paper we evaluate PMC tools to investigate safety of robots whose control policies are learned by reinforcement, i.e., considering feedback signals received upon acting in unknown environments. Introduced in previous contributions of ours, a new challenging application domain for PMC tools is represented by their usage 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 and assess their potential on various case studies, including both real and simulated robots accomplishing navigation, manipulation and reaching tasks.

ABSTRACT. Many real network, e.g. internet or communication systems, can be modeled as scale-free network. An important property of these type of networks is that the diffusion of information to all nodes is very fast. Therefore, immunization strategies are necessary for this type of networks to prevent that a virus can infect, starting from some nodes, the entire network. In recent years, various immunization strategies has been developed and they can be divided into two main class: centralized and distributed strategies. Both of these approaches have a limitation of having the need to know the number of nodes of the network that must be immunized. In this paper, we propose an AOC based immunization strategy modification in which the entities self regulate their population inside the network. In this strategy the entities are deployed in a network with a threshold of coverage of the graph to be achieved. The entities, while collectively search the nodes with the highest degree, estimate the coverage of the graph through the information in their local environment and reproduce accordingly. The self regulating mechanism is evaluated on a set of public benchmark networks, even with community-based structures, and experimental results about convergence, coverage efficiency, computational cost and scalability are presented.

ABSTRACT. The orthogonal cutting-stock problem tries to place a given set of items in a minimum number of identically-sized bins. As part of solving this problem with guillotine constraint, we propose to combine the new BLF2G, Bottom Left Fill 2 direction Guillotine, placement heuristic with an advanced genetic algorithm. According to the items order, the BLF2G routine makes a direct placement of items on bins to give a cutting format. The genetic algorithm exploits the search space to find the supposed optimal items order. Other methods tires to guide the evolutionary process by introducing a greedy heuristics to the initial population to enhance the results. We propose to enrich the population by qualified individuals, without disturbing the genetic phase, by introducing a new enhancement to guide the evolutionary process. We control the evolution and when we observe that there are no improvements, after some iterations, we inject a qualified individual to the population to avoid premature convergence to a local optimum. We generate a set of order-based individuals, to enrich the evolutionary process. Our method is compared with other heuristics and metaheuristics found in literature on existing data sets.