Diversified Local Search for the Optimal Layout of Beacons in an Indoor Positioning System

Abstract

The navigation of autonomous guided vehicles (AGV’s) in industrial environments is often controlled by positioning systems based on landmarks or artificial beacons. In these systems, the position of an AGV navigating in an interior space is determined by the calculation of its relative distance to beacons, whose location is known in advance. A fundamental design problem associated with landmark navigation systems consists of determining the optimal location of the minimum number of beacons necessary to achieve a desired level of accuracy and reliability. A local search procedure coupled with a diversification strategy is developed for this problem. We provide comparisons with an earlier solution method based on genetic algorithms and show that our proposed procedure finds better designs in a fraction of the computational time employed by the genetic algorithm.