Knowledge And Its Use In A Program For Going From One Place To Another

Introduction

A great part of our daily activities seems to be routine and trivial· cleaning, cooking, shopping, etc. are performed without demanding much of our intelligenc~ Yet the mental processes (behavior) involved in these activities are far from being clear and, on the contrary to their seemingful triviality, we realize we are making numerous decisions even when we go shopping for milka which market to go tor by what means to go; which roads to taker how much to buyr which section of the

market to go tor where to payr etc.

This paper presents an analysis of the mental processes in such activities. In particular, we choose an activity of going from one place to another, make our analysis in terms of the representation and use of knowledge, and subsequently describe a program to simulate the

behavior.

Representation of Knowledge

There are many studies that suggest the kinds of knowledge we possess, what the elements of knowledge are, how know­ ledge is organized, and how it may be utilized to perform certain tasks (cr. 1, 2, J, 4, 5). An increasing amount of re­ search concerns various aspects of our knowledge to attain systems for better understanding of natural language, to de­ sign versatile world models, or to create a robot that reacts to its environment

comprehensively (cr. 6, ?, 8, 9, 10, 11).

What we know about geography, or a map like that in Figure 1, may be express­

ed in English sentences asa

Euclid Avenue meets East 24 Street. Public Library is west of Alpha Univ. City Hall is on Lakeside Avenue at

Bus Terminal is on Chester Avenue between East 14 Street and East

East 9 Street.

18 Street.

KNOWLEDGE AND ITS USE IN A PROGRAM

FOR GOING FROM ON! PLA.CE TO ANOTHER

Teiji Furugori Department of Computer Science Cleveland State University

Cleveland, Ohio, USA

When we consider these sentences as the external representation of our know­ ledge on geography, one way to interna­ lize it is to analyze each sentence with a functor (relation) and its argument (concepts) (12, 13). The knowledge about the map in an application of this theory may be considered as names of streets and places (concepts) and relations among them. The relations essential to the knowledge seem to be that of inter­

sections, directions, etc.

The internalized knowledge may then have formsa

where X, or Y, is a street name, P is a place name, D is a direction (e.g. East), N is either a street name or a place name, and X ~ Y, N ~ N · When the internali­ zation is pe~form~d in this manner, its output is a network memory that is used to perform various tasks. The output from the use of knowledge in turn is be­ havior which may be physical, verbal, or mental. The example in Figure 2 shows a part of Figure 1 in a network form, where angular brackets stand for a street name, brackets for a place, and an ellipse for a relation. The totality of such a net­ work constitutes what we know about

geography.

reach B from c.

Use of Knowledge

It is possible to reach a certain place B from A by tracing all paths, when A and B are directly or indirectly relat­ ed in the network. This way of going from one place to another, however, is costly and we human beings seem to have better ways to achieve the objective. For instance, when we know B is north of A, we may use such information, i.e., direction, effectively to reach B. If we know how to reach a certain place C and B is located somewhere near c, we would probably go to C first and then try to

We do not necessarily take the shorb­ est path between the two places. If some routes are well known to us, they may be used as norms to reach other places. These routes may be the ones for schools,

shopping centers, offices, or the like.

To analyze the behavior in the above, we suppose that the knowledge of direction D plays the central role to go from one place to another and that the primary directions D' are East (E), West (W), South (S), and North (N), Others NE, NW, SE, and SW are secondary ones. When we go from A to B, the first thing we should know is what is the direction of B from A. The direction is a relation in the network and is found by asking a question whether there is a relation of category D with object A and value B, If the answer to this question is not null, we have found the direct relation between A and B, Our task then is to find a way to go toward the direction until we reach B.

When the answer is null, we must figure out D of A and B, We suppose that B is in D· for a certain place. Then the specific relation sd of B from A may be found if thft folloWing relations hold between x 0 and Xn·

where X ,--!4 X means D of X is X; for a directi!n D ~n D' and any two places Xi and X , The specific direction ~ of ~i 1 fr~m x 0 , defining D(Xi)·Xj when i = j,

.u

N if D1 · N and D2 · N

NE if D1 a N and D2 ""E or

E if D1 · E and D2 = E

D1 = E and D2 · N

SE if D1 = S and D2 = E or

s if D1 = S and D2 = S

D1 = E and D2 .. s

sw if D1 = S and D2 = W or

w if D1 · Wand D2 · W

D1 = W and D2 = S

NW if D1 = N and D2 ., W or

D1 ., W a~ D2 = N

As the most essential operation, the process of finding D of A from Xi is done as followsa

