Ecient 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 prob-lem and investigate new bid evaluation strategies in this domain. In this problem, a dierent 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 de-ned 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 minimiza-tion of total path length objective. An integer program-ming (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 environ-ment is dynamic or unknown, or the structure of the mission changes by online tasks. In real world domains, initial allocations assigned by computationally expen-sive methods are usually subject to change during run time. Our framework, capable of handling diverse con-tingencies, 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 op-tima reveal eciency of the bid evaluation heuristics combined with our framework