Memory-Based Navigation

1 Navigation and Memory-Based Learning

Learning to navigate ill a structured environment is a relevant test for an intelligent system. A robot moving inside a building has to cope with novel situations, such as changes in illumination , a person moving close to it , or a displacement of objects set along the walls.

Given these complex real-world conditions, it is im­ portant to choose an approach based on a flexible repre­ sentation of information: the system should have the capability of learning from experience, performing in real-time and adapting to a changing environment. This means that information processing should not be based on specific geometrical characteristics of the problem do­ main , such as, for example, the vanishing point of a cor­ ridor.

Real-time performance is a necessary requirement for a robot moving in real-world conditions. At the same time, autonomy must be achieved with reasonable computa­ tional requirements and low power consumption. While these constraints are usually considered only a:s limitations, in this context they can provide a useful indicat ion about the validity of the chosen paradigm.

The purpose of this work is to explore a memory-based approach to information processing. Memory-based pro­ cessing is a learning scherna based on a simple and gen­ eral principle. The basic operation is the comparison between present sensorial inputs and previously memo­ rized patterns .

Memory-based reasoning , in the form of similarity­ based induction , had been advocated as an exciting paradigm for a foundation of machine learning [Stan­ fill and Waltz , 1986]. Several years ago it seemed that feasibility would depend especially on the development of new parallel architectures . Thanks to technological advancement, standard CPUs and 'big' memories allow the potentials of memory-based processing to be tested even with a compact experimental setup.

Memory-based visual navigation

This paper presents a memory-based visual navigat ion system developed at I RST. A module implementing a follow-midline behavior was experimented on a small robot that moves autonomously along the corridors of the Institute .

The system is based on the comparison of the visual input with encoded labeled images of the surrounding en­ vironment . Inputs are 128 x 128 gray-level images that are encoded by a preprocessing module that extracts lo­ cal directional fields. The spatial position of the robot is represented by cla.'ises that discretize the lateral displace­ ment and the attitude (angle) of the robot with respect to the centerline of the corridor.

The system memory is formed by associating encoded images with the corresponding spatial cla.<Ss. During learning the robot explores a part of the environment and memorizes images taken at a known attitude and lateral displacement. During performance , the robot has to move along the corridor near the centerline. To per­ form this task , the robot modifies its driving and steering velocity in accordance with the cla.<Ss estimated from the current image.

The research work ha.'S been developed within the framework of MAlA , the general AI project under de­ velopment at IR.ST ([Stringa, 1992; Poggio and Stringa, 1992]). -

More on memory-based learning

Learning schernata related to rnemory-based processing seem to constitute a successful strategy for coping with a complex and changing environment .

The basic mechanism is simple and general. The sys­ tern rnemory is organized using a set of tcmplatr..s of the input pattern space. The output for a new sensorial in­ put is computed on the basis of its similar ity with the templates previously memorized.

From a general point of view, the solution of many A.l. problems can be regarded either as the construction of a mapping or the validation of a regression model from data . In the algorithmic approach, the mapping is a rigid procedure, which is devised to extract from the input the information relevant for a specific problem. Algorithmic procedures can have high performance when the task to be performed and the environmental setting are well de­ fined. However , a<; they are very specific , every task and environmental condition requires a different algorithm. The more a system is dedicated to a particular solution, the more bias we have to introduce in the model, reduc­ ing fl exibility and robustness [Geman et al. , 1992].

In memory-based processing the mapping is synthe­ sized by a general procedure that depends on the con­ tent of the system memory. We impose as little bias as poss ible in pre-processing. By reducing the amount of specialized knowledge in the pre-processing phase, the inforrnation stored in memory can be used by different centers of elaboration to perform different tasks with one basic procedure.

Main characteristics of the memory-based approach are flexibility, .speed and robustness. Necessarily, such a general approach is sensitive to the characteristics of the training data, which have to be as representative and informative as possible. On the other hand , whenever storage space and the number of comparisons can be limited (for example by the use of vector quantization techniques), information processing ba<;ed on matching can be very efficient .

2 System Architecture

