2003

[DIPISA/Mancarella/] P. Mancarella and G. Terreni An abductive proof procedure handling active rules. Proceedings AI*IA 2003 Springer Verlag LNCS 2829

Abstract. We present a simple, though powerful extension of an abductive proof procedure proposed in the literature, the so-called KM-procedure, which allows one to properly treat more general forms of integrity constraints than those handled by the original procedure. These constraints are viewed as active rules, and their treatment allows the integration of a limited form of forward reasoning within the basic, backward reasoning framework upon which the KM-procedure is based. We first provide some background on Abductive Logic Programming and the KM-procedure and then formally present the extension, named AKM-procedure. The usefulness of the extension is shown by means of some simple examples.

CONTRIBUTION TO SOCS WORKPACKAGES [WP3]: This work is relevant to WP3 in exploring alternative abductive proof procedure suitable to implement the KGP model.

[CITY/Stathis/] M. Witkowski, K. Stathis A Dialectic Architecture for Computational Autonomy In Proceedings of Workshop "Computational autonomy: potential, risks, solutions" (AAMAS-03), Melbourne, Australia.

Abstract: This paper takes the view that to be considered autonomous, a software agent must possess the means by which to manage its own motivations and so arbitrate between competing internal goals. Using the motivational theories of Abraham Maslow as a starting point, we investigate the role that argumentation processes might play in balancing the many competing aspects of a whole agent's motivational agenda. This is developed into an Agent Argumentation Architecture (AAA) in which multiple ``faculties'' argue for different aspects of the total behavior of the Agent. The overall effect of these internal arguments then defines which actions the agent will select for expression, and so define the overt and observable ``personality'' of the agent.

CONTRIBUTION TO SOCS WORKPACKAGES []

[CITY/Stathis/] W. Lu, N. Maudet, K. Stathis. Building Socio-Cognitive Grids by Combining Peer-to-Peer Computing with Computational Logic. Proceedings 1st International Workshop on "Socio-Cognitive Grids: The Net as a Universal Human Resource" (TALES 2003), Santorini, Greece.

Abstract: We present the initial design considerations of an implementation framework that combines computational logic - in the form of extensions of logic programming, with Peer-to-peer Computing - in the form of distributed network protocols that allow components to communicate and discover each other. We discuss how the combination of these technologies will allow us to build agent-based systems with cognitive and social capabilities. We exemplify the discussion by illustrating the potential of how to use agents of this kind to build socio-cognitive grids.

CONTRIBUTION TO SOCS WORKPACKAGES []

[ICSTM/Endriss/FernandezEndrissTBILISI2003] Raquel Fernandez and Ulle Endriss. Abstract Models for Dialogue Protocols. In Proceedings of the 5th International Tbilisi Symposium on Language, Logic and Computation, October 2003.

Abstract: We examine a variety of dialogue protocols, taking inspiration from two fields: natural language dialogue modelling and multiagent systems. In communicative interactions, one can identify different features that may increase the complexity of the dialogue structure. This motivates a hierarchy of abstract models for protocols that takes as a starting point protocols based on deterministic finite automata. From there, we proceed by looking at particular examples that justify either an enrichment or a restriction of the initial model.

CONTRIBUTION TO SOCS WORKPACKAGES [WP1,WP2,WP5]: This paper is a first attempt to give a classification of communication protocols in computation-theoretic terms. In this sense, it is relevant to both WP2 (which addresses the definition of communication protocols) and WP5 (which studies properties of such protocols). It also establishes connections between issues studied within SOCS and problems studied in computational linguistics.

[ICSTM-CITY/Endriss/EndrissMaudetESAW2003] Ulle Endriss and Nicolas Maudet. Welfare Engineering in Multiagent Systems. In Proceedings of the 4th International Workshop on Engineering Societies in the Agents World (ESAW-2003), October 2003.

Abstract: A multiagent system may be regarded as an artificial society of autonomous software agents. Welfare economics provides formal models of how the distribution of resources amongst the members of a society affects the well-being of that society as a whole. In multiagent systems research, the concept of social welfare is usually given a utilitarian interpretation, i.e. whatever increases the average welfare of the agents inhabiting a society is taken to be beneficial for society as well. While this is indeed appropriate for a wide range of applications, we believe that it is worthwhile to also consider some of the other social welfare orderings that have been studied in the social sciences. In this paper, we put forward an engineering approach to welfare economics in multiagent systems by investigating the following question: Given a particular social welfare ordering appropriate for some application domain, how can we design criteria that will allow agents to decide locally whether or not a proposed deal would further social welfare with respect to that ordering? In particular, we review previous results on negotiating Pareto optimal allocations of resources as well as allocations that maximise egalitarian social welfare under this general perspective. We also provide new results on negotiating Lorenz optimal allocations, which may be regarded as a compromise between the utilitarian and the egalitarian approaches. Finally, we briefly discuss elitist agent societies, where social welfare is tied to the welfare of the most successful agent, and envy-freeness.

CONTRIBUTION TO SOCS WORKPACKAGES [WP1,WP2,WP5]: This paper continues our analysis of the problem of reallocating resources in open societies by means of negotiation, one of the central problems addressed by the Global Computing initiative. It is also relevant to WP5, as it defines further interesting properties of societies of computees.

[CITY-ICSTM/Endriss/EndrissEtAlESAW2003] Ulle Endriss, Wenjin Lu, Nicolas Maudet, and Kostas Stathis. Competent Agents and Customising Protocols. In Proceedings of the 4th International Workshop on Engineering Societies in the Agents World (ESAW-2003), October 2003.

Abstract: In open agent societies, communication protocols and strategies cannot be assumed to always match perfectly, because they are typically specified by different designers. These potential discrepancies raise a number of interesting issues, most notably the problem of checking that the behaviour of an agent is (or will be) conformant to the rules described by a protocol. In this paper, we argue that the ability to merely conform to a protocol is not sufficient for an agent to be a competent user of that protocol. We approach the intuitive idea of protocol competence by introducing a notion that considers, broadly speaking, an agent's ability to reach a particular state of the interaction and we provide preliminary results that allow us to automatically check competence in the context of a specific class of logic-based agents. Finally, we illustrate how these results can facilitate the customisation of protocols used by agents that are not fully competent.

CONTRIBUTION TO SOCS WORKPACKAGES [WP2,WP5]: Properties of communication protocols are amongst the central issues of concern in SOCS and this paper continues our investigations in this area.

[DIFERRARA-UNIBO/Gavanelli/AGP2003-gavanelli] Marco Gavanelli, Evelina Lamma, Paola Mello, Michela Milano, and Paolo Torroni, Interpreting Abduction in CLP. In F. Buccafurri, editor, APPIA-GULP-PRODE Joint Conference on Declarative Programming, pages 25-35, Università Mediterranea di Reggio Calabria, Italy, Sept. 3-5 2003.

Abstract: Constraint Logic Programming (CLP) and Abductive Logic Programming (ALP) share the important concept of conditional answer. We exploit their deep similarities to implement an efficient abductive solver where abducibles are treated as constraints. We propose two possible implementations, in which integrity constraints are exploited either (i) as the definition of a CLP solver on an abductive domain, or (ii) as constraints à la CLP. Both the solvers are implemented on top of CLP(Bool), that typically have impressively efficient propagation engines.