1. Initialization - create empty lists S1 and S2 that hold place names, Set T to be one of D'. Put A to S1,
2. A+-topmost element of S1 with deletiona if this tails, i.e., S1 is empty, goto 4,
3. 2, D~direct relation between A and Xi1 if this succeeds, output D and stop.
4. Bottom of S2~places that are in T of AI if this succeeds, goto 1,
5. If S2 is empty, stop (no direc­ tion is found), Otherwise, S1~S2 with deletion and goto 1.

To find sd of B from A, we determine D1 of Xi ·from-rand then D2 of B from Xi' If X =B, there is no problem. But when Xi~t we must invoke the above process for D2 between X. and B. This is time consuming. Our program does not check the possibility of xi_,--- ~B with D2, but only X ~ B with D2. We assume that we can teli relatively well what are in the D' from where we are, but not from there.

Once the specific direction is foun~ we assume the knowledge of places in that direction becomes most important to reach B, This implies that we tend to go to our destination through the places which are well known to us, This part of inference is not very algorithmic but is roughly done as follows·

• 1, Find places X~ 1 , x 2 , ---,xJ in certain directlons from A,
• 2, Find places Y::{v 1 , y 2 , ---,yn) in certain directlons from B.
• J, Take intersection Z of X andY, 4, If Z is empty, try to go from A to x and if this is not possible, stop with failure.
• It xi · B, done. Otherwise take x as the immediate goal to be rtached and repeat the entire process.

X as the set of places incluges places that are located within 45 from A and the straight line that connects A and B. For instance, if B is SE of A, X includes the places inS, E, and SE of A. Y as the set of places includes places that are in the inverse directions of X from B, Y in the example therefore includes places in N, W, and NW from B. When we find out X or Y, we arrange its elements so that the places in the primary directions be put first in the list that hold elements of X or Y, This makes it easy to incorporate into our program an assumption that we tend to go straight if possible, or tend to make the least number of turns, to reach the destination.

It is quite unusual to go to x 1 __ from A even when x is S of A, if x is sw of B. That is, Aobody makes a detour, or goes to an unnecessary direction. The intersection Z between X and Y takes care of this part of our behavior,

When we try to go from A to x , we suppose that the streets where A aAd xi are located intersect directly. If th!s is not the case, we try to find the way by searching every path exhaustivelya we often look for every road near A to reach C when we know C is somewhere near A.

Program

The program creates a memory first and then answers questions on geography. Schematically it has the following two phases·

The Generator creates the network memory. The Simulator answers the questions. Both devices are supposed to take English sentences as input. But they take only a few types of sentences in reality. The Generator accepts only those types of sentences that are shown in a previous section or the ones in the examples below. The Simulator takes only two sentences·

IS A D OF B? TELL ME HOW TO GO PROM X TO Y.

where A, or B is a place name and X, or Y is a street name, place name, or intersec­ tions of two streets in a form X at Y. While it is desired that these restric­ tions be eliminated, they are not very crucial for our current objective· an account of our mental behavior, seen in going from one place to another, that is demonstrated by the answers in the examples below.

Examples

These examples are based on a small set of input aentencest

EAST 9 ST MEETS PROSPECT AVE. SUPERIOR AVE MEETS WEST 3 ST. EAST 9 ST MEETS EUCLID A VB. EAST 9 ST MEETS CARNEGIE AVE. EAST 14 ST MEETS LAKESIDE AVE. EAST 18 ST MEETS EUCLID AVE. PUBLIC LIBRARY IS WEST OF BUS

• TERMINAL. ABC MALL IS NORTH OF PUBLIC LIBRARY. BUS TERMINAL IS WEST OF ALPHA UNIVERSITY. POST OFFICE IS SOUTH OF COUNTY COURT. ZOO IS EAST OF POST OFFICE. ZOO IS SOUTH EAST OF COUNTY COURT. BETA UNIVERSITY IS ON EAST 9 ST AT PROSPECT AVE. BETA UNIVERSITY IS NORTH WEST OF ZOO. ALPHA UNIVERSITY IS ON BAST 24 ST AT EUCLID AVE. BUS TERMINAL IS ON CHESTER AVE BETWEEN EAST 9 ST AND lAST 14 ST. ABC MALL IS EAST 9 ST AT LAKESIDE AVE. COUNTY COURT IS ON WEST 3 ST AT LAKES IDE A VB. ZOO IS ON EAST 14 ST AT CARNEGIE AVE. BETA UNIVERSITY IS EAST OF POST OFFICE. POST OFFICE IS ON WEST 3 ST AT PROSPECT AVE.
• Qt IS BUS TERMINAL WEST OF ALPHA UNIVERSITY?

WEST(ALPHA UNIVERSITY)· BUS TERMINAL

ANSW!R1 YES

1. Q1 IS PUBLIC LIBRARY WEST OF ALPHA UNIVERSITY?

