
\documentclass[french,a4paper]{article}

\usepackage[francais]{babel}
\selectlanguage{francais}
\frenchspacing

%\usepackage{french}

\usepackage[T1]{fontenc}

\usepackage[normalem,normalbf]{ulem}

\usepackage{a4wide,apalike}

\newcommand{\To}{\Longrightarrow}

\title{Actes de langage et jeux de dialogue}

\author{Christophe Delord\\\\
delord@mygale.org\\
Laboratoire G.R.A.A.L.\\Groupe Raisonnement, Action et Actes de Langage\\
ENSEEIHT - IRIT\\
2, rue Camichel
TOULOUSE
}

\begin{document}

\pagestyle{headings}

\maketitle

\abstract{
	Nous présentons ici un modèle du dialogue basé sur les actes de dialogue et les jeux de dialogue.
	Le modèle précise le fonctionnement des agents et des jeux de dialogue.
}

\section{Introduction}

L'étude du dialogue est intéressante en elle-m\^eme, mais aussi pour ses applications en informatique,
dans les interfaces homme-machine par exemple.
Nous allons présenter ici un modèle du dialogue et des agents du dialogue qui utilise les actes de dialogue
de \cite{BUNT96} et étend la définition des jeux de dialogue de \cite{BEUN96}.
L'objectif de ces travaux est de proposer une implémentation d'un modèle du dialogue
en utilisant des techniques de l'intelligence artificielle.
Pour cela, notre modèle sera décomposé en deux parties : les agents et les jeux de dialogue.
Cette distinction permet de séparer ce qui est propre aux agents de ce qui dépend du dialogue.
Nous verrons aussi un petit exemple de dialogue.

\section{Présentation du modèle}

La modélisation du dialogue doit prendre en compte les agents et les jeux de dialogue.
Les agents sont caractérisés par leurs états mentaux et leurs systèmes inférentiels, indépendament du dialogue,
alors que les jeux sont des ensembles de règles représentant leurs comportements en fonction de l'état du dialogue.
Pour formaliser ce fontionnement, nous allons utiliser une logique modale non-monotone.

\subsection{Définitions}

Le modèle des jeux de dialogue utilise plusieurs notions qu'il faut tout d'abord définir.

\begin{description}
	\item [Actes de dialogue :] Définition plus précise et plus adaptée à notre modèle des actes de langage de \cite{SEARLE69}.
		\cite{BUNT96} distingue trois aspects de l'acte de dialogue : la forme de l'énoncé, sa fonction communicative et son contenu sémantique.
		Par exemple, l'énoncé << Est-ce qu'il pleut ? >>, la fonction communicative << question fermée >>
		et la proposition << il pleut >> ont pour effet de rajouter l'énoncé << Est-ce qu'il pleut ? >> au contexte linguistique
		et d'ajouter dans les croyances de l'auditeur que le locuteur veut savoir si la proposition << il pleut >> est vraie.
	\item [Jeu de dialogue :] On peut distinguer deux visions des jeux de dialogue : \nopagebreak
		\begin{description}
			\item [Selon \cite{LEVINMOORE80,MANN88}] les jeux de dialogue sont des ensembles de règles partagés par les agents.
			\item [Selon \cite{MACKENZIE79,BEUN91,BEUN96}] les jeux de dialogue se rapprochent de la théorie des jeux en considérant
				les actes de dialogue comme des coups.
		\end{description}
\end{description}

\subsection{Logique modale non-monotone}

Il est classique en intelligence artificielle de représenter des états mentaux par des expressions modales (tableau \ref{tab:modalites}).
Nous utiliserons aussi des modalités pour représenter les différents types d'actes de dialogue (tableau \ref{tab:actes}).

\begin{table}[ht]
\begin{center}
\begin{tabular}{|l|l|l|}
\hline
	Modalit\'e	& Exemple		& Signification											\\
\hline
	$B$			& $B_xp$		& L'agent $x$ croit $p$									\\
	$MB$		& $MB_{x,y}p$	& Les agents $x$ et $y$ croient \emph{mutuellement} $p$	\\
	$KIF$		& $KIF_xp$		& L'agent $x$ sait si $p$								\\
	$K$			& $K_xp$		& L'agent $x$ sait $p$									\\
	$W$			& $W_xp$		& L'agent $x$ d\'esire que $p$ devienne vrai			\\
