Logic-Based Agent
Implementation
An AgentLink/CoLogNet
Symposium
Implementing
Rational Features for Agents
in Logic Programming
Luís Moniz Pereira
Universidade Nova de Lisboa
E-mail: [email protected]
URL: http://centria.fct.unl.pt/~ lmp
3rd February, 2003
Barcelona, España
Authors
This work has been developed by (cf. publications):
• João Alcântara
• José Júlio Alferes
• António Brogi
• Carlos Damásio
• Pierangelo Dell’Acqua
• João Leite
• Luís Moniz Pereira
• Teodor Przymusinski
• Halina Przymusinska
• Paulo Quaresma
Outline
• Implementations of rational agent features
Available at site: http://centria.fct.unl.pt/~jja/updates/
• Overview of select features
– Dynamic Logic Programming
– Evolving Logic Programs
– Reasoning Integration Framework
– Semantic Web Application
• Implemented features left out: Belief Revision, Abduction, Abduction+Updates,
Constructive Negation.
• W4 project: Well-founded semantics for the World Wide Web
Rational Agent Features Implementation
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
7.
W4 project: WFS for the WWW
DLP
• DLP is a semantics for successive updates of LPs by other LPs,
with generalised rules (not’s in heads and bodies).
• Guarantees the most recent rules are in force, and that previous
rules are valid by inertia insofar as possible:
– i.e. they are kept as long they do not conflict with more recent rules, and
become revived if the latter are in turn superseded.
• DLP default negation is treated as in the Stable Models
semantics of generalized programs.
– presently DLP is also defined for the WFS.
EVOLP
• A Logic Programming language generalizing DLP and LUPS:
– For specifying evolution of knowledge bases.
– Allowing dynamic updates of specifications.
– Capable of dealing with external events.
• Deals with sequences of sets of EVOLP rules.
• EVOLP rules are generalized LP rules (i.e. not’s in heads and bodies)
plus the special predicate assert/1, which can appear both in
heads or bodies.
• The argument of assert/1 is any EVOLP rule (and so assert’s can
be embedded).
• Sequences may fork due to alternative assertions in alternative
models.
EVOLP semantics
• The meaning of a sequence 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 in
the sequence (i.e. at a state).
• A first model in a sequence is built by “computing” the
semantics of the first EVOLP program, where assert/1 is
treated as any other predicate.
• If assert(Rule) is true at some state, then the KB is updated
with Rule in the next state.
• This updating of the KB, and the “computation” of the next
model in the sequence, is performed as in DLP.
Email agent core example
• 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.
• The specification may change dynamically.
email EVOLP rules
• By default, messages are stored in the inbox:
assert(msg(M,F,S,B,T)) ← newmsg(M,F,S,B), time(T), not delete(M).
assert(in(M,inbox)) ← newmsg(M,F,S,B), not delete(M).
assert(not in(M,F)) ← delete(M), in(M,F).
• Spam messages are to be deleted:
delete(M) ← newmsg(M,F,S,B), spam(F,S,B).
• The definition of spam can be done by LP rules:
spam(F,S,B) ← contains(S,credit).
• This definition can later be updated:
not spam(F,S,B) ← contains(F,my_accountant).
More email EVOLP rules
• Messages can be automatically moved to other folders. When that
happens (not shown here) the user wants to be notified:
notify(M) ← newmsg(M,F,S,B), assert(in(M,F)), assert(not in(M,inbox)).
• When a message is marked both for deletion and automatic move
to another folder, the deletion should prevail:
not assert(in(M,F)) ← move(M,F), delete(M).
• The user is organizing a conference, assigning papers to referees.
After receipt of a referee’s acceptance, a new rule is to be added,
which forwards to the referee any messages about assigned papers:
assert( send(R,S,B1) ← newmsg(M1,F,S,B1), contains(S,PId), assign(PId,Ref) )
← newmsg(M2,Ref,PId,B2), contains(B2,accept).
Our XML Tools
• A non-validating XML parser supporting XML Namespaces,
XML Base, and complying with the recommendations of XML
Info Sets.
It can read US-ASCII, UTF-8, UTF-16, and ISO-8859-1 encodings.
• A converter of XML to Prolog terms.
• A RuleML compiler for the Hornlog fragment of the language,
and extended with default and explicit negation.
• Query evaluation procedures under our paraconsistent WellFounded Semantics with eXplicit negation (WFSXp).
Semantic Web Application
•
Logic Programming and the Semantic Web:
– RuleML group.
– 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.
Applications.
W4 project: Well-founded semantics for the WWW
Mission Statement
The W4 project aims at developing Standard Prolog inter-operable tools for
supporting distributed, secure, and integrated reasoning activities in the Semantic
Web.
Project Goals
•
•
•
•
•
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).
W4 project: Well-founded semantics for the WWW
Why Well-founded Semantics ?
• 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...
• A lot of extensions are built 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.
W4 project: major guidelines
• 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.
Why ?
Theoretical Issues: current proposals are limited to classical
definite logic programming, meaning that:
– Atoms are either true or false: no form of naturally representing
uncertainy (fuzzy, probabilistic, etc.).
– No default (non-monotonic) negation for representation of incomplete
information.
– No negation(s) for stating explicit negative information.
– No handling of contradiction/paraconsistency.
– No way of extending the language with new connectives.
Most of the above is raised in the Semantic Web Activity Statement, and
there are solutions to them in the LP lore.
Why ?
Practical Issues: current proposals seem not to address
some important problems, namely:
– What happens if a computation fails on the Web ?
– What happens if a loop is introduced in the course of distributed
inference (positive or negative) ?
– Can the computation safely proceed while answers do not arrive ?
– How to share and avoid redundant computations ?
– How to update knowlege (in the Web) ?
– How to handle event-condition-action rules ?
Logic programming based semantics and corresponding
implementation technology has answers to these questions.
Integration issues
• Integration of existing engines and semantics.
• Integration with XML technology:
namely RuleML, RDF, and OWL.
• Integration with database systems.
• Integration with Web Services.
Implementations
• Both for WF and Stable Model/Answer Set semantics.
• Several reasoning engines are functioning, namely our W4
RuleML query engine, and EVOLP over the Well-Founded
Semantics, and others.
• We take part in the implementation of advanced Prolog
compilers, namely GNU-Prolog and XSB with threads and
distributed tabling.
• We are working on the implementation of tabled distributed
query engines for RuleML.
Tabling in a Nutshell
• The first time a goal is called a new table is created for storing
its answers.
• The engine resolves the goal as in SLD resolution except that:
– Answers are put in the appropriate tables.
– Repeated answers are discarded.
– Calls to goals in already existing tables do not start new derivations:
each goal becomes a consumer of its table.
• Completion detection algorithms are necessary to ensure
termination, via SCC detection algorithms.
• Goal "identity" may be found by variant checking or by
subsumption checking.
• Handling of default negation requires additional machinery.
Distributed Tabling
• 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.
• Addresses the issue of table completion by resorting to known
distributed termination detection algorithms.
• Can be immediately extended to handle stratified negation.
...More on the third value
• The existence of an undefined logical value is fundamental.
• While waiting for the answers to a remote goal invocation it
can be assumed that its truth-value is undefined, and to
proceed the computation locally.
• This is the way loops through 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.
Architecture
• The Table Storage clients are responsible for:
– Keeping the answers for given goal calls, avoiding redundant answers.
– Managing the delivery of solutions to the appropriate invoking goals.
– They act simultaneously as proxy and cache systems.
• The Prover clients perform the logical expansion operations
on the set of active goals.
• We have a prototype meta-interpreter running on top of XSBPVM Prolog (1000 lines of code!) on a PC-cluster.
In this setting we have two other software components:
a goal manager and a table manager.
Building Systems
• The construction of prototypical systems depends on the
definition of:
– Syntactic extensions (apparently, not very difficult).
– Semantics (should we adopt WFS/SMs or any of its extensions as a core
semantics ?).
– Goal invocation 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.
What About Paraconsistency ?
• With the introduction of explicit negation, contradictions may
arise in knowledge bases.
• We have defined a paraconsistent well-founded semantics with
explicit negation, with very interesting properties:
– contradiction is "propagated" by the coherence principle, corresponding to
a localized Reductium ad Absurdum.
– we can detect dependency on contradiction, so we can reason safely in the
presence of contradiction.
– contradiction can be blocked by resorting to normalized default rules.
– there is a program transformation into WFS.
– there are polynomial inference procedures.
Reasoning Integration Framework
• We are able to integrate in the same logic programming
framework incomplete, uncertain and paraconsistent reasoning
forms. We can say:
neg strike ← <0.87, 0.13>
strike ← <0.87, 0.13>
% True figures !!
change_law ← strike
• In certain well-defined circumstances, our semantics detect the
dependencies on contradiction, such as in the example above.
Extended Antitonic Programs
• We have a proposal of a semantics allowing the integration of
explicit negation with default negation in a many-valued
setting.
• We adhere again to the coherence principle.
• Our main algebraic structures are bilattices, as defined by
Ginsberg and Fitting.
• Our results have been submitted. They are very encouraging.
Existing Embeddings
• 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 (with Jan Maluszynski and Aida Vitória).
What is missing
• Theory:
–
–
–
–
–
–
The floundering problem ...
Constructive negation ...
Abduction ...
Disjunction...
Constraints ...
...
• Pragmatics:
–
–
–
–
–
–
Integration with ontologies.
A proper type system.
A RuleML syntax in order to start developing more advanced systems.
Guidance of the community regarding direction of research.
Control problem.
...
WWW LP Agent Server
XML based Communication Layer
RuleML interface
XML Parser & Generator
EVOLP
DLP
Logic Programming Engines
Inter-Operability
Machine 1
Semantic
Web
Server
XSB
Prolog
Machine 3
Machine 2
Prolog
Prolog
DBMS
C++/Java
Table
Prolog
Prover
W4 project: Conclusions
• In our opinion, Well-founded semantics will 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 has been proposed.
Rational+Reactive Agent Architecture
Java
Control Cycle
InterProlog
can abduce
Rational
P
XSB Prolog
InterProlog
Reactive
P+R
XSB Prolog
cannot abduce
Rational + Reactive Agent Architecture
Action Handler
External
Interface
UpdateH
Updates
ext.project
int.project
CC
projects
Rational
P
Reactive
P+R
The End
Descargar

Implementing Rational Features for Agents in Logic …