Robot Exploration with Combinatorial Auctions

M. Berhault, H. Huang, P. Keskinocak, S. Koenig, W. Elmaghraby, P. Griffin, A. Kleywegt

Research output: Contribution to conferencePaperpeer-review

160 Scopus citations


We study how to coordinate a team of mobile robots to visit a number of given targets in partially unknown terrain. Robotics researchers have studied single-item auctions (where robots bid on single targets) to perform this exploration task but these do not take synergies between the targets into account. We therefore design combinatorial auctions (where robots bid on bundles of targets), propose different combinatorial bidding strategies and compare their performance with each other, as well as to single-item auctions and an optimal centralized mechanism. Our computational results in TeamBots, a multi-robot simulator, indicate that combinatorial auctions generally lead to significantly superior team performance than single-item auctions, and generate very good results compared to an optimal centralized mechanism.

Original languageEnglish (US)
Number of pages6
StatePublished - 2003
Event2003 IEEE/RSJ International Conference on Intelligent Robots and Systems - Las Vegas, NV, United States
Duration: Oct 27 2003Oct 31 2003


Other2003 IEEE/RSJ International Conference on Intelligent Robots and Systems
Country/TerritoryUnited States
CityLas Vegas, NV

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering
  • Software
  • Computer Vision and Pattern Recognition
  • Computer Science Applications


Dive into the research topics of 'Robot Exploration with Combinatorial Auctions'. Together they form a unique fingerprint.

Cite this