Contents

1. Implementing Rational Features for Agents in Logic Programming

2. Logic-based agent implementation

Outline

• Implementations of rational agent features[3].
• Overview of selected implemented features
  • Dynamic Logic Programming
  • Evolving Logic Programs
  • Reasoning Integration
  • Semantic Web application
• Implemented features left out: Belief Revision, Aduction
• W4 project: Well-founded semantics for the World Wide Web
• Conclusion

Introduction

We have implemented the following Rational Agent Features:

1. DLP - Dynamic Logic Programming

2. PDLP – DLP with preferences

3. MDLP - Multi-Dimensional DLP

4. LUPS - Language for Dynamic Updates

5. EVOLP – Evolving Logic Programs

6. Prolog based standard XML tools

Some of these are further detailed below. All can be followed up on via their respective hyperlink.

DLP is a semantics for updates of LPs by LP rules. It guarantees that most recent rules are set in force, and previous rules valid by inertia insofar as possible, i.e. are kept for as long as they do not conflict with more recent ones. Originally, in DLP default negation is treated as in the stable models semantics of generalized programs. Now it is also defined for the WFS.

EVOLP is a Logic Programming language for: specifying evolution of knowledge bases; allowing dynamic updates of specifications; capable of dealing with external events; dealing with sequences of sets of EVOLP rules.These rules are generalized LP rules (i.e. possibly with nots in heads) plus the special predicate assert/1, that can appear both in heads or bodies of rules. The argument of assert/1 can be a full-blown EVOLP rule. The meaning of a sequence of update rules is given by sequences of models. Each sequence determines a possible evolution of the KB. Each model determines what is true after a number of evolution steps (i.e. a state) in the sequence:

• A first model in a sequence is built by “computing” the semantics of the first EVOLP program, where assert/1 is as any other predicate. 

• If assert(Rule) is true at some state, then the KB must be updated with Rule.

• This updating of the KB, and the “computation” of the next model in the sequence, is done as in DLP.

An example application concerns a personal assistant agent for email management able to: Perform basic actions of sending, receiving, deleting messages; Storing and moving messages between folders; Filtering spam messages; Sending automatic replies and forwarding; Notifying the user of special situations.

All of this dependent on user specified criteria, and where the specification may change dynamically[4]. 

We can integrate within the same logic programming framework incomplete, uncertain and paraconsistent reasoning forms. Furthermore, our semantics are able to detect the dependencies on contradiction[5]. Existing embeddings of other formalisms into our fremework are: Ordinary Horn clauses; Generalized Annotated Logic Programs; Fuzzy Logic Programs; Probabilistic Deductive Databases; Weighted Logic Programs and Statistical Defaults; Hybrid Probabilistic Logic Programs; Possibilistic Logic Programs; Quantitative Rules; Multi-adjoint Logic Programming; Rough Sets.

Our XML tools:

 Non-validating XML parser with support for XML Namespaces, XML Base, complying with the recommendations of XML Info Sets. Reads US-ASCII, UTF-8, UTF-16, and ISO-8859-1 encodings.

• Converter of XML to Prolog terms.

• RuleML compiler for the Hornlog fragment, extended with default and explicit negation.

• Query evaluation procedures for Paraconsistent Well-founded Semantics with Explicit Negation.

These and the tools mentioned below, enable our group with possibilities regarding Semantic Web Applications of Logic Programming. This is being pursued in the wider context of the REWERSE NoE submitted to the FP6 (under evaluation but with good chances of approval, and having already passed the first hurdle). Our Logic Programming and the Semantic Web tools:

• RuleML standards.

• Implementation of Prolog based standard XML tools, namely a fully functional RuleML compiler for the Horn fragment with two types of negation (default and explicit).

• Evolution and updating of knowledge bases. The existing implementations are being integrated with RuleML.

• Semantics of logic programming. Supporting uncertain, incomplete, and paraconsistent reasoning (based on Well-founded Semantics and Answer Sets).

• Development of advanced Prolog compilers (GNU-Prolog and XSB).

• Development of distributed tabled query procedures for RuleML.

• Constraint Logic Programming.

The W4 project: Well-founded semantics for the WWW

The W4 project aims at developing Standard Prolog inter-operable tools for supporting distributed, secure, and integrated reasoning activities in the Semantic Web. The project goals are:

• Development of Prolog technology for XML, RDF, and RuleML.

