IRIA
laboria

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
B. P. 5 78150 - Le Chesnay
France
Tél.: 954 90 20

F

laboratoire de recherche
en informatique
et automatique

NATURAL LANGUAGE
UNDERSTANDING AS
A PATTERN RECOGNITION
PROBLEM

<figure><img src="image_1.png" /></figure>

Jean-Paul MAROY

Rapport de Recherche N° 171

Juillet 1976
NATURAL LANGUAGE UNDERSTANDING AS
A PATTERN RECOGNITION PROBLEM

J.P. Maroy

Résumé :

Nous présentons un programme qui «comprend» des commandes en langages naturels, c'est-
à-dire qui ont une forme libre, mais un contenu sémantique bien défini.

Nous montrons que par des techniques structurales de reconnaissance des formes, le programme peut «apprendre» à la fois le vocabulaire et la structure des phrases. Un exemple d'application à un «robot chauffeur de taxi» est donné.

Dans une deuxième étude nous analysons la simulation du «chauffeur de taxi» afin de mettre en évidence les différents niveaux de représentation et la sémantique qui leur est attachée.

Abstract :

We present a program that understands Natural Language Commands i.e. which have a free form but a well defined semantic content. We show that by Structural Pattern Recognition techniques, the program «learns» the vocabulary and the structure of the sentences. An example is given, «the taxi driver robot», which is directed by Natural Language Commands.

In a second paper the simulation of the «taxi driver» is studied to show the different levels of representation and the semantic structures associated with them.
PRESENTATION

1

The literature on Natural Language Understanding is very abundant. But it is not easy to state clearly which is the problem.² The main impression is that the situation is similar to that of Unsupervised Pattern Recognition. Data descriptions are processed directly : numeric measures in P.R., sentences in N.L. This analysis yields a number of classes of descriptions and we hope that the corresponding objects of a class will be of the same kind.

Some other studies give more attention to the objects. In P.R. it is a learning problem : an algorithm has to be devised from a sample of the objects we would like to recognize. This algorithm will be such that all the objects of the same kind will be in the same classes and objects of different kinds will be in different classes. If it is not possible the representation itself will be questioned.

In N.L. this tendency can be found under three headings : Grammatical Inference, Semantic Processing and Pattern Matching.

The first form corresponds in P.R. to supervised learning within a classification process. Once more we have the hypothesis that the choice of the process is definitly a good one. For N.L. the hypothesis is that the choice of the grammar is also a good one.³

Semantical studies are more concerned by the analysis of concepts and their organization than with the transformation of word-strings into semantic representations.⁴ These studies can restrict their field to a robot world⁵ or extend it to a human semantic domain⁶ or even to general semantic constructions.⁷
Translation processes vary widely from syntactic methods to crude pattern matching.

The P.R. equivalent of these methods can be found in structural or syntactic pattern recognition⁸.

Pattern Matching is somewhere in the middle⁹. Pattern Matching is in fact a technique for recognizing some arrangements in the input string and is not actually used as a control structure for the program. The programs we consider under this heading are those where there are no important assumptions (syntactic nor semantic) besides the pattern matching process. In that case the implicit assumption is that a simple sentence structure and a simple semantic structure are enough to account for the meaning.

The sentence structure being simple it will be easy to find it in the input sequence.

The semantic structure has also to be simple enough to be processed by a robot or a simulation program. Many of the most interesting programs in natural language understanding, interesting because they are simple, clear and efficient, are based upon this technique. Such are STUDENT,¹⁰ Eliza¹¹ and the simulation of Paranoia by Colby¹².

But these N.L. analysers are ad-hoc programs. They are based upon know-how, intuition and practice of the programmer for the definition of significant words and significant structures.

The goal of this study is to show that by learning procedures, by the analysis of the objects expressed by the language, we can construct more general programs for Natural Language Understanding
## BASIC PRINCIPLES

**First principle** : Recognition of some thing supposes some cognition. We have chosen the procedure call as general representation. Then the problem is to extract from the input string a sequence of procedure calls. This representation seems to be quite general as all the actions of a robot can be obtained by a sequence of commands or procedure calls with parameters, all search routines in a data base can be invoqued by procedure calls, etc...

**Second principle** : The significant vocabulary is determined by the necessities of discrimination of the different actions. The significant unit is not the word but a group of words or syntagm.

**Third principle** : The structure of actions is in fact their sequence. There is also a sentence structure which is the sequence in which the syntagms are found in the sentence. These two sequences can be different. Then the notion of transformation appears naturally as the operator which transforms the sentence structure into the action structure.

The algorithm will be based upon the analysis of the actions and will establish which are the significant elements of the sentence. Thus we can say that an object in defined by the action that can be executed upon it.

## REPRESENTATION OF THE ACTIONS

A N.L. understanding system suppose the execution of some validation : a command for a robot or an automatic tool, the output of a paraphrase or of a translation, an answer to a question. This validation is usually carried on by a sequence of procedure calls which inform the subsystem of the sequence of actions he has to execute.¹³ The semantic content of the language is necessarily constrained to the built-in capabilities of the execution subsystem. The set of procedures which can be used to communicate with this subsystem constitute the pragmatics of the language, i.e. the possible conversions of the sentences into actions.
The semantic unit is then an ordered list of items representing a procedure call with its parameters.

$(A_i \dot{p}_{i1} p_{i2} \dots p_{in})$

In a question answering system we may have the functions :

(1) (LIST EMPLOYEE AGE SUP 45)

(ENTER SMITH AGE 32)

For a robot taxi driver :

(TURN RIGHT)

For a Winograd-type- scene :

(SEIZE BOX BLUE)

Of course, pragmatics is bound to the representation we choose for the
action sub system. [See Maroy]. But once it has been fixed, it is well
defined.

The order of parameters is significant in a procedure call. It defines
the function of each parameter. To allow more freedom and to facilitate
the decomposition

< syntagm > → (semantic, item)

we can split the procedure call into its constituent provided that for
each constituent we give its position in the call :

$(A_i \dot{p}_{i1} p_{i2}) \equiv$

$(ACTION Ai) (P. Ai.1 \ p_{i1}) (P. Ai.2 \ p_{i2})$

where $(P.Ai.1 \ p_{i1})$ stands for first parameter affected to action $A_i$, $p_{i1}$
is the value of parameter $P.A_i.2$ .
Thus we can write the previous examples :

(2) (ACTION LIST) (P. LIST.1 EMPLOYEE) (P.LIST.2. AGE) (P. LIST.3 SUP)
(P. LIST.4 45)
(ACTION ENTER) (P. ENTER.1 SMITH) (P. ENTER.2 AGE) (P ENTER.3 32)
(ACTION TURN) (P. TURN.1 RIGHT)
(ACTION SEIZE) (P. SEIZE.1 BOX) (P. SEIZE.2 BLUE)

These semantic units (or sub-units in fact) can represent
some usual properties. Then can be named, defining semantic classes :

P. SEIZE. 1 = OBJECT
P. SEIZE. 2 = COLOR
P. TURN = DIRECTION

The comparison of various procedure calls like :

(ACTION SEIZE) (OBJECT BOX) [OBJECT = P. SEIZE]
(ACTION SEIZE) (OBJECT BALL)
(ACTION DRINK) (OBJECT WATER) [OBJECT = P. DRINK]

characterizes objects BOX and BALL as seizable and object WATER as
drinkable. Each parameter being linked to an action some others procedures
which need not to be in the linguistic part of the program, can tell us
if all seizable objects are drinkable or not.