The navigation module has been developed from the gen­ eral architecture of memory-ba<;ed learning systems pre­ sented in Ref. [Crespi et al., 1992; Stringa, 1990]. Inputs are gray-level images that are encoded by the receptive fi elds of the systern. The system output is a probabil­ ity distribution that determines the cla<;sification of the input image according to a Bayesian decision rule. The global structure of the system is sketched in Fig. I.

The input image, described by a matrix G(:r, y) of N x x Ny pixels , is covered by N., subsets S'a of fixed size /{ x x /{ y. These subsets may or may not be overlapping and can be considered the receptive fields of the system. The pixels of a subset form a pattern that is mapped into a code. In this representation, an image G = Un S'n (where I :S a :S Ns) is described by a vector of codes (code(Sn))n.

We may think of the encoding procedure as a map­ ping. The visual information contained in the image is decomposed into elementary patterns and then rnapped into the code .space. The encoding mapping is chosen to quantize and compress information while emphasiz­ ing the dominant directions contained in the S'n. The hypothesis here is that navigation is such a basic behav­ ior that we do need to take into account large or corn­ plex patterns. Relevant information for real tirne nav­ igation can be obtained by extracting local direct ional fields frorn sirnple patterns a<; shown in Fig. 2.

During learning a large number of images are associ­ ated into several classes. These associat ions are memo­ rized by constructing the frequency matrices ¢n( code I' I classk) which represent the number of times pattern code 1 , has appeared in images belonging to a certain classk in subset S'n.

The image G is divided into larger subregions called windows. For example, in Fig. :3, the image is divided into four windows , WI' w2 , WJ , and w4· Subsets be­ longing to the same window are grouped together and the corresponding ¢n are summed

where w = i ,2, ... ,Nwindows, k = i , 2, ... , Nclasse.<, and p ranges over all the possible patterns . The frequency rnatrices <l>w forrn the memory of the system.

During performance an unlabeled irnage is cla<;sified by computing the Bayesian probabilities

for every different pattern that appears in the image. The a priorz class probabilities P(classi ) are assumed to be equal. If we suppose, for simpli city, t hat patterns are mutua lly independent , the image G is assigned to the cl ass that maximizes the quantity

where k = 1, 2, ... , N classes and p ranges over a ll the pa t­ terns that appear in window Ww of the test image.

The probability distribution p ( class I image) is com­ puted from the elementary distributions Pw (class I code). It is not known a priori how these probabili t ies are correla ted . The simplest choice, that of considering individual patterns as mutually independent , turns out to be good enough for our purposes .

The encoding is ba.'3ed on the division of visual in­ forma tion between pattern space (type of pattern) and posit ion space (position of the pattern in the image): the pattern is the elementary concept , or content , at posi­ tion ( J:,, Ys ). We reduce the large amount of information contained in images giving more consideration to content than to locality. This means grouping together subsets belonging to large r subregions (windows) of the i111age. A total independence of locali ty would be obtained by summing over all the locations of the subsets, i.e. by setting to one the number of windows .

For navigat ion along corridors, t he relevant infonna­ t ion is contained in the slopes of the edges . If the subsets are large enough, they will be able to represent segments of different direct ions, long enough to give a good est i­ mation of the mean slope in a window of the irnage. Since the exact locat ion of the segments is not irnpor­ t.ant, t he loss of locali ty will not affec t the cl ass ifi cat ion of the image.

I ssues on preprocessing

As exp lained in the previous sect ion, the basic opera­ t ion during learning is the construction of the assoc ia­ t. iVP nwrnory in t.errns of tnat ri ces t hat. relate pattPms and cl asses.

Even for a sma ll recept ive fi eld , say 5 x 5 subregion, the number of possible patterns, Npattern.· = 256 5 x 5 , is too large to be explicitly addressed . T herefore it is necessary to reduce dras tically t he size of the pattern space wi thout losing important pieces of inforrnat ion.

This can be done by choosing a set of feature se lt>c­ tors . Every pattern appearing in a subset is filtered by the feature selec tors and the resulting activation vec­ tor, v1 , v2 , ... , VN 1 ," '""' is quant ized in [0 , Q] . The quan­ tized vector is the code assoc iated with the pat tern. The number of possible codes is a fun ct ion of the num­ ber of features and of the quant ization parameter Q, N = QNJ ~ afu r~~.

The net result of feature ext ract ion is to project the original pat tern space into a smaller code space. There­ fore it is important to choose a set of uncorrelated fea­ t tlres that span the region of t he pattern space that con­ tains most information. It is natural to choose primary features that emphas ize local directions, i .e . the princi­ pal direct ions of the pattern contained in a subset. In this work we as features segments of 8 direc tions, one every 22.5 degrees [Stringa, 9:3] .

The feature t>xtractors are analogous to the sirnple cells of the neo cognitron [Fukushima ct a!., 198:3] . Thesf' are cells tha t respond to part icular local features. In our cast> we have 8 different cells responding to 8 direct ions. The act ivation function of a cell can be defined in dif­ ferent ways, bu t the choice is not crucia l. Two met h­ ods were tried . One is convolu t ion with 5 x 5 masks of segment-like Laplacian opera tors . In the second we dis­ cret ize the direct ion of the gradient in [0 , 7], and average the result in each 5 x 5 subset. In this applica tion the gradient method gives better results.

The level of activation of a cell is quan t ized in [0 , Q]. The resulting vector is the code associated with the given pattern. For Q = 1 the number of possible codes is 2 8 , if Q = 2 we have :3 8 = 6651 codes. With Q = 0 we indicate a winner takes all strat egy in whi ch only the cell with maxirnurn ac tivation generates a code.

We tested the class ifi cation capability of the system with real images, real preprocessed images and virtual Images .

Artifi cial images ( 128 x 128) are composed by edges.

The virtual environment is a corridor, learning and test­ ing is done in a strip I 0-meters long and 2-meters wide. Th!' angl~' varies in the range [-:30 , +:30) degrees. Spatial positions are discretized in .5 x ,) classes. Since virtual images are simple and noiseless, the performance of the systern is very good for any reasonable choice of param­ eters. The number of correct answers is around 98%.

