Experience with a Functional-Logic Multi-Agent Architecture for Medical Problem Solving

Massimiliano Campagnoli Giordano Lanzola1 Harold Boley2

1 Department of Informatics and Systems Science

University of Pavia

Via Ferrata 1, 27100 Pavia, Italy

2 German Research Center for Artificial Intelligence – DFKI GmbH

Erwin-Schrödinger Straße (Bau 57) Postfach 2080

67608 Kaiserlautern, Germany

{max,giordano}@aim.unipv.it – boley@informatik.uni-kl.de

Abstract. This paper reports on our experience with applying a functional-logic language to distributed, multi-agent medical problem solving. RELFUN, used both as the agent-implementation and the communication-content language, cross-extends Horn relations and call-by-value functions just enough to yield a unified operator concept. Relations acquire application nesting and higher-order notation; functions acquire non-groundness and non-determinism. Relations are defined by Horn-like clauses; functions are defined by rules with an additional returned-value premise. The chosen multi-agent framework relies on the communication protocol of KQML (Knowledge Query and Manipulation Language), developed as part of the DARPA knowledge sharing effort. The selected medical problem concerns task planning for patients affected by AML (Acute Myeloid Leukemia). The medical professionals involved in AML treatment are modelled as agents communicating in a well-defined fashion. On the basis of a RELFUN representation of KQML performatives both cooperation and domain knowledge is formalized in a functional-logic style. Its declarative power is shown to be useful for this application. However, for communicating clausal knowledge, update operations turn out to be unavoidable, and RELFUN is extended towards assert/retract. The efficiency of the interpreter has been sufficient in this communication-intensive prototype.

Keywords: functional-logic programming, multi-agent systems, medical task planning

 

Introduction

There exist various experiences in constructing applications in functional and logic languages alone as reported, e.g., in the conference series "Lisp and Functional Programming" and "Practical Applications of Prolog", respectively. Applications in integrated functional-logic languages [Hanus, 1994] have been less frequent, however, and little has been reported about experiences with them. Historically, functional-logic languages started off with practically oriented, loose couplings of LISP and PROLOG components such as LOGLISP, and LISP-based hybrid expert-system shells often contained some PROLOG-like component. In the few applications written in these LISP-PROLOG couplings and shells, however, one of the integration partners was normally dominating. Later, theoretically oriented, tight syntheses of functional and logic components such as EQLOG were studied. Even in those syntheses that were really implemented, very few applications were developed – apart from the published examples demonstrating the new paradigm. Later, the accumulated theoretical insights in functional-logic concepts and implementations have led to a new treatment of practical problems, as attempted, e.g., by ALF, BABEL, and RELFUN. For the problems attacked, an initial distinction between internal tools (e.g., the ALF compiler in ALF) and external applications (e.g., the RTPLAST selector in RELFUN) can be made. Application-oriented projects in whose context RELFUN has been developed have exerted some pressure to test its general concepts on the latter category, namely on real-world examples from technical modelling, mostly in mechanical engineering. Experiences with RTPLAST, a RELFUN knowledge base for selecting Recyclable ThermoPLASTics that satisfy engineering requirements, have for example been reported at a materials-science conference [Boley et al., 1994].

The present paper reports on our experience with applying RELFUN [Boley, 1999] to problems in distributed medical care. This application arose "externally" in the original sense of the word: the first author, working with the LISP-based expert-system shell KEE, supporting frames as well as forward and backward rules, noticed RELFUN on the net and switched to it, since frames are mappable into clauses and RELFUN’s rules offer more versatility than KEE’s ones. After his initial implementation of a RELFUN-based distributed medical-care system, he contacted the third author, further developing RELFUN, and the Pavia/Kaiserslautern teams joined forces, with the second author being the expert in the medical domain.

The three authors then set out together on the implementation of a system composed of multiple communicating agents aimed at exploiting the rapidly emerging methodologies addressing Computer Supported Cooperative Work (CSCW) for the management of patients affected by Acute Myeloid Leukemia (AML). AML was carefully selected as the application domain since it greatly emphasizes the need for different health care professionals to cooperate towards the achievement of a common goal. We first extended RELFUN with a powerful set of KQML [Finin et al., 1992] communication primitives, and then we implemented several agents, each one encapsulating the domain specific and the strategic knowledge belonging to a different professional. The overall prototype described in this paper illustrates the potential of a methodology which may also prove to be useful in improving the quality and reducing the cost-efficiency ratio of the health care delivery process by laying down new organizational infrastructures exploiting distributed information technology.

The following aspects turned out to be important in this application (reasons known in advance, hence critical in choosing this language, are emphasized by an "*"):

* Like the previously used systems KEE and KQML, RELFUN is written in LISP, so that its implementation was easy to interface with existing software;

* RELFUN is highly portable among COMMON LISP versions and easy to install, especially if only the interpreter is needed, as in this prototype;

* The on-line documentation is satisfactory, containing many executable examples, on which other programs can be modelled;

* These existing kernel RELFUN features were needed:

* Relations and functions, both essential in the application, are integrated in a natural manner;

* Relations and functions may be of varying arity, helping to define generic KQML ask messages;

