ARTIMIS: Natural Dialogue Meets Rational Agency

1 Introduction

Natural human-computer dialogue is obviously a chal­ lenging application for intelligent systems: a system de­ signed ultimately to replace a human operator must sat­ isfy stronger requirements than most computer-based tools. For example, cooperative behaviour, such as pro­ viding suggestive answers, is an obvious prerequisite for acceptance by humans. This alone favours a generic intelligent-agent-based approach to automated dialogue. Futhermore, designing artificial autonomous agents to be kernels of intelligent systems requires the development of formal theories of reasoning and interaction.

In this paper, we describe the basic components of an effective generic communicating rational agent, AR­ TIMIS, applied to cooperative spoken dialogue [Sadek et al., 1996]. ARTIMIS' kernel is the implementation of a formal theory of interaction. This theory involves a set of generic axioms that models, in a homogeneous logical framework, principles ofrational behaviour, communica­ tion, and cooperation. It thus supports the rational unit of an autonomous communicating agent. It is expressed in a first-order (multi)modal logic of mental attitudes (belief, uncertainty, and intention) and actions.

Section 2 gives the context of the application, illus­ trated by a sample dialogue. Section 3 describes the heart of the system, a rational unit , which is a generic homogeneous logical theory interpreted by a specifically designed inference engine. This rational unit embodies a real demonstration of the applicability of our generic AI approach to dialogue. Section 4 describes specialised components devoted to deal with some of the problems relative to natural language input and output process­ ing. Section 5 presents a reasoning example. Finally, ARTIMIS is compared to related work in the field of intelligent agents.

2 Application and sample dialogue

ARTIMIS is currently being used on the AGS do­ main [Sadek et al., 1996]; i.e., the spoken query, over the telephone, of information voice services directory hosted by France Telecom (Audiotel services). We have cho­ sen to begin with the following restricted domain and semantic representation level: (1) the system only han­ dles two major classes of services: weather forecasts and employment, and (2) the services are described by rele­ vant attributes: theme, geographic area, etc. With this kind of semantic information as a background, the sys­ tem accepts nearly unconstrained spontaneous language as input, and reacts in a cooperative way (with natural­ sounding output). Below is a sample dialogue transcrip­ tion. S stands for the system, U for the user, R for the output of the speech recogniser, and XXX for "semantic garbage".

• S1 : Bienvenue sur le serveur A.G.S ARTIMIS. Que puis-je pour vous ? Welcome to the A.G.S. ARTIMIS server. How can I help you?
• U 1 : Je recherche un emploi a Calais. Est ce que i1 y a des serveurs ? I'm looking for a job in the Calais area. Are there any servers?
• R1: je XXX emploi a calais est ce que il y a XXX
• S2: Non, i1 n'y a pas de serveurs d 'emploi pour Calais. Par contre, i1 y a un serveur d'emploi pour le Pas-de-Calais et un serveur d 'emploi pour Lille. L 'un d 'eux vous con vi en t-i1 ? No, there aren't any employment servers for Calais. However, there is an employment server for Pas-de­ Calais and an employment server for Lille. Are you

interested in one of these?

• U2 : Pour le Nord pas Calais. For Nord, not for Calais.
• R2 : XXX nord pas calais.
• S3 : Le numero du serveur de petites annonces d'emploi pour le Nord est le 36 68 74 44. Desirez-vous un autre renseignement ?

The phone number of the server of employment adver­ tisements for Nord is 36 68 74 44. Do you want any other information?

Est-ce qu 'il est accessible de Calais ?

Is it accessible from Calais ?

est ce que XXX accessible de calais

Oui, il est accessible de Calais. Desirez-vous un autre renseignement ? Yes, it is accessible from Calais. Do you want any other information?

• Je veux aussi Ja meteo.

I also want the weather forecasts.

XXX XXX meteo

Etes-vous interesse par Ja meteo generaJe ou par Ja meteo specialisee ? Are you interested in general weather forecasts or in specialised weather forecasts?

