Nonsmooth analysis and sonar-based implementation of distributed coordination algorithms

Abstract

This paper investigates the behavior of a group of autonomous robots evolving in a polygonal environment according to a "move away from the closest neighbor" heuristic. We demonstrate that this distributed coordination algorithm optimizes an aggregate cost function that measures how uniformly distributed are the robots in their environment. Our technical approach based on non-smooth analysis and computational geometry unveils a sphere-packing problem. The algorithm is implemented in a testbed of indoor mobile robots equipped with sonar. We develop novel approaches for improving single point sonar scan performance. These algorithms are then shown to have improved reliability, resolution and speed in distributed environments as compared to other scanning methods.