CONTRIBUTION TO SOCS WORKPACKAGES [WP4]: For the implementation of the abductive proof procedure (WP4), we decided to check the feasibility of a CHR (Constraint Handling Rules) implementation. In fact, CHR is naturally linked to the constraint solver, so the integration of abduction and constraint solving should be simplified. The paper presents two explored implementations of an abductive proof procedure in CHR, that show different features.

[UNIBO-DIFERRARA/Torroni/LCMAS2003torroni] Marco Alberti, Marco Gavanelli, Evelina Lamma, Paola Mello, and Paolo Torroni. Specification and verification of agent interactions using social integrity constraints. In Wiebe van der Hoek, Alessio Lomuscio, Erik de Vink, and Mike Wooldridge, editors, Proceedings of the Workshop on Logic and Communication in Multi-Agent Systems, LCMAS 2003, Eindhoven, the Netherlands, 29 June 2003. Electronic Notes in Theoretical Computer Science, Vol. 85 No. 2, Elsevier Science, October 2003.

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.

CONTRIBUTION TO SOCS WORKPACKAGES [WP2, WP3, WP4, WP5]: The paper, based on an early version of Social Integrity Constraints (subject of WP2), investigates the applicability of our approach to different kinds of verification of properties (WP5). The paper also presents the basic strategy of verification that we formalize as an abductive proof procedure in WP3, and a Prolog/CHR-based implementation which is being expanded for WP4.

[UNIBO-ICSTM/Torroni/IJCAI03-multistage] Fariba Sadri, Francesca Toni, and Paolo Torroni, Minimally intrusive negotiating agents for resource sharing. In G. Gottlob, editor, Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI) . AAAI Press, August 2003. To appear.

Abstract: We study the problem of agents negotiating periods of time during which they can have use of resources, thus allowing for the sharing of resources. We define a multi-stage negotiation framework where agents, in order to obtain resources, step through a sequence of stages, each characterised by an increased chance of a mutually agreeable deal but at the price of disclosing more and more information. In the sequence, the agents may agree to move to the next stage if the previous stage fails to produce a deal amongst them. In this paper, we concentrate on two early negotiation stages, characterised by minimal disclosure of information. Thus, the agents negotiating at these stages can be thought of as ``minimally intrusive''.

CONTRIBUTION TO SOCS WORKPACKAGES [WP2, WP5]: This paper aims at studying interaction patterns in a negotiation scenario, defining protocols which we use as case studies in other publications [DALT2003torroni] and in some deliverables, such as D5 [D5], and singles out properties that we would like to study within WP5 [SOCS-roperties].

[UNIBO-DIFERRARA/Alberti/Alberti-FAMAS] Marco Alberti, Anna Ciampolini, Marco Gavanelli, Evelina Lamma, Paola Mello, and Paolo Torroni, Logic Based Semantics for an Agent Communication Language. In Barbara Dunin-Keplicz and Rineke Verbrugge, editors, Proceedings of the International Workshop on Formal Approaches to Multi-Agent Systems (FAMAS), pages 21–36, Warsaw, Poland, April 12 2003.

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 \textit{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, grounded on a computational logic framework) 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.

CONTRIBUTION TO SOCS WORKPACKAGES [WP2,WP3,WP4]: The paper presents an early version of Social Integrity Constraints (subject of WP2). It also introduces the computational mechanisms that have later been formalized as an Abductive Proof Procedure in WP3, and a prototype of the Social Compliance Verifier developed for WP4.

[UNIBO-DIFERRARA/Alberti/alberti03social-ceemas03] Marco Alberti, Anna Ciampolini, Marco Gavanelli, Evelina Lamma, Paola Mello, and Paolo Torroni, A social ACL semantics by deontic constraints. In V. Marik, J. Müller, and M. Pechoucek, editors, Multi-Agent Systems and Applications III. Proceedings of the 3rd International Central and Eastern European Conference on Multi-Agent Systems, CEEMAS 2003, volume 2691 of Lecture Notes in Artificial Intelligence, pages 204-213, Prague, Czech Republic, June 16-18 2003. Springer-Verlag.

Abstract: In most proposals for multi-agent systems, an Agent Communication Language (ACL) is the formalism designed to express knowledge exchange among agents. However, a universally accepted standard for ACLs is still missing. Among the different approaches to the definition of ACL semantics, the \textit{social} approach seems the most appropriate to express semantics of communication in open societies of autonomous and heterogeneous agents. In this paper we propose a formalism (\textit{deontic constraints}) to express social ACL semantics, which can be grounded on a computational logic framework, thus allowing automatic verification of compliance by means of appropriate proof procedures. We also show how several common communication performatives can be defined by means of deontic constraints.

CONTRIBUTION TO SOCS WORKPACKAGES [WP2]: The paper introduces a version of Social Integrity Constraints, focussing on the expressive power of the framework for semantics of communication and interaction protocols, also compared to that of other frameworks. Both the definition of Social Integrity Constraints and a comparison with related work were among the main tasks of WP2.

[UNIBO-DIFERRARA/Torroni/DALT2003torroni] Marco Alberti, Marco Gavanelli, Evelina Lamma, Paola Mello, and Paolo Torroni, Modeling interactions using social integrity constraints: a resource sharing case study. In J. A. Leite, A. Omicini, L. Sterling, and Paolo Torroni, editors, Declarative Agent Languages and Technologies, First International Workshop, DALT 2003. Melbourne, Victoria, July 15th, 2003. Workshop Notes, pages 81–96, 2003.

Abstract: Computees are abstractions of the entities that populate global and open computing environments. The societies that they populate give an institutional meaning to their interactions and define the allowed interaction protocols. Social integrity constraints represent a powerful though simple formalism to express such protocols. Using social integrity constraints, it is possible to give a formal definition of concepts such as violation, fulfillment, and social expectation. This allows for the automatic verification of the social behaviour of computees. The aim of this paper is to show by a concrete example how the theoretical framework can be used in practical situations where computees can operate. The example that we choose is a resource exchange scenario.

CONTRIBUTION TO SOCS WORKPACKAGES [WP2, WP5]: This paper draws from [IJCAI03-multistage], and it aims at showing the use of Social Integrity Constraints in a concrete application scenario. Its work has been used in some deliverables such as D5 [D5]. Some examples in the paper also aim at exploring some ideas about verification of properties, subject of WP5.

[UNIBO/Torroni/DALT2003notes] João A. Leite, Andrea Omicini, Leon Sterling, and Paolo Torroni, editors. Declarative Agent Languages and Technologies, First International Workshop, DALT 2003. Melbourne, Victoria, July 15th, 2003. Workshop Notes, pages x + 178, 2003.

CONTRIBUTION TO SOCS WORKPACKAGES [WP1-WP6]: Declarative agent languages and technologies are in the core of SOCS. Several members of the SOCS consortium have been Program Committee members. The purpose of this workshop was to provide a forum to discuss state of the art technologies, which are related to the SOCS objectives in many respects. The proceedings also include some work done by SOCS members [DALT2003torroni] with respect to WP2, but the volume is indeed related to all SOCS workpackages.