Annex 1 gives the description of the semantics of the commands of the
"taxi driver" which will be used as an example in this presentation.
DETERMINATION OF THE VOCABULARY

For a learning system we can make the hypothesis that the speaker will cooperate explicitely to the learning process. That is :

- He will try to be consistent.

- He will introduce elementary concepts one by one.

- He will correct wrong interpretations.

This will account for some of the positions which have been adopted in the construction of the algorithm.

The interpretation of a sentence follows a normal pattern matching process :
Known syntagms are replaced by the corresponding semantic units. If some
words are unknown the hypothesis that they are semantically un-important
is made. The result is then presented as an interpretation, if it corresponds
to a known phrase structure.¹⁴

In all cases whether it is a good interpretation or a bad one,the learning
process draws the necessary conclusions, directly or from the right answer
given by the professor. The first conclusions concern the vocabulary, the
other ones the phrase structure.

The vocabulary unit is the syntagm which is a string of words. A syntagm
can correspond to one or several semantic units.

in :

< take the second street on your right >

< take > → (ACTION TURN)

< the second street > → (ACTION GO) (P.GO 2)

If a sentence is interpreted for the first time, the sequence of actions
of the answer corresponds to the whole sentence considered as syntagm.

(3) < turn on your right > → (ACT TURN) . (P.TURN RIGHT)

Such expressions can be considered as production rules. Their right
side are analyzed for regularities. Then, when a new sentence enters the vocabulary, the dictionary will be searched for a production which presents the same action and a different parameter, on the right side. Suppose that we find :

(4) < take on your left > → (ACTION TURN) (P.TURN LEFT)

The comparison between (3) and (4) may give us a decomposition of the kind :

(5) < syntagm 1 > → (ACTION TURN)
< syntagm 2 > → (P. TURN RIGHT)
< syntagm 3 > → (P. TURN LEFT)

We note :

(6) < syntagm A > ≡ < Turn on your right >
< syntagm B > ≡ < Take on your left >

Then if we want to have (5) we must have a decomposition of (6) for example in :

(7) < syntagm A > = < syntagm 1 $ syntagm 2 >
< syntagm B > = < syntagm 1 $ syntagm 3 >

The $ operation will be explained further. It may be now seen as the concatenation of two strings.

In other words, a decomposition like in (5) is possible if we can find
in the two syntagms A and B a common part and two variable parts which
account for the action and the two values of the parameter.

In the case of (3) and (4) it is not possible. But if we find (8)
in the dictionary, the decomposition of (3) and (8) yields (9).
(8) `< turn on your left > → (ACTION TURN) (P. TURN LEFT)`

(9) `< turn on your > → (ACT TURN)
< right > → (P. TURN RIGHT)
< left > → (P. TURN LEFT)`

Then (3) and (8) are not kept in the dictionary. They are replaced by (9).
Then (4) is also decomposed, suppressed from the dictionary and replaced
by (10).

(10) `< take on your > → (ACTION TURN)`

This decomposition process brings some generalization by determination
of synonyms. The new sentence

(11) `< take on your right >`

will be interpreted by applying (10) and (9). If that decomposition had
not been made (4) would not have been enough to interpret (11).

A Syntagm is not necessarily a connex sequence of words.
There may be an inclusion within it.

In the following example we find syntagm (12) after applying rule (9).
Then suppose that we find afterwards syntagm (13).

`< turn on your right at the second street you find >`

(12) `< at the second street you find > → (ACTION GO) (P.GO 2)`

(13) `< at the third street you find > → (ACTION GO) (P.GO 3)`

From (12) and (13) we obtain syntagms (14) where the '*' indicates an
included syntagm. The nature of that syntagm is not memorized as it can
be in other systems. The phrase structure and the name information of each
semantic unit being sufficient.
(14) < at the * street you find > → (ACTION GO)
< second > → (P.GO 2)
< third > → (P.GO 3)

Then, the $ operation on syntagms allows the following decomposition,
into a common part and two variable parts, of two syntagms which correspond
to the same action :

(15) < syntagm A > ≡ < syntagm 1 | syntagm 2 >
< syntagm B > ≡ < syntagm 1 | syntagm 3 >

< syntagm A > ≡ < syntagm 1 | syntagm 2 | syntagm 1 >
< syntagm B > ≡ < syntagm 1 | syntagm 3 | syntagm 1 >

< syntagm A > ≡ < syntagm 2 | syntagm 1 >
< syntagm B > ≡ < syntagm 3 | syntagm 1 >

< syntagm A > ≡ < syntagm 2 | syntagm 1 | syntagm 2 >
< syntagm B > ≡ < syntagm 3 | syntagm 1 | syntagm 3 >

Note : - "|" indicates concatenation
- none of the syntagms is empty

We find 4 types of syntagms in the dictionary

- synonyms which correspond to the same semantic unit 15

(16) < turn on your > → (ACTION TURN)
< take on your > → (ACTION TURN)
- empty syntagms : which have no semantic meaning in the dialogue

(17) < very quickly > → (nil)
< the prettiest girl in the world > → (nil)
- polysemies : syntagms which appear several times with different meanings. As the two meanings of "follow" which can be extracted of (18)

(18) < Follow on your right > → (ACT TURN) (P. TURN RIGHT)
< Follow straight on > → (ACT GO) (P.GO 1)

(19) < Follow > → (ACT TURN)
< Follow > → (ACT GO)

- regular syntagms which appear once and correspond to a semantic unit which appears only once.

Polysemies occur also because a syntagm can be used for two distinct actions. Then these two occurrences are considered as different following the principle that an object is in fact defined by the actions that are possible with it. In a world of blocks for example some objects can be seized, pushed, turned-over. But these actions are not possible on every object. Then only the possibilities which have been found are memorized. No inference is done in that domain.

(20) < Ball > → (P. SEIZE BALL)
< Ball > → (P. PUSH BALL)
< Table > → (P. PUSH TABLE)
< Table > → (P. TURN OVER TABLE)

from these productions properties lists can be established.

Polysemies are solved by agreement between actions and parameters. For the example of "Follow" presented in (18) we will find for

< Follow on your left > :

{ (ACT TURN) } (P. TURN LEFT)
{ (ACT GO ) }

which will give the right interpretation.
## PHRASE AND ACTION STRUCTURES

In a limited semantic domain as ours it is somewhat pretentious to state that there are relations between the structure of language and the spatio-temporal structure of the phenomenon¹⁶

the sequence of actions to be executed is of primordial importance. But in fact the order of the syntagms in the language is often different of the corresponding sequence of actions.

Thus we have to consider two sequences of the same semantic units, each one with a signification, the phrase structure and the action structure. The action structure is the link between the interpretation program and the execution sub system. The phrase structure is an internal representation of the input string where each syntagm is replaced by the corresponding semantic units, a word by word translation.

As an example, the sentence (21) has (22) as phrase structure and (23) as action structure. The action structure expresses the fact that you have first to go to the intersection and only then turn whether the sentence expresses the two actions in the inverted order.

> (21) < turn on your right at the second street you find >

> (22) (ACTION TURN) (P. TURN RIGHT) (ACTION GO) (P.GO 2)

> (23) (ACTION GO) (P.GO 2) (ACTION TURN) (P. TURN RIGHT)

When the professor gives the right answer to the interpretation program, he gives the action structure and not the phrase structure. Then, during the learning process the order of the semantic units in the answer cannot be a clue for the determination of the correspondance between syntagms and semantic units.
As the two structures are different we need to transform one into another.
As the two sequences present the same elements this transformation is a
permutation. To each phrase structure is associated the permutation
which transforms it into the action sequence. Phrase structures and
transformations are memorized.