The data base of real images consists of 450 images ( 128 x 128) of a corridor of our institute. Images are randornly distributed in a strip 10-rneters long and 1rneter wide, the angle is in the range [ -20, +20) degrees. In typical tests 400 images are used for learning and .50 for testing . The data base is randomly subdivided between learning set and test set.

The nurnber of spatial classes used is nine, three classes for attitude and three for lateral displacement. With Q = I , the system classifies correctly 79% of the images; in the 20% of the cases only angle or displace­ ment is c.orrect , in 1% of the cases both classes are wrong. For Q=O we have (76%, 2:3%, 1:3%) respec­ tively. The performance improves if the code space is enlarged (Q=2) and the number of patterns is increased, for example by using overlapping subsets. In this case the performance reaches ~ 85% of right answers but the processing time increases. A more complicated prepro­ cessing, such as the use of an "edge follower" does not irnprove performance.

In the version implemented on the robot we use 15 classes, :3 classes for position and ,) classes for angle. More classes are needed for attitude because the range is wider than in the data base. In the Fourier method the features are the orthogonal Fourier basis functions with wavelength of 2-4 pixels and the code is obtained by a quantization of the absolute value of the corresponding coefficients.

In ref.[Crespi et a/. , 1992) we tested a processing rnethod based on local 2-D Fourier transform. The rnethod uses a much larger code space, N codes ~ 2 30 . Since the matrices are too large to be explicitly stored, mernory addressing is based on hash table techniques.

The 2-D Fourier c.oefficients·

represent directions. The direction corresponding to coefficient C:(p,q) is given by (q, -p). For example, C:(:3 , -:3) represents the 4.5° direction.

In every subset we compute the absolute values of co­ effi cients with Bmax 2: p 2 + q 2 2: (}min, where Bmax and (}min are chosen thresholds. Values corresponding to the same slope are added together. The resulting values rep­ resent the directional sper.trum of the subset and are quantized in the interval [0 , :3). For receptive fields of size 6 x 6 we consider 16 different direct ions correspond­ ing to (}min = .5 , Bmax = 18. The number of possible patterns is 4 16 .

In the Fourier method the features are the orthogonal Fourier basis functions with wavelength of 2-4 pixels and the code is obtained by a quantization of the absolute value of tht> corresponding coefficients.

The performance of the Fourier method on the same data ba::;e is similar , but the processing time is longer. This is due to the larger size of the space code. For nav igat ion purposes only a srnall number of features is suffi cient . However in a more cornplex environrnent in­ formation other than simple slope could become irnpor­ tant.

