Comparison of Classification Techniques for Wall Following Robot Navigation and Improvements to the KNN Algorithm

Abstract

Autonomous navigation is an important feature that allows the robot to move independently from a point to another without a tele-operator. This feature makes mobile robots useful in many tasks that require transportation, exploration, surveillance, guidance, inspection etc. Furthermore, autonomous robots deal with real time environments that tend to be complex, nonlinear and partially observed. They also operate with limited memory resources and tight time constraints. In this paper, we present an investigation related to mobile robot navigation. We first compare a group of classification algorithms using real traces of wall following robot navigation. Then we focus on the k Nearest Neighbors (KNN) algorithm to improve it and help it be more applicable in autonomous robot navigation. We applied a Nearest Neighbor set reduction technique to help reduce the high running time of KNN. The results indicate that KNN is a competing algorithm especially after decreasing the running time significantly by a factor of 19 and combining that with the KNN's existing features. Results are further improved by applying an attribute selection method.