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.
| |
|
|
|
 |
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]
|
|
|
|
|
1 |
| 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. |
|
|
|
|
|
|
2 |
|
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.
|
|
|
|
|
|
|
3 |
| A. Omicini
Abduction and
Object State Configuration
Work under revision
|
|
| Abstract. ...
Keywords: ...
|
|
|
|
|
|
|
4 |
|
| 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. |
|
|
|
|
|
|
5 |
|
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. |
|
|
|
|
|
|
6 |
| M.P. Schumann
Impact of
Object Orientation in Compiler Building - A Grammar
Related Extensible Class Library
Laurea Thesis
|
|
|
|
|
|
|
|
|
7 |
|
| 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. |
|
|
|
|
|
|
8 |
|
| 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. |
|
|
|
|
|
|
9 |
|
| 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. |
|
|
|
|
|
|
10 |
|
| 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.
|
|
|
|
|
|
|
11 |
| 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.
|
|
|
|
|
|
|
12 |
|
| 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. |
|
|
|
|
|
|
13 |
|
| 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. |
|
|
|
|
|
|
14 |
|
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.
|
|
|
|
|
|
|
15 |
|
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. |
|
|
|
|
|
|
16 |
| 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.
|
|
|
|
|
|
|
18 |
|
| 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
|
|
|
|
|
|
|
19 |
|
| 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
|
|
|
|
|
|
|
20 |
| 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.
|
|
|
|
|
|
|
21 |
|
| 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.
|
|
|
|
|
|
|
22 |
|
| 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
|
|
|
|
|
|
|
23 |
|
| 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
|
|
|
|
|
|
|
24 |
|
| 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. |
|
|
|
|
|
|
25 |
| 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. |
|
|
|
|
|
|
26 |
|
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
|
|
| |
|
|
|
|
27 |
|
| 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. |
|
| |
|
|
|
|
28 |
|
| 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. |
|
| |
|
|
|
|
29 |
|
| 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). |
|
| |
|
|
|
|
30 |
| 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. |
|
| |
|
|
|
|
31 |
| 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. |
|
| |
|
|
|
|
32 |
| 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. |
|
| |
|
|
|
|
33 |
| 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.
|
|
| |
|
|
|
|
34 |
|
|
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.
|
|
| |
|
|
|
|
35 |
|
|
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.
|
|
| |
|
|
|
|
36 |
|
|
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.
|
|
| |
|
|
|
|
37 |
| 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.
|
|
| |
|
|
|
|
39 |
| 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.
|
|
| |
|
|
|
|
40 |
| 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.
|
|
| |
|
|
|
|
41 |
| 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.
|
|
| |
|
|
|
|
42 |
| 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.
|
|
| |
|
|
|
|
44 |
| 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.
|
|
| |
|
|
|
|
49 |
| F. Focacci
Solving
Combinatorial Optimization Problems in Constraint Programming -
PhD Thesis
|
|
|
|
| |
|
|
|
|
50 |
| 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.
|
|
| |
|
|
|
|
51 |
| 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.
|
|
| |
|
|
|
|
52 |
| 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.
|
|
| |
|
|
|
|
53 |
| 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.
|
|
| |
|
|
|
|
54 |
| 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.
|
|
| |
|
|
|
|
55 |
| 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.
|
|
| |
|
|
|
|
56 |
| 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.
|
|
| |
|
|
|
|
57 |
| 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.
|
|
| |
|
|
|
|
58 |
| 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.
|
|
| |
|
|
|
|
59 |
| 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.
|
|
| |
|
|
|
|
60 |
| 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.
|
|
| |
|
|
|
|
61 |
| 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.
|
|
| |
|
|
|
|
62 |
| 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.
|
|
| |
|
|
|
|
64 |
| 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.
|
|
| |
|
|
|
|
66 |
| 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.
|
|
| |
|
|
|
|
67 |
| 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.
|
|
| |
|
|
|
|
68 |
| 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.
|
|
| |
|
|
|
|
69 |
| 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.
|
|
| |
|
|
|
|
70 |
|
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.
|
|
| |
|
|
|
|
71 |
| 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)
|
|
| |
|
|
|
72 |
|
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. |
|
| |
|
|
|
73 |
|
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. |
|
| |
|
|
|
74 |
|
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. |
|
| |
|
|
|
75 |
|
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.. |
|
| |
|
|
|
76 |
|
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. |
|
| |
|
|
|
77 |
|
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. |
|
| |
|
|
|
79 |
|
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. |
|
| |
|
|
|
82 |
|
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. |
|
| |
|
|
|
84 |
|
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.
|
|
| |
|
|
|
85 |
|
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. |
|
| |
|
|
|
89 |
|
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.
|
|
| |
|
|
|
90 |
|
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.
|
|
| |
|
|
|
93 |
|
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.
|
|
| |
|
|
|
94 |
|
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.
|
|
| |
|
|
|
95 |
|
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.
|
|
| |
|
|
|
97 |
|
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.
|
|
| |
|
|
|
99 |
|
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. |
|
| |
|
|
|
100 |
|
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. |
|
| |
|
|
|
101 |
|
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. |
|