* Many functions can be inverted, as convenient for sharing the specification between two (counter-)directed computations;

* Higher-order functions permit a declarative implementation of messages passed as data and activated in their receivers (function variables) as well as a high-level encoding of agent abilities within facilitators (functional values);

* Finite domains are usable as first-class citizens allowing a compact and efficient representation of disjunctive values.

2 Application-Oriented Functional-Logic Concepts

The two classical declarative paradigms are functional programming in the tradition of pure LISP and logic (relational) programming following pure PROLOG. Basic communalities between these or modern functional (e.g., Haskell) and relational (e.g., Gődel) languages have led to increasing efforts at their integration in search of a unified declarative paradigm for ”functional-logic" or "relational-functional" programming (cf. the survey [Hanus, 1994]). Here we discuss application-oriented issues of such an integration with an emphasis on syntactic and semantic simplicity as called for by practical use. Since the medical application is based on RELFUN [Boley, 1999], this language will be used to illustrate the required functional-logic concepts.

Having the new infix "&" precede an explicit value to be returned, as a simple extension to PROLOG’s Horn-clause syntax, a RELFUN operator is defined by a system of valued clauses which may embody increasing expressive power as follows:

(1) Unit clauses (facts) op(arg_1,...) for extensional relation definitions are implicitly true-valued. For example, healthy(p0) is a ground fact stating the health of individual p0. Generalizing PROLOG’s "|"-use in lists, varying arity is permitted in clause heads and in calls, e.g. the calls healthy(Who), healthy(First|Rest), and healthy( |Args) respectively bind Who to p0, First and Rest to p0 and [], and Args to [p0].

(2) Unconditional equations op(arg_1,...) :& exp for operator (normally, function) definitions whose case distinctions are made only via unification of left-hand sides (written as clause heads) return an explicit right-hand-side (rhs) expression value; in molecular rules exp specializes to a term. For example, bodytemp(p1) :& 39 is a ground molecular rule, specializing exp to a numeric constant, which specifies a unary bodytemp function that maps individual p1 to value 39. The calls bodytemp(p1) and bodytemp(Who) now both return 39, the latter also binding Who to p1.

(3) Non-unit clauses (rules) op(arg_1,...) :- cnd_1, . . . for relation definitions whose case distinctions require conditions (written as clause premises, also used for the accumulation of partial results) are implicitly true-valued. For example, bodytemp(P,37.5) :- healthy(P) specifies a binary bodytemp relation without preferred direction of computation. Using the fact in (1), the call bodytemp(p0,V) binds V to 37.5.

(4) Conditional equations op(arg_1,...) :- cnd_1, . . . & exp for operator (normally, function) definitions whose case distinctions require conditions, as in (3), again return an explicit rhs expression value, as in (2). For example, bodytemp(P) :- healthy(P) & 37.5 specifies a unary bodytemp function that maps variable P to constant 37.5. Using the fact in (1), the call bodytemp(p0) returns 37.5. Alternatively, bodytemp(P,37.5) :- healthy(P) & 0.9 specifies a binary bodytemp function that maps variable P and constant 37.5 to probability 0.9. Now the call bodytemp(p0,V) binds V to 37.5 and returns 0.9.

RELFUN’s primary concern is minimal integrative extensions of both declarative programming paradigms wrt fusion into a relational-functional kernel [Boley, 1999]. For this, two relational essentials, (R1) and (R2), are mapped to corresponding extensions of functional programming, and two functional essentials, (F1) and (F2), are similarly transferred to the relational paradigm:

(R1) The relational essential of permitting first-order non-ground terms (terms being or containing free logic variables, which may become bound by calls) is transferred to functional programming: a function can take non-ground terms as arguments by using (two-sided) unification instead of (one-sided) matching, and similarly can return non-ground terms as values. With call-by-value evaluation of functional applications this will lead to innermost conditional narrowing. Many functions (such as the unary bodytemp function) can thus be called inversely using the ".=" primitive, which generalizes PROLOG’s "is" to user-defined functions.

(R2) Since a non-ground (e.g., inverse) function call may deliver several "solution values", this also entails a transfer of the relational essential of (don’t-know) non-determinism (solution search, implemented by backtracking enumeration as in PROLOG) to functional programming. Historically, however, non-ground functional programming was proposed as a result of relational-functional integrations, while non-deterministic functional programming was first introduced as a purely functional generalization. For finitely non-deterministic calls RELFUN’s ordered bagof version tupof can be used to return the list of all values. For example, with the sequence of clauses in (1), (2), and (4) tupof(bodytemp(Who)) returns [39,37.5].

(F1) The functional essential of application values (function applications return value terms, hence can be nested into "functional compositions") is transferred to relational programming: a relation whose call succeeds always returns the value true in the manner of a characteristic function, besides possibly binding variables. On the other hand, each argument of a relation call may be the value returned by an application rather than a directly specified term. Hence, as a constructor-based language, RELFUN explicitly distinguishes (passive, instantiated) structures from (active, evaluated) applications, marking instantiation vs. evaluation by square brackets vs. round parentheses. For example, with (1) and RELFUN’s prelude definition tup( |R) :& [ |R], the nesting healthy(first(tup(p0,p1))) returns true.

