Common-Sense Knowledge of Space: Learning from Experience

1. INTRODUCTION

Commonsense knowledcc of space is a particularly interesting domain of human knowledge, because commonsense knowledge is a powerful and mysterious aspect of human thought, and because spatial knowledge is widely applied and distinctly different from linguistic knowledge. Knowledge of large-scale spilce (e.g. the "cognitive map" of a city) is particularly ilccessible to ~.ludy because the process of assimilating new i nform<~! ion is condr ained by I he speed of physical travel, so stales of p<~rlial knowledge are easily observable.

The iOUR modcl [1,2) is a computational model of the cognitive map, exhibiting a solution to the problem:

How can local observations acquired during travel be assimilated into a structure that permits answering route finding and relative position questions'

The model consi r.ls of a number of different representations for spatial relalionships, and inference rules for creating dc~.cr i pl i ons in one representation from information in others. The differenl represenlalions can be categorized:

1. Procedural. A description specifies a procedure for travel between lwo given places.
2. Nclwork. Descriptions specify lhc topological connectivity between pfHcs and paths, and the lOcal geometry of inleneclions.
3. Geometric ill. Dc~criplions specify relative position vectors, ilnd the coordinate frames in which they are defined.
4. Slruclurill. Descriptions !.pecify containment, the role of re ~ion bou11elnries, parallel relations, and rectangular grids.
5. Abslraclton. Descriplions link represenlations of spatial fcalures at different levels of detail.

The observational input to the :rOUR model is simulated as a sequence of part ially specified travel instructions containing onl y informal ion thai could be acquired from a local ob s er v <~lion . All other information is supplied by the assi mi lat ion process (1,2). While lhis permits subsequent acqui si tion of order ilnd local eeomelry informat ion (and thence lhe re5l of lhe w~:: nilive map), there remain easily observable phenomena for which no expl~nalion can be staled in terms of this representation.

1. "I can:tte/1 you how I gel there. I just know what to do.H In some cirwm5l ances, a person is able to use a stored route descr iption for pfl_1·slc.JIIr.we/, but not to anticipate up-commg l.lfldnw l<. s or to describe the route verbally.
2. Occasional/}· a person will have several different infernal descripllons for the so1me place .1nd not reo1fize it. Upon

noticing the identify, his cognitive map undergoes 'signifie~nt reore;~nizalion.

The problem is to find a representation for observational input that (a) refers to sensory events rather than previously acquired descriptions, (b) serves as an adequate base for. further proce~sine,, and (c) can express mechanisms to explain a wtder range of phenomena. The new representation is defined (Sadion 2), shown to interface correctly with the existing TOUR model (Seclion 3), and shown to exhibit graceful degradation of performance under severe resource limitations (Section 4).

2. TRIPLES

We assume two primitive descriptions of sensory events for interaction wilh the physical world: the view, or perceptual snapshol, and the acti~ causing or recording physical motion and simultaneously changing the current view. More formally:

Definition: A view (V) is the description produced by the perceptual system of the scene observed from one vantage point. While the internal slruclure of a view must certainly be very cotnplcx, for our purposes it is subject to only two operalions:

1. Malching. Two views can be compared to see if they describe the same place. Matching is subject to errors, primarily in the direction of failing to detecl an identity (e.g. due to differences in illumination, etc.).
2. lndexine,. A view can be used as the key for storage and retrieval of other internal descriptions.

Definition: An action (A) is the description produ'ced by the perceptual system of a physical motion within ihe environment. Suc.h a motion always produces a change in the current view. There are two types of action description, each of which may provide the observed value of an associated magnitude:

1. (TRAVEL <distance-measure>)
2. (ROTATE <angle-measure>)
3. A TRAVEL action corresponds to motion along some unambiguously idcnlifiable path wilhin the initial view (i.e. no path-selection decisions are required during the motion). A ROTATE action corre5ponds lo a change in the direction faced without translational motion. In addition to being observed, stored, and manipulated like any olher description, an action can he executed to produce physical motion.

The observations corresponding to travel in an environment will be a sequence of 11llernating views and actions:

