A novel Stochastic Clustering Auction for task allocation in multi-robot teams

Abstract

It will be shown that the global cost of the task allocations obtained with fast greedy algorithms can be improved upon by using a class of auction methods called Stochastic Clustering Auctions (SCAs). SCAs use stochastic transfers or swaps between the task clusters assigned to each team member, allow both uphill and downhill cost movements, and rely on simulated annealing. The choice of a key annealing parameter and turning the uphill movements on and off enables the converged solution of a SCA to slide in the region between the global optimal performance and the performance associated with a random allocation. The first SCA, called GSSCA, was based on a Gibbs Sampler, which constrained the stochastic cluster reallocations to simple single transfers or swaps. This paper presents a new and more efficient SCA, called SWSCA, based on the generalized Swendsen-Wang method that enables more complex and efficient movements between clusters by connecting tasks that appear to be synergistic and then stochastically reassigning these connected tasks. For centralized auctioning, extensive numerical experiments are used to compare the performance of SWSCA with GSSCA in terms of costs and computational and communication requirements. Distributed SWSCA is then compared with centralized SWSCA using communication links between robots that were motivated by a generic topology called a “scale free network”.