(F2) The functional essential of higher-order functions over named functions (named functions as functional arguments and values) is transferred to relational programming: a relation can take named relations as arguments. Our relational sublanguage permits logic variables also in the relation position of queries and definitions ("predicate variables"), introducing some syntax of second-order predicate logic; this is transferred to functional programming ("function variables"). The higher-order operators permitted here, although practically very useful, embody just conservative, syntactic extensions that can be reduced to first-order versions via an apply dummy operator. For example, with (1), the call Pred(p0) binds Pred to healthy, and, using this binding, Pred(p1) fails.

On the basis of the integrated RELFUN kernel provided by (R1) to (F2), common functional-logic extensions were developed. To illustrate, first-class finite domains are introduced as dom terms, which can be bound to variables, used as arguments, embedded in data structures, and returned as values. For successful constant-domain unification the constant must occur among the domain’s constants; on domain-domain unification the intersection of the domains is computed. For example, both p1 .= dom[p0,p1,p2] and dom[p0,p1] .= dom[p1,p2] return p1, equivalent to dom[p1].

3 A Multi Agent Environment Implemented on Top of RELFUN

Solving real problems is a complex cognitive activity requiring the exploitation of different knowledge types and calling for the dynamic selection of the goal to pursue as well as the subsequent choice of the most appropriate reasoning technique given that goal and the context shown by the problem. Thus a great deal of research in AI has been devoted to the identification of suitable knowledge representation formalisms, reasoning techniques, as well as to formulating epistemological frameworks [Ramoni et al., 1992] and computational architectures supporting them [Lanzola and Stefanelli, 1993].

Nevertheless, the key issue is that applications featuring a high complexity level necessarily require the encapsulation of increasing amounts of knowledge up to the point that the costs concerned with the process of acquiring, representing and maintaining that knowledge actually become unbearable also in research contexts [Lenat and Feigenbaum, 1991]. To overcome those limitations the scientific community has become increasingly aware of the need of developing sharable and reusable bodies of knowledge which may be easily interchanged among different systems [Neches et al., 1991; Klinker et al., 1991]. However many authors are actually considering that the ultimate solution towards automating problem solving entails a full reconsideration of its paradigm. Therefore, instead of adopting a "monolithic" approach where all of the problem solving expertise is constrained into a single system, the current efforts envision a different architecture composed of a community of multiple cooperating agents, each one responsible of providing a different expertise [Fisher and Wooldridge, 1993; Jennings et al., 1993].

This approach is much closer to the way problems are actually solved in real life through the cooperation of multiple individuals. Furthermore, it is also helpful in overcoming the constraint of integrating, within one single implementation, different knowledge types which presumably have been independently developed and very often make use of different, if not incompatible, formalisms. Several research efforts are currently aimed either at developing generic frameworks for building agents like AOP [Shoam, 1993] or analyzing the pragmatic issues concerned with inter-agent transactions as KQML [Finin et al., 1992]. While the former ones are more oriented towards representing agents by modelling their internal states in terms of beliefs, desires and intentions, the latter ones limit themselves to the investigation of the communication primitives as expressed by speech act theory [Searle, 1969]. In view of experimenting with a multi-agent architecture applied in clinical medicine, we preferred the KQML approach since it allowed us to focus on the communication requirements needed for exchanging and interpreting messages among separate agents. This has been useful in complementing the knowledge representation capabilities typical of a functional-logic programming approach such as the one provided by RELFUN, which was being used for implementing our agents.

KQML (Knowledge Query and Manipulation Language) is a language and a protocol designed to support communication between separate knowledge based modules as well as between knowledge based systems and databases. It has been developed within the ARPA Knowledge Sharing Effort (KSE) [Neches et al., 1991], a consortium established to develop conventions facilitating the sharing and reuse of knowledge. Based on speech act theory, it provides for a message format and a message-handling protocol supporting runtime interaction among different agents, while using standard messaging protocols as transport layer, e.g. SMTP, HTTP, etc. A typical KQML message consists of a performative with its associated content, expressed in a suitable language, and a set of transport arguments. Those basically include a message sender, a receiver, and two labels, one for properly identifying the message (identifying label) and the other one to be used as the message identifier in a possible peer agent reply (expected label). Other arguments indicating the assumed ontology and the content language can be added as well.

Several reserved performatives are defined in KQML:

The performative’s content can be expressed in different languages: KIF, PROLOG, LISP and RELFUN, to mention some. Of course, the agent implementation language and the performative’s content language do not need to be the same, nevertheless using RELFUN both to implement the agent and to encode the performative’s content is helpful in easing and speeding up the processing of incoming messages and providing appropriate replies.

Many of the KQML performatives described by [Finin et al., 1992] have been therefore implemented using RELFUN’s capability to process declarative knowledge. Here we give just a few simplified examples, skipping over network details.

The general form of a KQML message encoded in RELFUN is as follows:

kqml-msg(Sender,Receiver,Performative,Content,

In-reply-to,Reply-with)