[UNIBO-DIFERRARA-ICSTM/Torroni/AMAI-01] Anna Ciampolini, Evelina Lamma, Paola Mello, Francesca Toni, and Paolo Torroni. Co-operation and competition in ALIAS: a logic framework for agents that negotiate. Computational Logic in Multi-Agent Systems. Annals of Mathematics and Artificial Intelligence, 37(1–2):65–92, 2003.

Abstract: This paper presents ALIAS, an agent architecture based on intelligent logic agents, where the main form of agent reasoning is abduction. The system is particularly suited for solving problems where knowledge is incomplete, where agents may need to make reasonable hypotheses about the problem domain and other agents, and raised hypotheses have to be consistent for the overall set of agents. ALIAS agents are pro-active, exhibiting a goal-directed behavior, and autonomous, since each one can solve problems using its own private knowledge base. ALIAS agents are also social, because they are able to interact with other agents, in order to cooperatively solve problems. The co-ordination mechanisms are modeled by means of LAILA, a logic-based language which allows to express intra-agent reasoning and inter-agent co-ordination. As an application, we show how LAILA can be used to implement inter-agent dialogues, e.g., for negotiation. In particular, LAILA is well-suited to co-ordinate the process of negotiation aimed at exchanging resources between agents, thus allowing them to execute the plans to achieve their goals.

CONTRIBUTION TO SOCS WORKPACKAGES [WP1, WP2, WP3]: This paper studies a form of coordination of reasoning which is alternative to the social approach of D5. It presents an operational framework based on abductive reasoning, which puts together the reasoning of a bunch of agents. A meta-language to define the reasoning activities of agents has been one option considered for WP1 and WP3, of which this paper can be considered background work.

[DIPISA/Bracciali/] Paolo Mancarella and Giacomo Terreni. An abductive proof procedure handling active rules. In A. Cappelli and F. Turini, eds., Proceedings of the 8th National Congress on Artificial Intelligence, AI*IA 2003, Pisa, Italy, September 23-26, 2003. LNAI 2829, pp. 105-117. Springer-Verlag.

Abstract: We present a simple, though powerful extension of an abductive proof procedure proposed in the literature, the so-called KM-procedure, which allows one to properly treat more general forms of integrity constraints than those handled by the original procedure. These constraints are viewed as active rules, and their treatment allows the integration of a limited form of forward reasoning within the basic, backward reasoning framework upon which the KM-procedure is based. We first provide some background on Abductive Logic Programming and the KM-procedure and then formally present the extension, named AKM-procedure. The usefulness of the extension is shown by means of some simple examples.

CONTRIBUTION TO SOCS WORKPACKAGES [WP3]: This paper presents advances in the theory of computational proof procedures for ALP.

[UNIBO-DIFERRARA/Alberti/D5-aiia] Marco Alberti, Marco Gavanelli, Evelina Lamma, Paola Mello, and Paolo Torroni. An Abductive Computational Model for Open Societies. In A. Cappelli and F. Turini, eds., Proceedings of the 8th National Congress on Artificial Intelligence, AI*IA 2003, Pisa, Italy, September 23-26, 2003. LNAI 2829, pp. 287-299. Springer-Verlag.

Abstract: The focus of this work is on the interactions among (possibly heterogeneous) agents that form an open society, and on the definition of a computational logic-based architecture for agent interactions. We propose a model where the society defines the allowed interaction protocols, which determine the ``socially'' allowed agent interaction patterns. The semantics of protocols can be defined by means of social integrity constraints. The main advantages of this approach are in the design of societies of agents, and in the possibility to detect undesirable behaviour. In the paper, we present the model for societies ruled by protocols expressed as integrity constraints, and its declarative semantics. A sketch of the operational counterpart is also given.

CONTRIBUTION TO SOCS WORKPACKAGES [WP2, WP3]: The paper shows the abductive interpretation of the social specification that we give for WP2; the abductive interpretation allows to implement compliance verification as an abductive proof procedure (augmented with the concept of fulfillment), which is the object of WP3.

[UNIBO/Milano/] A. Guerri and M. Milano, Exploring CP-IP based techniques for the bid evaluation in combinatorial auctions Proceedings of CP2003, Springer Verlag LNCS

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.

CONTRIBUTION TO SOCS WORKPACKAGES []

[ICSTM/Endriss/endriss-ijcai2003] Ulrich Endriss, Nicolas Maudet, Fariba Sadri, and Francesca Toni. Protocol Conformance for Logic-based Agents. In Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI-2003), Morgan Kaufmann Publishers, August 2003.

Abstract: An agent communication protocol specifies the "rules of encounter" governing a dialogue between agents in a multiagent system. In non-cooperative interactions(such as negotiation dialogues) occurring in open societies it is crucial that agents are equipped with proper means to check, and possibly enforce, conformance to protocols. We identify different levels of conformance (weak, exhaustive, and robust conformance) and explore how a specific class of logic-based agents can exploit a new representation formalism for communication protocols based on simple if-then rules in order to either check conformance a priori or enforce it at runtime.

CONTRIBUTION TO SOCS WORKPACKAGES [WP2,WP5]: Communication protocols and their representation using computational logic are amongst the main themes in WP2 ("modelling interactions between computees") of SOCS and it is in this context that this paper was written. Additionally, our techniques for verifying conformance a priori on the basis of an agent's (or computee's) specification make an important contribution to WP5 ("verifiable properties of societies of computees").

[ICSTM/Endriss/endriss2003] Ulrich Endriss, Nicolas Maudet, Fariba Sadri, and Francesca Toni. Aspects of Protocol Conformance in Inter-agent Dialogue. In Proceedings of the 2nd International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS-2003), ACM Press, July 2003. Extended Abstract.

CONTRIBUTION TO SOCS WORKPACKAGES [WP2,WP5]: This poster is a preliminary version of our paper presented at IJCAI-2003.

[ICSTM/Endriss/endriss-aamas2003] Ulrich Endriss, Nicolas Maudet, Fariba Sadri, and Francesca Toni. On Optimal Outcomes of Negotiations over Resources. In Proceedings of the 2nd International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS-2003), ACM Press, July 2003.

Abstract: We analyse scenarios in which self-interested agents negotiate with each other in order to agree on deals to exchange resources. We consider two variants of the framework, one where agents can use money to compensate other agents for disadvantageous deals, and one where this is not possible. In both cases, we analyse what types of deals are necessary and sufficient to guarantee an optimal outcome of negotiation. To assess whether a given allocation of resources should be considered optimal we borrow two concepts from welfare economics: maximal social welfare in the case of the framework with money and Pareto optimality in the case of the framework without money. We also show how conditions for optimal outcomes can change depending on properties of the utility functions used by agents to represent the values they ascribe to certain sets of resources.

CONTRIBUTION TO SOCS WORKPACKAGES [WP1,WP2,WP5]: This paper is placed at the interface between WP1 ("a logic-based model for computees") and WP2 ("modelling interactions between computees") of SOCS by showing how specific choices made at the level of a single agent (or computee) can cause a particular behaviour to emerge at the level of society. Our results provide a theoretical analysis of the resource allocation problem in open societies, which has been identified as a central scenario of interest in SOCS and has also received much attention within the Global Computing initiative in general. The paper also provides the basis for our future work on the verification of welfare-related properties of societies of computees in WP5 ("verifiable properties of societies of computees").