• Development of a General Semantic framework for RuleML including default and explicit negation, supporting uncertain, incomplete, and paraconsistent reasoning.

• Development of distributed query evaluation procedures for RuleML, based on tabulation, according to the previous semantics.

• Development of Dynamic Semantics for evolution/update of Rule ML knowledge bases.

• Integration of different semantics in Rule ML (namely, Well-founded Semantics, Answer Sets, Fuzzy Logic Programming, Annotated Logic Programming, and Probabilistic Logic Programming).

Why have we chosen the Well-founded Semantics with tabling? Because:

• THE adopted semantics for definite, acyclic and (locally) stratified logic programs.

• Defined for every normal logic program, i.e. with default negation in the bodies.

• Polynomial data complexity.

• Efficient existing implementations, namely the SLG-WAM engine implemented in XSB. Good structural properties.

• It has an undefined truth-value...

• Many extensions exist over WFS, capturing paraconsistent, incomplete and uncertain reasoning.

• Update semantics via Dynamic Logic Programs.

• It can be readily "combined" with DBMSs, Prolog, and Stable Models engines.

• The existence of an undefined logical value is fundamental. While waiting for the answers to a remote goal invokation it can be assumed that its truth-value is undefined, and proceed the computation locally. Loops through default negation are dealt with in XSB, via goal suspension and resume operations.

• Tabling IS the right, successful, and available implementation technique to ensure better termination properties and polynomial complexity. Tabling is also a good way to address distributed query evaluation of definite and normal logic programs.

The major guidelines of the project are:

• Tractability of the underlying reasoning machinery.

• Build upon well-understood existing technology and theory, and widely accepted core semantics.

• General enough to accommodate and integrate several major reasoning forms.

• Should extend definite logic programming (Horn clauses). Desirable integration with (logic) functional languages.

• Most of the reasoning should be local (not very deep dependencies among goals at different locations).

• Fully distributed architecture, resorting to accepted standards, recommendations and protocols. Indeed, we have implemented and defined a general and “open” architecture for distributed tabled query-evaluation of definite logic programs. It has a low message complexity overhead. The architecture assumes two types of main components: table storage clients and prover clients. It addresses the issue of table completion by resorting to known termination detection distributed algorithms.  It can immediately be extended to handle stratified negation.

 The construction of prototypical systems depends on the definition of: Syntactic extensions (apparently, not very difficult); Goal invokation method (Namespaces, XLinks, SOAP, etc.) ; Selection of distributed query evaluation algorithms and corresponding protocols; Formatting of answers and substitutions (should be XML documents); Integration with ontologies. Further applications, testing, and evaluation is required for the construction of practical systems.

Conclusion

In our opinion, Well-founded semantics should be a major player in RuleML, properly integrated with Stable Models. A full-blown theory is available for important extensions of standard WFS/SMs, addressing many of the open issues of the Semantic Web. Most extensions resort to polynomial program transformations, namely those for evolution and update of knowledge bases. Can handle uncertainty, incompleteness, and paraconsistency. Efficient implementation technology exists, and important progress has been made in distributed query evaluation. An open, fully distributed, architecture is being proposed.

1. An updated summary of a presentation at “Logic-Based Agent Implementation”, An AgentLink/CologNet Symposium, 3rd February, 2003,  Barcelona, España. This work has been developed with contributions by (cf. publications): João Alcântara, José Júlio Alferes, António Brogi, Carlos Damásio, João Leite, Luís Moniz Pereira, Teodor Przymusinski, Halina Przymusinska, Paulo Quaresma.

2. E-mail: lmp@di.fct.unl.pt      URL: http://centria.di.fct.unl.pt/~ lmp 

3. Available at http://centria.fct.unl.pt/~jja/updates/

