Optimal bid valuation using path finding for multi-robot task allocation

When multiple robots are supposed to operate together, coordination and communication issues arise. "Which robot should execute which task?" is the key question of the multi-robot task allocation problem. Properly allocating tasks among robots so as to obtain optimality is a primary research problem in the multi-robot coordination domain. Based on a simultaneous consideration of the team cost and computation time, a new approach for integrating path planning into a robot's bids for tasks is presented. A practical path finding technique is proposed and combined with the Travelling Salesman Problem solution and Dijkstra shortest path solution for calculating bids. This combination produces a good alternative for path planning. By using this model for bid valuation, the cost is calculated without sacrificing the performance. Simulation experiments prove that the approach addressed in this paper has great advantages, including less computation, better real-time performance, a stronger ability to find the optimal result, etc.