These structures allow to memorize families of objects which have the
same properties. If we take as an example a world of blocks, the three
sentences (24) give (25) as phrase structure :

(24) < take the blue box >
< take the green box >
< take the blue ball >

(25) (ACT SEIZE) (P. SEIZE.1 BOX BALL) (P. SEIZE.2 BLUE GREEN)

Then sentence (26) will be recognized.

(26) < take the green ball. >

This representation stresses two properties :

- semantic categories are created which correspond to functional grouping of terms

- the analogy with linguistic transformations is clear and allow us to consider the phrase structure as surface structure and the action structure as the deep structure.

It would be less expensive to keep in memory the action structure and
all the transformations associated to it. It is only a retrieval facility
which induces us to keep the phrase structures instead.
## SEGMENTATION AND FUNCTIONALS OF THE LANGUAGE

We have only considered terms which have a semantic function. There exist also terms which have a function of organization of the language, of its surface expressions. Such are terms of segmentation and repetition that we can assimilate to algorithmic control structures.

(27) < turn on your right and then on your left >

(28) < turn on your left and then follow straight on >

In (27) "and then" has a function of repetition of the action. In the second one it is simply a mark of segmentation. If there is no special processing of these words they will have too much polysemy : all the actions repeated will appear on the right side.

< and then > → (ACT TURN)

< and then > → (nil)

Other syntagms have a strict algorithmic function.

In (29) the term "twice" repeats a whole action.

If it is processed by the normal learning mechanism it will have as many meanings as the different contexts where it appeared.

(29) < turn on your left twice > → (ACT TURN) (P. TURN LEFT)
(ACT TURN) (P. TURN LEFT)

Then there are two solutions :

- transformations of sequences of actions and parameters that can be learned i.e. which can be matched with some regularities in the action structure

- ad-hoc procedures which solve different cases but which cannot be modified by learning.
THE COMPUTER PROGRAM

We have written a computer program on these ideas. It learns the vocabulary
and the sentence structures of a dialogue which semantic contents can be
represented by a sequence of procedure calls with one parameter. This
program, written in LISP has some 500 instructions.

The segmentation is done by the presence of some key words and of the
ponctuation :

< Then, and, afterwards > <..;>

These words in fact indicate a sequencing of actions. Their list and their
effect is given a priori .<sup>17</sup>

Functionals of the language are treated like polysemy. This solution is
manageable for a restricted dialogue.

The program has three dictionaries :

SA : dictionary of the syntagms which correspond to one semantic unit and
cannot be decomposed.

SD : syntagms which can be decomposed

STP : Phrase structures which have been found and the corresponding transformation.

The sentence to be interpreted is segmented. Then for each segment the
interpretation and learning process is executed.

Dictionaries SA and SD are searched for known syntagms. They are replaced
in the sentence by the corresponding semantic units. If there are unknown
words we form with them a syntagm SV.
If the sequence of semantic units corresponds to a known phrase structure we propose the corresponding action structure as an answer. If this interpretation is correct, SV is entered into the dictionary as an empty syntagm.

If the sentence does not correspond to any known structure or if the interpretation is not correct, the professor gives the right answer. This answer is a sequence of actions. The learning phase begins. It is decomposed in two steps : learning the vocabulary and learning the phrase structure.

Learning new vocabulary is to make a correspondance between SV and the new semantic units which were introduced by the answer. Eventually SV is to be extended before with any mis-interpreted syntagm if we find in the interpretation a semantic unit not present in the correction of the professor.

Before entering the new syntagm SV in the dictionary a decomposition is tried. SV is compared with the syntagms present in SD. For each syntagm of SD which has the same action a decomposition into a common part and two variable parts is tried. If it succeeds the syntagm is suppressed from SD and the decomposition entered into SA.

It may happen that SV contains the whole segment of the sentence and that no decomposition is found.

Then the whole segment is entered into the dictionary. Thus a complex form, from which we dont find any variant, will never be decomposed. It will be directly replaced by its translation each time it will be found.

Then phrase structures are developped. Two cases can occur :

- the phrase structure was known. Only the vocabulary was new. The vocabulary range of the parameters is extended.

- the phrase structure has not been found before. It is entered into STP with the corresponding transformation.
## CONCLUSION

It its present version, with a simple segmentation principle and no treatment for the functionnals of the language, this program is well adapted to the processing of natural language commands of machines. Its simple structure allows it to be implemented on a small computer.

But it has also wider implications : the learning capabilities of a pattern matching process overcome the ad-hoc character of this technique without impending its efficiency.

Then we can think that it will be possible to propose general programs which will take into account the morphology and the extensibility of the vocabulary. By the analysis of the transformations it will be possible to explicit the class of languages this technique can interpret.
NOTES

1- See for example the bibliography given in:

D.E.WALKER- Automated language processing

*in Annual review of information science and technology*
vol.8 E.CUADRA ed.

American Society for Information Science -Washington 1973

2- See also a classification of methods and goals of language understanding in:

-L.SIKLOSSY and H.A.SIMON -Some semantic methods for language processing

*in Representation and meaning*
H.A.SIMON and L.SIKLOSSY eds.
Prentice Hall 1972

3- Two papers presented at the 1974 Nato Advanced Institute on Computer Oriented Learning Processes in Bonas (France) give a good example of grammatical inference as a Pattern Recognition problem:

-C.M.COOK and A.ROSENFELD -Some experiments in grammatical inference.

-D.COULON and D.KAISER -Grammatical inference on natural language samples in the framework of Artificial Intelligence.

4- The parsing of a sentence in this type of study can be found in

-R.C.SCHANK and L.G.TESLER -A conceptual parser for natural language

*in* 1st. IJCAI -Washington 1969

5- T.WINOGRAD -Understanding natural language

Academic press 1972
6- E.CHARNIAK -Toward a model of children's story comprehension
M.I.T. Artificial Intelligence Laboratory 1972

7- R.C.SCHANK -The conceptual analysis of natural language
*in* Natural language processing-Rustin ed.
Algorithmic press 1973

and also:

-R.C.SCHANK -Conceptual information processing
North Holland 1975

8-K.S.FU -Syntactic methods in pattern recognition
Academic press 1973

-P.H.WINSTON -Learning structural descriptions from examples
M.I.T. Artificial Intelligence Laboratory 1970

9- Y.WILKS -Understanding without proofs
*in* 3rd. IJCAI Stanford 1973

10-D.G.BOBROW -A question answering system for high school
algebra word problems
*in* FJCC 1964

-E.CHARNIAK -Computer solution of calculus word problems
*in* 1st. IJCAI -Washington 1964

-M.ROUSSEAU -Résolution automatique d'exercices d'électricité
posés en français
*in* RAIRO Juillet 1975
11- J.WEIZENBAUM -ELIZA, a computer program for the study of natural communication between man and machine

*in CACM vol 9 no. 1 1966*

12- K.M.COLBY, S.WEBER and F.D.HILF -Artificial paranoia

*in Artificial Intelligence vol. 2 no. 1 1971*

13- See the description of the Output-Action generator in:

-L.S.COLES -Talking with a robot in English

*in 1st. IJCAI -Washington 1969*

and the conclusion of:

-R.F.SIMMONS -Semantic networks, their computation and use for understanding English sentences

*in Computer models of thought and language*

R.C.SCHANK and K.M.COLBY eds.

*Freeman 1973*