where Sender and Receiver are the message sender and receiver, respectively. Performative is one of the reserved KQML performative names as defined by Finin [et al., 1992]. Content is a normally non-ground list of the form [Result, Finding[Arg1,...,ArgN]] where Result is obtained by activating the Finding structure to a function call via Result .= Finding(Arg1,..., ArgN). Finding is any kind of medical findings such as body temperature, blood pressure, etc. In-reply-to is the identifying label in a reply, while Reply-with indicates whether the sender expects a reply, and if so its expected label.

To send a KQML message, a call to:

s-msgend (Sender,Receiver,Performative,Content,

In-reply-to,Reply-with)

provides for the actual message delivery from Sender to Receiver using TCP/IP as the transport protocol. Receiver monitors its input message queue until a message arrives and then asserts the message in its knowledge base.

For example, a message sent from a medical agent a1 (say, an internist) to a medical agent a2 (say, a nurse) representing a query about the bodytemp value for patient p1 might be expressed with the following fact, asserted in a2’s knowledge base:

kqml-msg(a1,a2,ask-one,[What,bodytemp[p1]],‗,r1).

where a1 is the sender, a2 the receiver, ask-one the KQML performative, [What,bodytemp[p1]] the content, and r1 a label for the expected reply. Agent a1 keeps tracks of any sent message asserting them in its knowledge base. Agent a2 processes this message using the rules:

process-msg() :-

kqml-msg(Sender,a2,ask-one,[Result,Finding[ |Args]],‗,

Reply-with),

Result .= Finding( |Args),

send-msg(a2,Sender,tell,[Result,Finding[ |Args]],

Reply-with,‗).

process-msg() :-

kqml-msg(Sender,a2,ask-one,‗,‗,Reply-with),

send-msg(a2,Sender,sorry,‗,Reply-with,‗).

The first process-msg rule leads to the reply:

kqml-msg(a2,a1,tell[39,bodytemp[p1]],r1,‗).

being asserted in a1’s knowledge base, provided that the molecular rule:

bodytemp(p1) :& 39.

is present in a2’s functional bodytemp definition. Otherwise the second process-msg rule sends a sorry performative to agent a1, which indicates that a2 understands but is not able to provide any response to the message.

If agent a1 wants to know the name of some patient showing a given body temperature value, say 39, it will send a message to a2, who, once having received a1’s query, will assert the fact:

kqml-msg(a1,a2,ask-one,[39,bodytemp[Who]],‗,r1).

and, afterwards, will process it using the same process-msg rule employed above, with 39 .= bodytemp(Who) instantiating Who to p1. RELFUN’s invertible function bodytemp and higher-order constructor Finding thus help in answering different queries using the same specification.

The names of all patients showing a body temperature value equal to 39 can be asked to a2 as:

kqml-msg(a1,a2,ask-all,[39,bodytemp[Who]],‗,r1).

and answered by the rule:

process-msg() :-

kqml-msg(Sender,a2,ask-all,[Result,Finding[ |Args]],‗,

Reply-with),

Result .= tupof(Finding( |Args)),

send-msg(a2,Sender,tell,[Result,Finding[ |Args]],

Reply-with,‗).

Database performatives like insert and delete are easily implemented via RELFUN’s assertz and retractx:

process-msg() :-

kqml-msg(Sender,a2,insert,[Result,Finding[ |Args]],‗,

Reply-with),

assertz(Finding( |Args) :& Result.).

process-msg() :-

kqml-msg(Sender,a2,delete,[Result,Finding[ |Args]],‗,

Reply-with),

retractx(Finding( |Args) :& Result.).

A KQML facilitator is a specialized agent knowing what other agents are able to do. For example, our medical facilitator knows that a2 is able to answer queries on body temperature values, as well as on many other findings, keeping a table like:

ability(a2) :& bodytemp.

ability(a2) :& weight.

ability(a2) :& age.

...

Note that the values bodytemp, weight, age, ... of the ability higher-order function are themselves function names, representing a2’s "functionality".

If an agent, say a3, wants to acquire the body temperature value for patient p1, but does not know who can provide this information, it can contact the facilitator via the message:

kqml-msg(a3,facilitator,broker-one,

[bodytemp,Agent],‗,r1).

The facilitator, in turn, will determine agent a2 as the appropriate provider via the inversion bodytemp .= ability(Agent):

process-msg() :-

kqml-msg(Sender,facilitator,broker-one,

[Ability,Agent],‗,Reply-with),

Ability .= ability(Agent),

send-msg(facilitator,Sender,tell,

[Ability,Agent],Reply-with,‗).

The determination of the values of the body temperature and ability functions was possible by a simple table look-up. In general, working out a value may require much more complex tasks, where further agents implementing additional reasoning and planning may be involved. This occurs, for instance, when a query is aimed at finding out by which disease a patient is affected.

4 The Acute Myeloid Leukemia Task-Planning