4. Cf. J. J. Alferes, A. Brogi, J. A. Leite, L. M. Pereira, Logic Programming for Evolving Agents, Cooperative Information Agents (CIA0'3), Helsinki, Finland, August 2003. And, by the same authors, An Evolvable Rule-Based E-mail Agent (submitted).

5. J. Alcântara, C. V. Damásio, L. M. Pereira, An Encompassing Framework for Paraconsistent Logic Programs, Journal of Applied Logic, to appear, 2003. C. V. Damásio, L. M. Pereira, Hybrid Probabilistic Logic Programs as Residuated Logic Programs, Special issue on Logics in Artificial Intelligence, Studia Logica, 72(2):113-118, 2002.

Overview

The view of computational components as `agents' is widely used in contemporary software applications, such as Internet navigation, information management, autonomous process control, and e-commerce. The popularity of the agent paradigm stems not only from its intuitive and appealing nature, capturing the notions of flexibility and evolving behavior, but also from the range of theories, tools and techniques that have been developed over recent years for agent-based systems. 

However, the languages in which agents are typically implemented are often standard (usually, object-oriented) languages, with few `agent' concepts included as a central part. Thus, the abstractions that agent-based systems developers must work with are not always appropriate for producing effective agent applications, especially where `intelligent' or `rational' behavior is required. In addition, with agent-based systems beginning to be used in both safety/mission critical (e.g. autonomous control) and business critical (e.g. e-commerce and security) software, it is clear that more precise, and logically well-founded, development techniques will be required for agent-based applications in the future.

Thus, the aim of this special issue is to bring together high-quality papers exhibiting leading edge research where a "logic-based" approach is taken to the implementation of agent-based systems (often comprising `rational' or `intelligent' agents). Our view of `logic' here is not restricted to classical logic and logic programming techniques and, indeed, much of the leading work in this area does not easily fit within such a classification. We here take a broad view of logic, and consider implementation techniques for agents that are inherently based in some logical formalism. This logical formalism may have been developed for a variety of reasons. For example, the use of logic may enhance the abstractions used in the language, the potential for verification, the type of tools that can be utilized or the breadth of behaviors that can be developed.

The Journal

The Annals of Mathematics and Artificial Intelligence (Editor-in-Chief: Martin Golumbic. Associate Editors: Endre Boros; Sarit Kraus; Anil Nerode) is intended to represent a wide range of topics of concern to scholars applying quantitative, combinatorial, logical, algebraic and algorithmic methods to Artificial Intelligence areas as diverse as decision support, automated deduction, reasoning, knowledge-based systems, machine learning, computer vision, robotics and planning.  The journal is aimed at: applied logicians, algorithms and complexity researchers, Artificial Intelligence theorists and applications specialists using mathematical methods.  For more details, see http://www.kluweronline.com/issn/1012-2443

Important Dates

• Submission deadline:  1st March 2003
• Author notification:  1st July 2003
• Revised papers due:   1st September 2003

Topics of Interest

The topics of interest of this special issue include (but are not limited to):

• implementation techniques (together with accompanying software engineering methods) for agent-based or multi-agent systems based on: logic programming (including, concurrent/parallel logic programming); constraints (including, constraint logic programming and concurrent constraint programming); intentional programming; situation calculus; executable modal/temporal logics; and multi-paradigm approaches
• advanced techniques within logic-based agents, such as: knowledge representation, nonmonotonic reasoning; planning, problem solving and deliberation; learning, evolution and adaption; cooperation, teamwork, negotiation and social ability; and decision theory for multi-agent systems
• applications of logic-based agents, for example in: robotics, autonomous process control; knowledge/information management, WWW search/ navigation; e-commerce and B2B applications; embedded components; telecommunications; and general purpose agent programming.

Submission of Manuscripts

We invite submission of full (typically, 20-40 pages) high-quality research papers for this special issue. These should neither have been previously published in their full form, nor be under review elsewhere. Submissions consisting of the paper (preferably PDF or Postscript via email but, alternatively, five hard-copies) including an abstract in which the role of logic in the particular approach used is clarified, should be sent to Michael Fisher (address given below)to arrive no later than 1st March 2003. Formatting instructions can be found at the journal's web site.

Queries concerning this special issue should be directed to any of the guest editors. Up-to-date information will also be available from http://www.csc.liv.ac.uk/~michael/LBAI03


Special Issue Editors

Juergen Dix
 Department of Computer Science,
 University of Manchester, Manchester, U.K.
 email: dix@cs.man.ac.uk          url:  http://www.cs.man.ac.uk/~jdix

Michael Fisher
 Department of Computer Science,
 University of Liverpool, Liverpool L69 7ZF, U.K.
 email: M.Fisher@csc.liv.ac.uk    url:  http://www.csc.liv.ac.uk/~michael

Hector Levesque
 Department of Computer Science,
 University of Toronto, Toronto, Canada
 email: hector@cs.toronto.edu     url:  http://www.cs.toronto.edu/~hector

Leon Sterling
 Department of Computer Science and Software Engineering,
 University of Melbourne, Australia
 email: mailto:leon@cs.mu.oz.au   url:  http://www.cs.mu.oz.au/~leon