Efficient bids on task allocation for multi-robot exploration

We propose a real time single item auction based task allocation method for the multi-robot exploration problem and investigate new bid evaluation strategies in this domain. In this problem, a different version of the well known NP-hard MTSP (Multiple Traveling Salesman Problem), each target must be visited by at least one robot in its open tour. Various objectives may be defined for this problem (e.g. minimization of total path length, time). In this article, we present an extensive analysis of our bid evaluation strategies for minimization of total path length objective. An integer programming (IP) approach may be used to allocate tasks to robots. However, IP approach may become impractical when the size of the mission is not small, the environment is dynamic or unknown, or the structure of the mission changes by online tasks. In real world domains, initial allocations assigned by computationally expensive methods are usually subject to change during run time. Our framework, capable of handling diverse contingencies, performs an incremental allocation method based on the up-to-date situations of the environment. Experimental results in simulations compared to both the results of the Prim Allocation method and the optima reveal efficiency of the bid evaluation heuristics combined with our framework.