• La meteo specialisee. Specialised weather forecasts.

XXX meteo specialisee

Un serveur de quelle meteo specialisee ?

A server for which specialised weather forecasts?

Que me proposez vous ?

What can you suggest?

XXX proposez XXX

II y a huit types de meteo specialisees. Les deux pre­ mieres sont Ja meteo aerienne et Ja meteo cotiere. Vous recherchez un serveur de quelle meteo specialisee ? There are eight kinds of specialised weather forecasts. The two first are atmospheric weather forecasts and coastal weather forecasts. Which specialised weather forecast are you interested in?

Cotiere pour le Nord.

• Coastal, for the Nord.

R1 : cotiere XXX nord.

Ss: Le numero du serveur de meteo cotieres pour le Nord est le 36 68 08 59. Desirez-vous un autre renseigne­ ment?

The phone number of the server of coastal weather fore­ casts for Nord is 36 68 08 59. Do you want any other information?

Us: Que] est son fournisseur ?

Who is the provider?

Rs: quel XXX fournisseur

Sg: Le fournisseur du 36 68 08 59 est Meteo-France. Desirez-vous un autre renseignement ? The provider of 36 68 08 59 is Meteo-France. Do you want any other information?

Ug :

3 The Rational Unit

The central theme of our approach is that an intelli­ gent dialogue system has to be an intelligent system first of all. Futhermore, the commonly accepted pro­ totypical intelligent behavior is rational behavior. In a simplified way, to behave rationally is to be per­ manently driven, at a certain representation level, by principles that optimally select the actions leading to those futures in conformity with a given set of motiva­ tions and desires (see, e.g., [Cohen and Levesque, 1990a; 1990b] and [Sadek, 1991a; 1994]). It is at this (hypoth­ esised) Knowledge Level that the concepts of mental at­ titudes and intentional actions are relevant.

The rational unit is the kernel of an intelligent agent. It gives the system its dialogue abilities, which result from explicit reasoning processes, modelled by the formal theory of rational interaction. The theory itself will only be outlined here (for more details, see [Sadek, 1991a; 1991b; 1994; 1992; Bretier, 1995]).

In regards to the formal approach for knowledge rep­ resentation, the logic framework is adequate, for various reasons: homogeneity, genericity (due to its large cover­ age), ability to intuitively account for mental attitudes (which makes it easy to maintain), and its potential us­ ability, both as a modelling and an implementation tool.

Based on an integrated formal model of mental atti­ tudes and rational action, the theory provides a unified account, expressed in a homogeneous logical framework , for the different constituents and capabilities involved in (cooperative) communication, such as the manage­ ment of the logical relationships over the system's mental attitudes (beliefs, uncertainties, intentions, and plans). Communicative acts are introduced as regular actions, which can be recognised and planned using general prin­ ciples of rational behaviour. In this framework, dia­ logue is viewed as a derivable activity, which relies on more primitive abilities: it dynamically results from ex­ plicit reasoning processes motivated by the observation and the planning of communicative acts. Due to the genericity of the principles, this approach achieves the robustness required by an intelligent dialogue system: to soundly react to complex situations, possibly incom­ pletely specified when the system has been designed.

3.1 Logical Framewor k

The theory is expressed in a logic of attitudes and actions (or events), formalised in a first-order modal language (close in several aspects to that of [Cohen and Levesque, 1990a]). Let us briefly outline the part offormalism used in this paper. The symbols p, q, and r are taken to be (closed) formulae, ¢J and 7/J formula schemata, and i and j schematic variables denoting agents. Logical implication will be written using =>. We will write f= ¢J to mean that 1/J is valid. The constraints imposed on the semantic model will oe introduced as axioms.

