Tracking multiple moving objects for real-time robot navigation

This paper proposes a method for detecting and tracking the motion of a lar ge 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 d iscussed in the literature, our approach is not based on visual imagery but uses 2D range data obtained using a laser rangefinder. The direct availabi lity of range information contributes to the real-time performance of our a pproach, which is a primary goal of the project, since the purpose of the v ehicle is the transport of humans in crowded areas. Motion detection and tr acking of dynamic objects is done by constructing a sequence of temporal la ttice maps. These capture the time-varying nature of the environment, and a re denoted as time-stamp maps. A time-stamp map is a projection of range in formation obtained over a short interval of time (a scan) onto a two-dimens ional grid, where each cell which coincides with a specific range value is assigned a time stamp. Based on this representation, we devised two algorit hms for motion detection and motion tracking. The approach is very efficien t, with a complete cycle involving both motion detection and tracking takin g 6 ms on a Pentium 166 MHz. The system has been demonstrated on an intelli gent wheelchair operating in railway stations and convention centers during rush hour.