14- The process is different from learning systems which suppose a previous knowledge of the domain like in:

-P.L.MILLER -An adaptive natural language system that listens, asks and learns.

M.I.T. Natural Language Group memo 83a 1975

Here, both the vocabulary and the phrase structure are unknown.

We cannot use one to infer the other. But it could be possible to infer the meaning of some words after learning some phrase structures.

15- Another discussion of synonymy can be found in:

-R.F.SIMMONS -Mapping English strings into meanings

Department of Computer Science University of Texas 1973

The comparison between the two approaches stresses the importance of the determination of the meaning by discrimination of the actions that the robot can execute.
16- R.THOM -Topologie et linguistique

*in Essays on topology and related topics*

Mémoires dédiées à G. de Rham

Springer 1970

-B.G.DEUTSH -Establishing context in task oriented dialogs
Stanford Research Institute 1975

17- An extended list of such terms is given in:

-K.M.COLBY, R.C.PARKINSON and B.FAUGHT -Pattern matching
rules for the recognition of natural language dialog
expressions
Stanford U. Artificial Intelligence Laboratory 1974

18- This point is quite important for data base interrogation where objects are 'quoted' in the sense that their name is directly transmitted as a parameter to the retrieval and updating routines. Then it is their position in the sentence and not the word itself that indicates the functional meaning. See note 14 and:

-R.M.BALZER -Human use of world knowledge
Information Science Institute
University of Southern California 1974
# ANNEX 1

The taxi driver.

The main example which was studied with the learning program presented in this paper is the simulation of a taxi driver. A taxi, or a robot, is supposed to be lost in a maze and directed by radio towards its goal. The person who directs it has a map of the maze where the starting position of the robot and its destination are marked. There are no indication of the names of the streets. Just the pattern. This corresponds to the abilities of the robot which are restricted to counting intersections and turning.

A more general simulation was studied with the semantic implications of the dialogue in :

- J.P.MAROY - Multiple representations for a topographically constrained robot
  Document de travail IRIA 1975

Some other studies are related to that type of simulations:

- N.K.SONDHEIMER - English as a command language for machines and the semantics of 'left' and 'right'.
  Milwaukie symposium on automatic control -march 1974

In this dialogue there are four actions :

- Action START no parameter

- Action STOP no parameter

- Action GO one parameter: the number of intersections the robot must pass.

- Action TURN one parameter: the direction
Each parameter has also an UNDEFINED modality which corresponds to the case where the parameter is evaluated at execution time. For example when there is no ambiguity on the direction of a TURN action, the direction may be omitted.

Here is an example of the beginning of the training of the robot:

(TOURNEZ A DROITE)

* * *
UNKNOWN STRUCTURE
GIVE CORRECT ANSWER
((ACTION TURN) (PTURN RIGHT))
NO DECOMPOSITION IN SD
SYNTAXM ADDED TO SD
STRUCTURE ADDED TO STP
DICTIONARY
SA
NIL
SD
((TOURNEZ A DROITE) (ACTION TURN) (PTURN RIGHT))
STP
((1 2) (ACTION TURN) (PTURN RIGHT))

(TOURNEZ A GAUCHE)

* * *
UNKNOWN STRUCTURE
GIVE CORRECT ANSWER
((ACTION TURN) (PTURN LEFT))
COMPARISON
((TOURNEZ A DROITE) (ACTION TURN) (PTURN RIGHT))
DECOMPOSITION
((TOURNEZ A) (DROITE) (GAUCHE))
SYNTAXM ADDED TO SA
SYNTAXM ADDED TO SA
SYNTAXM ADDED TO SA
SYNTAXM DELETED FROM SD
STRUCTURE MODIFIED IN STP
DICTIONARY
SA
((TOURNEZ A) (ACTION TURN))
((DROITE) (PTURN RIGHT))
((GAUCHE) (PTURN LEFT))
SD
NIL
STP
((1 2) (ACTION TURN) (PTURN RIGHT LEFT))
(TOURNEZ A DROITE S JI VOUS PLAIT)
((ACTION TURN) (PTURN RIGHT))
INTERPRETATION
((ACTION TURN) (PTURN RIGHT))
ACKNOWLEDGE OR GIVE CORRECT ANSWER

(OK)

SYNTAXM ADDED TO SA
DICTIONARY
SA
((S IL VOUS PLAIT))
((TOURNEZ A) (ACTION TURN))
((DROITE) (PTURN RIGHT))
((GAUCHE) (PTURN LEFT))
SD
NIL
STP
((1 2) (ACTION TURN) (PTURN RIGHT LEFT))

(PRENEZ A DROITE)
* * (PTURN RIGHT)
UNKNOWN STRUCTURE
GIVE CORRECT ANSWER

((ACTION TURN) (PTURN RIGHT))
SYNTAXM ADDED TO SA

DICTIONARY
SA
((PRENEZ A) (ACTION TURN))
((S IL VOUS PLAIT))
((TOURNEZ A) (ACTION TURN))
((DROITE) (PTURN RIGHT))
((GAUCHE) (PTURN LEFT))
SD
NIL
STP
((1 2) (ACTION TURN) (PTURN RIGHT LEFT))

(PRENEZ A GAUCHE)
((ACTION TURN) (PTURN LEFT))
INTERPRETATION
((ACTION TURN) (PTURN LEFT))
ACKNOWLEDGE OR GIVE CORRECT ANSWER

(OK)

(PRENEZ LA TROISIEME RUE A DROITE)
((ACTION TURN) (PTURN RIGHT))
INTERPRETATION
((ACTION TURN) (PTURN RIGHT))
ACKNOWLEDGE OR GIVE CORRECT ANSWER

((ACTION GO) (PGO 3) (ACTION TURN) (PTURN RIGHT))
NO DECOMPOSITION IN SD
SYNTAXM ADDED TO SD
STRUCTURE ADDED TO STP

DICTIONARY
SA
((PRENEZ A) (ACTION TURN))
((S IL VOUS PLAIT))
((TOURNEZ A) (ACTION TURN))
((DROITE) (PTURN RIGHT))
((GAUCHE) (PTURN LEFT))
SD
((LA TROISIEME RUE) (ACTION GO) (PGO 3))
STP
((2 3 1 4) (ACTION TURN) (ACTION GO) (PGO 3) (PTURN RIGHT))
((1 2) (ACTION TURN) (PTURN RIGHT LEFT))
(TOURNEZ A LA TROISIEME RUE A GAUCHE)
((ACTION TURN) (ACTION GO) (PGO 3) (PTURN LEFT))
UNKNOWN STRUCTURE
GIVE CORRECT ANSWER
((ACTION GO) (PGO 3) (ACTION TURN) (PTURN LEFT))
STRUCTURE MODIFIED IN STP
DICTIONARY
SA
((PRENEZ A) (ACTION TURN))
((S JI VOUS PLAIT))
((TOURNEZ A) (ACTION TURN))
((DROITE) (PTURN RIGHT))
((GAUCHF) (PTURN LEFT))
SD
((LA TROISIEME RUE) (ACTION GO) (PGO 3))
STP
((2 3 1 4) (ACTION TURN) (ACTION GO) (PGO 3) (PTURN RIGHT LEFT))
((1 2) (ACTION TURN) (PTURN RIGHT LEFT))
(PRENEZ LA DEUXIEME RUE A DROITE)
((ACTION TURN) (PTURN RIGHT))
INTERPRETATION
((ACTION TURN) (PTURN RIGHT))
ACKNOWLEDGE OR GIVE CORRECT ANSWER
((ACTION GO) (PGO 2) (ACTION TURN) (PTURN RIGHT))
COMPARISON
((LA TROISIEME RUE) (ACTION GO) (PGO 3))
DECOMPOSITION
((LA * RUE) (TROISIEME) (DEUXIEME))
SYNTAGM ADDED TO SA
SYNTAGM ADDED TO SA
SYNTAGM ADDED TO SA
SYNTAGM DELETED FROM SD
STRUCTURE MODIFIED IN STP
DICTIONARY
SA
((LA * RUE) (ACTION GO))
((TROISIEME) (PGO 3))
((DEUXIEME) (PGO 2))
((PRENEZ A) (ACTION TURN))
((S JI VOUS PLAIT))
((TOURNEZ A) (ACTION TURN))
((DROITE) (PTURN RIGHT))
((GAUCHE) (PTURN LEFT))
SD
NIL
STP
((2 3 1 4) (ACTION TURN) (ACTION GO) (PGO 2 3) (PTURN RIGHT LEFT))
((1 2) (ACTION TURN) (PTURN RIGHT LEFT))
# ABSTRACT

