SOCS publications (not up-to-date)

## 2004

[UNIBO-DIFERRARA/Alberti/AlbertiCILC2004] M. Alberti, M. Gavanelli, E. Lamma, P. Mello, P. Torroni. Abduction with Hypotheses Confirmation. In Atti del Diciannovesimo incontro annuale dell'Associazione Italiana GULP (CILC'04). June 2004.

Abstract: Abduction can be seen as the formal inference corresponding to human hypothesis making. It typically has the purpose of explaining some given observation. In classical abduction, hypotheses could be made on events that may have occurred in the past. In general, abductive reasoning can be used to generate hypotheses about events possibly occurring in the future (forecasting), or may suggest further investigations that will confirm or disconfirm the hypotheses made in a previous step (as in scientific reasoning). We propose an operational framework based on Abductive Logic Programming, which extends existing frameworks in many respects, including accommodating dynamic observations and hypothesis confirmation.

CONTRIBUTION TO SOCS WORKPACKAGES [WP2,WP3]: The paper presents the SCIFF abductive framework and proof procedure, researched in WP2 and WP3 to formalize compliance of computee behaviour to agent interaction protocols, in the more general perspective of the generation and confirmation of hypotheses in hypothetical reasoning.

[UNIBO-DIFERRARA/Chesani/SOCS-SI-demo] M. Alberti, F. Chesani, M. Gavanelli, E. Lamma, P. Mello, P. Torroni. A Demonstration of SOCS-SI for AAMAS'04. In AAMAS'04 Conference, Demo Session, and Diciannovesimo Incontro dell'Associazione Italiana GULP (CILC'04), June-July 2004.

Abstract: The paper describes the demonstration of the SOCS-SI tool that will be given in the Demo session of AAMAS '04 Conference. The demonstration will show the concrete example of a "first price sealed bid" auction.

CONTRIBUTION TO SOCS WORKPACKAGES [WP4,WP6]: The demonstration focuses on the SOCS-SI tool, which was developed in WP4 as the verifier of compliance of computee interaction to interaction protocols, and will be used in WP6 for experimentation.

[UNIBO/DIFERRARA/Torroni/tapocs04-torroni] P. Torroni, M. Alberti, F. Chesani, M. Gavanelli, E. Lamma, P. Mello. In Proceedings of the 13th IEEE International workshops on Enabling technologies: Infrastructures for collaborative enterprises (WETICE-2004), 2nd International Workshop "Theory and practice of open computational systems (TAPOCS). Modena, Italy, June 14, 2004. IEEE Press. To appear.

Abstract: An important challenge posed by the design of open information systems concerns the choice of suitable methods to harness their complexity and to guarantee the correctness of their behaviour. In recent times, logic programming has been proposed as a powerful technology, formal and declarative, for the specification and verification of agent based and open systems. In this work, we focus on the interaction design. We base our approach on a logic-based formalism, which can be used to define the semantics of agent communication languages and interaction protocols. We advocate its use within a more general framework, drawing a design methodology which encompasses the specification of the interaction space and of its desired properties, and their verification.

CONTRIBUTION TO SOCS WORKPACKAGES [WP2,WP3,WP4,WP5]: The paper proposes a method for the design of the interaction space in multiagent system, by exploiting the declarative abductive framework defined in WP2, and its operational counterpart, defined in WP3 and implemented in WP4. It also explores the possibility of using this framework to prove properties of multiagent systems, which is subject of WP5.

[DIFERRARA/Alberti/alberti-lamma-unif04] M.Alberti, E.Lamma. Inference with arbitrarily quantified variables: preliminary report. In Proceedings of the 18th International Workshop on Unification (UNIF 2004), Cork, July 2004.

Abstract: First order reasoning requires to solve unification problems. Most first-order unification algorithms have been designed to solve existentially quantified sets of equations, but also more general settings where equations need to be solved under a mixed quantifier prefix have been considered in the literature. In this work, we discuss the case of inferences with arbitrarily quantified variables. We first introduce arbitrary quantifiers (possibly mixed) over variables as intensional notation standing for a corresponding extensional, semantical counterpart. Unification of variables (possibly differently quantified) is then mapped into corresponding operations over these extensional counterparts. In the paper, we also give soundness results for the proposed approach, and show how resolution can be covered in the framework.

CONTRIBUTION TO SOCS WORKPACKAGES [WP3,WP4]: The paper introduces and proves sound an inference rule applicable to a first order theory with arbitrarily quantified variables: this is relevant to the \sciff proof procedure, which, both in its definition and in its implementation, needs to cope with formulae where existential and universal quantifiers (possibly restricted) are applied to variables.