[ICSTM/Endriss/EndrissEtAlMFI2003] Ulrich Endriss, Nicolas Maudet, Fariba Sadri, and Francesca Toni. Resource Allocation in Egalitarian Agent Societies. In Secondes Journées Francophones sur les Modèles Formels d'Interaction (MFI-2003), Cépaduès-Éditions, May 2003.

Abstract: We introduce the notion of an egalitarian agent society and study the problem of finding an optimal allocation of resources by means of negotiation amongst the agents inhabiting such a society.

CONTRIBUTION TO SOCS WORKPACKAGES [WP1,WP2,WP5]: In this paper, we argue that the assumption, commonly made in the multiagent systems literature, that all agents are purely selfish and social welfare is only concerend with average utility is too restrictive for a range of interesting Global Computing applications. This notion of different agents or computees having different social attitudes and behaviour profiles is one of the central ideas developed in SOCS.

[DIFERRARA-UNIBO/Riguzzi/ngc-LamMelRigSto-2003] Evelina Lamma, Paola Mello, Fabrizio Riguzzi, Sergio Storari, Discovering Validation Rules from Micro-biological Data. New Generation Computing, Vol. 21 No. 2, Ohmsha and Springer Verlag, Tokyo, pp. 123-134, February 2003.

Abstract: A huge amount of data is daily collected from clinical microbiology laboratories. These data concern the resistance or susceptibility of bacteria to tested antibiotics. Almost all microbiology laboratories follow standard antibiotic testing guidelines which suggest antibiotic test execution methods and result interpretation and validation (among them, those annually published by NCCLS \cite{R2}\cite{R3}). Guidelines basically specify, for each species, the antibiotics to be tested, how to interpret the results of tests and a list of exceptions regarding particular antibiotic test results. Even if these standards are quite assessed, they do not consider peculiar features of a given hospital laboratory, which possibly influence the antimicrobial test results, and the further validation process. In order to improve and better tailor the validation process, we have applied knowledge discovery techniques, and data mining in particular, to microbiological data with the purpose of discovering new validation rules, not yet included in NCCLS guidelines, but considered plausible and correct by interviewed experts. In particular, we applied the knowledge discovery process in order to find (association) rules relating to each other the susceptibility or resistance of a bacterium to different antibiotics. This approach is not antithetic, but complementary to that based on NCCLS rules: it proved very effective in validating some of them, and also in extending that compendium. In this respect, the new discovered knowledge has lead microbiologists to be aware of new correlations among some antimicrobial test results, which were previously unnoticed. Last but not least, the new discovered rules, taking into account the history of the considered laboratory, are better tailored to the hospital situation, and this is very important since some resistances to antibiotics are specific to particular, local hospital environments.

CONTRIBUTION TO SOCS WORKPACKAGES [WP1]: This work explores techniques of machine learning and knowledge revision that could have been useful for the single computee. Since the learning and knowledge revision capability of computees has been put aside at this point, this paper has currently a limited relevance to WP1.

[DIFERRARA/Riguzzi/ngc-LamRigPer-2003] Evelina Lamma, Luiz M. Pereira, Fabrizio Riguzzi, Belief Revision via Lamarckian Evolution. New Generation Computing, Vol. 21 No. 3, Ohmsha and Springer Verlag, Tokyo, pp. 247-275, May 2003.

Abstract: We present a system for performing belief revision in a multi-agent environment. The system is called GBR (Genetic Belief Revisor) and it is based on a genetic algorithm. In this setting, different individuals are exposed to different experiences. This may happen because the world surrounding an agent changes over time or because we allow agents exploring different parts of the world. The algorithm permits the exchange of chromosomes from different agents and combines two different evolution strategies, one based on Darwin's and the other on Lamarck's evolutionary theory. The algorithm therefore includes also a Lamarckian operator that changes the memes of an agent in order to improve their fitness. The operator is implemented by means of a belief revision procedure that, by tracing logical derivations, identifies the memes leading to contradiction. Moreover, the algorithm comprises a special crossover mechanism for memes in which a meme can be acquired from another agent only if the other agent has ``accessed'' the meme, i.e. if an application of the Lamarckian operator has read or modified the meme. Experiments have been performed on the $n$-queen problem and on a problem of digital circuit diagnosis. In the case of the $n$-queen problem, the addition of the Lamarckian operator in the single agent case improves the fitness of the best solution. In both cases the experiments show that the distribution of constraints, even if it may lead to a reduction of the fitness of the best solution, does not produce a significant reduction.

CONTRIBUTION TO SOCS WORKPACKAGES [WP2]: Tthis work investigates an alternative form of communication among computees, namely communication by sharing genetic material. This line of research has been superseeded by the decision to adopt a symbolic communication language.

[UCY/Kakas/] A.C. Kakas and P. Moraitis. Argumentation based decision making for autonomous agents. In Proceedings of the 2nd International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS-2003), ACM Press, July 2003

Abstract: This paper presents an argumentation based framework to support the decision making of an agent within a modular architecture for agents. The proposed argumentation framework is dynamic, with arguments and their strength depending on the particular context that the agent finds himself, thus allowing the agent to adapt his decisions in a changing environment. In addition, in order to enable the agent to operate within an open environment where the available information may be incomplete we have integrated abduction within this argumentation framework. This is particular useful when the agent finds himself in a dilemma and hence needs additional information to resolve this. We have also developed, motivated by work in Cognitive Psychology, within the same framework an argumentation based personality theory for agents thus incorporating a dimension of individuality in the decisions of the agent.

CONTRIBUTION TO SOCS WORKPACKAGES [WP1]: This work is relevant to WP1 for the task of goal decision of a computee, as specified in D4. It considers the case where the computee's goal decision knowledge base contains a personality theory. In such a theory goals are generated and selected according to a general theory of high-level needs that they address for the computee.

[UCY/Kakas/] A.C. Kakas and P. Moraitis. Agents Negotiating via Argumentation. Technical Report.

Abstract: In this paper, we study how argumentation can be used as a basis for negotiation between autonomous agents, where negotiation strategies and policies of the different negotiating parties are represented as argumentation theories within their knowledge. We propose an argumentation based negotiation protocol where offers by the negotiating parties are linked to different arguments that they can build according to their individual negotiation strategy. The protocol exploits the added flexibility that the argumentation based representation of strategies offers and is able to take into account the different roles of agents and context of interaction, where the strength of the arguments supporting an offer can depend on these factors. The agents can adapt their negotiation strategies and offers, as their environment changes, in particular during the course of the negotiation as they exchange information. In addition, using abduction alongside with argumentation, agents can find negotiating assumptions to support an argument for an offer, thus extending the negotiation object in order to help find an agreement. To illustrate further the advantages of the approach we also study how we can capture and extend negotiation strategies within other negotiation mechanisms, in particular the two well-known mechanisms of the English auction and the bargaining with multiple parties. These expose further the main advantages of modularity and flexibility, under changes, of our argumentation based representation of negotiation strategies and the adaptability it offers in a changing environment of negotiation.