Medicine has always played a key role among the fields chosen by AI researchers for implementing prototypical applications aimed at testing any new methodology being developed. This is due to several distinguishing aspects imposing different constraints and increased demands on medical applications, thereby setting them aside from those addressing any other domain [Blois, 1984]. In particular there is hardly a domain featuring a more widespread distribution of knowledge, expertise and data as medicine does. Managing patients is a complex cognitive activity requiring high interoperability among the several health care professionals involved, who contribute with diverse knowledge support and must be able to exchange information and share a common understanding of a patient’s clinical evolution. Different users will then require different support types from different applications, which will be exploited for helping them in accomplishing their daily tasks [Lanzola et al., 1996].

Part of our research work is therefore being aimed at demonstrating the potential of combining the expressive power of a functional-logic programming language such as RELFUN with the Multi Agent (MA) paradigm and the methodology coming from research in the Computer Supported Cooperative Work area. Thus we carefully selected a particular specialty within medicine, concerning the management of patients affected by Acute Myeloid Leukemia (AML), which emphasizes the exploitation of different knowledge types coming from distinct professionals, and stresses interoperability issues among them such as cooperation and negotiation.

AML is a clonal, malignant disease of the hemopoietic tissue that is characterized by the proliferation of abnormal (leukemic) blast cells principally in the marrow and by an impaired production of normal blood cells [Lichtman, 1991]. It usually originates from a single transformed stem cell controlling hemopoiesis which is capable of differentiation into all blood cell lineages. This leukemic cell rapidly propagates itself in an abnormally regulated and disordered fashion and eventually will end up replacing all the normal blast cell population. AML therefore requires a prompt diagnosis and subsequent planning and administering of a strong therapy to eradicate the malignant cells, as any delay may turn out to have negative influence on the patient’s life expectancy. The process of diagnosing AML usually starts from some general and very unspecific signs and symptoms and goes on through more specific laboratory exams. Finally, in view of planning a suitable therapy, AML is ranked according to the French American British (FAB) classification into classes FAB-M1 through FAB-M7 [Bennet et al., 1985]. Basically there are only two therapies available for AML, which are Bone Marrow Transplantation (BMT) and Chemotherapy (CHT). The former has the greatest probability of success, but it is only applicable in some specific situations which clearly include the availability of a compatible donor. It also has a major counter-indication mainly consisting in the possibility for the patient to develop Graft-Vs-Host Disease (GVHD).

To summarize the AML management protocol, Figure 1 gives on AML task planning diagram where all the different actions are shown, pointing out how they relate to each other. Ovals represent decision steps in the management process and fall into two different types. Thin ovals refer to diagnostic actions aimed at assessing the state of the patient, while thick ones represent therapy planning stages useful for selecting the most appropriate treatment based on the patient data and on the currently available diagnosis. Rectangles simply refer to therapeutic actions which are usually performed according to a given protocol and do not require any specific decision making process. Finally, ovals encapsulated in black rectangles represent a monitoring action. They represent a process aimed at continuously assessing the patient state over time, looking for the occurrence of some particular events.

In the rightmost part of Figure 1 the main actors involved in each step of the management process are also indicated. The patient and the laboratory are supposed to be involved in each step, so they are indicated just once for all at the bottom. At the beginning of the management process the only additional actors will be the General Practitioner (GP) and the Hospital. After getting the results from the laboratory and diagnosing AML, the GP must interact with some hospitals in order to hospitalize the patient, and depending on AML seriousness and the availability of beds, this may require some negotiation. More specifically, the GP may wish to trade time with the possibility of selecting the hospital. If there are no available beds at the nearby hospital, depending on AML seriousness, the GP may wish to wait for one to become vacant or move the patient to a more distant hospital. Then, after a first CHT cycle is finished, the main therapy for the patient must be selected. This step requires a careful cooperation among the Oncologist, the Donor Bank and the BMT unit. In fact, selecting the right therapy not only depends on the patient findings alone, but also on the possibility of finding a suitable donor. So, even if in principle BMT may be the most appropriate treatment, its suitability must be weighed against the availability of a suitable donor given by the donor bank, and compared to that of CHT, as suggested by the oncologist. Moreover, the availability of a suitable donor may be a time dependent function, adding extra complexity to the problem.

As it transpires from the simplified description above, the whole process of managing AML-affected patients is a knowledge intensive activity involving several health care professionals who must be able to exchange information and use different reasoning techniques such as qualitative models [Ironi et al., 1990], or probabilistic reasoning [Quaglini et al., 1994].

With the aim of providing a specialized tool helping every single professional involved in AML management, we are presently implementing a set of agents each one encapsulating the domain knowledge of a given professional. All those agents are also being endowed with cooperation knowledge, in order that they be able to interoperate and perform negotiations among each other on the basis of the same model adopted by human agents. In the next section we shall provide a description of how RELFUN, complemented with a KQML communication protocol for message exchanging, is being used for this purpose.

5 The Functional-Logic Implementation

The implementation of our prototypical system has basically involved two different parts. The first one addresses the modelling of domain specific knowledge within each agent being implemented through RELFUN. To support this, a frame based representation of medical knowledge has been worked out, and deduction and abduction rules have been subsequently implemented for each specific medical task. The second part concerns modelling and representing cooperation knowledge in terms of a suitable set of rules implemented within each agent and aimed at achieving their ability to interoperate. This is based on the KQML multi agent environment described in section 3. The following subsections will explain both parts with typical examples; the full implementation is available and described in Campagnoli [1996].