[UNIBO-DIFERRARA/Lamma/deonSOCS-aiia04] Marco Alberti, Marco Gavanelli, Evelina Lamma, Paola Mello, Giovanni Sartor, Paolo Torroni. In Alfredo Milani, ed., Atti della Conferenza Italiana sui Sistemi Intelligenti CISI-04, 9th AI*IA Convention. Workshop Agenti e Vincoli: Modelli e Tecnologie per Dominare la Complessità. Perugia, Italy, 2004. Morlacchi Editore, Perugia. ISBN 88-89422-09-2.

Abstract: A number of approaches to agent society modeling can be found in the Multi-Agent Systems literature which exploit (variants of) Deontic Logic. In this paper, after briefly mentioning related approaches, we focus on the Computational Logic (CL) approach for society modeling developed within the UE IST-2001-32530 Project (named SOCS), where obligations and prohibitions are mapped into abducible predicates (respectively, positive and negative expectations), and norms ruling the behavior of members are represented as abductive integrity constraints. We discuss how this abductive framework can deal with Deontic Logic concepts, by introducing additional integrity constraints.

CONTRIBUTION TO SOCS WORKPACKAGES [WP2,WP3]: The paper proposes a mapping of deontic operators onto the abducibles of the SCIFF abductive framework, in order to link the deontic-based agent specification framework to ours, at both the declarative semantics (WP2) and operational counterpart (WP3) levels.

[UNIBO-DIFERRARA/Milano/aste-bofe-aiia04] Marco Alberti, Federico Chesani, Marco Gavanelli, Alessio Guerri, Evelina Lamma, Paola Mello, Paolo Torroni. Expressing Interaction in Combinatorial Auction through Social Integrity Constraints. In Alfredo Milani, ed., Atti della Conferenza Italiana sui Sistemi Intelligenti CISI-04, 9th AI*IA Convention. Workshop Agenti e Vincoli: Modelli e Tecnologie per Dominare la Complessità. Perugia, Italy, 2004. Morlacchi Editore, Perugia. ISBN 88-89422-09-2

Abstract: Combinatorial Auctions are an attractive application of intelligent agents; their applications are countless and are shown to provide good revenues. In a combinatorial auction, bidders can bid not only on single items, but also on sets of items; in this way, bidders can express complementarity of the goods offered in the auction. On the other hand, the computational complexity of the solving process (the Winner Determination Problem, WDP) is $NP$-hard; this delayed their practical use. Recently, efficient solvers have been applied to the WDP, so the framework starts to be viable. A second issue, common also to many other agent systems, is trust: in order for an agent system to be used, the users must trust both their representative and the other agents inhabiting the society: malicious agents must be found, and their violations discovered. The SOCS project addresses such issues, and provided a language, the social integrity constraints, for defining the allowed interaction moves, together with a proof-procedure (called SCIFF) able to detect violations. In this paper we show how to write a protocol for the combinatorial auctions by using social integrity constraints. In the devised protocol, the auctioneer interacts with an external solver that finds a solution to the winner determination problem.

CONTRIBUTION TO SOCS WORKPACKAGES [WP2,WP4,WP6]: The paper presents the modelling of a concrete scenario (combinatorial auction) in the SOCS social framework, defined in WP2. It also shows the results of the experimentation (relevant to WP6) of this scenario using the SOCS-SI tool, developed for WP4.

[CITY/Stathis/] K. Stathis, A. Kakas, W. Lu, N. Demetriou, U. Endriss, A. Bracciali "PROSOCS: a platform for programming software agents in computational logic" To appear in Proceedings 4th Symposium from Agent Theories to Agent Implementations, AT2AI04, Vienna, April 2004.

Abstract: We present the design and implementation of PROSOCS, a platform supporting the programming of software agents that have a mind'' and a body''. The mind reasons autonomously and logically via a collection of logic theories with generic functionality, developed using various extensions of logic programming, and controls the overall behaviour of the agent via a cycle theory'' that specifies preferred patterns of operation. The body, on the other hand, provides sensors and effectors for the mind to be able to access and change the environment in which the agent is situated. PROSOCS has been developed using Prolog - to program the functionality of the mind, Java - to program the functionality of the body, and the Peer-to-Peer system JXTA - to provide the functionality required for agent bodies to communicate and interact in an open distributed environment.

CONTRIBUTION TO SOCS WORKPACKAGES []

[ICSTM/Endriss/EndrissEtAlAAC2004] Ulle Endriss, Nicolas Maudet, Fariba Sadri, and Francesca Toni. Logic-based Agent Communication Protocols. In Advances in Agent Communication, LNAI 2922, Springer-Verlag, 2004.