This paper proposes a new structure for the representation of the world used by a topographically constrained robot. This structure relies upon multiple representations that can account for various kinds of ambiguities that can be found in natural language when communicating with the robot. The study takes as an example the problem of directing a robot through a maze.

# A INTRODUCTION

This research began with the problem of interpreting natural languages without a complete grammar and relying more on the semantic content. It has been shown (Winograd (-1-), Schank (-2-), Charniak (-3-), Rousseau (-4-) for example) that good results can be obtained if the field of discussion is well defined and if a good representation of the semantics or the knowledge can be found.

But most of these studies don't deal with the whole chain of communication from the sentence to the actual execution of the semantic structure. So these studies seem often to isolate too much the linguistic aspect and sometimes it is difficult to connect such a treatment to the command of a real robot.

We propose here to study at the same time the structure of the representation of the world of the robot and its language understanding process. We think that the use of multiple levels of representation or the world can formalize, or at least clarify some aspects of natural communication. The main idea being that the semantic structure itself acts as an imperfect link between the abilities (physical and intellectual) of the robot and the natural language that will be used to direct it.

The introduction of multiple representations can then take into account various ambiguities of natural languages that can occur at different levels: semantic level and execution level. The latter being due more to an imperfect plan transmitted to the robot rather than to intrinsic properties of natural language.

A further hypothesis would be that the complexity of the language is directly dependent of the intellectual abilities (or planning abilities) of the listener (and of course of the speaker who is not directly involved here).

This study will take as an example the problem of directing a robot through a maze or a taxi driver through the streets of a city.
# 1 REAL WORLD PROBLEMS

## 1.1 Two paradigms: the maze and the robot.

We will take as an example of a topographically constrained robot the problem of directing a robot through a maze. We can give two concrete applications. We can for example implement a turtle game for children (S. Papert, (-5-))n The game will consist in giving instructions in natural language to a turtle in a maze displayed on a cathode ray tube. To animate the game the goal towards which the turtle is to be directed can be changed at random.

We can also imagine that the maze is the pattern of the streets of a city. Our problem then is to direct by radio a taxi driver who is in an unknown neighborhood. We suppose that the person directing him has a map before him. On this map the beginning of the trip and its expected end are indicated. This is in fact a general study of direction prompting. It can be used as a model of how two persons communicate verbally on this subject. It can also be seen as a possibility of automating one of the two tasks: the driver or the prompter.

The paradigm of the maze is quite frequent in studies of robot problem solving. It is a very general paradigm which exists in most of the known cultures. Even if we restrict ourselves to concrete physical situations, it can represent or formalize many situations. The pattern of the streets of a city is the most obvious one. But it can also represent a natural landscape with its hills and valleys, the pattern of roads of a country, the pattern of lines on a map (which itself represents the natural maze). Nearer to our engineering world it can represent any flow in a network, any topographical relationship between objects like on printed circuits boards for example. The paradigm can also be extended to logical networks and their applications like question answering programs for data banks.

Another usual paradigm is the robot. We will not develop further the utility of this paradigm as a good deal of Artificial Intelligence is built upon it, but we will study some more the problem of the maze in robot worlds.

## 1.2 Geometric and non-geometric representations.

There are two main kinds of world representations in robotics: the geometric and the axiomatic representations. The geometric representation is seldom used. Most of the time it consists of a grid representation of the domain of the robot where each square of the grid can hold some information. In Findler (-6-) for example, the world of the robot is represented by the digitized map of its domain and information on the occupation of each square: nature of occupant, data on movement, height, noise etc... In fact each square points towards a description of the
object, or objects, or parts of objects, occupying this grid element. The accuracy of the description, the topographical accuracy, is obtained against the ease to extract information from this representation. Given for example two objects, it is quite cumbersome to verify if they are in contact or not, if the grid description is very accurate.

If that accuracy is something that cannot be lost, like for example in Space Planning (C. Eastman (-7-)) then there should be some refinement on the representation used (Maroy (-8-)). But it can be observed also that for the purposes of problem solving the topographical information is not always useful.

Some axiomatic representations have been proposed recently (Fikes and Nilsson (-9-)). These representations can be called 'topological' as most often, they are not concerned with a strict topographical description of the world but with relationships between objects. This representation (figure 1) is of course much more efficient and can be used directly to solve some classical problems of robotics.

The axiomatic representation is used in fact as an input to a problem solver in first order predicate calculus. The steps in the demonstration of the theorem form the plan that the robot has to find and then execute. If there is a real life simulation of the robot, this description corresponds to an abstract representation of the problem (J. C. Simon (-10-)). There is to find somewhere another process that would re-interpret it in the physical world. The box which has to be carried from one room to another in a typical robot situation, has to be left somewhere in the room. As long as it is not necessary to know exactly where, we can ignore it. But if we have to look precisely in the room for something it would be better to know then exactly where it is.

## 1.3 Multiple representations.

Siklossy (-11-) has shown that it is difficult to give an axiomatic description consistent with the real world even for a simple toy problem. In these studies a problem is given to be solved. Then the plan is executed. But this execution is of the same nature as the planning process. It is the definitive transformation of the world representation whereas the planning process was just allowed tentative transformations of the representation. If Siklossy finds a contradiction, for example the robot being at two positions at the same time, it is by a human re-interpretation if his axiomatization. The execution of the plan is only a verification of the correctness of the theorem prover. If we are to work with a more realistic robot we should have a representation which can allow also a more realistic verification of consistency. This will, in most of the cases, force us to use multiple representations, each one being adapted to some specific purpose.
<figure><img src="image_2.png" /></figure>

4. TOPOGRAPHICAL (GEOMETRICAL) COMPUTER REPRESENTATION

<figure><img src="image_3.png" /></figure>

b. GRAPHICAL (HUMAN) REPRESENTATION

< in box-a room1 >

< in box-b room2 >

< in robot corridor >

< in switch room2 >

< door room1 corridor >

< door room2 corridor >

c. AXIOMATIC (TOPOLOGICAL) REPRESENTATION

<caption>FIGURE 1 : REPRESENTATIONS</caption>
One example of multiple representations is given in Goldstein (-12-). This emphasizes the similitude with debugging. What is interesting is to compare two representations of the world to eventually discover a discrepancy between them. The next step is being of course to find a way to remove that discrepancy.

