Sequential single-item auction improvements for heterogeneous multi-robot routing

Abstract

We introduce new auction bidding and resolution algorithms to improve multi-robot sequential single-item auctions for heterogeneous systems. We consider two objectives, minimising the energy usage and time required to complete all tasks. Sequential single-item auctions are computationally inexpensive while producing efficient task allocations for homogeneous robots, but produce less efficient allocations for heterogeneous robots. Our algorithms provide consistent and significant (up to 20%) improvements for both objectives for a number of scenarios relative to the standard auction process, as tested in MATLAB simulations. Interestingly, our algorithms produce faster task completion even in homogeneous systems. We also introduce a new algorithm for sequential single-item auctions when robots have partial knowledge of their environment. We illustrate its improved performance and analyse its sensitivity, showing that precise tuning is not essential for faster and more efficient task completion. These improvements can reduce energy usage and task completion times for both indoor and outdoor robots in a variety of fields.