Abstract: An agent communication protocol specifies the rules of interaction governing a dialogue between agents in a multiagent system. In non-cooperative interactions (such as negotiation dialogues) occurring in open societies the problem of checking an agent's conformance to such a protocol is a central issue. We identify different levels of conformance (weak, exhaustive, and robust conformance) and explore, for a specific class of logic-based agents and an appropriate class of protocols, how to check an agent's conformance to a protocol a priori on the basis of the agent's specification.

CONTRIBUTION TO SOCS WORKPACKAGES [WP2,WP5]: This paper provides a consolidation of our work on shallow protocols, the representation of protocols using simple integrity constraints, levels of conformance, and a priori conformance checking carried out in the first two years of the project. It extends our main paper in this area (IJCAI-2003) by presenting additional results on exhaustive conformance checking and by discussing possible extensions of our methodology to non-shallow protocols. Like the IJCAI-2003 paper, it is particularly relevant to WP2 and WP5.

[ICSTM/Endriss/EndrissEtAlARW2004] Ulle Endriss, Paolo Mancarella, Fariba Sadri, Giacomo Terreni, and Francesca Toni. Abductive Logic Programming with CIFF. In Proceedings of the 11th Workshop on Automated Reasoning (ARW-2004), March 2004. Extended Abstract.

Abstract: This extended abstract introduces the CIFF proof procedure for abductive logic programming with constraints and its implementation.

CONTRIBUTION TO SOCS WORKPACKAGES [WP3,WP4]: The definition of the CIFF procedure is one of the central contributions of WP3, which deals with the computational counterparts of the formal models developed in the first phase of the project. In particular the planning, reactivity and temporal reasoning capabilities of computees have been modelled using abductive logic programming with constraints and CIFF is a suitable proof procedure for this formalism. The paper also relevant to WP4, because it announces our implementation of CIFF.

[ICSTM/Endriss/EndrissEtAlTR2004] Ulle Endriss, Paolo Mancarella, Fariba Sadri, Giacomo Terreni, and Francesca Toni. The CIFF Proof Procedure: Definition and Soundness Results. Technical Report 2004/2, Department of Computing, Imperial College London, May 2004.

Abstract: We introduce a new proof procedure for abductive logic programming and prove two soundness results. Our procedure extends that of Fung and Kowalski by integrating abductive reasoning with constraint solving and by relaxing the restrictions on allowed inputs for which the procedure can operate correctly. An implementation of our proof procedure is available and has been applied successfully in the context of multiagent systems.

CONTRIBUTION TO SOCS WORKPACKAGES [WP3]: The CIFF proof procedure for abductive logic programming with constraints is one of the central contributions of WP3. This paper presents the procedure in detail and contains the proofs for our soundness results for this procedure.

[ICSTM/Endriss/EndrissMaudetAAMAS2004] Ulle Endriss and Nicolas Maudet. On the Communication Complexity of Multilateral Trading. In Proceedings of the 3rd International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS-2004), IEEE Computer Society Press, July 2004.

Abstract. We study the complexity of a multilateral negotiation framework where autonomous agents agree on a sequence of deals to exchange sets of discrete resources in order to both further their own goals and to achieve a distribution of resources that is socially optimal. When analysing such a framework, we can distinguish different aspects of complexity: How many deals are required to reach an optimal allocation of resources? How many communicative exchanges are required to agree on one such deal? How complex a communication language do we require? And finally, how complex is the reasoning task faced by each agent? This paper presents a number of results pertaining, in particular, to the first of these questions.

CONTRIBUTION TO SOCS WORKPACKAGES [WP5]. This paper continues our work on microeconomic properties of societies of computees, which is one of the classes of verifiable properties that we have identified as being of particular interest to our work on WP5.

[ICSTM/Endriss/EndrissEtAlCILC2004] Ulle Endriss, Paolo Mancarella, Fariba Sadri, Giacomo Terreni, and Francesca Toni. Abductive Logic Programming with CIFF: Implementation and Applications. In Proceedings of the Italian Conference on Computational Logic (CILC-2004), June 2004.

Abstract. We describe a system implementing a novel extension of Fung and Kowalski's IFF abductive proof procedure which we call CIFF, and its application to realise intelligent agents that can construct (partial or complete) plans and react to changes in the environment. CIFF extends the original IFF procedure in two ways: by dealing with constraint predicates and by dealing with non-allowed abductive logic programs.

