A closed-loop bid adjustment approach to dynamic task allocation of robots

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 aim to assemble robot team information at a single location to make practicable decisions on task allocation. However, a main deficiency of auction-based methods is that robots generally do not have sufficient information to estimate accurate and reliable bids to perform tasks, particularly in dynamic environments where there are operational uncertainties. 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 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 ssesses and records its performance to reflect the discrepancy between the submitted bid price and the corresponding actual cost of the task. A series of such performance records, with time-discounting factors, are taken into account to damp out fluctuations of bid adjustments. 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 bid adjustment mechanism.