Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.cplire.ru/Lab144/iclp2003/a0_poster.doc Дата изменения: Mon Sep 24 14:58:03 2007 Дата индексирования: Tue Oct 2 04:50:24 2012 Кодировка: Поисковые слова: п п п п п п п п

Development and Application of Logical Actors Mathematical Apparatus for
Logic Programming of Web Agents

Alexei A. Morozov

Institute of Radio Engineering and Electronics RAS

Mokhovaya 11, Moscow, Russia, 125009

morozov@mail.cplire.ru

http://www.cplire.ru/Lab144

Web agents are programs that automate retrieval, recognition, extraction,
and analysis of information on the Internet oriented toward the needs of an
individual user (or group of users).

[pic]

Fig.1. An example of a 3D (VRML) report created by a Web agent

(available at http://www.cplire.ru/Lab144/space/prolog.html).

| |
|What is the fundamental problem to be solved in our |
|project? |
|We are interested in mathematical strictness of logic |
|programs that operate in dynamic outer world. Web agents|
|are only a particular case of such programs. Other cases|
|are the following: visual user interface, virtual |
|reality, control systems, etc. |

Agents differ from the widely used Internet retrieval systems in the
following:

1) They can autonomously operate during long periods of time (days,
weeks, or more).
2) As any other program, once created, an agent can be used many times,
whereas a query to a search engine invokes a single information
retrieval.

One of the most interesting and perspective approaches to programming
Web agents is logic programming of agents. The urgency of this approach is
determined, in particular, by the fact that the ideology and principles of
logic programming correspond to the problems of retrieval, recognition, and
analysis of ill-structured and also hypertext information. However, the
main advantage of logic programming is the fact that, in the framework of
this approach, there exist criteria for evaluating the mathematical
strictness of information processing methods, namely, the model-theoretic
semantics of programs and also the notions of soundness and completeness of
logic programs.
However, up to now, no mathematical apparatus which could provide
sound and complete work of logic programs (agents) in a dynamic external
environment (i.e., in conditions of permanent change and augmentation of
information in the Internet) was created. To solve this problem, we have
developed a mathematical apparatus based on the principle of repeated
proving of subgoals.

1. The Idea of Mathematical Apparatus:

Repeated Proving of Logical Actors

Our mathematical apparatus for logic programming of Internet agents
includes:

1) A logic language for describing the agents that operate in a dynamic
environment;
2) A declarative (model-theoretic) semantics of agents;
3) Control strategies for executing logic programs (Web agents) that are
sound and (under some conditions) complete with respect to the model-
theoretic semantics of these agents.

Within the framework of our model of intelligent agents, an Internet
agent (or a group of interacting Internet agents) is a logic program
controlled by a special strategy which implements the so-called repeated
proving of subgoals.
The idea of repeated proving consists in dividing the program into
separate subgoals (called logical actors) that have the following
properties (see Fig. 2):

1) Common variables are the single channel of data exchange between the
actors.
2) The proving of separate actors can be fulfilled independently in
arbitrary order.
3) One can cancel the results of proving of any actor while keeping all
other subgoals of the program.


[pic]