CONTRIBUTION TO SOCS WORKPACKAGES [WP1,WP2]: This work is relevant to WP1 in that it shows a flexible decision-making protocol for computees that extend the negotiation object by dealing appropriately with partial information. It is relevant to WP2 in that it also focuses on interactions among computees.

[UCY/Kakas/] N. Demetriou and A. Kakas. Argumentation with Abduction In Proceedings of the fourth Panhellenic Symposium on Logic, 2003.

Abstract: This paper presents a general approach to combining argumentation and abduction where the different uses of argumentation for preference reasoning and abduction for reasoning under incomplete information are synthesized together in an enhancing way. This integrated approach of argumentation and abduction can form the basis for encoding adaptable preference policies in the face of incomplete information from dynamic and evolving environments. The paper shows how this integration can be achieved within a suitable logic based framework and studies a simple computational model to capture the combined form of reasoning.

CONTRIBUTION TO SOCS WORKPACKAGES [WP1]: This document reports on studies for identifying the computational counterpart of reasoning with cycle theories and the goal decision capability of a computee, as specified in deliverable D4. This is based on a computational model for the underlying framework of LPwNF (Logic Programming without Negation as Failure). We illustrate this general approach with examples in LPwNF. The proposed argumentation framework and its integration with abduction has been implemented in the Gorgias system.

[UCY/Kakas/] A.C. Kakas and L. Michael. On the Qualification problem and Elaboration Tolerance To appear in Common Sense, 2003.

Abstract: In this paper we study the qualification problem in theories of reasoning about actions and change and the link of this problem to properties of representation for expressing such theories. We examine the interaction of the qualification problem with the frame and ramification problems and show how an integrated solution to these problems can be developed where the frame persistence and constraint satisfaction qualify implicitly the action effect laws of the theory. We compare the two approaches of implicit and explicit qualification of the effects laws and argue that from the point of view of knowledge representation the former has better properties pertaining to elaboration tolerance.

CONTRIBUTION TO SOCS WORKPACKAGES [WP1]: This work is directly relevant to the temporal reasoning capability of a computee, presented in deliverable D4, for its need to be able to recognize and deal with failing actions, so as to avoid obtaining inconsistencies. It provides representative examples illustrating failing actions and how such failing effects would interact with each other.

[UCY/Kakas/] Y. Dimopoulos, A.C. Kakas, L. Michael. Reasoning about Actions and Change in Answer Set Programming Submitted to LPNMR 2003.

Abstract: This paper studies computational issues related to the problem of reasoning about actions and change (RAC) by exploiting its link with the Answer Set Programming paradigm. It investigates how increasing the expressiveness of a RAC formalism so that it can capture the three major problems of frame, ramification and qualification, affects its computational complexity, and how a solution to these problems can be implemented within Answer Set Programming. Our study is carried out within the particular Language E. It establishes a link between Language E and Answer Set Programming by presenting encodings of different versions of this language into logic programs under the answer set semantics. This provides a computational realization of solutions to problems related to reasoning about actions and change, that can make use of the recent development of effective systems for Answer Set Programming. .

CONTRIBUTION TO SOCS WORKPACKAGES [WP3]: This work studies computational issues of the temporal reasoning capability of the computee and its possible computational models that are investigated in WP3.

2002

[UNIBO-ICSTM/Torroni/] F. Sadri, F. Toni, and P. Torroni, Resource reallocation via negotiation through abductive logic programming In Proc. JELIA 2002, Springer Verlag LNAI 2424, pp 419-431.

Abstract. In this paper we present a framework for agents negotiation based on abductive logic programming. The framework is based on an existing architecture for logic-based agents, and extends it by accommodating dialogues for negotiation. As an application of negotiating agents, we propose a resource-exchanging problem. The innovative contribution of this work is in the definition of an operational model, including an agent cycle and dialogue cycle, and in the results that apply in the general case of abductive agents and in the specific case of a class of agent systems.

CONTRIBUTION TO SOCS WORKPACKAGES [WP1,WP2,WP5]: Use of abductive logic programming for representing the knowledge of agents; Use of abductive logic programming for representing the communication policies of agents; Use of abductive logic programming for representing dialogues for negotiation; Specification of cycles for agents; The resource reallocation scenario; Formal specification of properties; Formal verification of properties

[UNIBO-ICSTM/Torroni/] F. Sadri, F. Toni, and P. Torroni, A multi-stage negotiation architecture for sharing resources amongst logic-based agents Short paper. In: Proceedings of UKMAS, 2002

Abstract. In earlier work we proposed a framework for agents negotiating for resources. The framework was based on abductive logic programming. It was assumed that its missing resources would have to be acquired by the agent before his plan could be carried out, but there was no explicit reference to time windows and duration of actions. Furthermore it was assumed that once a resource was acquired by an agent it was his indefinitely. In this paper we relax these assumptions to provide a richer framework for negotiation that allows better sharing of resources. We allow agent plans to be partially ordered sets of activities specified within time windows, each activity requiring certain resources. We develop negotiation protocols and policies that allow agents to strike deals for exchange of resources for agreed time windows so that (non-consumable) resources can be shared, thus allowing solutions to a wider range of resource reallocation problems.

CONTRIBUTION TO SOCS WORKPACKAGES [WP1,WP2,WP5]: Use of abductive logic programming for representing the knowledge of agents; Use of abductive logic programming for representing the communication policies of agents; Use of abductive logic programming for representing dialogues for negotiation; The resource reallocation scenario; Formal specification of properties; Formal verification of properties

[CITY-ICSTM/Toni/] F. Toni and K. Stathis, Access-as-you-need: A computational logic framework for accessing resources in artificial societies In Proc ESAW 02, International Workshop on Engineering Society in the Agent World.

Abstract. We investigate the application of abductive logic programming, an existing framework for knowledge representation and reasoning, for specifying the knowledge and behaviour of software agents that need to access resources in a global computing environment. The framework allows agents that need resources to join artificial societies where those resources are available. We show how to endow agents with the capability of becoming and ceasing to be members of societies, for different categories of artificial agent societies, and of requesting and being given or denied resources within societies. The strength of our formulation lies in combining the modelling and the computational properties of abductive logic programming for dealing with the issues arising in resource access within artificial agent societies.

CONTRIBUTION TO SOCS WORKPACKAGES [WP1,WP2]: This work studies how to endow computational-logic based agents with the capability to reason about their own and others' movements amongst open, semi-open and semi-closed societies, while trying to access resources controlled by societies.

[DIFERRARA/Alberti/] M. Alberti and E. Lamma, Synthesis of Object Models from Partial Models: A CSP Perspective In ECAI 2002. Proceedings of the 15th European Conference on Artificial Intelligence. Frank van Harmelen editor. Lyon, (France), 21-26 July 2002. Pages 116-120, IOS Press.

Abstract: In this work we present an approach for the synthesis of object models (expressed as Constraint Satisfaction Problems, CSPs) from views or partial models (expressed, in their turn, as CSPs as well). The approach we propose is general enough to consider different types of features and relationships in the views. This is achieved by introducing the notion of model representation, where features, relationships and their domains are expressed. The (complete) model can be synthesized through a proper algorithm, which provides a labeling between the (complete) model and the partial models' components. The generated CSP representing the synthesized model must satisfy (or, better, entail) any constraint among features and any relationship occurring in each partial model. The framework is applied for synthesizing object models (i.e., CSP descriptions). We provide two basic approaches for synthesizing a minimal or a correct model, and we experiment them by considering some case studies in artificial vision.