To allow reasoning about action, the universe of dis­ course involves sequences of events, in addition to indi­ vidual objects and agents. Events can be combined to form action expressions, such as sequential actions a1 ; a2 , or nondeterministic choice actions a1 I a2 . where a1 and a2 denote primitive sequences of events, or action expres­ sions. The language involves variables e, e1 , ... ranging over the set of event sequences, variable schemata a, a1 , ... for action expressions, and the operators Feasible and Done. The formula Feasible( a, p) means that a can take place and if it does p will be true after that ac­ tion. The formula Done(a,p) means that a has just taken place and p was true before that action. The abbreviations Feasible( a), Done( a) and Possible( 1/J ), will be used for Feasible( a, true), Done( a, true), and (3e) Feasible(e, 1/J), respectively.

The mental model of an agent is based on three atti­ tudes: belief, uncertainty, and choice (or, to some extent, goa0 . The attitude of intention is defined as a composite concept defined in terms of belief and choice [Sadek, 1991a; 1992]. In this paper, we only use belief and inten­ tion (intention is taken as a macro-attitude). These two attitudes are formalised by the modal operators B and I, respectively. Formulae such as B;p, and l;p can be read as "i (implicitly) believes (that) p" and "i intends to bring about p", respectively. The modelled agents are taken to be fully introspective and to have consis­ tent beliefs. Thus, the logical model for the operator B is a KD45-model.

3.2 Communicative Acts

We concentrate on communicative acts but the analysis applies to rational (or intentional) actions in general. By communicative act (CA), we mean any action performed by an agent with the intention that it be observed by (at least) one other agent.

As for an ordinary rational action, the components of a CA model that are involved in a planning process must characterise, on the one hand, the reason why this act is "selected," and, on the other hand, the conditions that have to be satisfied in order to plan the act. We call the first component the rational effect (RE) of the act and the second one its feasibility preconditions (FPs). It is worth noting that the RE is the effect inteded by the agent of the act ; and wether it will really take place or not, only concerns teh recipient and has not to (and cannot validly) be captured within the act model.

We introduce here without elaborated discussion sim­ plified, yet operationalt versions of the action models that we use later (see Sadek, 1991a; 1991b] for a de­ tailed analysis). The models in question are those of the act of i Informin~ j that cjJ, and the (abstract) act of i Informing j of a (referent of the term) 6 (or the 6, if the operator t for definite description is available):

< i,lnform(j,</J) > FP: B;</J 1\ -.B;Bj</J RE: Bj</J < i,lnformref(j,o(x)) > FP: (3x) B;8(x) 1\ -.B;(3x) Bj8(x) RE: (3x) Bj8(x)

Rational action models, and particularly CA models, are implemented in this theory using the axioms of log­ ical rationality presented in the next section.

3.3 Principles of Logical Rationality

The first property we introduce follows directly from the definition of intention (see, e.g., [Sadek, 1992]) and ex­ presses the fact that an agent can adopt the intention to bring about a state of affairs only if she believes that this state does not currently hold:

Axiom Al: F= l;</J ~ B;-.<jJ.

Axiom A2 provides an agent with the capability to plan an act, whenever she intends to achieve its RE. The agent's intention to achieve a goal generates the intention to perform one of the acts (1) that have the goal as RE

and (2) the agent has no reason for not carrying it out. 1

Axiom A2: F l;p ~ l;Done(al I ... I an), where ak, k E {1 ... n }, are the actions such that: (1) p is the RE of ak, and (2) -.J;-.Possible(Done(ak)).

Axiom A3 requires an agent to search for the satisfia­ bility of the FPs of an act whenever she selects that act (by axiom A2):

Axiom A3: F l;Done(a) ~ (B;Feasible(a) V l;B;Feasible( a)).

Obviously, an action is believed feasible by an agent when all of its FPs (from the agent's point of view, i.e., what the agent believes to be the action's FPs) are sat­ isfied. This is expressed by the following axiom:

Axiom A4: F B;(Feasible(a) {::} p), where p are the FPs of action a.