Mycroft is a program which is supposed to debug graphic programs written in Logo by children. It uses three different representations: an axiomatic description of the intended drawing, the child's program which might be in error and the graphic realization of it. It is clear that the three representations are needed. They are not necessary for the statement of the problem but they give a clear view of the problem conditions and allow a more elegant solution.

Goldstein could have employed only two representations. The intended drawing could have been described by a correct program instead of the axiomatic description. But it can be assumed that the axiomatic description would have been used implicitly to compare pieces of codes in spite of surface differences and to allow morphological variations in the drawings generated by the two programs, like differences in size. With multiple representations we can focus our attention and abilities and progress step by step. For example we can try a debugging technique and then run the program to see if it works better or not.

The point can be made more clearly in usual robotics. If an axiomatic representation is used it is because it does a powerful reduction of data and keeps only what is relevant to problem solving at a given level of abstraction. Then consistency is only relevant at that level and it is necessary to replay the plan which has been found at a more detailed level. For a usual robot this means at the physical level if possible or a more accurate simulation of this physical level.

## 1.4 Representations for topographically constrained robots.

The topographical aspect of the world is quite important when we work with robots that have a physical contact with the real world. Mainly when they have to find their way in a clustered environment (Bolt, Beranek and Newman (-13-)) which is a frequent case. In some instances we can evade that constraint by tricks. For example in Winograd (-1-) the robot works on a two dimensional world in fact: the hand never moves horizontally between the boxes but above them. It's access to the boxes is vertical. But in other cases we would like to ask the robot to follow a path even if there is a tree somewhere in the middle of the path. The robot should be able to go around the tree or report that he did find some unexpected difficulty when it cannot solve the problem by itself at execution time.

Let us take now a concrete example with the turtle problem or the taxi driver. What will be the different representations of the world for that type of problem? The first one is the natural language which describes more or less exactly the path to follow. The second one is a semantic representation of the information conveyed by the language. This is an intermediate level which is used to define invariants in meaning between sentences. Then
there will be the set of actions that the robot can perform.
Action is taken in a sense wide enough to encompass elementary
actions and the capability to organize them. The last level is
the maze itself or at least a representation of it which keeps
its topographical and geometrical properties.

So we have a construction of four distinct levels of description:
topographic description,
actions,
semantic description,
natural language.

Each of these levels can be subdivided as needed, mainly for
the sake of algorithmic treatments. But these four levels of
representation seem to be quite general and to emphasize
important articulations.

# 2 THE FOUR LEVELS OF DESCRIPTION

## 2.1 The topographic representation.

We adopt here for the problem of directing a robot through a
map, a graph representation which is general and can be applied
to various other problems as it has been shown in the first
section. By this first representation, we can put under the
term 'direction prompting' any problem of direction on any
relational data which can be represented by a graph.

This graph is to carry some information. First the position of
the different nodes. Then the length of the arcs. The latter
can be treated as an information attached to to the arc or by
introducing simple nodes between intersections. This solution
has the advantage of allowing a more precise definition of
segments of streets. To each multiple node or crossing we can
attach a description of the morphology: exceptional building,
form of the crossing, etc. To an arc we attach the name of
the street, the number sequence of both sides, the width of the
street, its curvature, etc...

For our example here we just take into account what has to be
used for directing the robot. The pattern of streets is
described by a graph. There are three types of nodes:

(i) End nodes which represent cul de sac or a street
going out of the limits of the map,

(ii) Simple nodes which -indicate length and geometric
characteristics of segments of streets.

(iii) Multiple nodes which represent crossings.
To each node we associate its coordinates and a name. No
information is associated here to arcs (figure 2).
The transformation of a map into a graph is an arbitrary and systematic procedure. The arc can be defined by the axis of the street. Multiple nodes are defined by intersections of axes. Simple nodes are defined when there is a change of direction of a street and to define a more or less regular subdivision of arcs.

In the computer representation of the graph, nodes are represented by the description of the arcs leading to it, i. e. by their neighbours. To each of these arcs is associated a direction computed in degrees from the coordinates of the nodes, so that when arriving at a node from a branch, a local orientation can be easily computed (figure 3).

We have given here a special representation for a somewhat precise problem. The graph representation may not be suitable for every maze. If for example the maze is defined by a cluster of separate objects on the plane, it is more difficult to define the graph from the boundaries of the objects. In that case the usual grid representation is more natural for most of the operations, like path-finding (Lee (-14-)). The point which seems important is to work also with that representation which ensures the re-interpretation in the real world of any transformation.

<figure><img src="image_4.png" /></figure>

<figure><img src="image_5.png" /><figcaption>FIGURE 2 : THE GRAPH REPRESENTATION</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>A. ANGLES ARE DEFINED IN REFERENCE TO A FIXED DIRECTION</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>B. WHEN COMING FROM A NODE CHANGES OF DIRECTION ARE COMPUTED</figcaption></figure>

<caption>FIGURE 3 : ANGLE DEFINITION</caption>
## 2.2 The actions.

Actions should be seen as a complement to the topographical representation. Both the topographical representation and the description of actions define the robot. Actions describe the possible elementary behaviours of the robot within its world. In the case of real world referent (simulation) actions and topographical representations are to be defined at the same time.

For our robot we need only two actions. The 'go' action which sets the robot into movement and the 'stop' action. The 'go' action has as parameters 'right' and 'left', which force the robot to turn, and 'straight', which lets him follow the same path.

But even for those simple actions one has to define the level of knowledge which is to be embedded into the robot. This knowledge corresponds to the type of distinction we can make in psychology between reflex and explicit thinking. Here for example we will assume that the 'go left' command will be effective only if there is an arc leaving on the left of the robot, and that the action procedure will itself test the existence of that arc and induce the natural behavior of going straight until a street on the left and then turn. So the 'go left' action will be a recursive procedure described by something like:

procedure 'go left';

if arc on left then turn left

else begin straight; go left end

end 'go left';

Thus we define a level of actions which allows us to build some knowledge of physical properties of the relationships between the robot and the real world. The action procedures are built upon the real physical elementary actions like commands on a machine tool, to form more elaborate and reflex-like behaviors of the robot which can display a certain autonomy.

We also have to provide more mental actions. The robot should have the ability to count and recognize features from the graph or from the data attached to the graph. This allows us to build more elaborate combinations of actions than mere concatenation. The counting has to be directed as we are to be able to distinguish arcs leaving on the right or on the left. So we have at least three counting functions: 'count right', 'count left' and 'count unef'. The last one counts any kind of side branch.

## 2.3 The semantic representation.

The semantic representation is used to describe how actions can be organized and combined into an algorithmic structure and to set the values of the parameters which are to be used. The action is represented by a semantic atom which can be seen as an action descriptor, and a sequence linkage (fig 4). It will be graphically displayed to facilitate the identification of parameters.
<figure><img src="image_8.png" /><figcaption>FIGURE 4: THE SEMANTIC ATOM</figcaption></figure>

The semantic atom itself has a structure which depends upon the represented action. That structure has to take into account the various parameters of the action, their status and the conditions of applicability. For example we can describe the GO statement by the structure of figure 5. This structure describes completely the various parameters of the GO statement. The first group of parameters is the direction definition. The robot will proceed on one of the three directions that can be defined.

<figure><img src="image_9.png" /><figcaption>FIGURE 5: THE GO SEMANTIC ATOM</figcaption></figure>

Each of these direction parameters is assigned a status and a qualitative. The status describes the fact that the information has been entered with more or less security: if it has been clearly stated or if it is only a hypothesis built by the system. The qualitative eventually describes the degree of fuzziness of the direction. This fuzziness is understood as in the case of choice at a multiple node when there are various arcs leaving on the same side.

