Improving Sequential Single-Item Auctions

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

Authors

• Xiaoming Zheng
• Sven Koenig
• Craig A. Tovey

Keywords

• Robot kinematics
• Costs
• Orbital robotics
• Intelligent robots
• Computer science
• Centralized control
• Concurrent computing
• Aerospace industry
• Computer industry
• Systems engineering and theory
• Environmental Remediation
• Bidding
• Hill-climbing
• Rescue Missions
• Minimum Distance
• Computational Burden
• Experimental Evaluation
• Single Target
• Lowest Cost
• Amount Of Computation
• Small Cost
• Table Reports
• Aspects Of Implementation
• Complete Assignments
• Target Pairs
• Traveling Salesman Problem
• Optimal Assignment
• Swarm Robotics
• Current Round
• Procedure Repeats