The high computational cost of abduction has limited the application of this powerful and expressive formalism to practical cases. SCIFF is an abductive proof procedure used for verifying the compliance of agent behaviour to interaction protocols in multi-agent systems; SCIFF has been integrated in SOCS-SI, a system able to observe the agent interaction, pass it to SCIFF for the reasoning process and to display in a GUI the results of the SCIFF computation. In order to assess the applicability of SCIFF and SOCS-SI to practical cases, we have evaluated qualitatively and experimentally (not yet formally) their computational behaviour, as far as limitations and scalability. In this paper we show the results of the analysis.

Keywords: Abduction, Proof Procedure, Experimentation, Agent Interaction Verification

We present a system designed to evaluate and certify Quantified Boolean Formulas (QBFs) by employing a hybrid approach to the problem. Issues in integrating different philosophies and the usage of meta-heuristics to compose the whole framework are addressed.

Keywords: Propositional Reasoning, QBF, Hybrid algorithms, Symbolic reasoning.

Multi-Processor Systems-on-Chips (MPSoCs) are becoming increasingly complex, and mapping and scheduling of multi-task applications on computational units is key to meeting performance constraints and power budgets. Abstract models of system components and deployment of advanced algorithmic techniques for the optimization problem can provide for fast design space exploration and for optimal solutions. We exploit Constraint Programming (CP) from Artificial Intelligence and Integer Programming from Operations Research (OR) as a means to capture different aspects of the same problem (optimality and feasibility), and prove the effectiveness of this hybrid approach. Moreover, we exploit an accurate MPSoC virtual platform for capturing mismatches between problem formulation and real-life systems, and for assessing their impact on expected performance. We introduce the notion of execution constraints in the model of the problem, thus making the solution expressible and implementable in the real world. The model without execution constraints is a relaxation of the real problem and therefore provides a super- optimal solution. We compare the effectiveness of this latter solution with the one provided by the simulator, and try to refine our models as well as our optimization techniques accordingly.

Keywords: Mapping, Scheduling, Constraint Programming, Benders Decomposition

The constraint NValue counts the number of different values assigned to a vector of variables. Propagating generalized arc consistency on this constraint is NP-hard. We show that computing even the lower bound on the number of values is NP-hard. We therefore study different approximation heuristics for this problem. We introduce three new methods for computing a lower bound on the number of values. The first two are based on the maximum independent set problem and are incomparable to a previous approach based on intervals. The last method is a linear relaxation of the problem. This gives a tighter lower bound than all other methods, but at a greater asymptotic cost.

Keywords: Constraint satisfaction, constraint programming, global constraints.

The question underlying this paper is the following: How to represent agent reasoning that takes into account possible perception failure? We try to give an answer to the above question, by studying this problem in the basic framework of the Extended Logic Programming. The paper thus presents a new semantics, extending the well known Answer Sets Semantics, for dealing with some meaningful aspects relating to the agent perception.

Keywords: answer set programming, stable models, knowledge representation, perception.

In this paper we investigate the use of SAT technology for solving constraint problems. In particular, we solve many instances of several common benchmark problems for CP with different SAT solvers, by exploiting the declarative modelling language NPSPEC, and SPEC2SAT, an application that allows to compile NPSPEC specifications into SAT instances. Furthermore, we start investigating whether some reformulation techniques already used in CP are effective even when using SAT as solving engine. We present preliminary but encouraging experimental results in this direction, showing that this approach can be appealing.

In this paper we propose a static analysis methodology for Answer Set Programming, which ia a new logic programming paradigm based on Gelfond-Lifschitz's answer set semantics (originally defined as `stable model semantics'). The method is based on: identifying the cycles contained in the program, showing that stable models of the overall program are composed of stable models of suitable subprograms, corresponding to the cycles; defining the Cycle Graph, where each vertex corresponds to one cycle, and each edge corresponds to one handle, which is a literal containing an atom that, occurring in both cycles, actually determines a connection between them. Several properties of a program, including consistency, can be checked on its Cycle Graph.

Keywords: Answer Set Programming, Graph Representations

This paper reports about the 2004 comparative evaluation of solvers for quantified Boolean formulas (QBFs), the second in a series of non-competitive events established with the aim of assessing the advancements in the field of QBF reasoning and related research. We evaluated sixteen solvers on a test set of about one thousand benchmarks selected from instances submitted to the evaluation and from those available at www.qbflib.org. In the paper we present the evaluation infrastructure, from the criteria used to select the benchmarks to the hardware set up, and we show different views about the results obtained, highlighting the strength of different solvers and the relative hardness of the benchmarks included in the test set.

The Traveling Tournament Problem (TTP) is a combinatorial problem that combines features both from the traveling salesman problem and from tournament scheduling. We propose a tabu search approach to the solution of TTP that makes use of a combination of two neighborhood relations. The algorithm has been experimentally analyzed on several sets of publicly available benchmarks and we show a comparison with previous approaches presented in the literature.

Keywords: Metaeuristiche, analisi sperimentale di algoritmi, esperienze applicative

CLP(FD) and normal logic programs in the context of Answer Set Programming are perhaps the two main declarative approaches to modeling and solving NP-complete problems. In this paper, we compare the encoding style and computational results for the two paradigms, studying some NP-complete problems.