The second group of parameters define when or where the action will take place. In fact it mainly describes at which intersection the GO statement will be executed. Two types of descriptions can be given: one by counting, the other by describing the morphology of the intersection. The intersection(s) on which that description and counting are performed are qualified of right, or left or are left unspecified (i. e. any intersection).
In both cases of intersection and direction, the introduction of a status parameter forces us to use an 'undefined' or 'unspecified' category to take into account the fact that it can be stated very clearly that we have to turn but that the direction is not stated like in the statement (figure 6):

'**turn at next street**'. In that case the direction of the movement will be defined at execution time by the fact that there will exist one or more branches at the next intersection.

With this representation we need in fact very few different semantic patterns. The only ones we have to define are START, GO and STOP. START has no argument. STOP has only half of the structure of GO: the 'when' side.

A complex command for the robot is transformed into a sequence of these semantic atoms. The algorithmic part of the command is buried into the quite complex structure of the semantic atom, mainly in the definition of the 'when' parameters. The representation of the semantic atom given here is to be seen as a sort of mnemonic notation to help to define parameters. Whereas a more discursive presentation, a programming language for example, would have stressed the algorithmic structure of the command. But the two representations are equivalent and it is quite simple to write a translator to change one into the other.

<figure><img src="image_10.png" /><figcaption>FIGURE 6: SEMANTIC ATOM FOR 'TURN AT NEXT STREET'.</figcaption></figure>
## 2.4 The natural language.

We will describe in another paper how an automatic interpretation of commands given in natural language is possible. In the present paper we will just show how semantic descriptions can be built from natural language commands. This section will show how semantic atoms are organized into sequences.

The simplest form of organization is the concatenation of simple actions in sentences like:

> 'take the first street on the left and then the second on the right'.

It is the concatenation of:

> 'the first street on the left'
> 'the second on the right'

Each one is represented by a semantic atom (fig7 and fig8) and the two atoms are concatenated to form the sequence of figure 9.

<figure><img src="image_11.png" /><figcaption>FIGURE 7: THE FIRST STREET ON THE LEFT</figcaption></figure>

<figure><img src="image_12.png" /><figcaption>FIGURE 8: THE SECOND ON THE RIGHT</figcaption></figure>

<figure><img src="image_13.png" /><figcaption>FIGURE 9: SEQUENCE OF STATEMENTS OF FIGURE 7 AND 8: CONCATENATION</figcaption></figure>
This example shows that the different values of the parameters
are not independent. For example, if you are to turn on the
left you should count the streets you are leaving on your left.
When you are going straight through an intersection or a number
of intersections, any street crossing the one you are following,
counts.

A second remark concerns the counting procedure. Each time
there is a change in direction the counter has to be reset to
zero as intersections are naturally counted from the last change
of direction or from the starting point.

These two remarks are important on two different levels. The
action level must have the counting behavior which is expected.
It must put its counters to zero each time the robot changes
direction. But the planning process, i. e. the translation
procedure here, which feeds in the parameters of the semantic
representation must also know that the robot has this property.
As this kind of ability is embedded at action level in the
procedure describing the action, it is embedded at semantic
level in procedures of translation of natural language into
semantic representations.

### 3 SOME RELATED PROBLEMS

Usually in robot problems, the real life situation is
simplified by some strong assumption on the validity of commands.
It is assumed that the robot is given possible, executable
commands and that these commands are accurate. But in real life
things are far from being that simple and the cognitive
organisation of the robot should be able to encompass that
situation.

At natural language level we can find various ambiguities: the
statement might be completely non-sensical. This case is not
interesting but should be handled by the system. Here the method
is quite straightforward. We admit only statements that can feed
in all necessary parameters for our representation and reject all
other sentences.

But sentences can also be ambiguous, fuzzy or errors. These
three kinds of properties ask for some response at different
levels of representation.
## 3.1 Antiquity.

Ambiguity can be considered as a difficulty at the level of natural language. It arises when, given a same sentence, two persons will interpret it in different ways.

Take for example the two sets of sentences:

(i) You find a first street. You turn at right. At the second street you turn left.

(ii) You find a first street. You follow straight. At the second street you turn left.

The difference between these two statements is in the behavior at the first crossing. These statements are ambiguous if presented to people. In the first case (i), the second street is understood as the second one after the change in direction. In the second case (ii), it is understood, most of the time, as the second street after starting.

Figures 1a, 11 and 12 show the semantic atoms of (i) and figure 13 their combination into a sequence after applying rules of simplification. Figure 14 shows the sequence corresponding to (ii). The representation is the same, the first direction only being different. The two sequences display the same ambiguity than the two statements.

<figure><img src="image_14.png" /><figcaption>FIGURE 10: YOU FIND A FIRST STREET</figcaption></figure>

<figure><img src="image_15.png" /><figcaption>FIGURE 11: YOU TURN AT RIGHT</figcaption></figure>

<figure><img src="image_16.png" /><figcaption>FIGURE 12: AT THE SECOND STREET YOU TURN LEFT</figcaption></figure>

<figure><img src="image_17.png" /><figcaption>FIGURE 13: STATEMENTS OF FIGURE 10 TO 12 AFTER SIMPLIFICATION. STATEMENT</figcaption></figure>

(i) OF TEXT
<figure><img src="image_18.png" /><figcaption>FIGURE 14: STATEMENT (ii) OF TEXT</figcaption></figure>

The ambiguity is difficult to pin point at this level. The locutor is supposed of course to know that 'most often' the robot changes counting also that it can forget it sometimes. Here for example, the interpretation can differ with the order in which the sentences are presented. At the language level we can suppose that the knowledge of counting behavior is not fully exploited and that the ambiguity is not established. The semantic representation is built exactly as possible from natural language assuming a certain 'normal' behavior. Then at execution time there might be some reason not to follow that behavior as it is quite easy to built up some discrepancy from that behavior at the level of actions. In other words, at the level of natural language, the robot is not supposed to be much more clever than the locutor.

## 3.2 Fuzzyness.

There are various kinds of fuzzyness that can be encountered which form a set of situations between ambiguity and error.

We have already presented the most obvious kind of fuzzyness: we are directed to turn to the right at a multiple node which has various right branches. Before coming to that node, the statement is in fact perfectly well defined. It is only at execution time, when reaching this node, that we have to decide, at the level of actions, what branch we should take or if we should ask for help. It is the 'physical' knowledge of the world that comes upon ambiguities which were not foreseen. It is natural that, the lower level of commands being allowed some independence, to keep some parameters undefined on the higher level until actual execution of the action.

Of course if we are directed to go left at a multiple node with various left branches, it is an omission of the person who directs the robot. But it is a frequent error and the process should have some provision to handle that sort of fuzzyness, at the level of actions, by taking decisions on what is more likely to be meant by 'at left' or just to call for help.
The instruction to go left is perfectly well defined but its execution can be ill defined in some special cases. In the proposed simulation the fuzzyness is handled by a dialog (call for help), but it could also be handled by a more sophisticated simulation. We can for example define a fuzzy scale of left branches at a multiple node and a random process that would choose between them. This example shows quite well the difficulty of tracing a clear boundary between what we can consider as a complete or exact simulation of a real life situation and what is enough to represent the basic understanding of orientation.

Another kind of fuzzyness is expressed directly in the language when distances or directions are defined by a grading: 'slightly on the left', 'atout 400 meters' (see Tanaka (-15-)). This usual definition of fuzzyness can be represented by a simulation as seen before but it involves also the semantic level. The quantification attribute in the semantic description and the fuzzyness handling procedure at the level of actions can solve that kind of problem.