CONTRIBUTION TO SOCS WORKPACKAGES [WP3,WP4]. This paper is relevant to WP4 as it describes the implementation of the CIFF proof procedure used in the PROSOCS platform. It is also relevant to WP3, because it discusses our approach to partial planning, which is based reasoning with CIFF.

[UNIBO/Milano/] M.Milano and A.Roli. MAGMA: A Multiagent Architecture for Metaheuristics. IEEE Trans. on Systems, Men and Cybernetics - Part B, Vol.34, Issue 2, April 2004.

Abstract: In this work we introduce a multiagent architecture (MAGMA, MultiAGent Metaheuristics Architecture) conceived as a conceptual and practical framework for metaheuristic algorithms. Metaheuristics can be seen as the result of the interaction among different kinds of agents: the basic architecture contains three levels each hosting one or more agents. Level-0 agents build solutions, level-1 agents improve solutions and level-2 agents provide the high level strategy. In this framework, classical metaheuristic algorithms can be smoothly accommodated and extended. The basic three level architecture can be enhanced with the introduction of a fourth level of agents, level-3 agents, coordinating lower level agents. With this additional level, MAGMA can also describe, in a uniform way, cooperative search and, in general, any combination of metaheuristics. We describe the whole architecture, the structure of agents in each level in terms of tuples, and the structure of their coordination as a Labelled Transition System. We propose this perspective with the aim to achieve a better and clearer understanding of metaheuristics, obtain hybrid algorithms, suggest guidelines for a software engineering-oriented implementation and for didactic purposes. Some specializations of the general architecture will be provided in order to show that existing metaheuristics (e.g., GRASP, Ant Colony Optimization, Iterated Local Search, Memetic Algorithms) can be easily described in our framework. We describe cooperative search and large neighborhood search in the proposed framework exploiting level-3 agents. We show also that a simple hybrid algorithm, called Guided Restart Iterated Local Search, can be easily conceived as a combination of existing components in our framework.

CONTRIBUTION TO SOCS WORKPACKAGES []

[UCY-DIPISA/Kakas/] Antonis C. Kakas, P. Mancarella, F. Sadri, K. Stathis and F. Toni, The KGP Model of Agency

Abstract: This paper presents a new model of agency, called the KGP (Knowledge, Goals and Plan) model. This model draws from the classic BDI model and proposes a hierarchical agent architecture with a highly modular structure that synthesises together various reasoning and sensing capabilities of the agent in an open and dynamic environment. The novel features of the model include: its innovative use of Computational Logic (CL) in a way that facilitates both the formal analysis of the model and its computational realisability directly from the high-level specification of the agents (a first prototype for the development of KGP agents exists, based upon a correct computational counterpart of the model); the modular separation of concerns and flexibility afforded by the model in designing heterogeneous agents and in developing independently the various components of an agent; and the declarative agent control provided through a context-sensitive cycle CL theory component that regulates the agent's operational behaviour, according to the current circumstances of operation, thus breaking away from the conventional one-size-fits-all control of operation.

CONTRIBUTION TO SOCS WORKPACKAGES [WP1]:This paper presents the KGP model of individual computees as detailed in deliverable D4 of the project.

[UCY-CITY/Kakas/] Antonis C. Kakas, Nicolas Maudet, and Pavlos Moraitis, Flexible Agent Dialogue Strategies and Societal Communication Protocols.

Abstract: We propose an argumentation-based framework for representing communication theories of agents that can take into account dialogue strategies and society protocols in a way that facilitates their modular development and extension. The proposed framework is flexible in handling context dependent strategies and protocols that can also include special circumstances.

CONTRIBUTION TO SOCS WORKPACKAGES [WP5]: This paper shows how different policies of a computee can be integrated together. This will be useful in our studies of properties of computees and their social interaction.

[DIFERRARA-UNIBO/Alberti/Daolio-SAC2004] Marco Alberti, Davide Daolio, Marco Gavanelli, Evelina Lamma, Paola Mello, and Paolo Torroni, Specification and verification of agent interaction protocols in a logic-based system. In Proceedings of the 19th Annual ACM Symposium on Applied Computing (SAC 2004). Special Track on Agents, Interactions, Mobility, and Systems (AIMS), Nicosa, Cyprus, Mar. 14-17 2004. ACM Press. To appear.

Abstract: In multiagent systems, agent interaction is ruled by means of interaction protocols. Compliance to protocols can be hardwired in agent programs; however, this requires that only "certified'' agents interact. In open societies, composed of autonomous and heterogeneous agents whose internal structure is, in general, not accessible, interaction protocols should be specified in terms of the agent observable behaviour, and compliance should be verified by an external entity. In this paper, we propose a Java-Prolog-CHR system for verification of compliance of agents' behaviour to protocols specified in a logic-based formalism (Social Integrity Constraints). We also present the application of the formalism and the system to the specification and verification of the FIPA Contract-Net protocol.