|A1, (, An |- |Logical actors |
|V1, (, Vm |- |Common variables |
|W1, (, Wk |- |Instances of classes (worlds) |


Fig.2. The idea of logical actors.

After canceling the results of the proving of the actor, its proving can be
repeated. Thus, one can implement a modification of reasoning. The logical
inference can be partially modified. The results and the consecution of
reasoning itself can be partly modified in the process and after the logic
inference. This makes it possible to eliminate the contradictions between
the results of the logical reasoning and new information.
We have developed also object-oriented means (classes, inheritance)
for structuring the search space.

2. Comparison with Nonmonotonic Approach

Our technique is an alternative to the nonmonotonic approach. The idea of
this technique can be illustrated by canonical example about the ostrich
Tweety.
We write the canonical example in two different ways. The first method
is based on the use of the logic program with the not statement, which is a
certain approximated implementation of nonmonotonic logic.
?- can_fly ("Tweety", Answer).
can_fly (Name, "yes") :-
bird (Name),
not ostrich (Name).
can_fly (Name, "not") :-
bird (Name),
ostrich (Name).
bird ("Tweety").
ostrich ("Tweety").

If the database does not contain the fact formulated as ostrich("Tweety"),
then the proof of the assertion not ostrich("Tweety") will succeed and
Prolog will read out Answer = "yes", meaning that Tweety can fly. However,
when the fact ostrich("Tweety") is appended, this negation becomes not
derivable, and Prolog will read out that Tweety cannot fly.
The second method is based on the use of the technique of logic
actors. Logic actors are subgoals of the logic program that can be proven
repeatedly without logic program backtracking. In what follows, we denote
logic actors by using the prefix @.

?- can_fly ("Tweety", Order, Answer).
can_fly (Name, Order, Answer) :-
bird (Name),
@ suitable_order (Order, Answer).
suitable_order ("conventional", "yes").
suitable_order ("ostriches", "not").
bird ("Tweety").
This works as follows. In the course of logic program run, the actor
@ suitable_order is proven as a usual subgoal; Prolog will output the
following result: Answer = "yes", and, in addition, it will assign the
value to the variable Order, i.e., Order = "conventional". Subsequently, if
it turns out that Tweety is an ostrich, this information must be
communicated to the program via the following destructive assignment
operation:
Order := "ostriches" .
The soundness of inference is certainly violated by this destructive
assignment. However, once the value of the variable Order has been changed,
the logic actor mechanism will automatically restore the soundness of the
inference by the repeated proving of a separate subgoal, namely, the logic
actor @ suitable_order. This time, the fact suitable_order ("ostriches",
"no") will be selected, and the program will output the new result:
Answer = "no" .
The second formalization method has the following merits:

1) The new data arrive in the form of terms (data items) rather than
logic statements.
2) If the source data have been changed, it is only necessary to prove
once again certain program subgoals.
3) We stay in the framework of classical monotonic logic with all its
descriptive and deductive abilities being preserved.


Logic Object-Oriented Model of Asynchronous Concurrent Computations

The most complicated and interesting problem to be solved for implementing
the idea of logical actors and repeated proving is the development of
control strategies supporting repeated proving which are sound and (if
possible) complete. We have developed several control strategies supporting
repeated proving.
One of the first control strategies was created for the execution of
sequential logic programs with logical actors. Further experiments on
visual logic programming of intelligent agents have shown that it is
expedient to develop more complex concurrent control strategies as well. To
the present day, we have expanded our computing model by introducing
concurrent processes.

[pic]
Fig.3. An example of concurrent logic program using flow messages, direct
messages, and so-called residents (R).

Each concurrent process is a system of logical actors. The processes
interact by using asynchronous messages of two kinds (see example on
Fig. 3):

1) The so-called direct messages (intuitively, they correspond to
asynchronous call of the predicates in one concurrent process from
another one);
2) Flow messages (corresponding to data transmission through the common
variables of processes).

The composition of messages of these two kinds helps us to describe the
complex behavior of agents without means of synchronization of concurrent
processes.
The main advantage of our expanded computing model is that it provides
a declarative (classical model-theoretic) semantics of concurrent logic
programs. The concurrent logic program is always sound w.r.t. its
declarative semantics. The program is not only sound but also complete
w.r.t. its declarative semantics if some strict limitations on the
properties of the system of processes are fulfilled.

1) Each separate process (as a separate logic program that computes some
data) must be complete with respect to its declarative semantics. In
particular, the absence of process cycling should be guaranteed.
2) The procedures that compute data transmitted from one process to
another must be deterministic in order that the completeness of logic
inference is not lost due to the impossibility of backtracking from
the receiving process to the transmitting one.
3) The information transmission between the processes should be strictly
one-directional. Only flow messages should be used (this condition can
be, in principle, softened). The system of interacting processes
should have no feedback.

The systems of interacting processes complying with these strict conditions
are of great practical importance, because they describe the flow
processing of data received by a system of intelligent agents from outside.
The soundness and completeness properties ensure the exhaustive
search, i.e., guarantee all solutions that fulfill the given logical
conditions.

Development of the Actor Prolog language