The information provided by the views and actions and their temporal ~equence is used by the assimilation processes to construct the cognitive map. We will summarize the spatial properties of the physical world by defining a function rel;~ting ob~erved views 11nd actions:

if the action A, taken when V is the current perceived view, results 1n the view V'.

Definition: A sequence of observations is stored as an internal description whose basic element is the Triple (V A V'). A-. part of ;~n internal description, a triple corresponds to:

a) the assertion that RESUL T(V, A) · V'.

1. the imperative to do A, when Vi's the current view. A triple can be partially specified: (V- -)and (VA-) are both me;~ningful triples, lhoiJgh they do not carry tho same as~ertional or imperative weieht as a full triple. A view or act1on can be inserted in an empty slot of a partially-filled triple.

!2£!ini~!!' A ~~~t£._dcsc!_iption (RO) is a set of full or partial triples (VA V'). It is suhject to two operations:

1. A new triple can be added to the ~et.

b) A triple in the set can be retrieved given its first element. ((n LISP, (IISSOC V RD) Em> (VA V').)

The assimilation process that creates internal route descriptions from sequences of observations s.imply creates triple-. from lernpor 11lly ilssocillled views and actions and collects them into a set. In humans, this process is extended over !-cvcrill traversals of the same route, and involves creating a set of partial triples and later filling in empty slots in tho~.e triples. The assimilation process works by using the current perceived view to retrieve a triple (if any) from the route description, lhen filling empty slol~ if possible. The ·.tale of puli111 ~.nowledge represented by the route description p;~sses throur.h three qualitatively distinct phases of behavior a~ ,y.!.imilation proceeds. Similar phases can be oln·erved in human heh11vior.

1. L~ndnlark RNo~nition. When the route desciplion consists of p~~i,-,;1--tri .pl~;:-ofli;eform (V - -),each triple serves only to confirm thilt the given view does in fat! occur along that route. It c arric·. no further 11sserlional or imper alive value, and can not be used for !.elf -guided tr ave I or for assimilation of inform;~tion into lhe olhcr perspectives in the cognitive map.
2. Self-Guided Travel. When the route description consists of p~~ti-;liriples of the form (V A -), each triple can be interpreted as an imperative. If sufficiently many are av11ilable lo form 11 sequence

where (Vi II; -)is in RD, and RESULT(Vi, A;l·Vi+l' and V 1 and Vn are the ·;iews at the endpoints of the route, then self­ p,uided )ravel is pOs!.Jble along lhe route. However, the .lr. ser/ionr. (Vi A; Vi+ 1 ) are not available in the internal de'.wplion, ~o it is not po!.sible to reheane the route without phy~. ical travel, or to a~~imilale information to other perspectives.

1. Menial Rehear~ When sufficiently many full triples

the entire route de~cription can be reviewed from the mental description alone. Both the a~serlional and imperative import of the triples are available, supporting self-guided travel, rehearsal of the route without physical travel, and assimilation of information to other perspectives.

Insight inlo the co!11rast between phases 2 and 3 can come from seeing a route description as consisting of decision information and sequence information. In phase 2, the decision information is represented internally, while sequence information is represented only by lhe physical structure of the world. Thus phy~ical travel is possible because information contained in the structure of the environment is accessible, but men I at rehearsal is not. In phase 3, both kinds of information are represented mentally. A route description in phase 2 accounts for the first phenomenon cited in the introduction: "I can't tell you how I get there. I just know whal to do."

3. INTERFACE WITH THE TOUR MODEL

A complete. set of fully specified triples can be used to create the partially specified route instructions previously assumed as input to lhe TOUR model [4). Thus, the previously described assimilation processes can operate with the new form of observations. The two procedural route descriptions are nonelhele$s necessary, since the Triples are slated in terms of sensory e·;enls, while the instructions are stated in terms of internal description~ of places and paths . Furthermore, the order of the steps in a route description cannot be observed trivially, but must be acquired in the process of assimilation from the associatively retrieved Triples to the sequentially ordered route instructions.

4. GRACEFUL DEGRADATION

One important properly of a representation for commonsense knowledge is r,raceful der,radatioil of performance under re~ource lir~itations: as conditions gel bad, performance ~hould become gradually worse, rather than failing catastrophically. It has its inverse in learning: as morP information is acquired or more assimilation lakes place, performance ~.hould r,radually improve, rather than remaining con~.tanl until a large lhreshhold is passed, then improving dramalically. This properly is fundamental to McCarthy's Advice Ta~.er [7), stated in terms of learning. Graceful degradation was explicitly presented as a design goal by Marr [6), and u!.ed as an explanatory device for several p!.ychological phenomena by Norman and Bobrow [8). Kuipers (3) presents a specific hierarchy of catastrophes of different le·;cls of severity, and discusses the way different representalion~ achieve gr11ceful degradation of performance under resource limitations.

In thi~ section we reformulate the Triples representation as a database accesr.ible to three associative retrieval functions, to ~ee lhe level of performance resulling from various kinds of errors. We !.how that the level of performance degrades gracefully as errors become more ~erious and frequent.

lnformat10n in the route de~cription RD is used by calling the retrieval function~ . Information is assimilated by indexing it under the appropriate key and retrieval function.

Tra·1el along a route corresponds to a sequence of alternating views and iiCtions:

VI A I V 2 A2 . . . V n ~uch thai RESULT(Vi, Ai) "'Vi+!' for i·l,2, ... n-1. (Recall that RESULT summari;es a properly of the physical world, not of a stored description of it. The definitions of the retrieval functions allow us to define precisely the different levels of pe r f o r m a n c e w e o b s e r v e d a b o v e f o r t he T r i p I e s represent at ion.

1. Landmark Recognition: (each l;mdmark is familiar) EN~ROUTE(Vi, RD) · T, lor i-1,2, ·.. n-1. 2. Sell-Guided Travel : (can use RD to get from A to B) EN-ROUlE(Vi, RD) "T, ACTION-AT(Vi, RD) = Ai, lor i·l,2, ... n-1. 3. Ment;~l Rehearsal: (can use RD for as~imilation) EN-ROUlE(Vi, RD) · T, ACTION-AT(Vi, RD) .. Ai, NEXT-VIEW(Vi, RD) "Vi+l' for i·l,2, ... n-1.

The level of performance provided by a given route­ description can be intermediate between these threshholds, with higher performance alone some parts of the route than can be susta1ned along its length.

It is clear from the definitions given above that a failure of one of the assOciati ve retrie'lal functions results in a drop, for that point in thP. route, to the next lower level of performance. Thus, we can easily determine the level of performance resultinu from any r,iven failure. Note that an error on retrieval causes a failure oi a particular call to a retrieval function, which may succeed on a later attempt. An error during storaee causes failures of all subsequent attempts to retrieve that Information until it is observed again and sue cess I ully assimilated. Thus errors during storage are intrinsically more serious than errors during retrieval.

We can give intuitive descriptions of the result of a failure as follows . Notice that none of these errors crash the system or propauatP. to invalidate other stored information. A failure of NEXT -VIEW provides the mildest possible catastrophe. A failure of ACTION-AT is more serious, and EN-ROUTE is the most critical of all.

EN-ROUTE: We're lost. We may or may not be on the dc~ ired route. The current travel goal must be abandoned and special proce!-smg invoked to find familiar territory. The remainder of the route -description is still intact, however, and subsequent observations can rebuild the description.

ACTION-AT: We don't know what to do. While still on the route, explicit guidance is needed to reach the next landmark, so the current travel goal need not necessarily be abandoned. The remainder of the route description still exists, and can be rebuilt.

NEXT -VIEW: We can't anticipate I he next landmark. The current trip is unaffected, but no further deductions are possible. An atlempt at mental rehearsal must be abandoned. Assimilation of the next-ob!.erved view in a physical trip will repair the failure.

We can see from the definitions of lhe levels of performance how different l;~ilures affect performance. To complete an Mgument for graceful degradation of performance we must show that the most likely errors cause the mildest catastrophes. This demonstration proceeds by considering first the levels of performance encountered in the normal learning process, second the effects of errors during storage, and lmally the effects of errors during retrieval. This discu~sion c;~n be found in (4). Thus we put a precise meaning to the claim that the Triples representation exhibits graceful degradation of performance under resource limitatiops.