A Fast Memory-Efficient Incremental Decision Tree Algorithm in its Application to Mobile Robot Navigation

Abstract

Incremental learning is vital in robots that need to adapt rapidly and respond appropriately to new or unexpected events that occur in its vicinity. This paper describes a novel incremental learning method here demonstrated in its reactive navigation of a mobile robot. The approach records acquired feature vectors in a compact statistical representation we term a frequency table that is purposely designed to contain sufficient information for the generation of a conventional C4.5 decision tree. During learning, further feature vectors can be added in an incremental manner to the frequency table which can then be used to generate new decision trees as required. A major advantage compared with previous incremental decision tree approaches that keep feature vectors in the tree itself, is that the frequency table's memory requirement is fixed and known a priori. Experimental results in the practical application of the method to the real-time navigation of a mobile robot through previously uncharted environments show that the calculation time is typically an order of magnitude less than that of an incremental generation of an ITI decision tree