Whenever an agent considers that a given event has just occurred, she is necessarily committed to believe that its effects and persistent FPs hold (from the agent's viewpoint):

Axiom AS: F B;(Done(a) ~ p), where pis an effect or a persistent FP (such as certain mental preconditions for CAs) of action a. 2 ·

The kernel of the process which enables an agent to derive a plan is specified by axioms A2 and A3. Thus, the planning process is merely a regular consequence of the rational-behaviour axioms, hence completely deductive: no extra planning algorithm is needed to implement the CA models.

3.4 Mental-Attitude Transfer & Cooperative Behaviour

In the part of the theory that we have outlined so far, nothing constrains an agent to adopt the beliefs of an­ other agent, or her intentions in order to be cooperative towards her (such as merely answering a question for her). For this to be possible, we need axioms to allow the transfer of mental attitudes.

A form of belief transfer appears when an agent i thinks that an agent j wants to communicate to her some mental attitude cjJ(j). In this case, and this is the first preliminary principle for cooperative behaviour, agent i comes to believe what she thinks that j wants to com­ municate to her, unless she believes the contrary:

The second preliminary principle for cooperative be­ haviour states that an agent i will adopt some intention

1 This property extends and formalises the principle of ra­ tionality proposed by Newell [1982] p. 102: If an agent has knowledge that one of its actions will lead to one of its goals, then the agent will select that action.

2 Concerning communicative acts, the effect in question is the intentional effect, i.e., the intention an agent attempts to make public in performing the act. For example, the intentional effect of agent i asserting p towards agent j is l;Bjl;Bjp.

(or goal) of an agent j, if she does not have the opposite intention:

Axiom AS: f= B;(li</J 1\ --.J;--.</J :::} l;Bj</1) .

The theory provides several other axioms and derived properties for cooperative behaviour. 3 The following ax­ iom, which formalised the harmony with other agents, will be used later:

Axiom A9: f= f :::} --.J;--.Bj</1 where f characterises the "right" circumstances, which, in some cases (depending on the instantiation of <P), can be merely reduced to true.

3.5 Implementation

To implement this kind of theory, two approaches can be adopted: either automate the inference process for­ malised by the theory, or use the theory as the formal specification of an effective system. We have adopted the first approach since it satisfies, in a more direct way, adequacy, genericity, and maintainability criteria. The inference engine [Bretier, 1995; Bretier and Sadek, 1996], based on a first-order modal logic, namely quantified­ KD45 (with respect to the belief modality), involves other modalities representing uncertainty, intention and action. Inference is automated using an extended reso­ lution method, where formulae are represented in their syntactical form and where the instantiation of axiom schemata uses sub-formulae unification.

4 Specialised Components

When applied to natural dialogue, the ARTIMIS sys­ tem includes two isolated subsystems to deal with nat­ ural language input and output. Currently, algorithmic bottlenecks (especially the size of the search space for the input side) prevent the direct logical specification of these processes in ·our forward-chaining theorem-proving framework . However, both are meant to be eventually integrated as logical theories in the rational unit.

4.1 Natural Language Input

The natural language interpretation subsystem features both syntactic and semantic robustness using island­ driven parsing and semantic completion. Island-driven parsing simply means finding small syntactic structures in the text, with as few long-range dependencies as pos­ sible. Example:

Input sentence:

I'd like the weather forecast for the Cotes-d'Armor area Recognized:

Ld_like X weather forecast X X cotes d armor area Concepts:

Iu weather _forecast cotes..il_armor

The result is a set of mentioned concepts, or a list of possible alternatives when overlapping phrases yield nondeterminism. Each of these hypotheses is then fed into the semantic completion process, which builds a well-formed logical formula out of the mentioned items. The fundamental hypothesis here is that of semantic connectedness: the user never mentions two concepts without (at least implicitly) linking them by some re­ lation(s) or other concept(s).

3 For example, axiom f= J;Bj</1 :::} B;</J V l;B;</J constrains an agent to behave sincerely; axiom f= B;(</J 1\ Bj--.</J) :::} l;Bj</J leads an agent to try to correct what she thinks to be erroneous beliefs of another agent (by corrective answers).

