2023/06/20 by Ashay Aswale, Carlo Pinciroli, Aswale, Ashay +1 · 1 citation
Computer Science · Decision Sciences · Engineering · #Auction Theory and Applications #FOS: Computer and information sciences #Optimization and Search Problems #Robotics (cs.RO) #Scheduling and Optimization Algorithms
paper · pdf · doi:10.48550/arxiv.2306.11936
openalex publication_date 2023/06/20 · openalex created_date 2023/06/24 · openalex updated_date 2026/07/28
We present an approach to task scheduling in heterogeneous multi-robot systems. In our setting, the tasks to complete require diverse skills. We assume that each robot is multi-skilled, i.e., each robot offers a subset of the possible skills. This makes the formation of heterogeneous teams (coalitions) a requirement for task completion. We present two centralized algorithms to schedule robots across tasks and to form suitable coalitions, assuming stochastic travel times across tasks. The coalitions are dynamic, in that the robots form and disband coalitions as the schedule is executed. The first algorithm we propose guarantees optimality, but its run-time is acceptable only for small problem instances. The second algorithm we propose can tackle large problems with short run-times, and is based on a heuristic approach that typically reaches 1x-2x of the optimal solution cost.