DEIS - Universitą di Bologna - L I A - Laboratorio d'Informatica Avanzata

LIA Technical Reports

LIA Technical Reports are intended to provide people working at LIA with a simple mean to make their research results available to the scientific community as quick as possible. Thus, the LIA Series is basically unrevised.

The LIA Technical Report Series is a subseries of the DEIS Technical Report Series. Each report is characterised by two numbers: the LIA Series number (used to index the reports) and the DEIS Technical Report number (DEIS-LIA-YY-NNN).

All remarks about this page and the content of the reports are obviously welcome.
LIA Technical Reports: How to do
Boari, M. [14]
Ciampolini, A. [9], [15], [27], [53], [62]
Chesani, F. [71], [72], [75], [76], [79], [89]
Corradi, A. [7], [8], [10], [12], [14], [28]
Denti, E. [26], [34], [35], [36],[37]
Gavanelli, M. [29], [62] , [67] 
Guerri, A. [64], [74] , [82] 
Lamma, E. [1], [4], [5], [9], [13], [15], [18], [19], [20], [21], [22], [27], [29],[44], [53], [62], [71], [72] , [75], [76]
Leonardi, L. [7], [8], [10], [12], [14]
Mello, P. [1], [4], [5], [9], [13], [15], [18], [19], [20], [21], [22], [27], [29], [53], [62], [71], [72], [75], [76], [79], [89]
Milano, M. [1], [4], [5], [13], [18] , [19], [20], [21], [22], [29] , [30], [31], [32], [50], [60], [64], [74], [77], [82], [101]
Montali, M. [76], [79], [89]
Monti, G. [97]
Moro, G. [70], [73]
Natali, A. [26],[34], [40], [41]
Omicini, A. [2], [3], [16], [26], [34], [35], [36],[37]
Riguzzi, F. [17], [23], [33], [44]
Roli, A. [31], [50], [51], [59], [60], [66], [69], [84], [93], [94], [95]
Stefanelli, C. [14], [15], [27], [28]
Torroni, P. [52], [53], [54], [55], [57], [58], [61], [62], [67], [68], [71], [72], [75], [76], [89], [99]
Viroli, M. [39],[40], [41]
Zambonelli, F. [7], [8], [10], [11], [12], [24], [25]

