Xiaoming Zheng, Sven Koenig and Craig Tovey, Improving Sequential Single-Item Auctions, In Proceedings of the IEEE International Conference on Intelligent Robots and Systems (IROS), pages 2238-2244, 2006. Also in: Proceedings of the AAAI 2006 Workshop on Auction Mechanisms for Robot Coordination.

Abstract: We study how to improve sequential single-item auctions that assign targets to robots for exploration tasks such as environmental clean-up, space-exploration, and search and rescue missions. We exploit the insight that the resulting travel distances are small if the bidding and winner-determination rules are designed to result in hillclimbing, namely to assign an additional target to a robot in each round of the sequential single-item auction so that the team cost increases the least. We study the impact of increasing the lookahead of hillclimbing and using roll-outs to improve the evaluation of partial target assignments. We describe the bidding and winner-determination rules of the resulting sequential single-item auctions and evaluate them experimentally, with surprising results: Larger lookaheads do not improve sequential single-item auctions reliably while only a small number of roll-outs in early rounds already improve them substantially.

Download the paper in pdf.