In the near future, teams of robots will take on tasks in initially unknown environments where human presence is not possible due to safety or cost reasons, including applications where robots have to visit or cover areas in initially unknown terrain, such as mine sweeping and de-mining, search and rescue operations after earthquakes, the exploration of distant planets, and hazardous material cleaning. The efficient and robust coordination of the robots is imperative for all of these scenarios. This project develops and implements methods for the dynamic assignment and re-assignment of tasks to robot teams through the use of combinatorial auctions in the context of exploration tasks in initially unknown environments. Previous work has demonstrated the use of single-item auctions for multi-robot task allocation, in which robots bid on tasks that are auctioned off one at a time. Unfortunately, single-item auctions do not take synergies between tasks into account, which can result in suboptimal task allocations and poor team performance. This project studies more complex auctions, including combinatorial auctions, where robots bid on bundles of tasks. Initial feasibility studies show that combinatorial auctions generally lead to significantly superior team performance compared to single-item auctions, and generate very good results compared to optimal centralized methods. The project focuses on combinatorial bidding strategies which result in team behavior that is efficient, effective, adaptable to dynamic environments, and robust in the presence of error conditions. It also studies alternative winner determination methods for various objective functions, such as minimizing the total travel distance (or energy consumption) and the total time to task completion. This interdisciplinary project between robotics and auction researchers will produce both theoretical and experimental results, in particular, new methods with theoretical analyses of their correctness and efficiency and their demonstration on both simple and complex multi-robot exploration scenarios with real-time requirements. The students involved in this research will learn to work as part of an interdisciplinary team and will deepen their understanding of two usually separate areas of research.