The last level of fuzzyness we will mention is related to the graph representation and its relation with the real world. How can we reproduce from an exact model like the graph representation the perceptual fuzzyness of a crossing of streets if it is ambiguous?

If we take for example a crossing where three streets meet (figure 15), it can be considered as a single crossing or as two distinct intersections. Our graph model being geometrically accurate will probably consider them as two distinct intersections (figure 16). But during the execution of a plan, the fuzzyness will have to be solved at the level of elementary actions: will the counting procedure (which is an action) or the 'go' procedure, take two points which are quite near, as two distinct intersections or not? It is easy to introduce here the perceptual ambiguity of confusing two multiple nodes which are very close. Furthermore, we can introduce it by some sort of learning procedure which can depict what the person directing the robot usually understands as a limit to define separate intersections. Of course, that sort of learning is not independent of some knowledge on what are the most frequent kinds of errors or ambiguities when reading a map.

<figure><img src="image_19.png" /><figcaption>FIGURE 15 : AN ILL DEFINED CROSSING</figcaption></figure>

<figure><img src="image_20.png" /><figcaption>FIGURE 16 : ITS GRAPH REPRESENTATION</figcaption></figure>
To summarize the discussion of fuzziness we can say that at each level (the map, the graph and the semantic representation) things are well defined. They are formed of solid, static objects. What is fuzzy is the operation of confronting different readings, different representations of the real world. One of these readings is particularly fuzzy: the human reading of the map and this fuzziness is conveyed by natural language.

We think that our decomposition of different representation realms can help to understand that kind of ill defined problems. In this particular problem, we have an exact representation (geometric). We have a first lecture which can be considered as inexact (mainly by lack of precision). It is transmitted through natural language to a robot which tries to understand it (semantic representation) and execute it (actions). This second lecture of the graph by the robot thunders to be the same as the first one but has its own logic and actually may be quite different.

### 3.3 Self-consciousness and planning abilities.

The time sequence of semantic atoms can be more elaborate than a concatenation of actions. This leads to the analysis of words like 'before'. It can have two meanings for us. First it can describe the sequence of actions. Then it can describe the position from a landmark:

(i) turn left at the first crossing before the fork.

(ii) turn left before the fork.

This use of the word can be considered as an ability that the robot should have to consider itself in another position than the one where it actually stands. In (i) it says clearly that -for a short sighted robot- that it has to go straight until it finds a fork and then back up its path until it finds the first crossing.

This a title of considering mentally a path induces various difficulties at both levels: actions and language.

We can imagine the behavior of the robot as in (i) going to the fork, recognising it and then coming back (figure 17). If he comes back, backwards, the direction will not be changed, but it introduces a new action. If he turns back then we have to change all direction references until he turns.

But we can also imagine that the action is suddenly interrupted when arriving at the crossing and that the robot jumps back to a previous decision point. The procedure is then a type of backtracking so we need to introduce a new representation, a decision tree or a stack to solve this forward references.

<figure><img src="image_21.png" /><figcaption>FIGURE 17: BACKTRACKING</figcaption></figure>
For any solution we have to introduce at the actions level, new actions or new representations. The problem is deeply changed by the introduction of the mental planning ability of the robot.

The second kind of transformation is on the language level. If the robot is allowed this capability of imagination, of seeing himself in an other position then the one he actually is in, then the complexity of the language increases too with cross references between states, hypothetical status of states, complex time sequences, etc... all off which have a correspondant in the tenses of verbs, use of pronouns and conjunctions, etc...

If we are to introduce this possibilities we will complexify at the same time the simulation and the language to be interpreted. This remark shows clearly the kind of relation that exists between the semantic model (cognitive model) of the robot, and a subset of natural language which will be used to speak to him.

## 4 CONCLUSION

This study of orientation in a maze aimed at a clear comprehension of how were combined in cognitive systems, different representations of the world. In the model proposed here we have defined a level of actions which acted on a graph representation of the world, a level of natural language which consisted in sentences a person pronounces when directing the robot through the maze and an intermediate level: the semantic level. Each level of representation carries its own imperfections and its own degree of autonomy.

This proposition shows that it is possible to define a quite simple semantic model for this type of robot. on the other hand, the taxi driver example shows that with this model it is possible to have a good simulation of the real world.

This study was in fact initiated with the intention to construct an interpreter for a subset of natural language for the very general paradigm of orientation through a maze. Very early in this study it appeared that a semantic representation was not enough, for it did not explain some ambiguities which did not lie in the language but in the interpretation that can be made of the semantic representation.

In our opinion a good natural language interpreter should also know about what will be done of its semantic representation and how it will be done. Our model allows that kind of behavior.
## ACKNOWLEDGMENTS

This paper is the result of many helpful discussions with
Pr. J.C. Simon and with M. Berthod at Paris 6 University and
I.R.I.A.

## BIBLIOGRAPHY

( -1- ) Winograd T.

Procedures As A Representation For Data In A Computer Program
For Understanding Natural Languages

M.I.T. AI. Tr. 17

( -2- ) Sefrank R.

The Conceptual Analysis Of Natural Language
in Natural Language Processing

Rustin ec.

Algoritimic Press 1973

( -3- ) Charniak E.

Jack A. and Janet In Search Of A Theory Of Knowledge
3rd Joint Conference On Artificial Intelligence

Stanford Aug. 1973

( -4- ) Rousseau M.

Resolution Automatique D'exercices D'electricite Poses En
Frangais

The Cycle Universite Paris 6 1974

( -5- ) Papert S.

Use Of Technology To Enhance Education

M.I.T. AI Lab memo 29 June 1973

( -6- ) Fincher N. V.

Design Of An Interactive Environment To Study The Behavior Of
Several Robots Which Can Learn, Plan Their Action And Coexist.

In Place Commner Institute On Computer Oriented Learning
(preliminary)

Dartmouth France Aug. 1974

( -7- ) Eastman C. M.

Representations For Space Planning

Communications Of The A.C.M. apr 1973

( -8- ) Maruyama J. M.

Representations On Allocation Spatiale
In Journey Graphiques AFCET-IRIA

Paris Dec 1973

( -9- ) Fikes R. E. and Milson N. J.

STRIPS: A New Approach To The Application Of Theorem Proving To
Problem Solving

Artificial Intelligence 1971

( -10- ) Simon J.C.

Recent Progress To A Formal Approach Of Pattern Recognition And
Scene Analysis

2nd Int. Joint Conf. On Pattern Recognition

Copenhagen Aug. 1974
( -11 -> Sixtossy L. and Dreussi J.

An Efficient Robot Planner Which Generates Its Own Procedures

3rd Joint Conference On Artificial Intelligence

Stanford Aug. 1973

( -12 -> Goldstein I. P.

Debugging Simple Picture Programs

M.I.T. Artificial Intelligence Laboratory

Draft 4: AI. Tr. 294 1974

( -13 ->olt, Peranek and Newman, Inc.

Robot, Computer Problem Solving System

Final Progress Report no 2646 Sept 1973

( -14 -> Lee C. Y.

An Algorithm For Path Connections And Its Applications

IRE Trans. On Elect. Computers Sept 1961

( -15 -> Tanaka K.

Learning In Fuzzy Machines, Execution Of Fuzzy Programs

in Nato Summer Institute On Computer Oriented Learning

(, reprints)

Bonas France Aug. 1974