Real Time Auction Based Allocation of Tasks for Multi-Robot Exploration Problem in Dynamic Environments

Contents

Single auction-based methods are known to be efficient for multi-robot problem solving. In this work, we investigate performance of our general multi robot coordination framework for multi robot multi target exploration problem under uncertainties in dynamic environments. Our framework offers a real time single item allocation method featuring different mechanisms for failure recovery. In multi robot exploration problem, a different version of well known NP-hard MTSP (Multiple Traveling Salesman Problem), each target is visited by at least one robot in its open tour. Overall objective function for cost optimization while visiting targets varies by different exploration domains. In this work, we present performance results for total cost minimization objective. There are many efficient centralized heuristic methods for generating close to optimal solutions. These heuristics may be used to allocate targets to robots. However, when the environment is dynamic and/or unknown, initially assigned targets may need to be reallocated during run time. In our framework, redundant calculations are eliminated by means of incremental assignments based on up-to-date situations of the environment. Offered precautions in the framework maintain the quality of solutions as close to optimal as possible. Experiments are conducted on simulations. The comparison of the proposed method is made with Prim Allocation method.