Solving the Task Variant Allocation Problem in Distributed Robotics

Jose Cano Reyes, David White, Alejandro (Alex) Bordallo, Ciaran McCreesh, Ana Lito Michala, Jeremy Singer, Vijayanand Nagarajan

Research output: Contribution to journalArticlepeer-review

Abstract

We consider the problem of assigning software processes (or tasks) to hardware processors in distributed robotics environments. We introduce the notion of a task variant, which supports the adaptation of software to specific hardware configurations. Task variants facilitate the trade-off of functional quality versus the requisite capacity and type of target execution processors. We formalise the problem of assigning task variants to processors as a mathematical model that incorporates typical constraints found in robotics applications; the model is a constrained form of a multi-objective, multi-dimensional, multiple-choice knapsack problem. We propose and evaluate three different solution methods to the problem: constraint programming, a constructive greedy heuristic and a local search metaheuristic. Furthermore, we demonstrate the use of task variants in a real instance of a distributed interactive multi-agent navigation system, showing that our best solution method (constraint programming) improves the system’s quality of service, as compared to the local search metaheuristic, the greedy heuristic and a randomised solution, by an average of 16%, 31% and 56% respectively.
Original languageEnglish
Pages (from-to)1-19
Number of pages19
JournalAutonomous Robots
Early online date25 Apr 2018
DOIs
Publication statusE-pub ahead of print - 25 Apr 2018

Keywords

  • Task Allocation
  • Distributed Robotics
  • Multi-objective optimisation

Fingerprint Dive into the research topics of 'Solving the Task Variant Allocation Problem in Distributed Robotics'. Together they form a unique fingerprint.

Cite this