Tracking multiple moving objects for real-time robot navigation

This paper proposes a method for detecting and tracking the motion of a large number of dynamic objects in crowded environments, such as concourses in railway stations or airports, shopping malls, or convention centers. With this motion information, a mobile vehicle is able to navigate autonomously among moving obstacles, operating at higher speeds and using more informed locomotion strategies that perform better than simple reactive manoeuvering strategies. Unlike many of the methods for motion detection and tracking discussed in the literature, our approach is not based on visual imagery but uses 2D range data obtained using a laser rangefinder. The direct availability of range information contributes to the real-time performance of our approach, which is a primary goal of the project, since the purpose of the vehicle is the transport of humans in crowded areas. Motion detection and tracking of dynamic objects is done by constructing a sequence of temporal lattice maps. These capture the time-varying nature of the environment, and are denoted as time-stamp maps. A time-stamp map is a projection of range information obtained over a short interval of time (a scan) onto a two-dimensional grid, where each cell which coincides with a specific range value is assigned a time stamp. Based on this representation, we devised two algorithms for motion detection and motion tracking. The approach is very efficient, with a complete cycle involving both motion detection and tracking taking 6 ms on a Pentium 166 MHz. The system has been demonstrated on an intelligent wheelchair operating in railway stations and convention centers during rush hour.