An auction-based approach with closed-loop bid adjustment to dynamic task allocation in robot teams

Abstract

Dynamic task allocation is among the most difficult issues in multi-robot coordination, although it is imperative for a multitude of applications. Auction-based approaches are popular methods that allocate tasks to robots by assembling team information at a single location to make practicable decisions. However, a main deficiency of auction-based methods is that robots generally do not have sufficient information to estimate reliable bids to perform tasks, particularly in dynamic environments. While some techniques have been developed to improve bidding, they are mostly open-looped without feed-back adjustments to tune the bid prices for subsequent tasks of the same type. Robots' bids, if not assessed and adjusted accordingly, may not be trustworthy and would indeed impede team performance. To address this issue, we propose a closed-loop bid adjustment mechanism for auction-based multi-robot task allocation, with an aim to evaluate and improve robots' bids, and hence enhance the overall team performance. Each robot in a team maintains and uses its own track record as closed-loop feedback information to adjust and improve its bid prices. After a robot has completed a task, it assesses and records its performance to reflect the discrepancy between the bid price and the actual cost of the task. Such performance records, with time-discounting factors, are taken into account to damp out fluctuations of bid prices. Adopting this adjustment mechanism, a task would be more likely allocated to a competent robot that submits a more accurate bid price, and hence improve the overall team performance. Simulation of task allocation of free-range automated guided vehicles serving at a container terminal is presented to demonstrate the effectiveness of the adjustment mechanism.