Logic Programming and the OpenKnowledge Project David Robertson University of Edinburgh UK Editor: Francesca Toni & Fariba Sadri Download: PDF This article summarises progress on a major European project on large scale knowledge sharing in a distributed environment.  An interesting aspect of this project is the extent to which it has applied well known methods from logic programming to a task that normally is viewed quite differently. Section 1 describes why we thought OpenKnowledge was necessary.  Section 2 situates the approach with respect to larger, existing efforts.  For logic programmers, the interesting bits are then Section 3 and Section 4 where current and future contributions of logic programming are discussed. Although this article is written by a single author, the work it describes is that of many researchers, many of whom (and their publications) are accessible via www.openk.org. 1. Motivation for the OpenKnowledge Project The OpenKnowledge project aims to make knowledge sharing easy and effective in a peer~to~peer environment.  This sort of environment is of interest because it offers the potential for large scale knowledge sharing.  From a knowledge sharing point of view the difficulty of peer to peer environments is that very little can be assumed about the peers and no component is given special authority over others, other than via the manner in which peers interact with humans and with each other.  A similar issue arises for open, multi-agent environments but we use the word ``peer'' to avoid raising too many presumptions about the abilities of individual agents.   This way of attempting to share knowledge between peers encounters elementary problems, familiar from traditional software and knowledge engineering: When two different components supply exactly the same formal expression this does not imply that they mean the same thing.  Conversely, when they supply different formal expressions they may mean the same thing.  In traditional knowledge (and software) engineering we avoid this problem by reaching a consensus amongst component designers on an ontology. To obtain an ontology one needs an oracle to decide which formal terms to use.  There are only two sources of oracle: human or mechanical.  Neither source scales well.  Human oracles can only agree in small groups for narrow tasks or domains.  Mechanical oracles need to acquire domain knowledge via automated learning  methods, none of which has scaled beyond narrow tasks or domains. Only some combinations of components work well together, even when the meanings of their appropriate inputs and outputs correspond, because of assumptions made deep within the design of components.  In traditional knowledge (and software) engineering this problem is detected through integration testing: by running assemblies of components comprising the system and checking for defects such as range errors (where the type of an input is correct but its value is outside the range anticipated by the component's designers).  It is infeasible to test all ranges for all variables for all components so integration testing only covers some small subset of the possible interactions. Components may fail without warning, either because they are removed or as a consequence of their environment.  Traditionally this problem is solved by ensuring that the components are in a shared, controlled environment.  No such controls are available in an open environment, in which we may not always know who, what or where are our peers. Even without the problems above, theoretical results show that in general it is impossible to guarantee consistently shared common knowledge in asynchronous distributed systems.  The engineering solution to this problem is to  provide mechanisms for establishing synchronisation between appropriate components, but for this we must have a frame of reference to bound the synchronisation - otherwise  synchronisation itself falls foul of the general consistency problem. Given the above, the aim of the OpenKnowledge project is to develop a form of knowledge sharing that is based not on direct sharing of ``true'' statements about the world but, instead, is based on sharing descriptions of interactions.  By making interaction specifications the currency of knowledge sharing we gain a precise context to interpreting knowledge that can be transmitted between peers.  The narrower notion of semantic commitment we thus obtain requires peers only to commit to meanings of terms for the purposes and duration of the interactions in which they appear.  This lightweight semantics allows networks of interaction to be formed between peers using comparatively simple means of tackling the perennial issues of query routing, service composition and ontology matching. 2. Comparison to Current Paradigms The OpenKnowledge project takes a different view from mainstream efforts but it does not aim to replace the infrastructures already in place.  Instead, we aim to address problems that don't fit existing moulds and, where there is significant overlap, then we fit through the current fashion since much of OpenKnowledge is neutral to deployment infrastructure and those bits that aren't can often be fitted to current practice via translation. Three of the most obvious points of contact are summarised below but readers interested in how OpenKnowledge applies are perhaps better to look more closely at our application examples (currently in astrophysics, bioinformatics, emergency response and game environments, with new applications being explored in healthcare and in business process enactment). Multi-agent Systems: The LCC language was, in part, stimulated by the use of electronic institutions in multi-agent systems.  Like  LCC, an electronic institution is a specification of the constraints that agents must observe in order to participate in a given form of  social interaction so, viewed from a multi-agent perspective, OpenKnowledge is a new way of making that idea operational.  An open  issue (which we are exploring) is the tension between agent autonomy and openness of access to the institution.  It is possible in OpenKnowledge to write interaction models that are self-contained in the sense that the means of satisfying all constraints in the model are supplied with it, in which case peers are no more than suppliers of processing power and certainly not autonomous agents. It also is possible, however, to write interacton models in which the means of satisfying constraints (and the decision of whether or not to satisfy them) is left to the agents, in which case agents possess local autonomy within the framework of the interaction. The flexibility to move between these extremes is crucial because autonomy varies according to the domain of application: sometimes the only restriction an interaction need impose is the choice of illocutions; in other applications it may not be practical to assume that agents always locally will observe the intended semantics of those illocutions so more explicit constraints on the interaction need to be in the LCC model. The Semantic Web: One view of the Semantic Web is data-centric, where nodes are data sources with which we associate formal specifications of content.  This needs to be supported by a way of sharing patterns of usage and knitting them into semantic annotations.  The LCC interaction models are a means of expressing such patterns.  Peer-to-peer routing makes it possible to share these on a large scale.  Various forms of ontological alignment (including manual alignment) can then be applied to allow peers to select (and collectively reinforce) specific patterns of usage that work when combining data. The need to represent potential interactions has long been recognised, hence the process specification elements of OWL-S.  In OWL-S, however, an interaction process is associated with a service (and with its data) rather than being separately defined.  By separating interaction specifications from data annotations we are able to knit together services with programming-oriented declarative specifications (LCC) rather than by requiring elaborate individual service specifications. Web Service Architectures: Our approach is intended to complement and extend a traditional Web service architecture by addressing a number of restrictions.  The Web Service Architecture, while distributed, is not inherently peer-to-peer (in particular, there is no support for efficient routing of messages between services, service discovery is performed in a centralised manner using registries, and there is the assumption that services will always be available at a fixed location).  Complex interactions require (sophisticated) service composition, which OpenKnowledge achieves directly via LCC.  The basic Web services architecture does not contain any support for assessing trust across services when conducting interactions.  Because our methods maintain explicit models of interaction to coordinate services we can apply a repertoire of trust assessment  methods to these. Grids: Our approach is consistent with the grid vision but without our methods being predicated on sophisticated underlying Grid infrastructure.  Traditional grid systems connect together specific services (or types of service) in stable networks - the aim being to do as much as possible to make these networks robust, secure and resistant to failure.  We concentrate on specifying interactions, which may take place with different combinations of services in an open, peer-to-peer environment where the only essential infrastructure requirement is the ability to pass messages between peers.  In this sense, our aim is an ``everyman's grid'' in the sense that we aim to maintain integrity of interaction (a key grid objective) without requiring specialist (centralised) infrastructure or computing resources to do so and at a very low entry cost. 3. The Current Role of Logic Programming The origin of OpenKnowledge is not specifically in logic programming and the OpenKnowledge kernel system (which will be available to download from October from www.openk.org) is in Java so readers of this newsletter may be surprised at how much of our research is essentially logic programming.  The main points of contact currently are: The Lightweight Coordination Calculus: At the core of the OpenKnowledge system is the LCC language in which interactions between peers is described.  It is an executable, declarative specification language in a style familiar to logic programmers.  Its purpose, however, is to define the roles adopted by peers during interaction, where roles are performed independently (according to their clause definitions) and synchronised only through message passing.  Constraints associated with message passing events provide the connections to programs changing the state of appropriate peers (analogously to built-in predicates or foreign function calls in Prolog programs).  Variables and data structures are handled similarly to Prolog.  The earliest interpreters for LCC were implemented in Prolog, although the interpreter for the OpenKnowledge kernel is in Java (which is more convenient for wide distribution, though much less elegant as code). Reducing brittleness: LCC specifications look like logic programs but in one sense they are significantly different: when a message is sent (or received) by a peer when performing its LCC role then that message cannot be un-sent (or un-received).  In other words, although we can use backtracking to choose between message passing, we are forced to use committed choice1. This makes interactions brittle in the sense that if a peer makes a choice that turns out to be unacceptable to other peers (in a situation when other choices were open to it) then, unless a recovery mechanism is defined within the LCC specification, the interaction will fail.  Logic programming has provided us with two methods (and there probably are more we have not discovered) for reducing this problem.  One is to use more flexible notions of variable instantiation, so we developed a variant of LCC that used finite domain constraint solvers and propagated variable ranges (rather than variable instances) across interactions.  The other was to supply, along with interaction models, a set of (interaction-specific) transformations that are applied as a means of ``patching'' an interaction when it is in danger of failing. Ontology mapping: The ontology mapping problem for OpenKnowledge is not the traditional one of obtaining a consensus on terminology across a peer group.  Instead it is the much more narrow and dynamic problem of maintaining a good enough agreement on terminology across an interaction.  Extensions to normal term matching are then necessary in order to achieve unification between terms in cases when they do not match perfectly.  This might at first sight seem daunting but is made tractable by the context of the interaction model, so it is possible for peers to share knowledge of mappings that work and then use these as statistical predictors based on the interaction history. Verifying properties of interactions: The most obvious use for verification in OpenKnowledge is in the design of LCC specifications, where it is useful to predict some of the behaviours of interactions.  Perhaps more interesting, however, is our use of verification at run time, when peers must choose whether to engage in interactions made available to them by other peers (of which they may have no previous knowledge).  One way to approach this is by testing interaction models against peers' deontic specifications (describing the permissions and obligations imposed locally by each peer).  We have been using XSB as a platform for performing this form of testing, allowing us to have compact definitions of LCC interpreter and temporal property derivation rules. 4. Future Opportunities for Logic Programming Although OpenKnowledge is not a logic programming initiative and its applications are not in logic programming, it has used many of the basic concepts of the field and there remain many opportunities to explore.  Three of these are below. Transformation: Logic program transformation methods have application at different stages in OpenKnowledge.  At design time it is useful to have transformations from domain/task specific languages to LCC, so as to allow users of those other languages to work with LCC without losing familiar representations.  We have, for example, built transformation systems from BPEL4WS (a business process language oriented to Web services) and SCUFL (a workflow language used for coordination of Grid services).  At interaction time transformation can be a way of reducing brittleness in interaction (as described above).  It may also be a way of reconciling (in part) the tension between an interaction-centric view of coordination and an agent-centric view of coordination (see below). Argumentation: Through involvement in the Argumentation Interchange Format, we have begun to explore how LCC might be used to support argumentation.  One way is simply by using LCC to define argument protocols (in which case it is no different from any other protocol implementation language, except for the peer to peer sharing mechanisms of OpenKnowledge).  It is, however, possible to use LCC to implement meta-interpreters for other interaction languages (the interpretation steps of the meta-interpreter being part of the LCC interaction) and this might give us a more general solution. Transformation also has a role to play here because one way to understand argument is as a sequence of adaptations to interaction models.  We have taken this approach to produce LCC versions of Dialogue Games. Constraint handling: We have produced a simple mechanism for propagating finite domain constraints across interactions and we also have experimented with distributed constraint relaxation algorithms in the same setting.  We have not, however, looked at other forms of constraint solving. Integrating interaction with agency: The view of interaction promoted throughout this article is mostly that of interactions as ``scripts'' to which agents subscribe.  That need not be the case, however, because the way we describe interactions maintains a clean separation between constituent roles, which are then partial specifications of acceptable agent behaviour in a given interaction context.  Furthermore, these specifications are already close to the  form in which they might be combined with other reasoning processes conducted within an agent that reasons with computational logic (rather than being some arbitrary Web service running private code).  For these sorts of agents, we could have a much more intimate interplay between internal reasoning and external communication. Acknowledgements The OpenKnowledge project is a collaboration between the University of Edinburgh, University of Trento, Free University of Amsterdam, Open University, Artificial Intelligence Institute in Barcelona and the University of Southampton.  It is funded by a European Framework 6 grant (FP6-027253). 1This is not entirely accurate.  We did at one point experiment with a means of backtracking across interacting roles but that was complex and there remained the insuperable problem that, although we might backtrack in the interaction specification, we could not backtrack inside the peers themselves.