WEST(ALPHA UNIVERSITY)·BUS TERMINAL W!ST(BUS TERMINAL)·PUBLIC LIBRARY. WEST(ALPHA UNIVERSITY)=PUBLIC LIBRARY ANSW!Rt YES

1. Q1 IS ABC MALL NORTH WEST OF ALPHA UNIVERSITY?

WEST(ALPHA UNIVERSITY)·BUS TERMINAL WEST(BUS T!RMINAL)·PUBLIC LIBRARY. NORTH(PUBLIC LIBRARY)·ABC MALL NORTH WEST(ALPHA UNIVERSITY).ABC MALL

ANSWER 1 YES - I THINK SO

1. Q1 TELL ME HOW TO GO FROM CHESTER AVE TO MAIN ST.

ANSWER 1 I DO NOT KNOW MAIN ST

1. Qt TELL MB HOW TO GO FROM WEST 3 ST AT LAKESIDE AVE TO EAST 18 ST.

ANSW!R1 TAKE LAKESIDE AVE TO EAST 9 ST TAKE EAST 9 ST TO EUCLID A VB

TAKE EUCLID AVE TO EAST 18 ST.

1. Q1 TELL ME HOW TO GO FROM ALPHA UNIVERSITY TO ABC MALL.

ANSWER1 WEST(ALPHA UNIVERSITY)·BUS TERMINAL WEST(BUS TERMINAL)·PUBLIC LIBRARY NORTH(PUBLIC LIBRARY)=ABC MALL NORTH WEST(ALPHA UNIVERSITY)= ABC MALL

WEST(ALPHA UNIV!RSITY)=PUBLIC LIBRARY

SOUTH(ABC MALL)=PUBLIC LIBRARY

WEST(ALPHA UNIVERSITY)·BUS TERMINAL

EAST(PUBLIC LIBRARY)·BUS

TERMINAL

• ANSWER· TAKE CHESTER AVE WEST TO EAST 14 ST TAKE EAST 14 ST NORTH TO LAKESIDE AVE TAKE LAKESIDE AVE WEST TO EAST 9 ST
• ?. Q1 TELL ME HOW TO GO FROM COUNTY COURT TO ZOO,

SOUTH WEST(COUNTY COURT)=ZOO SOUTH(COUNTY COURT)=POST OFFICE WEST(ZOO)=POST OFFICE EAST(POST OFFICE)=BETA UNIVERSITY NORTH WEST(ZOO)=BETA UNIVERSITY ANSWER a TAKE WEST 3 ST SOUTH TO PROSPECT AVE TAKE PROSPECT AVE EAST TO EAST 9 ST TAKE EAST 9 ST TO CARNEGIE AVE TAKE CARNEGIE AVE TO EAST 14

ST

Questions 1 to 3 no longer need explanations· Main St is simply not known in question 4, In question 5, the direction of East 18 St from West 3 St or Lakeside Ave is not found, So, we attempt to reach there directly by the exhaustive search as is shown in a treea

The search is width-first, or level by level, and no street node occurs more than once in the search tree, Once it appears, all possible routes are expanded from there, Thus, E9 and W3 are not attached to the tree as daughters of Prospect Ave.

After finding the direction of ABC Mall from Alpha University, Public Library is found to be the place we go by in question 6. Public Library in turn is reached by going by Bus Terminal. But in doing so, a small checking routine finds out that East 14 St, which is known in relation to Bus Terminal, tntersects directly to the one of streets (Lakeside Ave) on which ABC "l!all is located. Although the directions of Lakeside Ave fro~ Chester Ave and East 9 St from Lake­ side Ave at East 14 St are not known explicitly, they are calculated by the directional relations among Bus Terminal, Public Library, and ABC Mall. Question ? is answered in the same manner. But the directional relations between East 9 St and Carnegie Ave and between Carnegie Ave and East 14 St are not understood in this case,

Discussions

The program is written in Fortran for a local reason, though it has a number of deficiencies in representing knowledge, string and list processing, and other salient features that are avail­ able in the recent A. I. languages (14).

We have not discussed about the routes that may be used as norms to reach other places, This problem may be solved by organizing the network hieratchically so that we have a high-level subnetwork whose elements consist of well-known streets and places.

Information to be used for going from one place to another need not be restricted to the one we described, We may use knowledge on traffic conditions such as width of roads, traffic signals, lights, density, etc. Differences of distance in routes may be another impor­ tant piece of information.

If we put the exact mileages between any two places, we can use it to determine the shortest route. But to do so may not be consistent with our way of representing knowledge, Even if it is, it would not help much to explain our behavior unless we assume that we take the shortest path, which is often not the case at all, to reach our destination, Probably some sorts of nearness or farness is more adequate measure to be used to represent the concept of distance. But what sorts of information are satisfactory in a net­ work for a certain problem domain is yet an unsolved question,