Example: (mentioned) weather _forecast cotes..il_armor (default) phones(x) (inferred) phone(z,x) servers(z) weather _forecast(y) theme(z, y) domain(y,cotes..il_armor)

What we get is a minimal contextually consistent first­ order formula containing the mentioned objects. We then obtain a full-fledged communicative act (hopefully) conveying the user's request whose logical form is suited for direct use by the rational unit:

< u,Jnform(s,IuBrefu(tx phones(x) 1\ (3y) weather _f orecast(y) 1\ (3z) server( z) 1\ domain(y, cotes..il_armor) 1\ phone(z,x) 1\ theme(z,y))) >

Informally, this formula means that the user ( u) in­ forms the system (s) that she wants (Ju) to know (Brefu) the (LX) phone number of a weather forecast server for Cotes d 'Armor.

4.2 Natural Language Output

The natural language geiferation subsystem [Panaget , 1996] contains a linguistic act planner and a linguistic re­ aliser (see also [Appelt, 1985]) . The former is concerned with how the intentions of the system (i.e., communica­ tive acts) are communicated to the user . The latter is concerned with realising the acts specified by the planner as a well-formed utterance.

Linguistic acts serve as an abstract representation of utterances or parts of utterance. Two families are distin­ guished: surface speech acts and referring acts. Surface speech acts are used to deal with the fact that: (1) dif­ ferent communicative acts can be realised by the same utterance and (2) a single utterance can verbalise a com­ plex sequence of communicative acts. Linguistic acts are defined in terms of their effect and their preconditions of feasibility. The effect of a surface speech act is the ver­ balisation of communicative acts whereas the effect of a referring act is the reference to objects of the world. Pre­ conditions are used to express that: (1) the accomplish­ ment of a linguistic act must be relevant to the context in which the utterance will be used and (2) there exists a well-formed part-of-utterance. An interesting point is that the second type of precondition establishes explic­ itly the communication channel from the planner to the realiser.

The linguistic realiser satisfies the second type of pre­ condition by constructing the most relevant parts-of­ utterance and utterances according to the context and to its linguistic knowledge. During the construction, when the realiser requires a noun phrase, a pronoun or a proper name, it asks the planner to select a referring act. This mechanism establishes the second direction of the com­ munication channel.

For example, if the system wants to inform the user that there is a "provider" relation between the Cotes­ d'Armor weather forecast server and Meteo-France, the generator can produce, according to the context, either a simple declarative sentence with a proper name and a noun phrase, a positive answer with a pronoun and a proper name or an elliptical sentence:

"Meteo-France is the provider of the Cotes­ d 'Armor weather forecast server." "Yes, it is provided by Meteo-France." "Meteo-France."

5 Reasoning Example

Let us focus now on an example of CA planning, effec­ tively produced by ARTIMIS. Suppose that the system, s, has just observed theCA, a1(x), built in section 4.1. Let us use the following abbreviations:

The inference process performs the following steps. The first column displays the clause numbers as gen­ erated by our program, the second displays the clauses (or resolvents), and the third displays the numbers of the clauses and axioms used to produce the resolvents:

Once the KB is saturated, agent s (i.e., the system) performs those acts that it intends and believes are fea­ sible, namely, in the example, a2 ( c):

< s,Informref(u,£cphones(c)/\ (3y) weather _f orecast(y) 1\ (3z) server( z) 1\ domain(y, cotes d armor) 1\ phone(z,c) 1\ theme(z,y)) >

Then the NL generation subsystem verbalises this act by the following utterance:

s: The phone number of a weather-forecast server for the Cotes-d'Armor area is 36 68 02 22.

6 Comparison to related work

6.1 Formal semantics frameworks