CONTRIBUTION TO SOCS WORKPACKAGES [WP1] The work is relevant to WP1 in that performing synthesis of different descriptions of the same object is a potentially useful reasoning capability for a computee; in particular, it can help to build a representation of an object from distinct sensing actions.

[DIFERRARA/Gavanelli/] @INPROCEEDINGS{cp-ai-or02, author = {Marco Gavanelli}, title = {An implementation of {Pareto} Optimality in {CLP(FD)}}, booktitle = {CP-AI-OR - International Workshop on Integration of AI and OR techniques in Constraint Programming for Combinatorial Optimisation Problems}, year = {2002}, editor = {Narendra Jussien and Fran\c{c}ois Laburthe}, address = {Le Croisic, France}, month = mar # " 25 -- 27", organization = {Ecole des Mines de Nantes}, pages = {49-64}, url = "http://cpaior.emn.fr:8000/", ps = "http://www.ing.unife.it/docenti/MarcoGavanelli/cp-ai-or02.ps.gz", }

Abstract. The Constraint Problems usually addressed fall into one of two models: the Constraint Satisfaction Problem (CSP) and the Constraint Optimization Problem (COP). However, in many real-life applications, more functions should be optimized at the same time, and solutions are ranked by means of a Partial Order. In problems where two or more functions should be optimized at the same time (Multi-Criteria Optimization, or Pareto optimality) the possible solutions of the CSP are ranked by means of a partial order. In this paper, we propose an algorithm for solving Pareto Optimality problems in CLP($FD$). The algorithm is complete and does not make any assumption on the structure of the constraints. It exploits Point Quad-Trees for the representation of the set of solutions, in order to access the data structure efficiently. In this paper, an implementation of the algorithm for multi-criteria optimization is provided in a CLP(FD) language. It is important for SOCS, as both the society and the computees are implemented on top of a CLP(FD) language, so they could employ the provided algorithm for computing the Pareto optimal solutions given a set of objective functions.

CONTRIBUTION TO SOCS WORKPACKAGES []

[DIFERRARA/Gavanelli/] @ARTICLE{AIxIAnotizie2002, author = {Marco Gavanelli}, title = {An Algorithm Computing the {Pareto} Frontier in Constraint Satisfaction Problems}, journal = {AI*IA Notizie}, year = {2002}, volume = {{XV}}, number = {2}, pages = {15--23}, month = Jun, url = "http://www.dsi.unifi.it/AIIA/indice2002.htm" }

Abstract. Real-life problems often exhibit a multi-criteria structure: user requirements are many and possibly conflicting. In combinatorial optimization, criteria are functions, ranging on the set of possible solutions. A widely used approach suggests to compute a weighted sum of the different criteria. Unluckily, deciding the weights beforehand is not always straightforward; moreover, the weighted sum approach often provides extreme solutions, while the user usually prefers balanced solutions. Since the set of Pareto optimal solutions can be huge and the algorithm needs to access them efficiently, we propose to arrange them in a suitable data structure, namely Point Quad-Trees. Experimental results show the effectiveness of the proposed method.", } In this paper, we provide an algorithm that computes the whole Pareto Frontier in Constraint Satisfaction Problems. The algorithm successfully employs spatial data structures (namely, Quad-Trees) to efficiently store the set of non-dominated solutions. Concerning SOCS, it can be used in the society to provide a set of expectations with a minimal set of violations. Another application could be the resource allocation (possibly, through negotiation). In such cases, distinguishing the Pareto optimal allocations can be important, possibly in order to provide some notions of fairness amongst computees.

CONTRIBUTION TO SOCS WORKPACKAGES []

[DIFERRARA-UNIBO/Gavanelli/] @InProceedings{FroCoS2002, author = "Marco Gavanelli and Evelina Lamma and Paola Mello and Michela Milano", title = "Exploiting constraints for domain managing in {CLP(FD)}", booktitle = "4th International Workshop on Frontiers of Combining Systems - FroCoS'2002", year = "2002", month = Apr # " 8-10", address = "Santa Margherita Ligure, Italy", publisher = "Springer Verlag", editor = "Alessandro Armando", series = "Lecture Notes in Artificial Intelligence", volume = "2309", url = "http://www.mrg.dist.unige.it/conferences/frocos2002/", pages = {177-191}, }

Abstract. Constraint Logic Programming languages on Finite Domains CLP(FD) provide a declarative framework for dealing with problems in Artificial Intelligence (AI). However, in many applications, domains are not known at the beginning of the computation and must be computed. The domain computation can be time-consuming, since elements can be retrieved through an expensive acquisition process from the outer world. In this paper, we introduce a CLP language that treats domains as first-class objects, and allows the definition of domains through constraints in a CLP(FD) environment. We define operations and properties on variables and domains. The language can be implemented on top of different CLP systems, exploiting thus different semantics for domains. We state the specifications that the employed system should provide, and we show that two different CLP systems (Conjunto and \{log\}) can be effectively used.", } This paper provides a language based on Computational Logics that exploits constraint propagation for the acquisition of information from the environment. This is important, among the others, for planning applications: planning is one of the most successful applications of constraint languages and an agent's planning activity must interact with sensors and refer to data taken from the outer world.

CONTRIBUTION TO SOCS WORKPACKAGES []

[DIFERRARA/Gavanelli/] @InProceedings{ecai2002, author = "Marco Gavanelli", title = "An Algorithm for Multi-Criteria Optimization in {CSPs}", booktitle = "ECAI 2002. Proceedings of the 15th European Conference on Artificial Intelligence", year = "2002", month = Jul # " 21-26", address = "Lyon, France", publisher = "IOS Press", editor = "Frank van Harmelen", url = "http://ecai2002.univ-lyon1.fr/", pages = {136--140}, }

Abstract: Constraint Satisfaction and Optimization are important areas of Artificial Intelligence. However, in many real-life applications, more functions should be optimized at the same time; the user needs to be provided a set of solutions and a posteriori choose the most preferable. In this paper, we propose an algorithm for solving Multi-Criteria Optimization problems in this setting. The algorithm is complete, i.e., it finds all the non-dominated solutions, and does not make any assumption on the structure of the constraints nor on the type of the objective functions. It exploits Point Quad-Trees for the representation of the non-dominated frontier, in order to efficiently access the data. We describe the implementation and give experimental results showing that our algorithm outperforms widely used methods. This paper provides an algorithm for multi-criteria optimization in Constraint Satisfaction Problems. The algorithm is based on the so-called Optimization NoGoods. The algorithm is complete, in the sense that it is able to provide the whole non-dominated frontier of Pareto-optimal solutions. Comparison with a widely used method is provided. This study is important from the society viewpoint. It could be important for the society to provide a set of expectations such that the violated ones are minimal, or a set which is minimal with respect to set inclusion.

CONTRIBUTION TO SOCS WORKPACKAGES []

[CITY/Stathis/] K. Stathis, O. deBruijn, S. Macedo: Living memory: agent based information management for connected local communities. In Journal of Interacting with Computers, vol 14(6), Dec. 2002.

Abstract: We investigate the application of multi-agent systems to develop intelligent information interfaces for connected communities, a class of computer applications aimed at enhancing the way people interact and socialise in geographically co-located communities such as neighbourhoods. In this context, we study the problem of providing effective information management in support of social interaction when a diverse range of computing devices is employed. The novelty of our approach is based on combining innovative interactive devices with a framework based on agent roles in order to support the effective flow of community-related content for the people of a given locality. In particular, we have integrated existing techniques for information retrieval and filtering with measures of content popularity, to ensure that documents in the community system are optimally available. After reporting on the potential presence of the system in the community, we report on the development of a framework for multi-agent systems in which agents provide a number of services aimed at facilitating personalised and location-dependent information access to members of the community. We also present a summary of the results of an expert evaluation of the information flow resulting from the communication between agents, and a user-evaluation of the information dissemination facilities provided by the system.

CONTRIBUTION TO SOCS WORKPACKAGES []

[CITY/Stathis/] Wenjin Lu and Kostas Stathis. Gameplan: Adversarial Planning in Multi-Agent Systems--A Preliminary Report Department of Computing, School of Informatics, City University, London {lue,~kostas}@soi.city.ac.uk

Abstract. We study the problem of adversarial planning in the context of multi-agent system environments. In this context we present Gameplan, an algorithm that takes into account the open and unpredictable nature of such environments. Unpredictability manifests itself here as follows: what an agent assumes to hold at one stage of its interaction with the environment may change as a consequence of the unpredictable, and possibly adversarial, actions of other agents in that environment; such actions take place at later stages of the interaction. Gameplan is based on Graphplan, a general purpose and efficient planner for STRIPS like domains, where a plan is a compact structure represented as a graph specifying the flow of properties holding as a result of various actions taking place in the environment. Like Graphplan, Gameplan has the property that useful information for constraining search can quickly be propagated through the graph as it is being built. Unlike Graphplan, however, Gameplan constructs the planning graph by labelling each action level with the agent who will eventually execute this action, while the solution extraction is adapted to one that can be handled by a conditional planer to deal with the adversarial and uncertain behaviours of other agents in the environment.

CONTRIBUTION TO SOCS WORKPACKAGES [WP1, WP2]: The planning capability of agents is a main concern in the KGP model proposed in SOCS. This paper presents a preliminary research on the adversarial planning in multi-agetn system.

[ICSTM/Endriss/EndrissEtAlUKMAS2002-protocols] Ulrich Endriss, Nicolas Maudet, Fariba Sadri, and Francesca Toni. Communication Protocols for Logic-based Agents. In Proceedings of the 5th UK Workshop on Multiagent Systems (UKMAS-2002), December 2002. Extended Abstract.

CONTRIBUTION TO SOCS WORKPACKAGES [WP2,WP5]: This workshop poster is a preliminary version of our paper presented at IJCAI-2003.

[ICSTM/Endriss/endriss2002] Ulrich Endriss, Nicolas Maudet, Fariba Sadri, and Francesca Toni. Conditions for Optimal Outcomes of Negotiations about Resources. In Proceedings of the 5th UK Workshop on Multiagent Systems (UKMAS-2002), December 2002.

Abstract: We analyse scenarios in which individually rational agents negotiate with each other in order to agree on deals to exchange resources. We consider two variants of the framework, one where agents can use money to compensate other agents for disadvantageous deals, and another one where this is not possible. In both cases, we analyse what types of deals are necessary and sufficient to guarantee an optimal outcome of negotiations. We also show how these conditions can change depending on properties of the utility functions used by agents to represent the values they ascribe to certain sets of resources.

CONTRIBUTION TO SOCS WORKPACKAGES [WP1,WP2,WP5]: This workshop paper is a preliminary version of our paper presented at AAMAS-2003.

[DIPISA/Bracciali/] Bracciali A., Brogi A., Ferrari G. and Tuosto E. Security and Dynamic Compositions of Open Systems. In H.R. Arabnia editor, Proc. of the International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA02), pages 1372-1377, vol III. Las Vegas, NV, 2002, CSREA Press (ISBN 1-892512-89-0).

Abstract: Designing software by coordinating components is becoming a pervasive software development methodology. This practice of building (distributed) applications is currently supported by several industrial standards competing in the marketplace. Moreover, Internet facilitates the distributions of services to be embedded into applications. In this highly dynamic scenario, we discuss a methodology to formally describe the (behavioural) features of the single components and to reason about the properties of the assembled applications.

CONTRIBUTION TO SOCS WORKPACKAGES [WP2]: This work investigates the problem of software compositions in terms of autonomous entities in a dynamic scenario. Such a general problem occurs in MAS architectures.

[DIPISA/Bracciali/] Baldan P., Bracciali A. and Bruni R. Bisimulation by Unification. In H. Kirchner, C. Ringeissen editors, Proc. 9th International Conference on Algebraic Methodology And Software Technology (AMAST'2002), pages 254-270. Reunion Island, 2002. Lecture Notes on Computer Science 2422, Springer.

Abstract: We propose a methodology for the analysis of open systems based on process calculi and bisimilarity. Open systems are seen as coordinators (terms with place-holders), that evolve when suitable components (closed terms) fill in their place-holders. The distinguishing feature of our approach is the definition of a symbolic operational semantics for coordinators that exploits spatial/modal formulae as labels of transitions and avoids the universal closure of coordinators wrt all components. Two kinds of bisimilarities are then defined, called strict and large, which differ in the way formulae are compared. Strict bisimilarity implies large bisimilarity which, in turn, implies the one based on universal closure. Moreover, for process calculi in suitable formats, we show how the symbolic semantics can be defined constructively, using unification. Our approach is illustrated on a toy process calculus with ccs-like communication within ambients.

CONTRIBUTION TO SOCS WORKPACKAGES [WP2]: This work investigates the problem of software compositions in open systems, of whcih MAS architectures in general are a particular case.

[DIPISA/Bracciali/] J. J. Alferes, A. Brogi, J.A. Leite, L.M. Pereira. Evolving Logic Programs. In Proc. JELIA 02, 8th European Conference on Logics in AI, September 2002.

Abstract: Despite Logic Programming has often been considered not properly adequate for modeling dynamic changes in knowledge bases, we show in this paper how generalised logic programs can properly express knowledge base updates. We define a language, called EVOLP (after EVolving Logic Program), and provide it with a model-theoretic characterisation of the possible evolutions of EVOLP programs. Evolutions can be motivated both by internal updates as well as external updates, modeling the relations of a program with the environment where it is executed.

CONTRIBUTION TO SOCS WORKPACKAGES [WP1,WP2]: The work proposes a logic-programming based approach to coping with evolving scenarios. This is a relevant aspect of the life of a computee and the society in which it operates.

[UCY/Kakas/] A.C. Kakas and P. Moraitis. Argumentative Agent Deliberation, Roles and Context In Proceedings of CLIMA02. Electronic Notes in Theoretical Computer Science Vol. 70, No 5, 2002.

Abstract: This paper presents an argumentation based framework to support an agent's deliberation process for drawing conclusions under a given policy. The argumentative policy of the agent is able to take into account the roles agents can have within a context pertaining to an environment of interaction. The framework uses roles and context to define policy preferences at different levels of deliberation allowing a modular representation of the agent's knowledge that avoids the need for explicit qualification of the agent's decision rules. We also employ a simple form of abduction to deal with the incompleteness and evolving nature of the agent's knowledge of the external environment and illustrate how an agent's self deliberation can affect the mode of interaction between agents. The high degree of modularity of the framework gives it a simple computational model in which the agent's deliberation can be naturally implemented.

CONTRIBUTION TO SOCS WORKPACKAGES [WP1]: This work is directly relevant to WP1 for the task of goal decision, as specified in D4. It considers adaptability issues and enables the straighforward incorporation of roles in the behaviour of a computee.

[UCY/Kakas/] A.C. Kakas and P. Moraitis. Argumentative Deliberation for Autonomous Agents. In Proceedings of the ECAI02 workshop on Computational Models of Natural Argumentation, pp. 65-74, 2002.

Abstract: We have developed a general framework of argumentation and abduction within which the computee can represent in a flexible and modular way its various decision policies. This framework captures in a natural way roles and context and allows adaptability in the decision making of a computee in the face of a dynamically changing environment part of which maybe unknown to the computee. Within the same framework a computational personality theory for a computee is developed and shown how this affects its overall decision-making.

CONTRIBUTION TO SOCS WORKPACKAGES [WP1]: This work is relevant to WP1 for the tasks of goal and plan decision of a computee and the definition of cycle theories of behaviour, as discussed in deliverable D4.

[UCY/Kakas/] A.C. Kakas and L. Michael. Modeling Complex Domains of Reasoning about Action and Change In Proceedings of the 9th International Workshop on Non-Monotonic Reasoning, NMR'2002, pp. 380-388, Toulouse, France, 2002.

Abstract: This paper studies the problem of modeling complex domains of actions and change within high-level action description languages. We investigate two main issues of concern: (a) can we represent complex domains that capture together different problems such as ramifications, non-determinism and concurrency of actions, at a high-level, close to the given natural ontology of the problem domain and (b) what features of such a representation can affect, and how, its computational behaviour. The paper describes the main problems faced in this representation task and presents the results of an empirical study, carried out through a series of controlled experiments, to analyze the computational performance of reasoning in these representations. The experiments compare different representations obtained, for example, by changing the basic ontology of the domain or by varying the degree of use of indirect effect laws through domain constraints. This study has helped to expose the main sources of computational difficulty in the reasoning and suggest some methodological guidelines for representing complex domains. Although our work has been carried out within one particular high-level description language, we believe that the results, especially those that relate to the problems of representation, are independent of the specific modeling language.

CONTRIBUTION TO SOCS WORKPACKAGES [WP1]: The paper examines problems related to modelling effectively large domains of reasoning about action and change. This work is directly relevant to the KGP model of a computee presented in deliverable D4 for (a) its need to maintain a view of (and reason about) its changing environment and (b) conditional planning with sensing actions when the computee has incomplete information about its environment.

[UNIBO/Milano/] M. Milano and A. Roli. On the relation between complete and incomplete search an informal discussion. UNIBO In Proc. CP-AI-OR'02, Le Croisic (France), March 2002.

Abstract: In this paper, we propose a variant of the LDS strategy, called Climbing Discrepancy Search (CDS) by underlying similarities and differences with a well known metaheuristic strategy called Variable Neighborhood Descent (VND). LDS in this setting can be seen as a bridge between tree and local search. We then argue that this process of comparing LDS with metaheuristics can lead to many different variants of LDS that can be used to exhaustively explore different neighborhoods and different regions of the search landscape. A discussion on open perspectives is presented.

CONTRIBUTION TO SOCS WORKPACKAGES []

[UNIBO/Roli/] A. Roli: Impact of structure in parallel local search for SAT. UNIB In Proc. SAT 2002, Cincinnati, Ohio, USA, May 2002.

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 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.

CONTRIBUTION TO SOCS WORKPACKAGES []

[UNIBO-DIFERRARA/Ciampolini/] A. Ciampolini, E. Lamma, P. Mello, and P. Torroni. Coordinating the Safe Execution of Tasks in a Constrained Multi-Agent System.Tech. Rep. DEIS-LIA-01-009, Univ. of Bologna (Italy), 2001. LIA Series no. 53. Presented at AAMAS'02 Workshop on Distributed Constraint Reasoning (DCR'02). Also published as a short paper in Proc. AAMAS'02, Bologna (Italy), ACM, July 2002

Abstract: In this paper tackles 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, a formalism to express the coordination of tasks, (where the tasks represent services) is introduced. This formalism could be used in association 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 paper proves that the operational semantics is correct and complete with respect to the agent denotation.

CONTRIBUTION TO SOCS WORKPACKAGES [WP2]: This paper introduces a logic-based way to coordinate and verificate agents behavior which is alternative to the social approach of D5.

[UNIBO-DIFERRARA/Ciampolini/] A. Ciampolini, E. Lamma, P. Mello, and P. Torroni. A Proof System for the Safe Execution of Tasks in Multi-Agent Systems In: Proceedings of the 8th European Conference on Logics in Artificial Intelligence (JELIA'02), Springer-Verlag LNAI 2424, 2002, pp. 14-26.

Abstract: The paper proposes an operational semantics based on a proof calculus for providing the consistent execution of tasks in a constrained multi-agent setting. The agent model presented is abstracted from previous work on abductive logic agents, and it is generalized in the paper. The contribution of this work is two-fold. Firstly, a formalism and an operational semantics is introduced, to express the way agents can coordinate their requests of services, and to verify that they do not collide with each other's conditions. Then, we show that such operational semantics can be used to verify the correct execution of multiple, possibly conflicting tasks, in dynamic and adaptive systems.

CONTRIBUTION TO SOCS WORKPACKAGES [WP2]: The proposed proof represent a formal approach for the coordination and verification of agents behavior which could be considered a less general alternative to the social approach proposed in D5.

[UNIBO-DIFERRARA/Ciampolini/] A. Ciampolini, P. Mello, and S. Storari. Distributed medical diagnosis with abductive logic agents. UNIBO Tech. Rep. DEIS-LIA-02-003, Univ. of Bologna (Italy), 2002. LIA Series no. 56. Presented at ECAI'02 Workshop on Agents Applied in Health Care, July 2002.

Abstract: This work describes the application of a multi-agent system for medical diagnosis. This problem is faced by extending the ALIAS coordination mechanisms towards probabilistic abduction. In this way, several (possibly partial/multiple) diagnosis obtained by distinct medical agents can be merged into a final set of abductive diagnosis, each marked with a probability value that allows the selection of the most plausible one.

CONTRIBUTION TO SOCS WORKPACKAGES [WP2]: As in D5, agents interaction is grounded on an abductive mechanism, that guarantees the consistence of obtained diagnosis w.r.t some constraints. The association of probabilities to abducibles could be of interest for D5, as a way of extending the society in order to attribute some degree of uncertainty to events, e.g. in a possibly untrusted environment.

Back to : Main Page