We have created an object-oriented logic language Actor Prolog on the basis
of our mathematical apparatus (the definition of the language, including
all new means, is available at our Website http://www.cplire.ru/Lab144). We
have also introduced some special means that support programming of Web
agents in recent versions of the language:

1) There are predefined classes implementing HTTP and FTP protocols.
2) There are means for visual programming based on translation of
Structured Analysis and Design Technique (SADT) diagrams into Actor
Prolog.
3) There are syntactical features supporting component-oriented
programming.

Now, we have a working version of a system of logic programming of
Internet agents on the basis of the developed mathematical apparatus and
Actor Prolog.


[pic]
Fig.4. Control panel of Actor Prolog player.

You are welcome to take part in beta testing of Actor Prolog. Please
contact Dr. Alexei A. Morozov (morozov@mail.cplire.ru).

Speculative Concurrent Computations

The principle of interaction of concurrent processes developed by the
author and his colleagues is a generalization of the method of speculative
computations.
The idea of speculative computations implies that certain branches of
the algorithm can be implemented in advance, prior to the moment when it
becomes clear whether the obtained data are needed for further program
execution. The use of this idea and the mathematical apparatus of logic
programming makes it possible not to delay concurrent processes for their
synchronization.
Instead of delaying the processes, we use a modification of logic
inference; as a result, the general scheme of interaction of concurrent
processes can be represented as follows.
Each process performs computations with data available at the present
moment. If some data are not yet received, the process performs
computations with incomplete data. The developed strategy of execution of
logic programs is sound with respect to their declarative semantics;
therefore, any results obtained during computations are correct with
respect to the declarative semantics of the program.
Computations with incomplete input data can be regarded as a certain
form of computing by default. Subsequently, when new or modified input data
arrive in the process, the conducted computations are modified and the
earlier obtained results are refined.
Modification of logic inference in our computation model is based on
the principle of the repeated proving of subgoals.
| |
|The Actor Prolog Project |
|Theoretical results: |
|A logical interpretation of object-oriented programming (OOP). |
|Repeat proving of logical actors providing soundness in dynamic |
|environment. |
|A new concurrent computing model. |
|Programming technology issues: |
|Visual programming based on Structured Analysis and Design Technique |
|(SADT). |
|Component-oriented programming. |
|Implementation issues: |
|All the Actor Prolog agents are persistent. |
|Predefined classes support FTP and HTTP now. |
|You are welcome to participate in beta testing of Actor Prolog |
|(http://www.cplire.ru/Lab144). |


Visual Programming of Internet Agents

We have developed experimental tools for visual logic programming of Web
agents. The use of SADT-diagrams forms the basis. SADT-diagrams are a
variety of functional diagrams and are widely applied for the analysis and
design of complex systems.
The system of visual programming implements the following scheme for
intelligent agent design.

1) SADT tools are used to develop the graphic description of an
intelligent agent. SADT-description is a hierarchy of blocks that
receive and pass data flows (see example on Fig. 5).
2) Each elementary block of a SADT-model is put into correspondence with
a logic description in the form of a certain class of Actor Prolog.
The source text in Actor Prolog can be written by a programmer or
taken from the library of reusable modules.
3) The graphic description of the agent is automatically translated into
the text in Actor Prolog. The syntactic means of Actor Prolog make it
possible to implement the block-hierarchical structure and links
between blocks of a diagram in the form of communicating processes.
4) Assembling the automatically created text and descriptions of
elementary blocks, we obtain a ready-to-use program in Actor Prolog.


[pic]
Fig.5. An example of SADT diagram describing data processing.

Experimentation with visual programming has shown that SADT-diagrams
can be conveniently used not only as a visual programming language but
simply as a user graphic interface. At present, visual programming system
automatically creates visual interface of a logic program on the basis of
source SADT-diagram (see examples on the figures 6, 7).
Individual blocks of an SADT-based user interface are implemented by
using concurrent processes. As a rule, each elementary block of a diagram
has its own dialog box that opens by the click of a mouse.

[pic]
Fig.6. An example of visual user interface based on SADT.

The color of the block changes automatically depending on the state of
the corresponding process. A user can interact with the blocks in any
order.
The tools for visual programming based on the object-oriented logic
approach substantially simplify the creation of Web agents, as well as
their subsequent support and modification.

Persistent Agents