[1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [44] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [64] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [84] [84] [93] [94] [95]

E. Lamma, P. Mello, M. Milano

A Meta Constraint Logic Programming Architecture for Qualitative and Quantitative Temporal Reasoning

Abstract. In this paper we present a two module CLP architecture (object- and meta-level modules) for reasoning with both qualitative and quantitative temporal constraints. The object level module is a finite domain constraint solver while the meta-level system is an extension of CLP for dealing with qualitative temporal information. For each module we define, from a theoretical and practical point of view, the operational semantics and the constraint domain. Moreover, we define the interactions between the two levels in terms of linking rules.
The paper shows how Constraint Logic Programming (CLP) can be used as an effective tool for representing and reasoning about time by specializing the CLP general scheme for the quantitative and qualitative temporal domains.
The advantages of using a meta architecture mainly concerns modularity, flexibility and expandibility of the architecture. The expressive power of CLP is also increased. CLP uses constraints for guiding the computation but it is not able to reason and to infer information about constraints. On the other hand, our meta architecture performs computation on constraints and infers information about them.
Finally, the paper describes an implementation of the system.

A. Omicini

Constraining Objects as Logic Theories

Abstract. The aim of this work is to present a computational model based on logic programming where constrained computations can be performed over application domains described through an object-oriented data model. This model is essentially based on two kind of constraints: provability constraints and hierarchical constraints.
Provability constraints concern the truth value of a formula with respect to a given logic theory, which is bounded to satisfy the formula. Message passing is then re-interpreted in a declarative way as a relation constraining specific object properties.
Hierarchical constraints make it possible to define an object taxonomy in terms of a hierarchy of theories. Relationships such as class/instance and class/superclass can then be uniformly handled as constraints, which can be either statically defined in the text of a program, or dynamically inferred during a computation. This suggests a new notion of logic program, which is no longer statically defined once for all, but may instead grow dynamically in a declarative way, as a result of a constrained computation.
Examples of constrained object-oriented computations are presented by using two simple multi-theory logic languages. Their operational semantics is finally given in form of a transition system, by extending the typical CLP semantics characterisation.

Keywords: Constraints, Object-Oriented Programming, Multi-Theory Logic Languages.

A. Omicini

Abduction and Object State Configuration

Work under revision

Abstract. ...

Keywords: ...

E. Lamma, P. Mello, M. Milano

A Multi-Level CLP Architecture for Consistency Techniques

Abstract. In this paper, we define a multi-level Constraint Logic Programming architecture which is able to reach different levels of consistency in a modular and incremental way. Each level of the architecture is a finite domain constraint solver that achieves an i-consistency and reasons on constraints of the underlying level. In general, a special purpose algorithm should be implemented by scratch each time a higher consistency level is needed. Instead, thanks to our meta architecture we can increase the degree of consistency simply by adding further (meta) levels. In this way, the consistency algorithm can be implemented in a declarative and incremental way.

E. Lamma, P. Mello, M. Milano

A Meta Constraint Logic Programming Scheme

Abstract. We present a Meta Constraint Logic Programming (MCLP) general scheme. The idea behind the work concerns the possibility of building meta CLP architectures by adding CLP solvers as meta level reasoners on the constraints of the underlying object systems. In this way, we are able not only to increase the expressive power of CLP, but also to implement several constraint satisfaction techniques like arc, path and in general, k-consistency by using lower degrees of consistency algorithms in order to obtain higher degrees of consistency.
The purpose of the work is to provide a general scheme which can be specialized in those domains and applications where the expressive power of CLP does not suffice. A distinguishing feature of the architectural scheme concerns its operational semantics and, in particular, the linking rules between different levels.
In this paper, we propose, as an example, two different specializations of a Meta CLP on finite domains (FD) architecture: the first concerns the possibility of embedding the capability of performing qualitative reasoning in a CLP framework, while the second concerns a multi-level architecture for obtaining different degrees of consistency by using weaker algorithms.

M.P. Schumann

Impact of Object Orientation in Compiler Building - A Grammar Related Extensible Class Library

Laurea Thesis

Abstract. ...

A. Corradi, L. Leonardi, F. Zambonelli

Experiences toward an Object-Oriented Approach to Structured Parallel Programming

Abstract. In parallel programming, communication patterns are rarely arbitrary and unstructured. Instead, parallel applications tend to employ predetermined patterns of communication between their components. If the most commonly used patterns - such as pipelines, farms and trees - are identified (both in terms of their components and their communication), an environment can make them available as high-level abstractions for use in writing applications. This can yield a structured approach to parallel programming. The paper shows how this structured approach can be accommodated within an object-oriented language. A class library provides the most commonly used patterns and programmers can exploit inheritance to define new patterns. Several examples illustrate the approach and show that it can be efficiently implemented.

A. Corradi, L. Leonardi, F. Zambonelli

Diffusive Algorithms for Dynamic Load Balancing in Massively Parallel Architectures

Abstract. The paper investigates the area of dynamic load balancing with the specific target of massively parallel architectures. The lack of centralisation makes the architectures cost effective and scalable but require suitable simple system policies without centralisation and with decisions based on a limited amount of information. The paper analyses the class of load balancing policies inspired to diffusion and shows how they can lead a system to a system balanced configuration. The paper evaluates and compares the effectiveness of several diffusion-based policies depending both on the external environment (i.e., the properties of the system load) and on the internal parameters. All presented policies show a robust and scalable behaviour: they are able to reach a good load balancing quality with promptness, low intrusion and with little dependence on the system size. Moreover, the paper shows that the enlargement of the scope of a diffusive policy can be effective only in case of slow load dynamicity. In any other case, policies with a limited scope are to be preferred.

A. Ciampolini, E. Lamma, P. Mello, V. Pagone

An Abstract Interpreter for Improving the Efficiency of Dynamic Modular Logic Languages

Abstract. In this work, we focus on modular logic languages where module composition is performed through union of clauses and where the set of definitions to be used in order to evaluate a goal can be extended during the computation through implication goals. In order to improve the implementation of these languages, we consider the application of static analysis techniques. In particular, we apply abstract interpretation in order to compute the minimal sets of modules (minimal contexts) which are needed for any successful computation for a given predicate. The results of the analysis are exploited by the underlying implementation in order to reduce the overhead due to failing, useless computations. The abstract interpreter has been implemented in Prolog, through meta-interpretation techniques.

A. Corradi, L. Leonardi, F. Zambonelli

High-Level Management of Allocation in a Parallel Objects Environment

Abstract. Widespread diffusion of parallel architectures is currently limited by the lack of tools that allow to efficiently exploit the available resources with few programming efforts, in particular with regard to the allocation problem. The paper presents a configuration language (ACL) implemented within an object-oriented parallel programming environment. By the means of ACL, the user can specify its applications allocation needs without being aware of the architectural details. The main point is that ACL directives guide the run-time support, by adapting its general-purpose behaviour to follows applications peculiar allocation needs. The ACL approach is validated by testbed applications.

Keywords: Parallelism, Object-Orientation, Programming Tools, Load Balancing.

C. McHale, F. Zambonelli

How to Control the Allocation of Parallel Applications: a Survey on Tools and Language Constructs

Abstract. The paper focuses on the allocation area, with the aim of providing a survey on systems that provides facilities to codify the behaviour of an application with regard to its allocation onto a target architecture. The paper analyses the design issues that arise in the definition of these facilities and presents the solutions adopted in several systems and programming environments. Open issues and future directions of research are outlined.

Keywords: Allocation, Dynamicity, Tools, Language Constructs.

A. Corradi, L. Leonardi, F. Zambonelli

Distributed Tuple Spaces in Highly Parallel Systems

Abstract. The tuple space abstraction is widely recognized as a powerful and general coordination model for parallel programming. However, it is based on the abstraction of a global space and therefore difficult to be efficiently implemented in highly parallel architectures. The paper discusses the implementation issues of the tuple space abstraction on large parallel systems and proposes a new implementation model suitable for massively parallel systems: the model achieves scalability by organizing the system in a hierarchical way and by encouraging the presence of multiple tuple spaces with a constrained scope. The paper describes and analyses the model for a transputer-based implementation: the hierarchical organization makes the access time to tuples proportional to the locality of the references and, in most cases, bounded by the logarithm of the system size.

E. Lamma, P. Mello, M. Milano

Reasoning on Constraint in Constraint Logic Programming

Abstract. Constraint Logic Programming solvers on finite domains use constraints to prune those combinations of assignments which cannot appear in any consistent solution. There are applications, such as temporal reasoning or scheduling, requiring some form of qualitative reasoning where constraints can be changed (restricted) during the computation or even chosen when disjunction occurs. We embed in a CLP(FD) solver the concept of constraints as first class objects. In the extended language, variables range on finite domains of integers and {\em relation variables} range on finite domains of relation symbols. We define operations and constraints on the two sorts and one constraint linking the two. Programming examples are given, showing the advantages and the expressive power of the extension proposed.

M. Boari, A. Corradi, L. Leonardi, C. Stefanelli

A Routing Strategy for Object-Oriented Applications in Massively Parallel Architectures

Abstract. This paper describes an adaptive routing algorithm, called Virtual Path, designed to provide efficient communications for object-oriented applications running on massively parallel architectures. The main property of the algorithm is to route messages without any knowledge of the allocation of communicating entities (the objects) to the processors.
Allocation transparency becomes a basic requirement when dealing with dynamic object-oriented applications where the decision of whether to create/destroy objects is taken at run-time and, in addition, objects can migrate from one node to another to achieve load balance. The presented routing algorithm is topology independent and can be employed with any topology of interconnection.
The Virtual Path routing algorithm alternates two different phases. In the first phase, the algorithm is completely adaptive and chooses one path to connect the nodes where the communicating objects reside. In the second phase, the algorithm uses the found path to route all messages exchanged by the same couple of objects. To obtain adaptivity, the routing system updates a virtual path whenever the situation changes significantly: for instance, in case of object migration.

Keywords: Massively Parallel Systems, Parallel Objects, Dynamicity, Routing.

A. Ciampolini, E. Lamma, P. Mello, C. Stefanelli

Improving Distributed Unification through Abstract Interpretation

Abstract. In this paper we apply static analysis techniques for improving the distributed implementation of logic programming languages, especially with regard to unification. In a distributed implementation, unification involves sending and receiving messages containing information about the goal arguments. Each message can contain either the entire copy of goal arguments or only a part of it. The aim of the analysis is to determine the optimal level of copying to be adopted for each goal argument of a given program. This level of copying is the minimal one which avoids the need for any remote dereferencing during the computation. In this respect, the analysis done is related to the strictness analysis for functional languages which helps in deciding whether a function argument can be evaluated directly, instead of evaluating it only when needed.
The analysis is grounded on abstract interpretation, and size relation analysis in particular. The optimal level of copying for each predicate argument is determined starting from the mode of the predicate, and by determining relations among the size and use of each term. The results of the analysis are exploited by a distributed implementation scheme, based on an abstract machine where the level of copying for each goal argument can be tuned at compile-time, thus reducing the overhead due to message exchange for remote dereferencing.

A. Omicini

A General Framework for Multi-Theory Logic Languages

Abstract. Multi-theory logic languages are a wide class of programming languages which extend the standard logic programming paradigm by partitioning the logic program into a multiplicity of logic theories. Such an extension is generally meant to address typical software engineering issues, such as modularity, component reuse, incremental software design and development. Despite of the many syntactic and semantic differences, what multi-theory logic languages share is the partitioning of the program according to the abstractions of the domain of discourse, by associating different collections of axioms to different domain elements. The aim of this work is then to introduce a general framework for multi-theory logic languages, providing a uniform approach for their definition and description. An extended notion of logic formula is introduced, which makes the relationship between formulae and domain abstractions explicit. A class of extended logic languages is consequently defined, which is general enough that any multi-theory logic language can be mapped onto it through suitable translation functions. Such languages, called scope languages, can then be used as a mean to express the semantics of any multi-theory logic language, and as a tool for the comparison of different languages of that kind.

Keywords: Multi-Theory Logic Languages, Object-Oriented Logic Programming, Modules.

F. Riguzzi

A Survey of Software Metrics



S.Buzzi, E. Lamma, P. Mello, M. Milano

Consistent Orderings for Constraint Satisfaction Scheduling

Abstract. The job shop scheduling problem has been formulated in Constraint Logic Programming as one of finding a consistent assignment of start times for each operation of each job. Nonetheless, in some proposals within the Artificial Intelligence area, the problem has been alternatively formulated as one of establishing sequencing constraints between pairs of operations contending for the same resource over time. In this work, we follow this latter approach within a Constraint Logic Programming (CLP) framework. CLP solvers on finite domains use constraints to prune those combinations of assignments which cannot appear in any consistent solution. Scheduling problems require some form of qualitative reasoning where constraints can be changed (restricted) during the computation or even chosen when disjunction occurs. We embed in a CLP(FD) solver the concept of constraints as first class objects to represent ordering relations between pairs of tasks and apply the resulting language to scheduling problems.

Keywords: Scheduling, Constraint Logic Programming

E. Lamma, P. Mello, M. Milano

An Incremental Consistency Algorithm for Adaptive Consistency

Abstract. Constraint Satisfaction Problems (CSPs) play a central role in many Artificial Intelligence fields. Many different approaches have been proposed for solving CSPs ranging from pure backtracking to sophisticated methodologies. However, many efforts have concentrated on the use of a single algorithm for solving all problems. Recent results have shown that a single algorithm is not always the best choice for all classes of problems. Thus, adaptive consistency suggests to dynamically switch the consistency algorithm during the computation. In this paper, we propose an incremental and modular algorithm for achieving any degree of consistency by combining different, weaker consistency algorithms. In this way, for reaching higher levels of consistency we do not have to switch the algorithm, but we have to add as many uniform levels as we need, depending on the algorithm performed at each level.

Keywords: Adaptive Constraint Satisfaction

A. Caprara, F. Focacci, E. Lamma, P. Mello, M. Milano, P. Toth, D. Vigo

Integrating Constraint Logic Programming and Operations Research Techniques for the Crew Rostering Problem

Abstract. In this paper, we investigate the possibility of integrating Artificial Intelligence (AI) and Operations Research (OR) techniques for solving the Crew Rostering Problem (CRP). CRP calls for the optimal sequencing of a given set of duties into rosters satisfying a set of constraints. The optimality criterion requires the minimization of the number of crews needed to cover the duties. This kind of problem has been traditionally solved with OR techniques. In recent years, a new programming paradigm based on Logic Programming, named Constraint Logic Programming (CLP), has been successfully used for solving hard combinatorial optimization problems. CLP maintains all the advantages of Logic Programming such as declarativeness, non-determinism and an incremental style of programming, while overcoming its limitations, mainly due to the inefficiency in exploring the search space. CLP achieves good results on hard combinatorial optimization problems which, however, are not comparable with those achieved by OR approaches. Therefore, we integrate both techniques in order to design an effective heuristic algorithm for CRP which fully exploits the advantages of the two methodologies: on the one hand, we maintain the declarativeness of CLP, its ease of representing knowledge and its rapid prototyping; on the other hand, we inherit from OR some efficient procedures based on a mathematical approach to the problem. Finally, we compare the results we achieved by means of the integration with those obtained by a pure OR approach, showing that AI and OR techniques for hard combinatorial optimization problems can be effectively integrated.

Keywords: Constraint Logic Programming, Operations Research, Crew Rostering Problem, Combinatorial Optimization Problems.

R.Cucchiara, E. Lamma, P. Mello, M. Milano

An Interactive Constraint-Based System for Selective Attention in Visual Search

Abstract. We face in this paper the problem of model-based object recognition in a scene. Computer vision techniques usually separate the extraction of visual information from the scene from the reasoning on the symbolic data. We propose to interactively intertwine the two parts: the reasoning task on visual information is based on constraint satisfaction techniques. Objects are modeled by means of constraints and constraint propagation recognizes an object in the scene. We extend the classical Constraint Satisfaction Problem (CSP) approach which is not suitable for coping with undefined information. We thus propose an Interactive CSP model for reasoning on partially defined data, generating new constraints which can be used to guide the search and to incrementally process newly acquired knowledge.

Keywords: Machine Vision, Constraint Satisfaction.

R. Cucchiara, E. Lamma, P. Mello, M. Milano

Interactive Constraint Satisfaction

Abstract. We present an Interactive Constraint Satisfaction model for problems where knowledge is not completely defined at the beginning of the computation, but can be interactively acquired during the computational process. In this case, domains can be partially defined when the constraint satisfaction process starts. Thus, domains are dynamically defined in contrast with classical CSPs where domains are statically defined at the beginning of the constraint satisfaction process. The interactive CSP model copes with incomplete domain definition by propagating constraints on already defined domain values and by adding new constraints on undefined parts of domains. These new constraints can be used to incrementally process new information without restarting a constraint propagation process from scratch each time new information is available. In addition, these constraints can be eventually used in order to guide the knowledge acquisition process. Examples are given in order to show the effectiveness of the approach. In particular, a case study in the field of visual object recognition is considered.

Keywords: Constraint Satisfaction, Vision

F. Gramantieri, E. Lamma, P. Mello, F. Riguzzi

A System for Measuring Function Points from Specifications

Abstract. We propose a knowledge based approach for the automated measurement of the Function Point metric starting from the specifications of a software system expressed in the form of an Entity Relationship (ER) diagram plus a Data Flow Diagram (DFD). We consider an integration of the two diagrams, which we call ER-DFD, in which the data stores of DFD are substituted by the entities and relationships of the ER. We have specialized the general rules for counting Function Points for the case of a specification in the form of an ER-DFD model. The informal counting rule expressed in natural language have been translated into formal rules that express properties of the ER-DFD graph. A knowledge based system has been implemented in Prolog that automatically counts Function Point by analyzing the graph.

Keywords: Software Engineering, Software Metrics, Knowledge Based Systems

F. Zambonelli

Logging Algorithms for Parallel Programs Replay

Abstract. Debugging parallel and distributed long-running programs requires incremental replay, i.e., the capability of reexecuting selected parts of an execution without replaying the entire program. To support incremental replay, processes must periodically checkpoint and the content of some message must be logged: this allows to break dependencies of the current state of the execution on past events. The paper characterizes the replay behaviour of message-passing parallel programs by introducing the replay set concept, the amount of computation required to replay a given part of an execution, and by showing how it can be detected on-line. The paper presents several logging algorithms that, either exactly or approximately, detect the replay set and dynamically decide whether to log a message or not in order to diminish its size. Both the performance of the presented algorithms and their implementation problem are analysed to shows the trade-offs between the information available to the algorithms, the amount of messages logged and the size of the replay set.

F. Zambonelli

Performance Comparison of On-line Algorithms for Consistent Checkpointing

Abstract. The paper addresses distributed computations where processes can take local checkpoints without coordinating with each other. In such a scenario, a local checkpoint is useful only if it belongs to at least one consistent global checkpoint and, then, execution can be restarted from it. The paper presents several on-line algorithms that grant the usefulness of any local checkpoint by forcing additional checkpoints in processes. The effectiveness of these algorithms is evaluated in several application examples.

E. Denti, A. Natali, A. Omicini

Expressive Power of the ACLT Reaction Specification Language

Abstract. The notion of programmable coordination medium as a shared communication device whose behaviour can be defined according to the global system needs has indeed an impact over the design of multi-component software system. In fact, it allows coordination systems to be organised around a high-level inter-component interaction protocol, while the low-level details are delegated to properly programmed communication abstractions. This leads to a shift of (part of) the computational charge of a multi-component system from the communicating components (agents) to the communication device, and raises the issue of the expressive power of a programmable coordination medium.
As an example, this paper discusses the case of ReSpecT, the first-order logic language used by the ACLT coordination model to specify and define the behaviour of its multiple programmable logic tuple spaces. Its expressiveness is compared with that of Petri Nets (and of some of the variants and extensions), taken as a reference as one of the most used formalisms for the specification and design of concurrent and distributed systems. In particular, we show that ReSpecT is Turing-powerful. This makes it possible for the designer of a multi-component architecture to freely split the system's computational load between the communicating components and the communication device, so that local and global properties of a coordination system can be respectively embodied into the coordination entities (ACLT agents) and the coordination media (ACLT programmable logic tuple spaces) in the most natural way.

Keywords: Multi-agent systems, Coordination, Tuple Spaces, Petri Nets, Programmable Coordination Media, Turing equivalence

A. Ciampolini, E. Lamma, P. Mello, C. Stefanelli

Abductive Logic Agents

Abstract. In this work, we show how abduction can be introduced in a (logic) multi-agent environment by adopting a basic coordination protocol among agents. In particular, we define and implement a distributed protocol to coordinate the reasoning of all the abductive agents in the system, inspired to the basic algorithm for abductive reasoning presented by Kakas and Mancarella. In the implementation we use a parallel logic language with multi-head guarded clauses and committed-choice behavior.

A. Corradi, M. Cremonini, C. Stefanelli

Melding Abstractions with Mobile Agents

Abstract. Mobile Agents (MA) seems to be the most suitable technology for distributed systems to integrate the Internet in a synergic way. One of the problems that should be faced when considering MA models for distributed applications is the lack of a thorough model capable of describing the Internet world composed of interconnected networks, each of them with its peculiar policies (for administrative, management and security purposes). We propose a Mobile Agent system based on a model designed to consider and favour aggregations of abstract and protected (network) domains: the use of this model makes easy the development of Internet applications. The paper describes the MAMA system (Melding Abstractions and Mobile Agents) and its implementation in the Java language. An application for distributed monitoring provides the results achieved within the MAMA system.

DEIS-LIA-98-001 (pdf)
R. Cucchiara, M. Gavanelli, E. Lamma, P. Mello, M. Milano, M. Piccardi

Extending CLP(FD) with Interactive Data Acquisition for 3D Visual Object Recognition

Abstract. This paper addresses the 3D object recognition problem modelled as a Constraint Satisfaction Problem. In this setting, each object view can be modelled as a constraint graph where nodes are object parts and constraints are topological and geometrical relationships among them. By modelling the problem as a CSP, we can recognize an object when all constraints are satisfied by exploiting results from the CSP field. However, in classical CSPs variable domains have to be statically defined at the beginning of the constraint propagation process. Thus, not only feature acquisition should be completed before the constraint solving process starts, but all image features should be extracted even if not belonging to significant image parts. In visual applications, this requirement turns out to be inefficient since visual features acquisition is a very time consuming task. We present an Interactive Constraint Satisfaction model for problems where variable domains may not be completely known at the beginning of the computation, and can be interactively acquired during the computational process only when needed (on demand). The constraint propagation process works on already known domain values and adds new constraints on unknown domain parts. These new constraints can be used to incrementally process new information without restarting the constraint propagation process from scratch each time new information is available. In addition, these constraints can guide the feature acquisition process, thus focussing attention on significant image parts. We present the Interactive CSP model and a propagation algorithm for it. We propose an implementation of the framework in Constraint Logic Programming on Finite Domains, CLP(FD).

F. Bosi, M. Milano

Enhancing CLP Branch and Bound Techniques for Scheduling Problems

Abstract. Constraint Logic Programming has been proved to be a suitable tool for solving combinatorial problems. However, it presents some limitations in dealing with optimization criteria, since the pruning of the search space on the basis of the objective function is very weak. On the other hand, Operation Research lower bounding techniques provide a powerful way of reducing the search space on the basis of objective function reasoning. They provide effective bounds for the original problem by computing the optimal solution of a relaxed problem. In this paper, we propose an integration of OR lower bounding techniques in CLP in order to achieve the benefits of both paradigms. We have implemented this technique in the CLP language CHIP and applied it, as a case study, for a Job Shop Scheduling application in the field of production planning. By integrating the OR lower bounding techniques in CLP, we are able to achieve promising results and to optimally solve problems which are one order of magnitude greater than those solved by a pure CLP approach.

M. Milano, A. Roli

Solving the Satisfiability Problem with Boolean Networks

Abstract. We present a new approach to solve the satisfiability problem (SAT), based on boolean networks. The application of a particular mapping to a SAT instance generates a boolean net with a dynamics characterized by fixed points corresponding to the solutions of the instance. The mapping presented permits to develop a new class of algorithms to solve SAT. Moreover, this new approach suggests new ways to combine symbolic and connessionistic computation.

F. Focacci, A. Lodi, M. Milano, D. Vigo

Solving TSP through the Integration of OR and CP Techniques

Abstract. Constraint Programming techniques have been successfully applied to several combinatorial optimization problems. One of their advantages is the availability of complex global constraints performing efficient propagation and interacting with each other through shared variables. However, Constraint Programming techniques have shown their limitations in dealing with objective functions, since they are usually able to prune only few levels of the search tree when most decision variables have been already instantiated. In this paper, we integrate well-known Operations Research (OR) techniques within global constraints, thus obtaining optimization oriented constraints. The idea is to prune the search space using reduction rules based on lower bound and reduced costs calculation. The interest of integrating efficient well-known OR algorithms into CP is mainly due to the CP domain reduction mechanism which can be seen as a communication channel among different constraints. We have applied this technique to symmetric and asymmetric Travelling Salesman Problem (TSP) instances both because the TSP is an interesting problem arising in many real life applications, and because pure CP techniques lead to disappointing results for this problem. We have tested the proposed optimization constraints using the ILOG Solver library. Computational results on benchmarks available from literature, and comparison with related approaches will also be described in the paper.

F. Riguzzi

Extensions of Logic Programming as Representation Languages for Machine Learning

Abstract. The representation language of Machine Learning has undergone a substantial evolution, starting from numerical descriptions to an attribute-value representations and finally to first order logic languages. In particular, Logic Programming has recently been studied as a representation language for learning in the research area of Inductive Logic Programming. The contribution of this thesis is twofold. First, we identify two problems of existing Inductive Logic Programming techniques: their limited ability to learn from an incomplete background knowledge and the use of a two-valued logic that does not allow to consider some pieces of information as unknown. Second, we overcome these limits by prosecuting the general trend in Machine Learning of increasing the expressiveness of the representation language. Two learning systems have been developed that represent knowledge using two extensions of Logic Programming, namely abductive logic programs and extended logic programs. Abductive logic programs allow abductive reasoning to be performed on the knowledge. When dealing with an incomplete knowledge, abductive reasoning can be used to explain an observation or a goal by making some assumptions about incompletely specified predicates. The adoption of abductive logic programs as a representation language for learning allows to learn from an incomplete background knowledge: abductive reasoning is used during learning for completing the available knowledge. The system ACL (Abductive Concept Learning) for learning abductive logic programs has been implemented and tested on a number of datasets. The experiments show that the performance of the system when learning from incomplete knowledge are superior or comparable to those of ICL-Sat, mFOIL and FOIL. Extended logic programs contain a second form of negation (called explicit negation) besides negation by default. They allow the adoption of a three-valued model and the representation of both the target concept and its opposite. The two-valued setting that is usually adopted in Inductive Logic Programming can be a limitation in some cases, for example in the case of a robot that autonomously explores the surrounding world and that acts on the basis of the partial knowledge it posseses. For such a robot is important to distinguish what is true from what is false and what is unknown and therefore it needs to adopt a three-valued logic. The system LIVE (Learning In a three-Valued Environment) has been implemented that is able to learn extended logic programs containing a definition for both the concept and its opposite. Moreover, the definitions learned may allow exceptions. In this case, a definition for the class of exceptions is learned and for exceptions to exceptions, if present. In this way, hierarchies of exceptions can be learned.

E. Denti,A. Natali, A. Omicini

Merging Logic Programming into Web-based Technology: a Coordination-based Approach

Abstract. Current WWW technology is becoming the de-facto standard platform for groupware applications, yet it provides virtually no effective coordination capabilities. New applications, instead, demand higher-level middleware services, with intelligent behaviours, deductive capabilities, and effective coordination. In this work we discuss a possible extension to the current Web-based architectures whose aim is to support the integration between logic-based and conventional components, and to introduce the concept of programmable communication abstraction. Within the framework of the current Java-based architecture, logic programming is used as a base for Linda-like coordination. Thus, the coordination medium may be interpreted as the theory of communication, and exploited for reasoning over communication and for introspection over the overall system state. Logic programming is also used to define reactions to communication events, which allow the communication abstraction behaviour to be extended and tailored to achieve specific coordination policies.

E. Denti,A. Omicini

From Tuple Spaces to Tuple Centres

Abstract. A tuple centre is a Linda-like tuple space whose behaviour can be programmed by means of transactional reactions to the standard communication events. This paper defines the notion of tuple centre, and shows the impact of its adoption as a coordination medium for a distributed multi-agent system on both the system design and the overall system performance.

E. Denti,A. Omicini

An Architecture for Tuple-based Coordination of Multi-Agent Systems

Abstract. Multi-agent system development calls for powerful and expressive coordination models, languages and patterns, as well as for an effective coordination technology. A good deal of the current research efforts focuses on tuple-based coordination, exploiting its well-known advantages, such as agent uncoupling and associative access to information, and addressing its limitations, such as its weakness in flexibility and control capabilities. In particular, the behaviour of a Linda-like tuple space is fixed once and for all by the coordination model, and cannot be tailored to the specific application needs. So, we first introduces the notion of tuple centre, a tuple space whose behaviour can be programmed by defining transactional reactions to the basic communication events. This allows coordination laws to be explicitly defined and embedded into the coordination media. In this paper, we present the architecture of a run-time system for tuple-based coordination where tuple centres work as an extensible kernel around which multi-agent systems can be designed and deployed. We sketch the implementation and show the advantages which can be achieved from both the design and the performance viewpoints.

E. Denti,A. Omicini

Coordination Technology for the Development of Multi-Agent Systems on the Web

Abstract. The development of multi-agent systems on the Web requires powerful and effective coordination models, languages and patterns. Even more, it calls for an effective coordination technology, not only implementing a coordination model, but also supporting its metaphors at the development system level, and enabling developers to work at any time at the abstraction level required. This paper presents the LuCe coordination system for the development of multi-agent systems on the WWW. Based on the full integration of Java and Prolog technologies, LuCe implements a coordination model based on the notion of Logic Tuple Centre, a coordination medium which is also exploited as the core of the development system. The power of the LuCe coordination technology is first discussed in general, then shown in the context of an application example, a TicTacToe game among intelligent software agents and human players on the Web.

DEIS-LIA-99-005 (postscript)
M. Viroli

Modelli per l'elaborazione distribuita: il pi-calculus e sue specializzazioni

Abstract. In questo lavoro si descriverÆ il framework semantico introdotto dai name-passing calculi e dal loro prototipo, il p-calculus di Milner, candidato a rappresentare il riferimento per la specifica dei sistemi concorrenti ed interattivi. In un panorama di linguaggi, modelli e architetture, piuttosto vasto ed eterogeneo, il p-calculus si propone come modello fondazionale della computazione concorrente al pari di quello che rappresenta il l-calculus per la computazione sequenziale classica. Partendo dalla descrizione delle caratteristiche del l-calculus, lo standard de facto nella descrizione semantica dei meccanismi della programmazione tradizionale, si giungerÆ alla descrizione della teoria del name-passing calculus suggerita da Milner, fornendo numerosi esempi della sua espressivitÆ. Si passeranno poi in rassegna i piÿý significativi sottocalcoli del p, analizzando per ognuno le problematiche che li hanno ispirati, le caratteristiche ed i campi d'utilizzo.

G. Moro, A. Natali, M. Viroli

An Interactive Computational Model for Monitoring Systems

Abstract. Monitoring systems are often realized using low level approaches that mix mechanisms and policies, causing the programmer to spend much time realizing things that could be automatically done by tools built over a higher level model. The paper presents a paradigm that views monitoring system in terms of new computational structures, the Active Expressions. With these compositional abstractions the main dimensions of monitoring system, which are computation, interaction, and time, are captured and managed in a simple yet powerful way. This model is formally specified using an abstract machine introduced in the interactive computing area, the Sequential Interaction Machine. The paper considers semantics issues about correctness and consistency and how these properties can be guaranteed in monitoring transactional-based resources like database systems.

DEIS-LIA-00-001 (postscript)
M. Viroli, A. Natali

Parametric Polymorphism in Java through the Homogeneous Translation LM: Gathering Type Descriptors at Load-Time

Abstract. The introduction of parametric polymorphism in Java with translation approaches has been shown to be of considerable interest, allowing the definition of extensions of Java on top of the existing Virtual Machines. Homogeneous translations furthermore, seem to be more useful than heterogeneous, avoiding the continuous increase of library code with redundant information. At this time however, homogeneous approaches aren't as flexible as heterogeneous, with extensions failing to integrate well with base language typing. In this paper, using some of the features of the Core Reflection of Java, we introduce a homogeneous translation in which run-time information about instantiation of type-parameters is carried, allowing full integration of parameterized types with Java typing. Performance overhead is highly decreased using a brand new translation technique based on the deferring of the management of type information at load-time. The same power and flexibility of previous heterogeneous approaches is obtained while maintaining homogeneous translation advantages.

DEIS-LIA-00-002 (postscript)
M. Viroli

On the Recursive Generation of Parametric Types

Abstract. For efficiency reasons, the typical implementations of parametric polymorphism in modern languages are built so as to prepare all the information about the instantiations of the parametric types an application use before its actual execution. In some situations however, a program may recursively refer an infinite set of such instantiations, causing the compilation failing to terminate. Most current C++ compilers and proposals for adding parametric polymorphism in Java suffer from this problem. In this paper we introduce a formal framework for reasoning about parametric types, type variables and their dependency. Using this, we analyze in a formal way this non-termination issue and give a necessary and sufficient condition for a program not to cause this inconvenience. By testing this condition future versions of all the compilers may provide for early detection of the problem.

DEIS-LIA-00-004 (postscript)
E. Lamma, F. Riguzzi, L. M. Pereira

Belief Revision via Lamarckian Evolution

Abstract. We propose a genetic algorithm to accomplish belief revision. The algorithm implements a new evolutionary strategy resulting from a combination of Darwinian and Lamarckian approaches. Besides encompassing the Darwinian operators of selection, mutation and crossover, it comprises a Lamarckian operator that mutates the genes in a chromosome that code for the believed assumptions. These self mutations are performed as a consequence of the chromosome phenotype's experience obtained while solving a belief revision problem. They are directed by a belief revision procedure which relies on tracing the logical derivations leading to inconsistency of belief, so as to remove the latter's support on the gene coded assumptions, by mutating the genes. The algorithm, with and without the Lamarckian operator, has been tested on a number of belief revision problems, and results show that the addition of the Lamarckian operator improves the efficiency of the algorithm. Additionally, the combination of Darwinian and Lamarckian operators is useful not just for standard belief revision problems, but for problems where different chromosomes may be exposed to different constraints and observations. In these cases, the Lamarckian and Darwinian operators play different r\^oles: the Lamarckian one is employed to bring a given chromosome closer to a solution (or even to find an exact one) to the current belief revision problem, whereas the Darwinian ones exert the r\^ole of randomly producing alternative chromosomes in order to deal with unencountered situations, by means of exchanging genes amongst them. We also tested this hypothesis, with positive results, for the case of a multi-agent belief revision setting.

DEIS-LIA-01-005 (zip file)
F. Focacci

Solving Combinatorial Optimization Problems in Constraint Programming - PhD Thesis


DEIS-LIA-01-006 (postscript)
A. Roli, M. Milano

Metaheuristics: A Multiagent Perspective

Abstract. In this work we introduce the multiagent metaphor as a framework for metaheuristic algorithms. The first step is the definition of agents which search on a fitness landscape. In this framework it is possible to implement the classical metaheuristic algorithms and introduce cooperative search in a well-defined way. The second step extends the model in a multi--level system, where agents at each level have different computational capabilities and tasks: solution construction, solution improvement, extracting solutions building blocks, analyzing regions of the search space and perform meta-reasoning on the behavior of lower level agents. We propose this perspective with the aim to achieve a better and clearer understanding of metaheuristics, obtain new algorithms and suggest directions for a software engineering-oriented implementation.

DEIS-LIA-01-007 (tar file)
A. Roli

Boolean Networks: An application to the Satisfiability Problem - Laurea Thesis (in Italian)

Abstract. In this work we present a new approach to solve the Satisfiability Problem (SAT), based on Boolean Networks.

DEIS-LIA-01-008 (compressed postscript)
Paolo Torroni

A study on the termination of negotiation dialogues

Abstract. Dialogue represents a powerful means to solve problems using agents that have an explicit knowledge representation, and exhibit a goal-oriented behaviour. In recent years, computational logic gave a relevant contribution to the development of Multi-Agent Systems, showing that a logic-based formalism can be effectively used to model and implement the agent knowledge, reasoning, and interactions, and can be used to generate dialogues among agents and to prove properties such as termination and success. In this paper, we discuss the meaning of termination in agent dialogue, and identify a trade-off between ensuring dialogue termination, and therefore robustness in the agent system, and achieving completeness in problem solving. Then, building on an existing negotiation framework, where dialogues are obtained as a product of the combination of the reasoning activity of two agents on a logic program, we define a syntactic transformation of existing agent programs that aims at ensuring termination in the negotiation process. We show how such transformations can make existing agent systems more robust against possible situations of non-terminating dialogues, while reducing the class of reachable solutions in a specific application domain, that of resource reallocation.

DEIS-LIA-01-009 (zipped postscript)
Anna Ciampolini, Evelina Lamma, Paola Mello, and Paolo Torroni

Coordinating the Safe Execution of Tasks in a Constrained Multi-Agent System

Abstract. In this paper, we tackle the problem of ensuring that the execution of tasks in a constrained multi-agents setting is consistent with respect to its constraints. In order to do that, we propose a formalism to express the coordination of tasks, where the tasks represent services, associated with abstract specifications that express conditions on the services, and the agents are given a denotation in terms of service provided and associated conditions. The constraints, contained in the body of the agents, may include -- but are not limited to -- policies on provided services, and limitations about the use and allocation of bounded resources. We then give the inference rules that define an operational semantics to verify that the execution of such services does not determine an inconsistency, in terms of the conditions of service. We prove that the operational semantics is correct and complete with respect to the agent denotation.

DEIS-LIA-02-001 (DVI,postscript)
Fariba Sadri, Francesca Toni, and Paolo Torroni

An abductive logic programming approach for negotiation and communication in multi-agent systems

Abstract. In this paper, we present a framework for agent negotiation based on abductive logic programming. The framework extends an existing architecture for logic-based agents by accommodating dialogues for negotiation. We also consider the well-known resource reallocation problem, and show how it can be solved in the proposed framework.

DEIS-LIA-02-002 (postscript dvi pdf)
Anna Ciampolini and Paolo Torroni

Using Abductive Logic Agents for Legal Justification.

Abstract. In this paper we present a novel approach for legal justification based on an abductive multi-agent system. Legal justification has the main objective of finding the plausible explanations for some given pieces of evidence, for instance in a crime trial. In our approach, the process of justification is done through the collaborative abductive reasoning of agents, which operate within a logic-based architecture called ALIAS. We apply the proposed approach on an example borrowed from the literature. We show that using ALIAS agents in legal justification allows not only to produce plausible explanations for observed evidences, but also to detect either collusion or inconsistencies among trial characters, and to take into consideration the credibility of the persons (e.g., witnesses) involved in the trial.

DEIS-LIA-02-003 (PDF)
A. Ciampolini, P. Mello, S. Storari

Distributed Medical Diagnosis with Abductive Logic Agents

Abstract. We describe the application of a multi-agent system for the distributed diagnosis of infections within an hospital. Diagnosing infections within an hospital is a complex task that may require to collect data (e.g. analysis results, details on patient's clinical history, diagnosis hypotheses) from several information sources (such as, for example, analysis laboratories, hospital wards. These sources act autonomously and they often have a partial knowledge about patients health, their clinical history, and medical information in general. As a natural consequence, this may lead a single entity (e.g., a specialist) to formulate incorrect diagnosis. In such a context, to obtain a correct diagnosis on the basis of information coming from different sources, a coordination mechanism is needed for the integration of collected data into a final diagnosis which should be compatible both with patient's anamnesis and other knowledge (possibly distributed over the system) related to the clinical case. In the paper we face this problem by using abduction, which is a reasoning mechanism for formulating hypotheses in the case of incomplete knowledge, suitably extended to a multi-agent setting. In particular, we first apply ALIAS abductive agents to distributed diagnosis and show how the coordination mechanisms provided by such system are well suited when composing several (possibly partial) diagnosis into a final response, which is consistent with the knowledge of involved agents (i.e., hospital entities or specialist doctors). In the second part of the paper, we extend basic ALIAS coordination mechanisms towards probabilistic abduction. In this way, several (possibly partial) diagnosis obtained by probabilistic abductive reasoning can be merged into a final set of abductive diagnosis, each marked with a probability value.

DEIS-LIA-02-004 (postscript)
Paolo Torroni, Paola Mello, Anna Ciampolini, Evelina Lamma, Michela Milano, Rebecca Montanari, Fabrizio Riguzzi, and Andrea Roli

The SOcieties of ComputeeS Project: a position paper.

Abstract. In the first year of the project, Bologna (UNIBO) will spend 14 months on WP1, a logic-based model for computees, and 10 months on WP2, modelling interactions between computees. Ferrara (DIFERRARA) will spend 12 months on WP1 and 8 months on WP2. This internal document is the result of a series of preliminary, informal meetings held in Bologna, during September and October 2001. It wants to help ourselves introduce our background and viewpoints on the SOCS project, and to sketch a tentative workplan, aimed at starting a discussion with the other groups involved in the project, about the first steps to do within it. Much space is dedicated to possible scenarios that we can use in the course of this project, as possible testbeds to check if our objectives are met.

DEIS-LIA-02-005 (zipped postscript)
Paolo Torroni

Reasoning and interaction in logic-based multi-agent systems.

Abstract. PhD thesis. The main objective of this thesis is to study the application of abductive reasoning to a multi-agent setting. Several possibilities are considered to coordinate the agent reasoning, with a special focus on abduction, leading to the design of an agent architecture, Abductive LogIc AgentS (ALIAS, for short), where (logic-based) agents are intelligent and have social abilities, and where local reasoning and global interaction are specified in a logic programming-based paradigm. The results of this thesis are applied to a typical multi-agent problem, that of negotiation. A dialogue-based negotiation framework is presented, along with some interesting results regarding termination, soundness, and completeness.

DEIS-LIA-02-006 (postscript)
A. Roli

Criticality and parallelism in structured SAT instances

Abstract.In this work we address the question of whether and how parallel local search, which simultaneously applies more than one local move, exhibits the {\it criticality and parallelism} phenomenon when performed on structured instances. We investigate the behavior of a parallel version of GSAT as a function of the number $\tau$ of parallel flips on structured SAT instances. First, we experimentally show that also for structured instances there exists an optimal value of parallelism which enables the algorithm to reach the optimal performance. Second, by analyzing the frequency of node degree of the graphs associated with the SAT instances, we observe that an asymmetric and not regular distribution strongly affects the algorithm performance with respect to $\tau$. Finally, we provide a method that, given an instance, enables to set $\tau$ to the optimal value, so as to effectively apply multi-flip moves to boost local search.

DEIS-LIA-02-007 (postscript)
A.Roli and M.Milano

MAGMA: A Multiagent Architecture for Metaheuristics

Abstract. In this work we introduce a multiagent architecture conceived as a conceptual and practical framework for metaheuristic algorithms (MAGMA, MultiAGent Metaheuristics Architecture). Metaheuristics can be seen as the result of the interaction among different kinds of agents: level 0 agents constructing initial solutions, level-1 agents improving solutions and level-2 agents providing the high level strategy. In this framework, classical metaheuristic algorithms can be smoothly accommodated and extended, and new algorithms can be easily designed by defining which agents are involved and their interactions. Furthermore, with the introduction of a fourth level of agents, coordinating lower level agents, MAGMA can also describe, in a uniform way, cooperative search and, in general, any combination of metaheuristics. We propose this perspective with the aim to achieve a better and clearer understanding of metaheuristics, obtain new algorithms and suggest guidelines for a software engineering-oriented implementation. Some specializations of the general architecture will be provided in order to show that existing metaheuristics can be easily described in our framework.

DEIS-LIA-02-008 (postscript)
Fariba Sadri, Francesca Toni, and Paolo Torroni

A multi-stage negotiation architecture for sharing resources amongst logic-based agents

Abstract. In earlier work we proposed a framework for agents negotiating for resources. The framework was based on abductive logic programming. Agents had knowledge bases, goals and plans for achieving their goals. The plans required resources, and each agent did not necessarily own at the start all the resources it required. Agents had to negotiate with each other to obtain the resources that they needed. In this paper we extend the earlier work by providing the agents with richer knowledge and more sophisticated negotiation capabilities so that they can negotiate periods of time during which they would have use of resources, thus allowing for the sharing of resources. We explore a sequence of stages of negotiation such that in the earlier stages agents need to do little "thinking" and disclose very little about their plans and constraints, but as they step through the sequence they will have to do more "thinking" and disclose more about themselves. If one stage fails to produce a deal amongst the agents they may agree to move to the next stage where there is a better chance of a mutually agreeable deal.

DEIS-LIA-03-001 (postscript)
Marco Alberti, Anna Ciampolini, Marco Gavanelli, Evelina Lamma, Paola Mello, and Paolo Torroni

Logic Based Semantics for an Agent Communication Language

Abstract. Agent communication is one of the key issues in multi-agent systems. Traditional interprocess communication formalisms are usually considered insufficient for this purpose because of their lack of expressiveness; thus, in most proposals for multi-agent architectures, an Agent Communication Language (ACL) is designed to provide for agent communication. However, a universally accepted standard for ACLs is still missing. Agent communication in open societies of heterogeneous agents poses requirements on ACLs semantics (formal syntax and semantics, declarativeness, verifiability, meaningfulness) which a social approach seems to meet best. In this paper we propose a logic-based social approach for ACL semantics. We give a functional abstract model of societies and agents. Then we propose a formalism (deontic constraints) to express interaction protocols and give a social semantics to the behavior of agents, focusing on communicative acts. Finally, we sketch a prototypical implementation of deontic constraints exploiting the Constraint Handling Rules language.

DEIS-LIA-03-003 (pdf)(ps)
A. Guerri and M. Milano

Exploring CP-IP based techniques for the bid evaluation in combinatorial auctions

Abstract. Combinatorial auctions are now an important e-commerce application where bidders can bid on combination of items. The problem of selecting the best bids that cover all items, i.e., the winner determination problem (WDP), is NP-hard. The time constrained variant of this problem, considered in this paper, is the bid evaluation problem where temporal windows and precedence constraints are associated to each task in the bid. Many approaches have been proposed for the winner determination problem, coming mainly from the Integer Programming (IP) community and recently from the multi-agent community, while the bid evaluation problem received less attention.
Surprisingly, the Constraint Programming (CP) community has almost never considered neither of the problems, while we believe that CP solvers or hybrid CP-IP solvers can provide an important contribution to the field. In particular, as soon as temporal side constraints are introduced in the problem. In this paper, we propose different algorithms based on CP, IP and CP-IP. We show that even the simplest pure CP based approach outperforms existing approaches. Since none of the algorithms developed in this paper dominates all the others, they are good candidates for algorithm portfolio design. Therefore, we identified a set of instance-dependent structural features that allow to select the best class of algorithms to apply. An interesting result achieved is that we found a correspondence between the standard deviation of the clustering coefficient and the performances of IP or CP based algorithms. We believe this is the first step toward an automatic algorithm portfolio selection.

DEIS-LIA-03-005 (pdf)
A. Roli

Metaheuristics and Structure in Satisfiability Problems (PhD Thesis)

Abstract. In this thesis, we present and describe metaheuristics, focusing on their applications to the Satisfiability Problem (SAT) and the Maximum Satisfiability Problem (MAXSAT). Moreover, we discuss the impact of problem structure on algorithm behavior, by studying how some constraint graph properties affect the search performance. We first present the state of the art in metaheuristics, underlining the importance of intensification and diversification, and showing that metaheuristics can be conceptually analyzed on their basis. We then provide an architecture that enables the design and implementation of metaheuristics in a component-based fashion, moving the focus from the algorithmic and conceptual viewpoint, to the software engineering approach. The issues of algorithm design and implementation are considered in the novel application of two metaheuristics to MAXSAT. We present the development and implementation of Ant Colony Optimization and of Iterated Local Search metaheuristics. Aftewards, we capitalize the results achieved in the analysis and design of metaheuristics by investigating the impact of SAT/MAXSAT problem structure on metaheuristic behavior. We first define the structure on the basis of the constraint graph associated to the instances. This approach enables us to extract general properties of the problem structure. In particular, we study the impact of connectivity among variables on the parallelization of local search. We find empirical evidence for the presence of an optimal number of parallel local moves that enables the algorithm to achieve the highest effectiveness. We also discover that the optimal number of parallel moves is negatively correlated with the connectivity among variables. The results obtained can give insight into the Criticality and Parallelism phenomenon and into the behavior of trajectory methods. Finally, we also investigate the hardness of small-world SAT instances, finding results which may support the conjecture that small-world instances are among the hardest to solve for both approximate and complete algorithms.

DEIS-LIA-03-006 (pdf ps)
Marco Alberti, Marco Gavanelli, Evelina Lamma, Paola Mello, and Paolo Torroni

Specification and Verification of Agent Interaction using Social Integrity Constraints

Abstract. In this paper we propose a logic-based social approach to the specification and verification of agent interaction. We firstly introduce integrity constraints about social acts (called Social Integrity Constraints) as a formalism to express interaction protocols and to give a social semantics to the behavior of agents, focusing on communicative acts. Then, we discuss several possible kinds of verification of agent interaction, and we show how social integrity constraints can be used to verify some properties in this respect. We focus our attention on static verification of compliance of agent specifications to interaction protocols, and on run-time verification, based on agents' observable behavior. We adopt as a running example the NetBill security transaction protocol for the selling and delivery of information goods.

DEIS-LIA-03-007 (pdf)
Paolo Torroni

Computational Logic in Multi-Agent Systems: recent advances and future directions

Abstract. Starting from the early days of multi-agent systems research, considerable effort has been devoted to giving formal foundations to agent technologies. Work done in this direction, based on computational logic, is an attempt to bridge an existing gap, between theoretical frameworks and their practical implementations. In the last two editions of the workshop on Computational Logic in Multi-Agent Systems, CLIMA'01 and CLIMA'02, two discussion panels have been organized, aimed at bringing researchers together and exchanging ideas on a number of topics. In this article, we elaborate on the outcome of such panels, to draw some considerations about the recent advances and future directions of Computational Logic in Multi-Agent Systems.

DEIS-LIA-04-001 (pdf)
A. Roli

Symmetry-Breaking and Local Search: A Case Study

Abstract. Symmetry-breaking has been proved to be very effective when combined with complete solvers. Conversely, it has been conjectured that the use of symmetry-breaking constraints has negative effect on local search-based solvers. This work presents an attempt to model the effect of symmetry-breaking on the search landscape explored by local search. The results, on the one hand, exclude that symmetry-breaking constraints negatively affect the topology of the search space. On the other hand, they strongly suggest that symmetry-breaking perturbs the configuration of local and global optima basins of attraction, making global optima more difficult to be reached.

DEIS-LIA-04-002 (pdf)
A.M. Ouksel, G. Moro

G-Grid: A Class of Scalable and Self-Organizing Data Structures for Multi-dimensional Querying and Content Routing in P2P Networks

Abstract. Peer-to-Peer (\ptop) technologies promise to provide efficient distribution, sharing and management of resources, such as storage, processing, routing and other sundry service capabilities, over autonomous and heterogeneous peers. Yet, most current P2P systems only support rudimentary query and content routing over a single data attribute, such as the file-sharing applications popularized in Napster, Gnutella and so forth. Full-fledged applications in distributed data management and grid computing demand more complex functionality, including querying and content routing over multiple attributes. In this paper, we present a class of scalable and self-organizing multi-dimensional distributed data structures able to efficiently perform range queries in totally decentralized dynamic P2P environments. These structures are not imposed a priori over the network of peers. Rather, they emerge from the independent interactions of autonomous peers. They are also adaptive to unanticipated changes in the network topology. This robustness property expands their range of usefulness to many application areas such as mobile ad-hoc networks.

DEIS-LIA-04-003 (pdf)
Marco Alberti, Federico Chesani, Marco Gavanelli, Evelina Lamma, Paola Mello, and Paolo Torroni

Compliance Verification of Agent Interaction: a Logic-based Software Tool

Abstract. In open societies of agents, where agents are autonomous and heterogeneous, it is not realistic to assume that agents will always act so as to comply to interaction protocols. Thus, the need arises for a formalism to specify constraints on agent interaction, and for a tool able to observe and check for agent compliance to interaction protocols. In this paper we present a Java-Prolog software component built on logic programming technology, which can be used to verify compliance of agent interaction to protocols, and that has been integrated with PROSOCS.
This article will appear in Applied Artificial Intelligence, Taylor & Francis (2005)

DEIS-LIA-04-004 (pdf)
Marco Alberti, Federico Chesani, Marco Gavanelli, Evelina Lamma, Paola Mello, and Paolo Torroni

On the automatic verification of interaction protocols using g-SCIFF

Abstract. Interaction protocol verification has been in recent years intensively investigated within and outside multi-agent research. Many techniques and models have been proposed based on a number of assumptions and choices, among which are the kind of knowledge available and the kind of properties that are subject of verification. We focus on interaction protocol verification in open multi-agent systems, where the internal architecture of the individual agents is not known a-priori. In such a setting, while it is not possible to predict the behaviour of individual agents, it is still possible to approach the interaction verification problem either by assuming that agents will indeed comply to the protocols, thus focussing on the study of properties of the interaction protocols, or by assuming that the agent behaviour, if not predictable, is at least observable, and then focussing on the run-time verification of compliant behaviour of interacting agents by reasoning on the messages they exchange with each other. In this article, we build on previous work on logic-based specification and run-time verification of protocol compliance, and we extend the SOCS social framework towards verification of protocol properties. In doing so, we propose a unified formal and computational framework based on abductive logic programming which can be used to (i) design and specify interaction protocols that provably exhibit desirable properties and (ii) verify, at run-time, that agent interaction actually complies to the specified interaction protocols.

DEIS-LIA-04-005 (pdf)
Gianluca Moro and Gabriele Monti

M-Grid: a P2P Self-Organizing Infrastructure for Routing and Location Service in Mobile Ad-Hoc Networks

Abstract. Latest improvements in wireless communications and electronics have enabled the development of smaller and more powerful mobile devices. Hence, ad-hoc networks and sensor networks are becoming very popular and they now both need scalable routing algorithms. So far, the main proposals have been geographic routing and on-demand routing but they have many limitation such as the dead-ends problem, that happen when greedy routing fails because a node has no neighbor closer to the destination. Anyway, the main problem is that most of these routing strategies require nodes to know their exact geographic location, actually there are many situations in which that information is not available. So far, the few papers that have been addresses to how to route in absence of location information mainly consider the case where some (not none) nodes have geographic information. In this paper we present a system which supply both a virtual coordinates system and a non-geographic routing algorithm. It basically works mapping the peers on a binary tree and generating a coordinates space which reflects the underlying connectivity between them, moreover, the use of virtual coordinates instead of the node's physical position eliminates the risk of dead-ends. Over this tree framework we can implement different G-Grid structures (which works with binary trees as well) to store and distribute any kind of information.


DEIS-LIA-05-001 (pdf)(ps)

Luca Benini, Davide Bertozzi, Alessio Guerri, and Michela Milano

Allocation and Scheduling for MPSoCs via decomposition and no-good generation

Abstract. This paper describes an efficient, complete approach for solving a complex allocation and scheduling problem for Multi-Processor System-on-Chip (MPSoC). Given a throughput constraint for a target application characterized as a task graph annotated with computation, communication and storage requirements, we compute an allocation and schedule which minimizes communication cost first, and then the makespan given the minimal communication cost. Our approach is based on problem decomposition where the allocation is solved through an Integer Programming solver, while the scheduling through a Constraint Programming solver. The two solvers are interleaved and their interaction regulated by no-good generation. Experimental results show significant speedups w.r.t. pure IP and CP solution strategies.


DEIS-LIA-06-001 (pdf)

Marco Alberti, Federico Chesani, Marco Gavanelli, Evelina Lamma, Paola Mello, and Paolo Torroni

Verifiable Agent Interaction in Abductive Logic Programming: the SCIFF proof-procedure

Abstract. SCIFF is a new abductive logic programming proof-procedure for reasoning with expectations in dynamic environments. SCIFF is also the main component of a framework thought to specify and verify interaction in open agent societies. In this paper we present the declarative and operational semantics of SCIFF, its termination, soundness and completeness results, and some sample applications to demonstrate its use in the multi-agent domain..


DEIS-LIA-06-002 (pdf)

Marco Alberti, Federico Chesani, Marco Gavanelli, Evelina Lamma, Paola Mello, Marco Montali, and Paolo Torroni

Policy-based reasoning for smart web service interaction

Abstract. We present a vision of smart, goal-oriented web services that reason about other services' policies and evaluate the possibility of future interactions. To achieve our vision, we propose a proof theoretic approach. We assume web services whose interface behaviour is specified in terms of reactive rules. Such rules can be made public, in order for other web services to answer the following question: "is it possible to inter-operate with a given web service and achieve a given goal?" In this article we focus on the underlying reasoning process, and we propose a declarative and operational abductive logic programming-based framework, called WAVe.


DEIS-LIA-06-003 (pdf)

Michele Lombardi, Michela Milano

Stochastic Allocation and Scheduling for Conditional Task Graphs in MPSoCs

Abstract. This paper describes a complete and efficient solution to the stochastic allocation and scheduling for Multi-Processor System-on-Chip (MPSoC). Given a conditional task graph characterizing a target application and a target architecture with alternative memory and computation resources, we compute an allocation and schedule minimizing the expected value of communication cost, being the communication resources one of the major bottlenecks in modern MPSoCs. Our approach is based on the Logic Based Benders decomposition where the stochastic allocation is solved through an Integer Programming solver, while the scheduling problem with conditional activities is faced with Constraint Programming. The two solvers interact through no-goods. The original contributions of the approach appear both in the allocation and in the scheduling part. For the first, we propose an exact analytic formulation of the stochastic objective function based on the task graph analysis, while for the scheduling part we extend the timetable constraint for conditional activities. Experimental results show the effectiveness of the approach.


DEIS-LIA-07-001 (pdf)

Federico Chesani, Paola Mello, Marco Montali, and Sergio Storari

Towards a DecSerFlow Declarative Semantics based on Computational Logic

Abstract. In this paper we exploit a computational logic-based framework, called SCIFF, for the formalization of DecSerFlow. DecSerFlow is a graphical, extendible high-level language for the declarative specification of service flows, and is grounded on LTL. SCIFF was originally developed in the context of the SOCS european project, where we addressed the issue of providing a formal language to define and verify interaction protocols in open environments. More specifically, in this work we show that SCIFF is concretely able to formalize the DecSerFlow core template formulae, tackling two complementary issues: on one hand, it is possible to specify SCIFF rules by using an intuitive and user-friendly graphical language; on the other hand, a DecSerFlow model may be grounded not only on LTL but also on an abductive framework, acquiring some new advantages and features. Finally, we propose to extend DecSerFlow by exploiting some useful features of the SCIFF framework, like for example the explicit notion of time, which could be used to specify temporal constraints and deadlines.


DEIS-LIA-07-004 (pdf)(ps)

Luca Benini, Davide Bertozzi, Alessio Guerri, and Michela Milano

Allocation, Scheduling and Voltage Scaling on Energy Aware MPSoC

Abstract. In this paper we introduce a complex allocation and scheduling problem for variable voltage Multi-Processor System-on-Chip (MPSoC) platforms. We propose a methodology to formulate and solve to optimality the allocation, scheduling and discrete voltage selection problem, minimizing the system energy dissipation and the overhead for frequency switching. Our approach is based on the Logic Benders decomposition technique where the allocation is solved through an Integer Programming solver, and the scheduling through a Constraint Programming solver. The two solvers are interleaved and their interaction regulated by cutting plane generation. The objective function depends on both master and sub-problem variables. We demonstrate the efficiency of our approach on a set of realistic instances.


DEIS-LIA-07-006 (pdf)(ps)

Luca Di Gaspero and Andrea Roli

A preliminary analysis on metaheuristics methods applied to the Haplotype Inference Problem

Abstract. Haplotype Inference is a challenging problem in bioinformatics that consists in inferring the basic genetic constitution of diploid organisms on the basis of their genotype. This information allows researchers to perform association studies for the genetic variants involved in diseases and the individual responses to therapeutic agents. A notable approach to the problem is to encode it as a combinatorial problem (under certain hypotheses, such as the pure parsimony criterion) and to solve it using off-the-shelf combinatorial optimization techniques. The main methods applied to Haplotype Inference are either simple greedy heuristic or exact methods (Integer Linear Programming, Semidefinite Programming, SAT encoding) that, at present, are adequate only for moderate size instances. We believe that metaheuristic and hybrid approaches could provide a better scalability. Moreover, metaheuristics can be very easily combined with problem specific heuristics and they can also be integrated with tree-based search techniques, thus providing a promising framework for hybrid systems in which a good trade-off between effectiveness and efficiency can be reached. In this paper we illustrate a feasibility study of the approach and discuss some relevant design issues, such as modeling and design of approximate solvers that combine constructive heuristics, local search-based improvement strategies and learning mechanisms. Besides the relevance of the Haplotype Inference problem itself, this preliminary analysis is also an interesting case study because the formulation of the problem poses some challenges in modeling and hybrid metaheuristic solver design that can be generalized to other problems.


DEIS-LIA-07-007 (pdf)

Domenico Corapi

Tesi di laurea (Master Project / in Italian)

Traduzione di un linguaggio per l’ingegneria dei requisiti orientato agli agenti in logica computazionale

Abstract. The objective of this master project is to investigate the application of formal verification methods based on computational logic to agent-oriented requirements engineering. This report starts by presenting the Tropos methodology for agent-oriented requirements engineering, and by defining the Tropos model buildng blocks: actors, goals, tasks, dependencies, delegations. Then it presents the SCIFF language and proof-procedure, which will be adopted for the specification and verification of Tropos model. After these background sections, in Chapter 3 the author illustrates a possible translation of Tropos and shows how to do simulationa and analysis of Tropos models using its SCIFF translation. Chapter 4 describes B-Tropos, i.e., an extension of Tropos geared towards business process modelling. Chapter 5 presents a formalization of B-Tropos, with a specific emphasis on time-related aspects of such a formalization. Such aspects will be discussed in comparison with Allen's interval algebra in Chapter 6, in which the authors shows how to check the consistency of temporal relations in B-Tropos models and provide possible valid execution instances using a Prolog solver. Before drawing conclusions, Chapter 7 addresses the problem of stepping through various phases of design, starting from architectural models to detailed design and implementation. The report is rich in examples that illustrate the use of B-Tropos as a formal tool to automatize relevant implementation and verification tasks.


DEIS-LIA-08-003 (pdf)

Federico Chesani, Paola Mello, Marco Montali, and Paolo Torroni

An Efficient Implementation of Reactive Event Calculus in SCIFF

Abstract. In this work, we propose a reactive version of the Event Calculus (EC) implemented on top of the SCIFF framework. Being reactive, such an implementation is able to dynamically update the status of fluents as events occur. Therefore, it can be employed to perform run-time reasoning and monitoring.


DEIS-LIA-08-004 (pdf)

Marco Montali, Marco Alberti, Federico Chesani, Marco Gavanelli, Evelina Lamma, Paola Mello, and Paolo Torroni

Verification from declarative specifications using Logic Programming

Abstract. We address the problem of formal verification for systems specified using declarative languages. We propose a verification method based on the g-SCIFF abductive logic programming proof-procedure and evaluate our method empirically, by comparing its performance with that of other verification frameworks.


DEIS-LIA-09-003 (pdf)

Stefano Benedettini, Luca Di Gaspero and Andrea Roli

Genetic Master-Slave Algorithm for Haplotype Inference by Parsimony

Abstract. Haplotype Inference is a challenging problem in bioinformatics that consists in inferring the basic genetic constitution of diploid organisms on the basis of their genotypes. This piece of information makes it possible to perform association studies for the genetic variants involved in multifactorial diseases and the individual responses to therapeutic agents. A notable approach to the problem is to encode it as a combinatorial problem (under certain hypotheses, such as the pure parsimony criterion) and to solve it using combinatorial optimization techniques. Recently, several new approaches to the problem were presented. Among them, solvers based on hybrid metaheuristics have been proven to be effective in solving large size instances. In this paper, we present an master-slave hybrid approach, in which a master solver optimize the parameters used by a slave solver for constructing a solution. By testing the algorithm on common Haplotype Inference benchmarks, we show that this approach can produce good quality solutions in a very short execution time.


DEIS-LIA-09-004 (pdf)

Andrea Roli and Christian Blum

Tabu Search for the Founder Sequence Reconstruction Problem: A Preliminar y Study

Abstract. The problem of inferring ancestral genetic information in terms of a set of founders of a given population arises in various biological contexts. In optimization terms, this problem can be formulated as a combinatorial string problem. The main problem of existing techniques, both exact and heuristic, is that their time complexity scales exponentially, which makes them impractical for solving large-scale instances. We developed a new constructive heuristic and a tabu search method with the explicit aim of providing solutions in a reduced amount of computation time. Experimental results show that when the number of founders grows, our algorithms have advantages over the ones proposed in the literature.


DEIS-LIA-09-005 (pdf)

Stefano Benedettini, Andrea Roli and Luca Di Gaspero

EasyGenetic: A Template Metaprogramming Framework for Genetic Master-Slave Algorithms

Abstract. In this work we present EasyGenetic, a genetic solver based on template metaprogramming, that enables the user to configure the solver via templates. The framework allows to combine flexibility with efficiency. The framework is designed to be applied to problems for which a master-slave solution strategy can be defined. In the realm of combinatorial optimization, such problems can be those for which a parametrized constructive procedure is available and the solver search the parameter space. We present two successful applications of EasyGenetic to hard optimization problems, namely the Haplotype inference problem and the Capacitated vehicle routing problem.


DEIS-LIA-07-009 (pdf)

Gabriele Monti

WPA-GPG: Wireless authentication using GPG Key

Abstract. In this paper we present WPA-GPG, a modification on WPA- PSK wireless authentication protocol that allows a wireless station to access a protected network using a GnuPG public key. GnuPG, (GPG) short for GnU Privacy Guard, is a complete, multi-platform and open source implementation of the OpenPGP standard as defined by RFC4880. Like WPA-PSK, WPA-GPG is based on IEEE802.1X and EAP protocols, therefore it does not require any special hardware to work, any wireless card supporting IEEE 802.11i (WPA2) standard is suitable for WPA-GPG. Differently from WPA-PSK, WPA-GPG ensures in-network users' privacy and non-repudiation of network traffic.



Ozgur Kafali and Paolo Torroni

Diagnosing commitments: Delegation revisited

Abstract.The success of contract-based multiagent systems relies on agents complying with their commitments. When something goes wrong, it is important to understand what are the commitments' mutual relations as well as their individual states. Accordingly, we explore how commitments are related through the three-agent commitment delegation operation. We then propose exception monitoring based on such relations, and demonstrate it via a case study.



Marco Montali, Fabrizio M. Maggi, Federico Chesani, Paola Mello, and Wil M. P. van der Aalst

Monitoring Business Constraints with the Event Calculus

Abstract. Today, larger systems are composed of smaller interconnected sys- tems and need to evolve over time. The dynamic nature and the complexity of such systems trigger the need for runtime verification and monitoring facilities. These are needed to check whether the actual behavior complies with expected business constraints. In this work, we present a novel monitoring framework that tracks streams of events and continuously determines the state of busi- ness constraints. The framework exploits the Event Calculus as a logic-based, expressive language for the formal specification of constraints. Moreover, our framework uses a light-weight, logic programming-based Event Calculus ax- iomatization for dynamically reasoning on partial, evolving execution traces. We demonstrate that the approach can be exploited to formalize ConDec, a declarative process modeling language, and to extend it with quantitative time constraints. We then sketch how it has been implemented by exploiting the operational decision support architecture of ProM. To demonstrate the appli- cability of our proposal, we provide a concrete case study dealing with maritime safety and security.



Alessio Bonfietti, Michele Lombardi, Michela Milano

Disregarding Duration Uncertainty in Partial Order Schedules? Yes, we can!

Abstract. In the context of Scheduling under uncertainty, Partial Order Schedules (POS) provide a convenient way to build flexible solutions. A POS is obtained from a Project Graph by adding precedence constraints so that no resource conflict can arise, for any possible assignment of the activity durations. In this paper, we use a simulation approach to evaluate the expected makespan of a number of POSs, obtained by solving scheduling benchmarks via multiple approaches. Our evaluation leads us to the discovery of a striking correlation between the expected makespan and the makespan obtained by simply fixing all durations to their average. The strength of the correlation is such that it is possible to disregard completely the uncertainty during the schedule construction and yet obtain a very accurate estimation of the expected makespan. We provide a thorough empirical and theoretical analysis of this result, showing the existence of solid ground for finding a similarly strong relation on a broad class of scheduling problems of practical importance.

About this Server
About this Server
Mail to DocMaster
Mail to WebMaster
LIA WebMaster

[LIA Home] [LIA Research] [DEIS Research] [DEIS Home] [Alma Mater Home]