Learning Decision Trees for Mapping the Local Environment

in Mobile Robot Navigation

Ian Sillitoe
Department of Electronic and Electrical Engineering Loughborough University of Technology
Loughborough, Leicestershire, LE11 3TU, U.K. [email protected]

Tapio Elomaa
Department of Computer Science
P. O. Box 26 (Teollisuuskatu 23)
FIN-00014 University of Helsinki, Finland
[email protected]

Abstract

This paper describes the use of the C4.5 decision tree learning algorithm in the design of a classifier for a new approach to the mapping of a mobile robot's local environment. The decision tree uses the features from the echoes of an ultrasonic array mounted on the robot to classify the contours of its local environment. The contours are classified into a finite number of two dimensional shapes to form a primitive map which is to be used for navigation. The nature of the problem, noise and the practical timing constraints, distinguishes it from those typically used in machine learning applications and highlights some of the advantages of decision tree learning in robotic applications.

1 INTRODUCTION

Ultrasonic sensors are often used to measure distances and in the majority of cases the time of flight of an ultrasonic pulse of energy is utilized. That is, the total time taken for the pulse to leave the transmitter, reach the object in question, and then on the final leg of its journey, the time for the reflections wave front to reach the receiver. When the total time is divided by the speed of sound an estimate of the shortest distance travelled by the pulse can be obtained. There are many variants of this technique in which a single transducer is used as both the transmitter and receiver or where there are arrays of both receivers and transmitters. Much attention has been placed upon the accurate determination of the beginning of the received pulse, since this plays an important role in maximising the accuracy of such a system (Barshan and Kuc, 1992).

These approaches essentially give a spot reading; i.e., they return the distance to a given spot on the object. In order to allow a time-of-flight ultrasonic system to produce a more detailed map of the surface of the object the sensor spot must be moved across the object. This can be done in either of two ways: mechanically, where the sensor is moved relative to the object (Kuc and Bozma, 1991), or through the use of a phased array technique, whereby the relative phase

of a number of transmitters is altered so that the combined wave front is shifted. The mechanical procedure requires that the sensor is moved and reading taken many times during a single scan. Hence, the procedure is limited to the mapping of environments which remain static during this long sampling period. Whilst, the phased array approach is based upon electronic scanning and so its response time is dominated by the much shorter time-of-flight measurement. The approach, however, places stringent requirements on the complex hardware used to both generate and process the transmitted and received waveforms.

This paper describes an alternative approach to the use of ultrasonic sensors for the classification of surfaces, one in which both the hardware and software requirements are extremely modest and which only requires the analysis of a single pulse. The technique uses two receivers and a single transmitter which are arranged so that their active volumes almost completely overlap and, hence, the two receivers `see' the same `illuminated' volume in front of the sensor array (see Figure 1). Thus, this system is similar in its physical arrangement to the 'Bat Sonar' system (Barshan and Kuc, 1992), which used time of flight to identify the position of objects within its working volume. However, it differs in three significant features: firstly, the whole echo returned by the object is processed, not only the time-offlight measurement, secondly, the objective of this system is to classify the shape of the object as well as determining its position, and thirdly, this approach constraints the objects to be `close' to the sensor. These characteristics make the approach useful for rapid mapping of the local environment as required in mobile robot applications.

In addition to introducing the new approach to the use of ultrasonic sensors for the classification of surfaces, we also describe, in this paper, how machine learning techniques have been used to facilitate feature extraction for the classifier. We report some of our preliminary experiences on using the C4.5 algorithm (Quinlan, 1993) to construct decision tree classifiers from feature vectors recorded for example objects exposed to the sensor system. In our experience, decision tree learning seems to suit the purpose very well.