\hline
\end{tabular}
\[	\begin{array}{l}
			MB_{x,y}p \equiv B_xp \land B_yp \land MB_{x,y}(B_xp \land B_yp)	\\
			KIF_xp \equiv B_xp \lor B_x \lnot p
		\end{array}
\]
\caption{Exemples de modalit\'es}
\label{tab:modalites}
\end{center}
\end{table}

\begin{table}[ht]
\begin{center}
\begin{tabular}{|l|l|l|}
\hline
	Acte	& Exemple	& Signification												\\
\hline
	$!$		& $!_xp$	& L'agent $x$ affirme $p$.									\\
	$?$		& $?_xp$	& L'agent $x$ a posé la question $p$.						\\
	$!?$	& $!?_xp$	& L'agent $x$ affirme son ignorance sur $p$.				\\
	$\$$	& $\$_x$	& L'agent $x$ n'a plus rien à dire (fermeture du dialogue).	\\
\hline
\end{tabular}
\caption{Exemples d'actes de dialogue}
\label{tab:actes}
\end{center}
\end{table}

En ce qui concerne le système inférentiel, on pourra utiliser le système $S5$ par exemple.
Ce système est bien adapté pour modéliser les croyances (Tableau \ref{tab:s5}).
On rajoute aussi des règles pour traiter l'intention (modalité $W$, tableau \ref{tab:want}).

\begin{table}[ht]
\begin{center}
\begin{tabular}{|lll|}
\hline																								&&\\
	$(K)$	& $\displaystyle \frac{B_xP \land B_x(P \to Q)}{B_xQ}$	&								\\ &&\\
	$(T)$	& $\displaystyle \frac{K_xP}{P}$						&								\\ &&\\
	$(4)$	& $\displaystyle \frac{B_xP}{B_xB_xP}$					& (introspection positive)		\\ &&\\
	$(5)$	& $\displaystyle \frac{\lnot B_xP}{B_x \lnot B_xP}$		& (introspection n\'egative)	\\ &&\\
\hline
\end{tabular}
\caption{Système $S5$}
\label{tab:s5}
\end{center}
\end{table}

\begin{table}[ht]
\begin{center}
\begin{tabular}{|llp{5cm}|}
\hline																				&&\\
	$(W_+)$		& $\displaystyle \frac{W_xKIF_xQ \land B_x(P \to Q)}{W_xKIF_xP}$	&
		(apparition directe d'une intention)										\\ &&\\
	$(W_+')$	& $\displaystyle \frac{B_x?_yQ}{B_xW_yKIF_yQ}$						&
		(apparition d'une croyance sur les intentions de l'autre agent)				\\ &&\\
	$(W_-)$		& $\displaystyle \frac{KIF_xQ}{\lnot W_xKIF_xQ}$					&
		(disparition d'une intention)												\\ &&\\
\hline
\end{tabular}
\caption{Traitement de l'intention}
\label{tab:want}
\end{center}
\end{table}

La logique doit \^etre non-monotone.
En effet, après un coups de dialogue il faut souvent réviser les états mentaux et
maintenir la cohérence.

\subsection{Jeux de dialogue}

Les jeux de dialogue modélisent le comportement des agents lors du dialogue.
Ils doivent donc spécifier :
\begin{itemize}
	\item le passage d'un jeu à un autre (conditions de changement de jeux),
	\item le traitement des coups et des états mentaux (règles des jeux).
\end{itemize}
De plus les jeux peuvent \^etre imbriqués pendant le dialogue, les agents peuvent donc jouer
plusieurs jeux en m\^eme temps (ce qui permet par exemple de décomposer des problèmes en
sous-problèmes dans un dialogue coopératif).

Dans la suite, nous prendrons comme exemple un jeu qui permet de poser une question,
en fonction des intentions de l'agent.

\subsubsection{Conditions de changement de jeux}

Le changement de jeu est caractérisé par trois types de condition : \nopagebreak
\begin{description}
	\item [Condition d'entrée] Etat activant un jeu
		\subitem $W_xKIF_xQ$ (Entrée dans un jeu de type question)
	\item [Invariant] Etat vérifié pendant le jeu
	\item [Condition de sortie] Etat terminant un jeu
		\subitem $KIF_xQ$ (Sortie du jeu de type question)
\end{description}

\subsubsection{Règles des jeux}

Dans la suite $\cal C$ désigne l'ensemble des coups et $\cal EM$ celui des états mentaux.

Le comportement des agents relativement à un jeu est défini par quatre types de règles : \nopagebreak
\begin{description}
	\item [Perception] $\cal C \longrightarrow EM$ : Modification des états mentaux en fonction des coups joués.
		\subitem $!_yP \To B_x!_yP$ (Mémorisation d'une assertion)
	\item [Mise à jour des états mentaux] $\cal EM \longrightarrow EM$ : Modification des états mentaux
		en fonction des états mentaux courants.
		\subitem $B_x?_yQ \To B_xW_yKIF_yQ$ (Interprétation des coups)
		\subitem $B_xB_yP \land \lnot B_x \lnot P \To B_xP$ (Appropriation de croyances)
	\item [G\'en\'eration] $\cal EM \longrightarrow C$ : Production d'un ensemble de coups candidats à la génération
		en fonction des états mentaux.
		\subitem $W_xKIF_xQ \land \lnot B_x \lnot KIF_yQ \To ?_xQ$ (Question)
	\item [Interdiction] $\cal EM \longrightarrow \lnot C$ : Filtrage des coups générables en fonction des états mentaux.
		\subitem $\lnot B_xP \lor B_x \lnot P \To \lnot !_xP$ (Sincérité)
\end{description}

Le fonctionnement des jeux est donné par ces règles (figure \ref{fig:generation}).
Les règles de perception permettent de mémoriser les coups.
Ensuite, les règles de mise à jour travaillent, en parallèle avec les règles d'inférence de l'agent
pour transformer ses états mentaux.
Les règles de génération et d'interdiction construisent un ensemble de coups générables et non-interdits.
Finalement, le coup réellement joué sera choisi par une heuristique basée sur une force attribuée aux états mentaux.

\begin{figure}[ht]
\begin{center}
\unitlength 1cm
\begin{picture}(11,7)(0,0)
	\put(0,6){\framebox(3,1){Coups précédents}}		\put(4,6){\framebox(3,1){Perception}}
	
													\put(4,3){\framebox(3,1){Etats mentaux}}	\put(8,3){\framebox(3,1){Mise à jour}}

	\put(0,0){\framebox(3,1){Coup généré}}			\put(4,0.5){\framebox(3,0.5){Génération}}
													\put(4,0){\framebox(3,0.5){Interdiction}}

	\put(3,6.5){\vector(1,0){1}}
													\put(5.5,6){\vector(0,-1){2}}
														\qbezier(6,4)(7.5,7)(9,4) \put(9,4){\vector(1,-2){0}}
														\qbezier(6,3)(7.5,0)(9,3) \put(6,3){\vector(-1,2){0}}
													\put(5.5,3){\vector(0,-1){2}}
	\put(4,0.5){\vector(-1,0){1}}
\end{picture}
\end{center}
\caption{Processus de génération d'un coup}
\label{fig:generation}
\end{figure}

Les jeux de dialogue que nous avons présentés peuvent \^etre étendus.
En utilisant la notion de coups logiques \cite{MAUDET98}, on peut aussi définir de manière analogue des jeux logiques.
Un coup logique est un coup interne à l'agent (application d'une règle d'inférence ou d'un jeu, changement de jeux, \ldots).
Les jeux logiques permettent de générer des coups logiques et donc d'expliciter plus finement le fonctionnement
des jeux de dialogue et des agents, en contr\^olant :
\begin{itemize}
	\item les inférences
	\item l'application des règles
	\item le changement de jeux
\end{itemize}

\subsection{Agents du dialogue}

Un agent est caractérisé par :
\begin{description}
	\item [Base de connaissances] Ensemble de formules de la logique modale représentant les états mentaux de l'agent.
	\item [Jeux] Ensemble de jeux que l'agent peut jouer pendant le dialogue.
	\item [Repr\'esentation de l'autre] Description de l'autre agent tel que le voit l'agent.
		C'est un agent << fictif >> qui permet la simulation d'un agent dans les états mentaux d'un autre agent
		pour essayer d'en prévoir le comportement, de tenir compte de ses états mentaux supposés.
\end{description}

\section{Exemple de dialogue}

Le modèle que nous avons présenté a été implémenté et permet de simuler des dialogues.
Considérons par exemple le cas de deux agents coopératifs\footnote{Cet exemple a été simplifié
pour les besoins de cet article. Pour plus de détails, voir \cite{DELORD98}} (Tableau \ref{tab:dialogue1}).

\newcommand{\z}[1]{\sout{#1}}

\begin{table}[ht]
\begin{center}
\begin{tabular}{r|l|l|c|l|l|}
\cline{2-6}
	& \multicolumn{2}{c|}{Agent $x$}			& Coups			& \multicolumn{2}{c|}{Agent $y$}			\\
	& Jeux				& Etats mentaux			&				& Etats mentaux			& Jeux				\\
\cline{2-6}
1	& Jeu de base		& $B_x(p \to q)$		&				& $B_yp$				& Jeu de base		\\
	& 					& $B_x(q \to r)$		&				& $W_yKIF_yr$			& Question(r)		\\
\cline{2-6}
2	&					&						& $?_yr$		&						&					\\
\cline{2-6}
3	& Reponse(r)		& $B_xW_yKIF_yr$		&				&						&					\\
	& Question(q)		& $W_xKIF_xq$			&				&						&					\\
\cline{2-6}
4	&					&						& $?_xq$		&						&					\\
\cline{2-6}
5	&					&						&				& $B_yW_xKIF_xq$		& Reponse(q)		\\
\cline{2-6}
6	&					&						& $!?_yq$		&						&					\\
\cline{2-6}
7	& Question(p)		& $W_xKIF_xp$			&				&						&					\\
\cline{2-6}
8	&					&						& $?_xp$		&						&					\\
\cline{2-6}
9	&					&						&				& $B_yW_xKIF_xp$		& Reponse(p)		\\
\cline{2-6}
10	&					&						& $!_yp$		&						&					\\
\cline{2-6}
11	&					& $B_xp$				&				&						& \z{Reponse(p)}	\\
	&					& $B_xq$				&				&						&					\\
\cline{2-6}
12	& \z{Question(p)}	&						& $!_xq$		&						&					\\
\cline{2-6}
13	& \z{Question(q)}	& $B_xr$				&				& $B_yq$				&					\\
\cline{2-6}
14	&					&						& $!_xr$		&						& \z{Reponse(q)}	\\
\cline{2-6}
15	& \z{Reponse(r)}	&						&				& $B_yr$				& \z{Question(r)}	\\
\cline{2-6}
\end{tabular}
\end{center}
\caption{Exemple de dialogue}
\label{tab:dialogue1}
\end{table}

Dans l'état initial (1), l'agent $y$ veut savoir si $r$.
Il pose donc la question (2).
L'agent $x$ reconnaît donc l'intention de $y$ de savoir si $r$ (3)
et a donc l'intention de savoir si $q$ (qu'il connaît comme étant une justification de $r$),
il pose la question $q$ (4).
L'agent $y$ ne peut pas répondre (6).
L'agent $x$ a alors l'intention de savoir si $p$ (7) et pose la question (8).
A partir de là, les agents peuvent répondre aux questions posées et le dialogue se termine.
Pour ce dialogue, nous avons besoin de trois jeux : un jeu de base et des jeux de question et réponse.
La structure du dialogue est présentée dans le tableau \ref{tab:dialogue1}.

\section{Caractéristiques importantes du modèle}

\subsection{Au niveau des agents}

\subsubsection{Partage ou non de structure entre les agents}

Nous avons choisi de n'utiliser aucune structure partagée entre les deux agents.
Les agents ont cependant besoin d'avoir une représentation (m\^eme approximative) de l'autre pour pouvoir en simuler le fonctionnement.
Cela est nécessaire si l'on veut pouvoir interfacer un agent informatique avec un agent humain,
l'agent humain ne pouvant bien évidemment pas partager quoi que ce soit avec un programme informatique.

\subsubsection{Limitation de l'omniscience}

Toujours dans l'optique de l'interfa\c{c}age d'un agent humain et d'un agent informatique,
il serait peu réaliste d'utiliser une représentation omnisciente de l'agent humain.
Le modèle doit donc permettre de modéliser des agents limités ou de tenir compte des limites d'un autre agent.
Cette limitation peut se faire en comtr\^olant les inférences, en limitant la profondeur du moteur d'inférence par exemple.
		
\subsection{Au niveau des jeux}

\subsubsection{Dépendance entre jeux et contexte}

Les jeux de dialogue permettent aux agents d'adopter un comportement (défini par les règles du jeu)
qui dépend du contexte (les jeux ne sont activés que sous certaines conditions~:~conditions d'entrée)

\subsubsection{Dialogue et sous-dislogues}

Les jeux correspondent à un comportement dépendant du contexte.
Ce comportement doit pouvoir changer durant le dialogue.
Pour cela, on utilise une pile pour mémoriser les jeux activés à un instant donné.
La structure de pile permet par exemple de modéliser l'emboitement des questions et des réponses dans le cas
d'une résolution coopérative de problème (à la huitième étape de l'exemple du tableau \ref{tab:dialogue1}, la pile
de l'agent $x$ contient les jeux <Jeu de base, Reponse(r), Question(q), Question(p)>)

\subsubsection{Jeux de dialogue - Jeux logiques}

Nous avons essentiellement parlé des jeux de dialogue.
Dans notre modèle, nous utilisons aussi les jeux logiques.
Les jeux logiques ont pour but de contr\^oler les inférences des agents,
les coups logiques produits étant des applications de règles d'inférence.
L'utilisation des jeux logiques permet une explicitation plus précise du fonctionnement des agents.

\section{Conclusion}

Nous avons proposé un modèle des jeux de dialogue et des agents du dialogue basé sur une représentation par états mentaux,
en distingant ce qui est propre aux agents et ce qui caractérise le dialogue.
Le modèle s'inspire de la théorie des jeux en considérant les actes de dialogue comme des coups, les règles des jeux
permettant de jouer ou non certains coups.
Ce modèle a été effectivement implémenté et laisse appara\^itre des applications int\'eressantes, par exemple
dans la réalisation de clients/serveurs, lorsqu'une entité de l'application est en relation avec un utilisateur humain.


\bibliographystyle{apalike}
\bibliography{informatique}

\end{document}
