From Ants to Service Robots : an Exploration in Stigmergy-Based Navigation Algorithms

Navigation is a core functionality of mobile robots. To navigate autonomously, a mobile robot typically relies on internal maps, self-localization, and path planning. Reliable navigation usually comes at the cost of expensive sensors and often requires significant computational overhead. Many insects in nature perform robust, close-to-optimal goal directed navigation without having the luxury of sophisticated sensors, powerful computational resources, or even an internally stored map. They do so by exploiting a simple but powerful principle called stigmergy: they use their environment as an external memory to store, read and share information. In this thesis, we explore the use of stigmergy as an alternative route to realize autonomous navigation in practical robotic systems. In our approach, we realize a stigmergic medium using RFID (Radio Frequency Identification) technology by embedding a grid of read-write RFID tags in the floor. A set of mobile robots, then, build and store maps used for navigation in the stigmergic medium itself. These maps are of three types: (1) goal maps which guide robots to known locations; (2) clearance maps which help robots avoid obstacles; (3) feature maps which can be used to store observable properties, such as light intensity or gas concentration. We show how these maps can be built both in static and in dynamic environments and used for navigation of heterogeneous robots. We also show that goal maps can be used for navigation to previously unknown and/or dynamic locations, and that feature maps can be used to navigate towards specific features, e.g., places with high gas concentration that are beyond the sensor’s range. We address the issue of perceptual errors (e.g., broken tags) during navigation. We further study the use of the built navigation maps to enable different types of human-aware robot navigation on the RFID floor. We define several stigmergic algorithms for building maps and navigating on these maps. We formally analyse the properties of the main algorithms, and empirically evaluate all the algorithms both in simulation and with multiple physical robots. Results collected from tens of hours of real experiments and thousands of simulated runs demonstrate the effectiveness of our approach