A Distributed Technique for Localization of Agent Formations From Relative Range Measurements

Abstract

Autonomous agents deployed or moving on land for the purpose of carrying out coordinated tasks need to have good knowledge of their absolute or relative position. For large formations, it is often impractical to equip each agent with an absolute sensor such as GPS, whereas relative range sensors measuring interagent distances are cheap and commonly available. In this setting, this paper considers the problem of autonomous distributed estimation of the position of each agent in a networked formation using noisy measurements of interagent distances. The underlying geometrical problem has been studied quite extensively in various fields, ranging from molecular biology to robotics, and it is known to lead to a hard nonconvex optimization problem. Centralized algorithms do exist that work reasonably well in finding local or global minimizers for this problem (e.g., semidefinite programming relaxations). Here, we explore a fully decentralized approach for localization from range measurements, and we propose a computational scheme based on a distributed gradient algorithm with Barzilai-Borwein stepsizes. The advantage of this distributed approach is that each agent may autonomously compute its position estimate, exchanging information only with its neighbors, without need of communicating with a central station and without needing complete knowledge of the network structure.