Keywords: CLP(FD), ASP, NP-completeness

We define a new heuristic h_DS for ASP, and implement it in the (disjunctive) ASP system DLV. The new heuristic improves the evaluation of Σ^P₂/Π^P₂-hard ASP programs while maintaining the benign behaviour of the well-assessed heuristic of DLV on NP problems. We experiment with the new heuristic on QBFs. h_DS significantly outperforms the heuristic of DLV on hard 2QBF problems. We also compare the DLV system (with h_DS) to three prominent QBF solvers. The results of the comparison, performed on instances used in the last QBF competition, indicate that ASP systems can be faster than QBF systems on Σ^P₂/Π^P₂-hard problems.

Keywords: ASP, Heuristics, QBF

In this paper we describe a system for representing and running benchmarks. The tool was started for benchmarking AI systems, but is actually usable for arbitrary command-line systems. It is fully implemented and available on the web.

Keywords: Benchmarking Tool, Command-line Systems

LPG is a planner that performed very well at the last two International planning competitions (2002 and 2004). The system is based on a stochastic local search procedure incorporating several heuristic features. In this paper, we experimentally analyze the most important of them with the goal of understanding and evaluating their impact on the performance of the planner. In particular, we examine (i) three heuristic functions for evaluating the search neighborhood, (ii) some settings of the ``noise'' parameter, that randomizes the search for escaping from local minima, and (iii) some additional heuristic techniques for restricting the search neighborhood and (iv) for selecting the next flaw to handle. The experimental analysis is based on the statistical test of Friedman, which is a suitable test for the empirical comparison of the performances of different algorithms.

Keywords: Automated planning, Local-search, Experimental analysis of algorithms and planning systems.

Answer Set Programming (ASP) and propositional satisfiability (SAT) are closely related. In some recent work, we have shown that, on a wide set of logic programs called ``tight'', the main search procedures used by ASP and SAT systems are equivalent, i.e., that they explore search trees with the same branching nodes. In this paper, we focus on the experimental evaluation of different search strategies, heuristics and their combinations that have been shown to be effective in the SAT community, in ASP systems. Our results show that, despite the strong link between ASP and SAT, it is not always the case that search strategies, heuristics and/or their combinations that currently dominate in SAT are also bound to dominate in ASP. We provide a detailed experimental evaluation for this phenomenon and we shed light on future development of efficient Answer Set solvers.

Keywords: Answer set programming, propositional satisfiability.

The research described in this paper is aimed at understanding the structural trademarks of the causal knowledge that a scheduling tool inherits from a classical planner within a loosely-coupled integrated planning and scheduling (P&S) framework. This type of combination of planners and schedulers is such that the plans produced by the first component represent scheduling problems to be reasoned upon by the scheduler. Specifically, we analyze the quality of the plans in terms of two well-known properties of scheduling problems, namely the Restrictiveness and the Resource Strength. To this end, we describe a set of experiments carried out on a series of state-of-the-art planners aimed at assessing the bias of different planning strategies in the context of the integrated P&S framework.

Keywords: Planning, Scheduling, P&S Integration.

This paper presents some basic ideas for the creation of a benchmark generator for reactive scheduling problem instances. The main motivations behind this work grow out either from the recognized lack (hence the necessity) of benchmark sets for this specific problem as well as from the conviction that the resolution of a scheduling problem consists both in the synthesis of an initial solution (``static'' scheduling) and in the utilization of a number of methodologies dedicated to the continuous preservation of solution consistency. In fact, the occurrence of exogenous events during the execution phase in real working environments, often compromises the schedule's original qualities.

Keywords: Scheduling, Benchmark Generator

In this paper we present a comparison of two Inductive Logic Programming (ILP) systems on the Sisyphus dataset. The aim of the comparison is to to show how the systems behave on a large dataset. The considered systems are Aleph and Tilde. Both systems have an unacceptable execution time on the whole dataset, so they are run over samples extracted from the dataset.

The comparison shows that, on average, Tilde finds more accurate theories in a smaller time.

Keywords: Machine Learning, Inductive Logic Programming

Recent results in constraint satisfaction and combinatorial optimization have shown that complex networks (such as scale-free networks, characterized by a frequency node degree following a power law) can be fruitfully used to modeling problem structure. By conveying results and tools from complex networks to combinatorial optimization, it is possible to achieve a deeper understanding of algorithm behavior. Moreover, some features of the network that models an instance can guide the design of specific heuristics and enable to choose the best solver among a portfolio of algorithms. This work describes two representative cases in this interdisciplinary research field.

Keywords: Combinatorial optimization problems, constraint graph, problem structure, complex networks

Questo articolo descrive l'utilizzo di algoritmi genetici (GA) e simulated annealing (SA) nella ricerca di configurazioni ottime di reti neurali artificiali, all'interno di una specifica architettura, TSAGANN. Lo studio comparativo e` stato condotto con benchmark consolidati, ed e` descritto in dettaglio. I risultati indicano che SA sembra non essere penalizzato rispetto a GA.

Keywords: algoritmi genetici, simulated annealing, ottimizzazione, reti neurali artificiali, benchmark, PROBEN1, TSAGANN.