Connections with similar paradigms

The simplest instance of the rnemory-based approach is the neare.st-neighbor regression scherna: the response for a new input x is obtained by averaging the responses of the reference patterns contained in a neighborhood of the input pattern.

More generally, in the Parzen-window sche1na non­ negative kernel functions are evaluated for each new in­ put. Local estimation is then obtained with kernel func­ tions usually having a maximum at prototype pattern x and decreasing value away from x.

Many learning schernata usually placed in the neural networks paradigm are a further extension of this idea. A rnajor exarnple is given by networks implernenting the approxirnation schema f(x) = LZ=o caC:n(llx- tall) where the basis functions c;(llx - t a II) exhibit a ra­ dial symmetry with respect. to the center.s t,.. Po­ sition of centers and parameters of the expansion are learned via presentation of exemplar pairs (input, output) and optimized with respect to a cost functional. A well founded extension of this schema is the HyperBF net­ work (see [Poggio, 1990) and references therein). A Hy­ perBF network is applied in [Aste and Caprile , 1992] to address the same navigation task for a robot moving in a synthetic world and with a more elaborated preprocess­ ing phase.

We have mentioned above how the use of memory­ based reasoning on massively parallel computer wa.<; ad­ vocated a.<; a possible foundation of rnachine-rea.<;oning in [Stanfill and Waltz, 1986] . Although we are not explic­ itly using a distance metric between templates and new inputs, our approach is consistent with the .similar-ity­ based induction criterion proposed in that paper. Our navigation module implemented on a PC board indicates that memory-based reasoning is a valid approach to in­ formation processing even on standard computers.

Experimental Setting

The robot used for the experiments is a small platform (see Fig. 4) developed at IRST [Bellutta, 1991). The mo­ tion is governed by two stepping motors programmable in terms of displacement or motor speed and acceler­ ation. The robot measures 40 x 40 em and weights 30 Kg. The robot "brain" is a 486 CPU (25 MHz) equipped with a visual system consisting of a Matrox PIP frame grabber and a gray-level camera.

In the navigation experiment, spatial positions (d, a) of the robot in a corridor are represented by 15 cla.<;ses, 5 cla.<;ses for attitude angle a in the interval [-45°, +45°) degrees, and :3 classes for lateral displacement d from t.he centerline in the interval [-0.60 m, 0.60 m). To better control the system performance we have chosen to label images with their spatial position and not to associate irnages and commands directly as done in [Pomerlau , 1991) .

3 Results and Discussion

In Fig. 5 we show some typical trajectories of the robot . The system implemented on the robot is based on the 8-direction feature extractors. Similar results where ob­ tained with Fourier preprocessing in [Crespi et a/., 1992]. In Fig. 6 some trajectories obtained with the two meth­ ods are compared. The robot is trained in the gray areas. In each area the robot memorizes 225 images , :3 images for each spatial class. During performance the robot changes its steering and driving velocities according to the image present. The driving speed is about 0 .. 5 m/sec and the processing speed is 2 .. 5 images per second .

To test the generalization capability of the system, learning is limited to a small part of the corridor . The robot is able to move along the entire corridor and avoid obstacles that narrow the perspective of the corridor, such as air conditioners and plants set along the walls (see Fig.5 .b,d). Furthermore it is able to navigate in other r.orridors of different geometrical shapes , see for exarnple Fig.5.d. System performance does not depend on illurnination r.ondit ions. Learning and testing were done at different times and under very different lighting r.onditions.

Deviations of the trajectories from the centerline are usually due to the presence of windows, reflections on the walls, openings , etc. The deviation is usually confined to a 50 ern band around the "optimal" trajectory.

The experiments show that a memory-ba.<;ed architec­ ture can provide an efficient and flexible method for pro­ cessing sensorial inputs even using standard sequential computers. The basic system can be easily adapted to a specific application and has a good generalization capa­ bility.

Our results indicate that the extraction of local direc­ tional fields is an important technique in processing vi­ sual information . For navigation purposes only a small number of local features and a single layer network is sufficient in the analysis of the visual input. For more r.omplex tasks the system r.ould be easily expanded to include several layers in which the local features of the first layer are combined into higher order structures.