Several formalisations of intention, based on a possible­ worlds semantic model, have been proposed in the lit­ erature, but they differ in their interpretation of what a possible world represents. In [Cohen and Levesque, 1990a], and also in [Konolige and Pollack, 1993], a world is a time-line representing a sequence of events, tempo­ rally extended infinitely into the past and the future. In [Rao and Georgeff, 1991], a world is a branching-time structure with a single past and multiple futures. In both, a temporal index is used to identify a particular point in the course of events. In our framework, a pos­ sible world is a single point in the course of events , and the possible worlds are related to each other by event­ dependent accessibility relations. The resulting struc­ ture is a branching-time structure with a single past and multiple futures. Even though these three possible­ worlds models seem to be nearly equivalent, they deter­ mine the intuitive interpretation of the formalisation.

Concerning the definition of mental attitudes, our model is similar to Cohen & Levesque's [1990a]. How­ ever, there are some significant differences between the two models, particularly in the definition of intention. For example, in C&L's model, an agent can have an in­ tention to bring about a proposition without necessarily having this proposition as an achievement goal. So, the primary interest of an agent is not the end result of her intention but that she will achieve this result by her­ self. In our definition of intention, the primary interest of an agent is the end result of her intention (the def­ inition explicitly imposes on the intended property to be a persistent goal) . Moreover the achievement of the proposition in question may result from a multi-agent sequence of events, that is, it should be possible that the actions of other agents be a part of the agent's plan.

6.2 Theories of rational agency

Significant developments in rational agency have been elaborated in [Cohen and Levesque, 1990a; Rao and Georgeff, 1991; Konolige and Pollack, 1993; Shoham, 1993; Traum, 1996; Wooldridge, 1996]. The method­ ological frameworks proposed are of great interest for analysing the concept of intentional action. However, except for [Cohen and Levesque, 1990a], none of them provides an explicit formalisation of action, or of com­ munication and cooperation principles. Moreover, while C&L's account of communicative act models is intended to be part of a theory of rational (inter)action, it lacks needed precision on when and how the act models can be used by an agent when carrying out a planning process.

In our case, we show that rationality principles can and need to be clearly specified within a unified logical framework of a rational action theory, in order for com­ municative acts to be planned as regular actions. More­ over, we show that (interagent communication) planning can be a fully deductive process, which naturally de­ rives from the mere application of rationality principles t~ (communicative) act models, without any external de­ vices.

6.3 Implementations

Several agent-oriented tools have been implemented. The AGENTO language [Shoham, 1993] allows the programming of agents in terms of commitment rules. In [Lesperance et al., 1996), GOLOG, an agent pro­ gramming language based on situation calculus is in­ troduced. Other researchers directly implement their logical theories with theorem provers, thus giving the implemented systems a precise semantics. Concurrent METATEM [Wooldridge, 1996] is a multi-agent language based on the execution of a temporal belief logic by a tableaux-based decision procedure. Rao & Georgeff [Rao and Georgeff, 1995] also present tableaux-based provers for BDI logics.

However, except for Rao & Georgeff, none of these analyses the interaction of the modal operators. Our system is specifically designed to implement a first-order modal logic which includes axioms formalising the in­ teraction between modal operators for belief, intention, and action. Moreover, our system is the only one which does not need external devices to implement planning or communicative/ cooperative behaviour. These features are naturally obtained by formalising mental attitudes, actions, and rationality principles, in the same homoge­ neous logical framework.

7 Conclusion

The ARTIMIS system runs on a single Sun Ultra­ SPARC1 workstation. An ISDN interface handles phone calls, getting the standard 8kHz Jl-law speech input. Speech processing is realised by a HMM-based speaker­ independent, continuous-speech recogniser, using a hi­ gram language model [Dupont, 1993; Jouvet et al., 1991] and a PsoLA-based TTs system [Bigorgne et al., 1993].

ARTIMIS displays advanced human-computer cooper­ ative spoken dialogue abilities. This dialogue technology, based on the concept of communicating rational agent, is expected to be experimented, in the short or middle term, in context of real services. The results of an eval­ uation of the first version of the system can be found in [Sadek et al., 1996].