A flocking and obstacle avoidance algorithm for mobile robots

Mobile robots cooperating in groups offer several advantages such as redundancy and flexibility and can sometimes perform tasks that would be impossible for one single robot. We have developed a new algorithm for navigating a group of robots to a predefined target while avoiding obstacles and staying together in a formation. The algorithm merges a potential-based method that provides the shortest unobstructed path to the goal with an approach from coverage control, where the centroids of Voronoi partitions are used to optimize the placement of sensors in a scalar field. Our algorithm guarantees safety: there will be no collisions between robots or with obstacles of arbitrary shape. It has shown reliable goal convergence in simulations, and the robots form a hexagonal lattice when moving in open fields. Further, the algorithm is completely decentralized and the processing load for each robot is virtually unaffected by adding more group members. This report provides a description of the algorithm and its properties, as well as results from simulations in both Matlab and Fenix, a graphical simulation environment developed at FOI, where the robots are modeled as the US Army HMMWV all-terrain vehicle.