Back
Computer Science

Cooperative and load-balancing auctions for heterogeneous multi-robot teams dealing with spatial and non-atomic tasks

In our research, we address the problem of coordination and planning in heterogeneous multi-robot systems for missions that consists of a set of spatially localized tasks. Conventionally, this problem has been framed as a task allocation problem that maps tasks to robots. However, all previous work assumes that tasks are atomic procedures. In this work we relax this assumption and adopt a non-atomic model of tasks that enables robots to accomplish mission tasks in an incremental manner over disjoint periods of time, precisely to account for the possibility of having a task being serviced by multiple individual contributions over time. This model can be useful in search and rescue scenarios: the same portion of the environment can be explored at different times by different agents using different sensors. We propose a cooperative, load-balancing task allocation and scheduling algorithm based on sequential single-item auctions (CoLoSSI). Our approach explicitly considers the non-atomicity of tasks and promotes synergies between agents enabling cooperation while at the same time maintaining computational tractability. We also study a fully distributed implementation of the task allocation approach in sparse, communication-restricted scenarios, and propose an effective strategy to enhance its computational efficiency. A computational and simulation validation is also carried out, confirming the efficacy of the proposed approach for generating good quality mission plans with low computational effort.

View poster   |  Watch video

  • Authors

    Abubakr Mohamed, Ishaq Ansari

  • Advisor

    Saquib Razak, Eduardo Feo-Flushing

  • Carnegie Mellon University in Qatar

    Education City
    PO Box 24866
    Doha, Qatar
  • Phone

    +974 4454 8400
  • Don’t miss out

    If you want to keep up to date on the latest at CMU-Q send us your email address