Upper-bound cost analysis of a market-based algorithm applied to the initial formation problem

Abstract

In this paper, an analysis of a market-based approach applied to the Initial Formation Problem is presented. This problem tries to determine which mobile sensor should go to each position of a desired formation in order to minimize an objective. In our case, this objective is the global distance traveled by all the mobile sensors. In this analysis, a bound on the efficiency for the market-based algorithm is calculated and it is shown that the relative difference as compared with the optimal solution increases with the logarithm of the total number of mobile sensors. The theoretical results are validated with numerous simulations.