Il Milione: A Journey in the Computational Logic in Italy La Logica Computazionale in sistemi basati su agenti Computational Logic in Agent Based Systems Paolo Mancarella e Francesca Toni 70 Il Milione: A Journey in the Computational Logic in Italy SOMMARIO/ABSTRACT briefly summarize one such approach which has lead to the defnition of the KGP model for agency, and which is being Viene descritto l’utilizzo della logica computazionale further developed to cope with the specification of agents a supporto della formalizzazione ed implementazione in service-oriented applications. di agenti in sistemi multi-agente. In questo ambito è necessario l’uso di varie forme di logica computazionale, tra le quali abduzione, argomentazione e sistemi basati 2 The KGP model su preferenze. Viene presentato a grandi linee il modello KGP is an acronym for Knowledge, Goals and Plan. The per agenti denominato KGP, nonché una sua estensione model is intended to provide a modular and hierarchical in corso di definizione per la modellazione di agenti specification of agents equipped with a variety of advanced in ambienti distribuiti quali il Grid e più in generale reasoning features to allow intelligent decision making and architetture service-oriented behaviour. KGP agents are particularly suited to open dy- namic environments where they have to adapt to changes We describe recent work on the deployment of computa- in their environment and they have to function in circum- tional logic to support the formalisation and implemen- stances where they have incomplete information. Here we tation of agents in multi-agent systems. Several forms give an overview of the KGP agent model and its compo- of computational logic systems are needed in this setting, nents [4, 3]. The model relies upon including abductive, argumentative and preference-based − an internal (or mental) state, holding the agent systems. We briefly sketch the agent model called KGP, Knowledge base (beliefs), Goals (desires) and Plans (in- and an ongoing extension of it which is needed to model tentions), agents in distributed settings such as the Grid and, more − a set of reasoning capabilities, generally, Service-oriented architectures. − a set of physical capabilities, − a set of transition rules, defining how the state of the Keywords: Logica computazionale, sistemi multi-agente, agent changes, and defined in terms of the above capabili- abduzione, argomentazione ties, − a set of selection operators, to enable and provide ap- 1 Introduction propriate inputs to the transitions, − a cycle theory, providing the control for deciding which Computational Logic (CL) has been successfully adopted, transitions should be applied when, and defined using the in recent years, in modelling agents within agent based sys- selection operators. The model is defined in a modular tems. The adoption of CL techniques has the advantage fashion, in that different activities are encapsulated within that formal specifications come along with their compu- different capabilities and transitions, and the control is a tational counterparts in the form of provably correct and separate module. The model also has a hierarchical struc- executable proof procedures. The formal and computa- ture, depicted in figure 1. tional models needed in the agent based settings require Internal state. This is a tuple hKB0 , F, C, Σi, where: an integrated treatment of different features, which can be handled within various extensions of the basic logic pro- • KB0 holds the (dynamic) beliefs of the agent about gramming framework, including abduction, argumentation the external world in which it is situated, as well as a and constraint logic programming. In this short paper we record of the actions it has already executed. 71 Il Milione: A Journey in the Computational Logic in Italy strained sub-goals and actions designed for achieving the input goals. • Reactivity, which is used to provide new reactive top- level goals, as a reaction to perceived changes in the environment and the current plans held by the agent. • Goal Decision, which is used to revise the non- reactive top-level goals, adapting the agent’s state to changes in its own preferences and in the environ- ment. • Identification of Preconditions and Identification of Effects for actions, which are used to determine ap- propriate sensing actions for checking whether ac- Figure 1: A graphical overview of the KGP model tions may be safely executed (if their preconditions are known to hold) and whether recently executed ac- tions have been successful (by checking that some of • F is a forest of trees whose nodes are goals, which their known effects hold). may be executable or not. Each tree in the forest gives a hierachical presentation of goals, in that the • Temporal Reasoning, which allows the agent to rea- tree represents the construction of a plan for the root son about the evolving environment, and to make pre- of the tree. The set of leaves of any tree in F forms dictions about properties, including non-executable a currently chosen plan for achieving the root of the goals, holding in the environment, based on the (par- tree. Executable goals are actions which may be tial) information the agent acquires over its life-time. physical, communicative, or sensing. Non-executable • Constraint Solving, which allows the agent to reason goals may be mental or sensing. Only non-executable about the satisfiability of the temporal constraints in mental goals may have children, forming (partial) C and Σ. plans for them. Actions have no children in any trees in F. The roots of trees in F are referred to as In the concrete realisation of the KGP model, we have top-level goals, the executable goals are referred to chosen to realise the above capabilities in various exten- as actions, and non-executable goals which are not sions of the logic programming paradigm. In particular, top-level goals are referred to as sub-goals. Top- we use (conventional) logic programming for Identifica- level goals are classified as reactive or non-reactive. tion of Preconditions and Effects, abductive logic program- Roughly speaking, reactive goals are generated in re- ming with constraints for Planning, Reactivity and Tempo- sponse to observations, e.g. communications received ral Reasoning, and logic programming with priorities for from other agents and changes in the environment, for Goal Decision. example to repair plans that have already been gener- ated. Non-reactive goals, on the other hand, are the Physical capabilities. In addition to the reasoning capa- chosen desires of the agent. Note that some top-level bilities, the agent is equipped with “physical” capabilities, (reactive) goals may be actions. linking the agent to its environment, consisting of • C is the Temporal Constraint Store, namely a set of • A Sensing capability, allowing the agent to observe constraint atoms in some given underlying constraint that properties hold or do not hold, and that other language. These basically constrain the time variables agents have executed actions. of the goals in F. For example, they may specify a time window over which the time of an action can be • An Actuating capability, for executing (physical and instantiated, at execution time. communicative) actions. • Σ is a set of equalities instantiating time variables Transitions. The state hKB0 , F, C, Σi of an agent with time constants. For example, when the time vari- evolves by applying transition rules, which employ the ca- ables of actions are instantiated at action execution pabilities as follows: time, records of the instantiations are kept in Σ. • Goal Introduction (GI), possibly changing the top- Reasoning capabilities. These are: level goals in F, and using Goal Decision. • Planning, which generates plans for mental goals • Plan Introduction (PI), possibly changing F and C given as input. These plans consist of temporally con- and using Planning. 72 Il Milione: A Journey in the Computational Logic in Italy • Reactivity (RE), possibly changing the reactive top- within a single framework of abductive logic program- level goals in F and possibly C, and using the Reac- ming, temporal reasoning, constraint logic programming, tivity capability. and preference reasoning based on argumentation in order to support a diverse collection of capabilities. Each one of • Sensing Introduction (SI), possibly introducing new these is specified declaratively and equipped with its own sensing actions in F for checking the preconditions provably correct computational counterpart. These com- of actions already in F. putational models are heavily based upon proof procedures • Passive Observation Introduction (POI), changing for (various extensions of) logic programming. In particu- KB0 by recording unsolicited information coming lar, the operational model for KGP agents relies upon CIFF from the environment, and using Sensing. [2], a proof procedure for abductive logic programming with constraints, and Gorgias [1], for logic programming • Active Observation Introduction (AOI), possibly with priorities. These procedures have been obtained by changing Σ and KB0 , by recording the outcome of adapting and suitably extending two existing proof proce- (actively sought) sensing actions, and using Sensing. dures for logic programming, namely Fung and Kowalskis IFF procedure for abductive logic programming for CIFF, • Action Execution (AE), executing all types of actions and Kakas and Tonis argumentation-based procedure for and as a consequence changing KB0 and Σ, and us- negation as failure in logic programming for Gorgias. The ing Actuating. overall operational models are sound and (in some cases) complete with respect to the abstract KGP model, and form • State Revision (SR), possibly revising F, and using a solid bridge between the KGP model and its implemen- Temporal Reasoning and Constraint Solving. tation within the PROSOCS platform, a prototype imple- mentation using Sicstus Prolog and JXTA [5]. Cycle and Selection operators. The behaviour of an agent is given by the application of transitions in se- quences, repeatedly changing the state of the agent. These 3 Argumentative agents in ARGUGRID sequences are not determined by fixed cycles of behaviour, as in conventional agent architectures, but rather by reason- The use of agent technology offers a solution to dynamic ing with cycle theories. Cycle theories define preference service composition in distributed settings such as the Grid policies over the order of application of transitions, which and more generally Service-Oriented Architectures. Dif- may depend on the environment and the internal state of ferent services can be associated with autonomous agents an agent. They rely upon the use of selection operators for that can identify and negotiate, on behalf of service re- detecting which transitions are enabled and what their in- questors and providers, implementation plans that take into puts should be, as follows: account the requirements of both sides. The ARGUGRID −action selection for inputs to AE; project1 aims at defining and deploying argumentation- this selection operator uses the Temporal Reasoning and based agents to support the selection and composition of Constraint Solving capabilities; − goal selection for inputs services over the Grid and Service-Oriented Architectures to PI; [6]. We have proposed in [7] an agent architecture inte- this selection operator uses the Temporal Reasoning and grating a number of argumentative modules (for various Constraint Solving capabilities; − effect selection for in- forms of decision-making), a module for interaction with puts to AOI; this selection operator uses the Identification other agents, “physical” modules for carrying out this in- of Effect reasoning capability; teraction via communication, and several data structures. − precondition selection for inputs to SI; this selection op- This type of argumentative agents can be seen as a vari- erator uses the Identification of Preconditions, Temporal ant of KGP agents. This variant relies upon the use of an Reasoning and Constraint Solving capabilities. argumentation decision-making tool supporting all reason- The provision of a declarative control for agents in the ing capabilities, and it makes use of argumentative proto- form of cycle theories is a highly novel feature of the cols for persuasion in negotiation. Argumentative agents model, which could, in principle, be imported into other are equipped with a specialised internal state, consisting of agent systems. In the concrete realisation of the KGP requirements, abstract or partially instantiated workflows, model, we have chosen to realise cycle theories in the same concrete workflows, planned communicative actions and framework of logic programming with priorities and con- actions executed in the past by the agent or by others, and straints that we also use for Goal Decision. arguments. The KGP modular architecture allows us to adopt a specialised set of reasoning capabilities supporting 2.1 Computational model the various forms of decision-making needed in ARGU- GRID and inter-agent interaction, as well as a capability One central distinguishing feature of the KGP model, in for revising the knowledge/beliefs of agents, which is actu- comparison with other models for agency, including those based on logic programming, is its modular integration 1 www.argugrid.eu 73 Il Milione: A Journey in the Computational Logic in Italy ally missing in the original KGP model. Specialised phys- 4 Conclusions ical capabilities are also needed in this setting to provide suitable forms of inter-agent communications, and finally We have briefly described work carried out in recent years appropriate transitions encapsulate the new capabilities. In and still ongoing, which aims at adopting computational this setting, agents need to be able to perform communica- logic for the description of agents in agent based systems. tive actions (for requesting services, accepting or refusing The use of computational logic allows us, on one hand to the provision of services, etc.) and actions for consulting partially fill the gap between agent models and their com- registries, inquiring about services and their providers. In putational realization. Indeed, the specification of KGP their internal state, agents store (a selection of) all commu- agent is a sort of executable specification due to the fact nicative acts they have participated in, as either speakers or that the computational logic tools adopted in this setting receivers, as well as the set of their current commitments, are equipped with suitable concrete proof procedures. On namely the contracts they have committed to. Basically, teh other hand, the modularity of the KGP model allows argumentative KGP agent are characterised by one to extend it naturally to support new forms of reason- ing, such as the ones needed in order to model the type • a (transient) state, consisting of of agents needed in service-oriented applications. Again, − a knowledge base, called KB0 as for the KGP computational logic tools, based on various forms of argu- model, but holding communicative acts by or to the mentation, can be adopted in these settings to support the agent, acts for consulting registries by the agent, as new type of capabilities needed, such as decision making well as contracts and negotiation. This is still ongoing work we are carrying − a set of goals, namely requirements by the user out within the ARGUGRID project. “owning” the agent − a set of decisions, of different kinds (to get ser- vices of known types from some yet-to-be-decided REFERENCES providers or from some known providers, or a deci- [1] N. Demetriou and A. C. Kakas. Argumentation with sion to utter something, or a decision to consult some abduction. In Proceedings of the fourth Panhellenic registry) Symposium on Logic, 2003. − a set of arguments, providing justifications and rea- sons for goals and decisions in the state [2] U. Endriss, P. Mancarella, F. Sadri, G. Terreni, and F. Toni. The CIFF proof procedure for abductive logic • a number of extended reasoning capabilities, namely programming with constraints. Lecture Notes in Arti- abstract decision-making, social decision-making, ficial Intelligence, 3229:680–684, 2004. communicative reactivity, registry consultation; each capability is supported by an appropriate argumenta- [3] A. C. Kakas, P. Mancarella, F. Sadri, K. Stathis, and tion system (base) F. Toni. Declarative agent control. Lecture Notes in • a revision capability, for modifying the argumentation Artificial Intelligence, 3487:96–110, 2005. systems supporting the various reasoning capabilities [4] A.C. Kakas, P. Mancarella, F. Sadri, K. Stathis, and • physical capabilities, namely listening, talking, and F. Toni. The KGP model of agency. In R. Lopez de consulting Mantaras and L. Saitta, editors, Proceedings of the Six- teenth European Conference on Artificial Intelligence, • a set of transitions, namely ADM (using the abstract Valencia, Spain (ECAI 2004). IOS Press, August 2004. decision-making capability), SDM (using the social decision-making capability), CR (using the commu- [5] K. Stathis, A.C. Kakas, W. Lu, N. Demetriou, U. En- nicative reactivity capability), RC (using the registry driss, and A. Bracciali. PROSOCS: A platform for consultation capability), R (using the revision capa- programming software agents in computational logic. bility), LI, TA, CON (using the listening, talking and Applied Artificial Intelligence, 20(4-5), 2006. consulting capabilities, respectively) [6] F. Toni. Argumentative KGP agents for service com- • a control, in the form of a conditional policy, that, for position. Proc. AITA08, Architectures for Intelli- each transition, gives one or more possible next tran- gent Theory-Based Agents, AAAI Spring Symposium, sitions depending on whether a number of conditions March 2008, Stanford University, CA, USA, 2008. hold or not. [7] M. Morge, P. Mancarella, F. Toni, J. McGinnis, S. Bro- Here, the consulting capability is intended for accessing muri, and K. Stathis Toward a modular architecture of information in registries. The reasoning capabilities corre- argumentative agents to compose services. In Proceed- spond to the IDM (individual decision-making), SDM (so- ings JFSMA 2007, 2007. cial decision making), and SI (social interaction) modules in [7]. The listening and talking capabilities are special cases of sensing and actuating in the KGP model. 74 Il Milione: A Journey in the Computational Logic in Italy 5 Contacts Paolo Mancarella (Corresponding Author) Dipartimento di Informatica, Università di Pisa Largo B. Pontecorvo, 3 56127 Pisa, Italy Tel: +39 050 2212 710 paolo.mancarella@unipi.it Francesca Toni Department of Computing, Imperial College London South Kensington Campus, Huxley Building London SW7 2AZ, UK Tel: +44 (0)20 7594 8228 ft@doc.ic.ac.uk 75