Motion in ambiguity: Coordinated active global localization for multiple robots

The task of the robot in localization is to find out where it is, through sensing and motion. In environments which possess relatively few features that enable a robot to unambiguously determine its location, global localization algorithms can result in ‘multiple hypotheses’ locations of a robot. This is inevitable with global localization algorithms, as the local environment seen by a robot repeats at other parts of the map. Thus, for effective localization, the robot has to be actively guided to those locations where there is a maximum chance of eliminating most of the ambiguous states — which is often referred to as ‘active localization’. When extended to multi-robotic scenarios where all robots possess more than one hypothesis of their position, there is an opportunity to do better by using robots, apart from obstacles, as ‘hypotheses resolving agents’. The paper presents a unified framework which accounts for the map structure as well as measurement amongst robots, while guiding a set of robots to locations where they can singularize to a unique state. The strategy shepherds the robots to places where the probability of obtaining a unique hypothesis for a set of multiple robots is a maximum. Another aspect of framework demonstrates the idea of dispatching localized robots to locations where they can assist a maximum of the remaining unlocalized robots to overcome their ambiguity, named as ‘coordinated localization’. The appropriateness of our approach is demonstrated empirically in both simulation & real-time (on Amigo-bots) and its efficacy verified. Extensive comparative analysis portrays the advantage of the current method over others that do not perform active localization in a multi-robotic sense. It also portrays the performance gain by considering map structure and robot placement to actively localize over methods that consider only one of them or neither. Theoretical backing stems from the proven completeness of the method for a large category of diverse environments.     

Hierarchical Sampling from Sketches: Estimating Functions over Data Streams

We present a randomized procedure named Hierarchical Sampling from Sketches (Hss) that can be used for estimating a class of functions over the frequency vector f of update streams of the form . We illustrate this by applying the Hss technique to design nearly space-optimal algorithms for estimating the pth moment of the frequency vector, for real p≥2 and for estimating the entropy of a data stream. Preliminary version of this paper appeared as the following conference publications. “Simpler algorithm for estimating frequency moments of data streams,” Lakshminath Bhuvanagiri, Sumit Ganguly, Deepanjan Kesh and Chandan Saha, Proceedings of the ACM Symposium on Discrete Algorithms, 2006, pp. 708–713 and “Estimating entropy over data streams,” Lakshminath Bhuvanagiri and Sumit Ganguly, Proceedings of the European Symposium on Algorithms, LNCS, vol. 4168, pp. 148–159, Springer, 2006.