CONTRIBUTION TO SOCS WORKPACKAGES [WP2, WP3, WP4]: The article presents a modified version of Social Integrity Constraints as introduced in WP2; it also presents a Java/Prolog/CHR-based verification system, which has served as a preliminary version of the prototype object of WP4.

[DIFERRARA-UNIBO/Gavanelli/CLIMA-IV-gavanelli] Marco Gavanelli, Evelina Lamma, Paola Mello, and Paolo Torroni, An abductive framework for information sharing in multi-agent systems. In J. Dix and J. Leite, editors, CLIMA-IV: Computational Logic in Multi-Agent Systems, Fourth International Workshop. Proceedings, Fort Lauderdale, FL, USA, Jan. 6-7 2004. To appear in the series Lecture Notes in Artificial Intelligence, published by Springer-Verlag.

Abstract: In this paper, we propose a framework for information exchange among abductive agents whose local knowledge bases are enlarged with a set of abduced hypotheses. We integrate the aspects of information exchange and abductive reasoning, and show theoretically the information inferred by the single abductive agent as a product of joint reasoning activity. We show examples, like dining philosophers, resource exchange and speculative computation, and give an implementation of the space of interactions based on CLP(SET).

CONTRIBUTION TO SOCS WORKPACKAGES [WP2, WP3]: The paper studies the information exchanged among a group of abductive agents that try to reach an agreement, when they share a common hypotheses space. This study was performed as an early model for the society, in order to understand the feasibility (both from WP2 and WP3 viewpoints) of a society which has a goal to reach given in a declarative language, and the computees do not have an explicit protocol, but their interaction patterns are ruled by a set of integrity constraints.

[UNIBO-DIPISA/Torroni/CLIMA-IV-bracciali] Andrea Bracciali and Paolo Torroni, A New Framework for Knowledge Revision of Abductive Agents through their Interaction (preliminary report). In J. Dix and J. Leite, editors, CLIMA-IV: Computational Logic in Multi-Agent Systems, Fourth International Workshop. Proceedings, Fort Lauderdale, FL, USA, Jan. 6-7 2004. To appear in the series Lecture Notes in Artificial Intelligence, published by Springer-Verlag.

Abstract: The aim of this work is the design of a framework for the interaction among abductive reasoning agents, addressing issues such as how to exploit knowledge multiplicity to find abductive explanations that agents could not individually find, what information must be passed or requested, how agents can take advantage from the answers that they obtain, and how they can revise their reasoning process as a consequence of interacting with each other. In this preliminary report, we describe a novel negotiation framework in which agents will exchange not only abductive hypotheses but also meta-knowledge, such as their own integrity constraints. Besides, we formalise some aspects of such a framework, introducing an algebra of integrity constraints, aimed at formally supporting the updating/revising process of the agent knowledge.

CONTRIBUTION TO SOCS WORKPACKAGES [WP1, WP2, WP3, WP5]: WP2 and WP5 aims at modelling interaction and at verifying properties of interaction among computees. Such interactions are normally motivated by the computee's state, defined in WP1 and WP3. This work aims at exploring means and properties of richer forms of interaction than those presented in the SOCS deliverables, in a negotiation scenario, and with a focus on the revision of the knowledge of computees as a result of interaction.

[UNIBO-DIFERRARA/Chesani/alberti04compliance] Marco Alberti, Federico Chesani, Marco Gavanelli, Evelina Lamma, Paola Mello, and Paolo Torroni, Compliance Verification of Agent Interaction: a Logic-based Tool. In R. Trappl, editor, Proceedings of the 17th European Meeting on Cybernetics and Systems Research (EMCSR'2004), Vol. II, Symposium "From Agent Theory to Agent Implementation" (AT2AI-4), pp. 570-575, Vienna, Austria, April 13-16, 2004. Austrian Society for Cybernetic Studies.

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 an external tool able to observe and check for its compliance to interaction protocols. In this paper we present a Java-Prolog software component which can be used to verify compliance of agent interaction to interaction protocols written in a logic-based formalism (Social Integrity Constraints).

CONTRIBUTION TO SOCS WORKPACKAGES [WP3, WP4]: The article presents Social Infrastructure prototype that has been developed for WP4; it also shows the correspondence between the abductive proof procedure, subject of WP3, and the Prolog/CHR-based implementation.

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