5.1 Representing Domain Knowledge

RELFUN has been very helpful in representing structured knowledge within each single agent, providing an easy implementation of an inheritance mechanism in a frame-based (OOP) hierarchy:

For example, the diagnoser agent has the task of initially assessing the patient state, coming up with a solution which is then used as a starting point by those devoted to planning a therapy. Diseases are ranked in a taxonomy, where a class-subclass link is the leading one for arranging them according to pathophysiological criteria. The following KB fraction shows how acute-leukemia is defined as a leukemia, having Acute Myeloid Leukemia (aml) as its subclass. The latter has instances such as fab-m1, fab-m2, ... (actually through fab-m7), representing the actual disease type.

class(leukemia,top,[]).

class(acute-leukemia,leukemia,

[[examinations,bone-marrow-blasts]]).

class(aml,acute-leukemia,

[[examinations,[blast-pas,black-sudan]]]).

instance(fab-m1,aml,

[[treatments,[bmt,cht]],

[examinations,blasts-morphology]]).

instance(fab-m2,aml,

[[treatments,[bmt,cht]]).

. . .

Each disease class also has attributes, and the only one shown in the example above is that concerning the examinations required to find out if the patient is affected by the corresponding disease. Given the nature of the problem it is not possible to reach a satisfactory diagnostic conclusion at a high level in the taxonomy, as its determination depends on very specific findings which are usually associated with low-level subclasses and disease instances. To this end we have to implement a specific inheritance mechanism which calls upon discarding superclass values in presence of any local value for the examinations attribute. The KB fraction performing this task is shown below:

override(Slots,[]) :& Slots.

override(Specific,[[Attribute,‗]|General]) :-

member([Attribute,‗],Specific)

& override(Specific,General).

override(Specific,[[Attribute,Value]|General]) :-

naf(member([Attribute,‗],Specific))

& tup([Attribute,Value]|override(Specific,General)).

inherit(top,Slots) :& Slots.

inherit(Class,SpecificSlots) :-

class(Class,Superclass,ClassSlots)

&

inherit(Superclass,override(SpecificSlots,ClassSlots)).

slots(Instance) :-

instance(Instance,Class,InstanceSlots)

& inherit(Class,InstanceSlots).

5.2 Representing Cooperation Knowledge

Our effort is now focused on the implementation of the several agents involved in the distributed architecture emulating the interoperational model adopted by humans. Each agent, after being endowed with the domain specific knowledge corresponding to a given health care professional, is therefore also being provided with an explicit model of the strategies adopted by that professional for interacting with others.

As a simple example describing how the interoperation among different agents has been achieved, let’s specify the start of the AML task planning in section 4, namely the strategy adopted by the medical agent emulating the general practitioner (GP). The GP’s first task, as sketched in the AML task planning diagram in Figure 1, will consist in assessing the patient state in search for a diagnosis. Once this has been accomplished and the diagnosis has been identified as AML, the next task to be carried out by GP will deal with hospitalizing the patient. The following clauses, stored within the GP knowledge base, characterize the seriousness of the conditions of two patients who have been diagnosed as affected by AML, and list three hospitals, ordered according to their distance from the patient’s dwelling:

seriousness(patient1) :& stage3.

seriousness(patient2) :& stage5.

hospital(h1).

hospital(h2).

hospital(h3).

Then GP will send out a KQML message to a facilitator (cf. section 3) looking for some information from those hospitals concerning bed availability and the associated costs.

send-msg(gp,facilitator,ask-all,

[Result,availability[Month]],

‗,a1).

The facilitator, after contacting all the available hospitals in behalf of GP, will provide a summary of the gathered [hospital,cost] availability results, sending it back to GP as a reply to the original query. What is returned will be stored as a set of clauses within GP’s knowledge base, and will look like the following (the non-deterministic availability function represents the facilitator’s multiple results from the hospital agents for each fixed month):

availability(january) :& [h1,900].

availability(january) :& [h2,750].

availability(january) :& [h3,300].

availability(february) :& [h1,800].

availability(february) :& [h2,450].

availability(february) :& [h3,200].

...

Based on that information and on a suitable selection strategy which accounts for the hospital distance, charged costs and bed availability as a function of time, and the possibility to delay the patient hospitalization according to the seriousness of its state, GP will choose a hospital:

choose(Date,Patient) :-

hospital(Hospital),

[Hospital,Cost] .= availability(Date),

acceptable(Cost,seriousness(Patient)),

confirm(Hospital,Patient)

& Hospital.

If the previous rule fails, which means that it has not been possible to identify a solution according to the strategy it models, the following rule pair will be applied:

choose(Date,Patient) :-

stage5 .= seriousness(Patient),

hospital(Hospital),

[Hospital,‗] .= availability(Date),

confirm(Hospital,Patient)

& Hospital.

choose(‗,Patient) :-

naf(stage5 .= seriousness(Patient)),

[Hospital,‗] .= min-cost(tupof(availability(‗))),

confirm(Hospital,Patient)

& Hospital.

The first one chooses the nearest available hospital, without taking into account any cost, if the patient condition is such that it requires an immediate treatment. The second one, which will be invoked when the patient’s condition is less deteriorated, selects the cheapest hospital available over the whole year.

For implementing the hospital selection strategy, the cost charged by the hospital is compared to the seriousness of the patient as expressed by the AML stage according to the following rules:

acceptable(Cost,Seriousness) :-

Seriousness .= cost(Min,Max),

<=(Min,Cost),

>=(Max,Cost).

cost(0,100) :& dom[stage1,stage2,stage3,stage4,stage5].

cost(100,200) :& dom[stage3,stage4,stage5].

cost(200,300) :& dom[stage4,stage5].

cost(300,1000) :& dom[stage5].

Finally, in the above-mentioned cases, when the strategy has succeeded, the choose rule will also take care of contacting the hospital for issuing a reservation for the patient. This is accomplished through the rule:

confirm(Hospital, Patient) :-

send-msg(gp,Hospital,tell,[confirm,Patient],‗,ack1).

6 Conclusions

If the functional-logic paradigm wants to get closer to mainstream languages, as accomplished by the relational-database (SQL3) and OOP (Smalltalk, Java, and C++) paradigms, it, too, has to tackle real-world applications and handle their non-declarative aspects. The multi-agent medical application described in this paper has confirmed the practical use of purely functional-logic features such as non-ground function calls for function inversion. Even the RELFUN implementation of overriding inheritance is pure, and the entire prototype does not yet require a cut operator. On the other hand, we have found problems with the lack of LISP- or PROLOG-like KB-update operators such as assert and retract in modern functional-logic languages: the RELFUN users needed a dynamic assert because they wanted KQML-content parts of messages to become available as clauses in a receiving agent – clauses not different from those pre-existing in the receiver’s KB, hence not somehow "coded" as data; conversely, users needed retract. In a delivery version of the prototype, RELFUN’s module system could be used to ‘localize’ – and buffer – message I/O.

After some initial reservations by the RELFUN developers, the needed non-declarative extensions were made. Interestingly, functional-logic integration offered advantages compared to functional or logic programming alone even for these non-declarative primitives: both assertz and retractx are value-returning, permitting assertz-modify-retractx compositions; retractx itself need only retract one eXactly specified clause, since for unification-based retractions clause generation can be reused from RELFUN’s clause-returning builtin via non-deterministic retractx-clause compositions. Also, in functional-logic languages such non-declarative primitives can be built on top of an already integrated declarative kernel, thus avoiding their duplication in the two component languages. The same principle was already successful for declarative, not integration-relevant but uniformity-preserving extensions of the pure RELFUN kernel such as finite domains, which are relegated to outer pure RELFUN shells.

Summarizing the experience with our prototype, besides the assertz/retractx extension by the developers, the current RELFUN interpreter turned out to be easy to extend and use: for example, the users were able to implement the KQML interface via LISP built-in extensions with little help from the developers. Because of its KB hashing, the interpreter was also efficient enough for this communication-intensive application. With the RELFUN compiler plus (C) emulator [Perling, 1998], this functional-logic prototype could be developed into a real-world application.

While the prototype exploits several specifics of RELFUN, it is fairly clear that other implemented functional-logic integrations such as ALF and BABEL could have been used instead, adapting things to their language concepts. For example, our current frame-based hierarchy accesses lists of attribute-value pairs recursively, which could be built in via the notion of feature terms [Smolka and Treinen, 1992], as, e.g., implemented in Oz, and also envisaged as a RELFUN extension. For functional-logic comparison, it would thus be interesting to reimplement (parts of) this architecture in these other languages, and, for ultimate reuse, in a standard proposal like Curry [Hanus et al., 1995].

With the advent of XML, the functional-logic rules of our prototype could now also be represented in markup languages such as RFML (http://www.relfun.org/rfml) or the standard proposal RuleML (http://www.dfki.de/ruleml). Besides such XML-encoded content, also the KQML performatives of agent messages could be marked up in XML and RDF; this is one of the topics of the current DFKI FRODO project (http://www.dfki.uni-kl.de/frodo).

The ever increasing costs faced by the delivery of health care services, combined with the need to rapidly spread the latest reasearch achievements, require a better organization and structuring of the practice meant as a team work. To this aim the Pavia group is merging the agent methodologies with organizational issues and workflow modeling techniques towards the implementation of a distributed system supporting health care workers in planning and coordinating their activities [Lanzola et al., 1999].

7 References

[Bennet et al., 1985] Bennet, J.M., Catovsky, D. Daniel, M.T. et al. Prepared revised criteria for the classification of acute myeloid leukemia: a report of the French American British Cooperative Group. American Journal of Medicine, 103:620-629, 1985.

[Blois, 1984] Blois, M. Information and Medicine: the Nature of Medical Descriptions, Berkeley Press, 1984.

[Boley et al., 1994] Boley, H., Buhrmann, U. and Kremer, K. Towards a sharable knowledge base on recyclable plastics. In: Knowledge-Based Applications in Material Science and Engineering (McDowell, K.J. and Meltsner, J.K., Eds.) pp. 29-42, TMS, 1994.

[Boley, 1999] Boley, H. A Tight, Practical Integration of Relations and Functions. Springer-Verlag, Berlin, Heidelberg, LNAI 1712, 1999.

[Campagnoli, 1996] Campagnoli, M. Una Architettura per la Comunicazione e Cooperazione fra Agenti Software. Tech. Rep., University of Pavia, 1996.

[Finin et al., 1992] Finin, T., Weber, J., Wiederhold, G., Genesereth, M. R., Fritzson, R., McKay, D., McGuire, J., Pelavin, P., Shapiro, S. and Beck, C. Specification of the KQML Agent Communication Language. Technical Report EIT 92-04, Enterprise Integration Technologies, Palo Alto, CA, 1992.

[Fisher and Wooldridge, 1993] Fisher, M. and Wooldridge, M. Specifying and verifying distributed intelligent systems. In: Progress in Artificial Intelligence, Proc. EPAI’93. Lecture Notes in Artificial Intelligence (Filgueiras, M. and Damas, L., Eds.), Vol. 727, pp. 13-28, Springer-Verlag, 1993.

[Hanus, 1994] Hanus, M. The Integration of Functions into Logic Programming: From Theory to Practice. Journal of Logic Programming, 19,20:583-628, 1994.

[Hanus et al., 1995] Hanus, M., Kuchen, H. and Moreno-Navarro, J.J. Curry: A Truly Functional Logic Language. In: Visions for the Future of Logic Programming: Laying the Foundations for a Modern Successor to Prolog. Proc. Workshop in Association with ILPS ‘95, Portland, Oregon, pp. 95-107, 1995.

[Ironi et al., 1990] Ironi, L., Stefanelli, M. and Lanzola, G, Qualitative Models in Medical Diagnosis. Artificial Intelligence in Medicine, 2, 85-101, 1990.

[Jennings et al., 1993] Jennings, N.R., Varga, L.Z., Aarnts, R.P., Fuchs, J. and Skarek, P. Transforming Standalone Expert Systems into a Community of Cooperating Agents. Engineering Applications in Artificial Intelligence, 6 (4), 317-331, 1993.

[Klinker et al., 1991] Klinker, G., Bhola, C., Dallemagne, G., Marques, D. and McDermott, J. Usable and Reusable Programming Constructs. Knowledge Acquisition, 3,117-135, 1991.

[Lanzola and Stefanelli, 1993] Lanzola, G. and Stefanelli, M. Inferential Knowledge Acquisition. Artificial Intelligence in Medicine, 5,253-268, 1993.

[Lanzola et al., 1996] Lanzola, G., Falasconi, S. and Stefanelli, M. Cooperating Agents Implementing Distributed Patient Management. In: Agents Breaking Away, Proc. MAAMAW ‘96, Eindhoven, The Netherlands, Lecture Notes in Artifical Intelligence (Van de Velde, W. and Perram, J., Eds.), Vol 1038, pp. 218-232, Springer-Verlag, 1996.

[Lanzola et al., 1999] Lanzola, G., Gatti, L., Falasconi, S. and Stefanelli, M. A framework for building cooperative software agents in medical applications. Artificial Intelligence in Medicine, 16, 223-249, 1999.

[Lenat and Feigenbaum, 1991] Lenat, D.B. and Feigenbaum, E.A. On the treshold of knowledge. Artificial Intelligence, 47:185-250, 1991.

[Lichtman, 1991] Lichtman, M.A. Hemopoietic stem cell disorders: Classification and manifestations. Hematology, McGraw-Hill, 148-157, 1991.

[Neches et al., 1991] Neches, R., Fikes, R.E., Finin, T., Gruber, T.R., Patil, R., Senator, T. and Swartout, W. Enabling technology for knowledge sharing. AI Magazine, 12:36-56, 1991.

[Perling, 1998] Perling, M. The RAWAM: Relfun-Adapted WAM Emulation in C. Technical Memo TM-98-07, DFKI GmbH, December 1998.

[Quaglini et al., 1994] Quaglini, S., Bellazzi, R., Locatelli, F., Stefanelli, M. and Salvaneschi C. An Influence Diagram for Assessing GVHD Prophylaxis After Bone Marrow Transplantation in Children. Medical Decision Making, 14, 223-235, 1994.

[Ramoni et al., 1992] Ramoni, M., Stefanelli, M., Magnani, L. and Barosi, G. An Epistemological Framework for Medical Knowledge-Based Systems. IEEE Transactions on Systems, Man, and Cybernetics, 22(6):1361-1375, 1992.

[Searle, 1969] Searle, J.R. Speech Acts: an Essay in the Philosophy of Language. Cambridge University Press, 1969.

[Shoham, 1993] Shoham, Y. Agent Oriented Programming. Artificial Intelligence, 60:51-92, 1993.

[Smolka and Treinen, 1992] Smolka, G. and Treinen, R. Records for logic programming. In: Proc. Joint International Conference and Symposium on Logic Programming, Washington, DC, MIT Press, 1992.