All programs written in Actor Prolog are long-lived (persistent). A user
can at any moment save the state of the operating program into a file and
then restart it from that point. Actor Prolog saves states of all objects
of a program, including the contents of text windows and current positions
of open files. This feature is of great importance for Web agents, because
they operate during long periods of time. So, they can restore their states
in cases of hardware or software malfunctions in the computer system.

[pic]

Fig.7. An example of visual expert system written in Actor Prolog

(see details at http://www.cplire.ru/Lab144/start/e_oil.html).


Conclusions

The mathematical apparatus of logic programming of intelligent agents
performing the search and recognition of information in a dynamic Internet
environment is developed. The developed mathematical apparatus is based on
the principle of the repetitive proving of subgoals, which makes it
possible to modify the logic reasoning during the execution of logic
programs.
Based on the developed apparatus of modifiable reasoning, we have
created the Actor Prolog, concurrent object-oriented logic language, which
ensures the correctness of Web agents functioning under conditions of
permanent change and updating of information.
The developed tools make it possible to create agents for gathering
and analyzing information on the Internet. The developed approach supports
visual and component-oriented programming of Internet agents.

References

1. Actor Prolog Website http://www.cplire.ru/Lab144 .
2. Morozov A.A. Actor Prolog: an Object-Oriented Language with the
Classical Declarative Semantics // Proc. of IDL'99 workshop. - Paris,
France, September 27-28, 1999. (http://www.cplire.ru/Lab144/paris.pdf)
3. Morozov A.A., Obukhov Yu.V. On the Problem of Logical Recognition in the
Dynamic Internet Environment // Pattern Recognition and Image Analysis. -
2001. - Vol.11. - No.2. - pp.454-457.
(http://www.cplire.ru/Lab144/pria5.pdf)
4. Morozov A.A., Obukhov Yu.V. An Approach to Logic Programming of
Intelligent Agents for Searching and Recognizing Information on the
Internet // Pattern Recognition and Image Analysis. - 2001. - Vol.11. -
No.3. - pp.570-582. (http://www.cplire.ru/Lab144/pria570m.pdf)
5. Morozov A.A. Getting Started in Actor Prolog. - IRE RAS: 2002. -
http://www.cplire.ru/Lab144/start/ .
6. Morozov A.A. On Semantic Link Between Logic, Object-Oriented,
Functional, and Constraint Programming // Proc. of MultiCPL'02 workshop.
- Ithaca, USA, September 8, 2002. - pp.43-57.
(http://www.cplire.ru/Lab144/multicpl.pdf)
7. Morozov A.A., Obukhov Yu.V. Development of the Methods and Tools for
Mathematically Correct Logic Programming of Internet Agents // Pattern
Recognition and Image Analysis. - 2003. - Vol.13. - No.2. - pp.225-227.
(http://www.cplire.ru/Lab144/pria225.pdf)
8. Morozov A.A. Logic Object-Oriented Model of Asynchronous Concurrent
Computations// Pattern Recognition and Image Analysis. - 2003. - Vol.13.
- No.4. - pp.640-649. (http://www.cplire.ru/Lab144/pria640.pdf)
See examples of Actor Prolog programming in
Morozov A.A. Getting Started in Actor Prolog. -

IRE RAS: 2002. - http://www.cplire.ru/Lab144/start/ .

|We look for International co-operators. The possible directions of |
|joined efforts could be the following: |
|Participation in the INTAS and EC projects. |
|International cooperation in development of new generation logic |
|programming means. We work about 15 years on the following problems: |
|Logic interpretation of object-oriented approach. The main idea is the |
|following: OOP should be not only a supported feature, but a basis of |
|any modern programming language. |
|The destructive assignment and dynamic environment semantics problems. |
|These problems have no generally accepted solutions now: from the |
|model-theoretic semantics standpoint, current standard Prolog is a |
|prover, rather than a programming language. We have an idea how to |
|improve the situation. |
|Development of logic languages syntax design. From our point of view, |
|current standard Prolog has a design of interpretation (script) |
|language, rather than of a modern compilable language. So, Prolog |
|should be totally revised. |
|Development and implementation of Actor Prolog language. We want to |
|create an open implementation of the language. |
|Research, development, and implementation of compilers from Actor |
|Prolog into Java, .NET, C++. |
|Any other ideas and suggestions are welcome! |