Computing a Map from Michi-Annai-Bun or Written Descriptions

CCMPUTING A MAP FRCM MIC!-U~ANNAI-BUN OR WRITI'EN DIREGriOOS

Teiji Furugori

University of Electro-communication~ Chofu, Tokyo , Ja,'::Jnn

to another. An "exist-sentence" is a sentence that sh<Ms us the existence of landmarks along the way to the destination. A "cooment-sentence" is a sentence that gives us sane other useful

information on directions.

Each sentence in michi-annai-bun's is divided into a verb and cases associated with it. In particular, a move-sentence contains at most five cases and an exist-sentences two cases. The cases we came up with for the move-sentence are or1g1n, goal way, direction, and distance. Those for the exist-sentence are position and object . For instance, the sentence

Koushuu-kaidou-o migi-ni magaru.

(Turn right at Koushuu-kaidou.)

is a move-sentence that has a move-verb )agaru

(tum) and two cases, way(Koushuu-kaidou and direction(migi). The sentence

Koujou-ga aru. (There is a factory.)

is an exist-sentence that has an exist-verb aru (to be) and the case, object(koujou).

The sentence

Minogasu koto-wa arimasen. (You can not

miss it.)

is an example of the exist-sentences.

MAP CCMPUTATIOO

Map canputation from michi-annai-bun's has three distinct processes: sentence analys i s , internal code generation, and map drawing. First , a michi-annai-bun is decomposed into a set of simple sentences each of Which, in tum, is divid­ ed into a verb and it case relations. Second, the semantic structure of each simple sentence is transfonned into a matrix (or matrices ) and the michi-annai-bun becomes a sequence of mat­ rices. Finally, with the information supplied by the matrices, a set of Fortran routines that uses GPSL (Graphic Plotting Subprogram Library ) is called to compute a map on a display device.

Sentence Analysis. Sentence analysis does two

successive decompositions of michi-annai-bun:

1. michi-annai-bun -+ simple sentences
2. simple sentence --t standard f orm (verb

ABSTRAcr

This paper describes processes of transfOrming michi-annai-bun, literally street-guide-sentence into a map on a display device: we first sh<M h<M such transformation is perfonned, and then we discuss what it means in terms of understanding natural language expressions.

INTRooocrroo

In Artificial Intelligence and Cop;nitive Science there have been a nunber of studies concerned with maps and directions. Notably, Kuipers[l) presented a model of representation of large scale envirorrnents and used it in constructing routes with street descriptions. Riesbeck(2] observed that !Tn.lCh of spatial reasoning was unnecessary when one reads a written set of directions. He claimed that, without detailed information on all the turns, distances, and locales, the set of directions was clear and sensible if it is satisfied certain conditions. He then wrote a program that judged the clarity and cruciali ty of the sentence in the text giving directions.

Here we present another program that i s concerned with michi-annai-bun, literally street­ guide-sentence. Our program canputes a picture (map) from michi-annai-bun or texts giving directions. The effort is made with a similar ideas in mind that Slinmons described when he canputed pictures from natural language for

the cl<Mn 's micr<Morld[3).

MICHI-ANNAI-BUN

A michi-annai -bun is a sequence of sentences (instruc tions) that tells us h<M to get to a place from certain point. For example:

0.~ off a\ c·ora a\a\1oa and \ako ~ ftor\h ox1\. ~, for a ··or\ d1a\an~o aad Cyoal ... a liqueur o~re Oft ~our rash\. ·ad Cyoul ora a\ Kyuu-kouahuu-kaldoa. Turn rlth~. ~Oft \urn lof\ ln a vorv ahor~ while at Toukal bank oft your loft. Co a\raat·\ for about 2&1 aa\ara aad Cyoal ~··· \o a aaall ia\eroec\lon. Go a ll~tla further aftd Cyoul ... a noodle abop, Touahuu, oa your loft, aad \ho blf (ouahuu-kaidoa to ~hera . Turn lor~. Go a ll\~la and lyoul cooo \o ... an olo .. atary ach~l on your lor~ and \ho blf ~n~auu­ dal on your rlth\.

Michi -annai -bun · s have three types of !:en­ tences: move-sentences, exist-sentences, and cooment-sentences. A "move-sentence" is a sen­ tence that directs us to move from one point The purpose of the decanposi tions is to enunerate in standard fonns a train of conceptual units that corresponds to actions and situations perti­ nent to the michi-annai-bun.

The sentence analysis in michi-annai-bun is reduced to a pattern matching process, given the sets of move-verbs and exist-verbs in a dictio­ nary and the fact that a simple sentence consists of a sequence of noun and adverb phrases, with case indicating particles at the end of each phrase, follONed by a verb. HONever, the order of phrases in a sentence is quite flexible (except f or the rule that the verb canes at the end), and sanetimes actual cases used in it differ f ran those of the surface structure in the pattern matching process.

The patterns for noun phrases may be compli­ cated by a nunber of nouns, adjectives, particles tha t do not signify the overt cases for michi­ annai-bun's, inflected forms of verbs, and other constituents allONed to appear in a phrase.

Carment-sentences are treated just like carment statements to compilers. When the verb used in a sentence is not for a move-verb or an exist-verb, the sentence is ignored as a com­ ment sentence. This situation also 0ecurs when the decompositions failed for sane reasons.

Internal Code Generation. Once the case frcrne is built for each sentence, information in each phrase is sought to extract the semantic structure of the sentence. That is to say, adjectives and other constituents of a phrase may contain fUrther information about the sentence. In a phrase ookina gakkou (a big school) , for instance, the adjective ookina provides information on the size of the building gakkou.

All the information in a sentence is put in a matrix structure that will describe the semantic structure of a sentence. Fran the verb and the elements that constitute a phrase, we may get the size, type, and name of the landnarks or width, type, and name of the street concerned. Fran the preceding sentences or follONing ones, we may get more information about the origin, goal, position, etc . Such information, which i s crucial to draw a map, will be put in the matrix. If necessary information is missing, then a default value may be supplied to the appro­ priate place in the matrix. When the noun signi­ fies an object that may be given a special symbol on a map, then the information is extracted fran t he dictionary and inserted in the matrix.

The use of the you-are-here pointer is an important intermediary to generate matrices. This is a struc ture with various variables that keep track of the current location and desti,1a­ tion, direction, the side of s treet you are on, e t c . In particular, two variables are kept for the direction s ince absolute directions, e.g., nor t h, and relative directions, e.g., right, may be used interchangeably in michi-annai-bun' s.

MAP DRAWING. A map is computed by a Fortran program that uses GPSL, a set of Fortran sub­ routines for graphics.

The sequence of matrices generated in the previous section contains the information needed to draw a map. Each matrix should nON have suffi­ cient information about a motion or a landmark along the way to the next (intermediate) goal.

The Fortran program contains, for instance, the subroutine WALK which requires several argu­ ments and draws a straight road from the current location; the subroutine CROSS draws an inter­ section; and the subroutine BUILD generates a special symbol through one of the arguments.

The verb or noun put in the matrix determines which subroutine is to be called. Then necessary values for the arguments of the subroutine are sought in the matrix. If crucial information is missing and the default value i s not in the matrix, the system generates an appropriate ques­ tion, and the user is required t o supply the necessary information.

AN EXAMPLE

Consider the follONing michi-annai-bun for an illustration:

EKI-DE ORIRU. KIT~I ~ATTE ~so;u 6USU"U. EKlftAE-DOURI-HI DETA-AA HIDARI-HI ftACARU. SOSHITE SUKOSHI IKu-TO KOUIAH-CA ARU.

tC.\ orr a\ \he a\attoa. Faco t~· aorth aad 10 a\ratth\. Coae to Ek···e-dourt aad tara loft. Go a lt\t\e fur\hor, aa4 \here 1a th· pollee a\aad.l

When this is analyzed, seven simple sentences , with their case frames belON on the right, are identified.

Ill ek1-4e or1ra.

<a> kt\e-a1 ··kau.

(31 .aaauga ·····u·

t4i ek1·ai-4oart-n& dera.

<S> htdart-e .. ,aru.

<6> aukoah& tka.

<7> kou~aa-ga are.

ortruCekJ,-,-.-,-> ·ukaut-,-,-,k1\e,-) auaueuc-,-,-.-, .. ··kgw> arut-,ek&eae-do·r&J

~erul-,-,-,h1dart,->

ik·(-,-,-,-,auko·hJ)

arat-,lcou~an J

The verb used in each s imple sentence is changed t o its uninflected forrr.. The c;:se i ndic,, t. i ng particles and unnecessary conjunctions , i f any , are eliminated also.

The order of the cases is origin, goal , way, direction, and distance f or the move-sen­ tences. That of the exist-sentences is pos ition and object. Here, except for ( 4 ) and ( 7 ) , all verbs are move-verbs.

Each matrix to be generated represents a semantic primitive. A semantic primitive cor res­ ponds to one of the three scenes on the mi chi­ annai-bun: the existence of a street, the exis­ tence of a building, and the movement to be ini­ tiated by us. Thus, massugu susunu generates a matrix for a movement; kouban-ga aru generates a matrix for an existence of buildings . In this example, the nunber of matrices i s t he same as that of the simple sentences as each sentence entails a semantic primitive.

(2), (3), and (6) use the subroutine WALK with various arguments. Eki (tra i n sta tion)

as origin in ( 1) requires a special symbol and detennines which subroutine be called. (4) in­ vokes the subroutine TSHAPE to draw a T-shape intersection. (deru in (4) is a move-verb, but is considered to be an exist-verb in the context here. ) However, the drawing was the result of a system's interaction with the user since the shape of the comer was not specified in the original sentence and no clue to determine it was obtainable. ( 5) changes not one's position but his direction.

In (7) the side of kouban was not specified but "on your left" was assuned in the matrix. The reasoning was the result of the assunption that, unless specified otherwise, one remains on the same directional side that prevailed in the previous tum, i.e., hidari (left) in this case, and that, if not specified, a landmark is located on the same side as one is on.

An output from this ex~nple is:

Figure 1 shows an outpL·<· fo;' t!1e michiannai-bun exemplified in the sec'.i.or: 'iichi.-annai­ bun. This michi-annai-bun itself ;s rather dull, but the map created is about right for Dentsuu­ dai from the Chofu station. Here, the symbol ll and X are the standard ones for banks and schools, respectively.

FUiiAL Rfl.1ARKS

In the end, the structure of language used in michi-annai-bun's is nothing different from that in exressing any other subjects: one may put it any way he likes . Realistically, however, the main components of a michi-annai-bun are "move-sentences" and "exist-sentences", and most of them are picturable.

The drawing maps from michi-annai-bun's is interesting in two reasons. Pedagogically, it provides with the student a concise example

''f natural langu<lge processing. Here ~"' under­ s tanding nf natural language is clear <"r~rl ODE-ra­ tional, and the student gets a hands-on ex~~riment in this field. Theoretically, we le2;rn much about the properties of natural language process­ ing =d thP nature of natural language understand­ ing. The map drawing reveals relations between natural language expressions and picture represen­ tations. A map represents relative distance and directions among objects well. Michi-annai­ !:Jt:n' s are poor at doing this. On the other hand, fuzzy concepts such as "second or third street" are not picturable . The same is true for the ex;Jressions like "tall buildin.r.'', "noisy . street", "3. street with a good smPll of lumber", etc.

In many cases , maps drawn from michi-annai­ bun' s are far from the actual ones . One tends not to express certain local environments in michi-annai-bun; concepts used by him are too fuzzy for the picture drawing. In tum left, for instance, we do not necessarily mean an angle of 90 degr'C'es, which our program assuned. Yet , such a michi-annai-bun is clearly understood when we read it. When we specified all the de­ tails in michi-annai-bun's, our program was able to compute fine maps, but then we had hard time to comprehend the michi-annai-bun's.

The map drawing encounters problems ccmnon with natura l language computation syst~ms like the one presented by Biermann and B&1lard[4). On one hand, noun phrases require much the same types of semantic analysis. On the other, our program could be made to draw accurate maps just like they tried to have a matrix calculation program using natural language. However, our intention at the moment was not to have a complete map-drawing program. Instead we are intere.-'::ed more in an understanding of a good michi-annai­ bun and its relation to the street map.

• REFERENCES [1) Kuipers, B. "Modelling Spatial Knowledge," ~~gnitive Science, Vol.2, No.2, 1978
• [1) Riesbeck, C. K. "You can't miss it: Judging the Clarity of Directions," Cognitive Science, Vol.4, No.3, 1980
• Sirrmoms , R. F. "The Clowns Microworld," In Theoretical Issues in Natural Language Processing, Cambridge, Mass. 1975
• Biermann, A. W. and Ballard, B. w. "Toward Natural Language Computation," ~rican J. of Computc:tional Linguistics, Vol . 6, No.2, 1980