Cano José, White David R, Bordallo Alejandro, McCreesh Ciaran, Michala Anna Lito, Singer Jeremy, Nagarajan Vijay
1School of Informatics, University of Edinburgh, Edinburgh, EH8 9AB UK.
3Department of Computer Science, University College London, London, WC1E 6BT UK.
Auton Robots. 2018;42(7):1477-1495. doi: 10.1007/s10514-018-9742-5. Epub 2018 Apr 25.
We consider the problem of assigning software processes (or tasks) to hardware processors in distributed robotics environments. We introduce the notion of a , 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.
我们考虑在分布式机器人环境中将软件进程（或任务）分配到硬件处理器的问题。我们引入了一种支持软件适应特定硬件配置的概念。任务变体有助于在功能质量与目标执行处理器的所需容量和类型之间进行权衡。我们将将任务变体分配到处理器的问题形式化为一个数学模型，该模型纳入了机器人应用中常见的约束条件；该模型是多目标、多维度、多选择背包问题的一种受限形式。我们针对该问题提出并评估了三种不同的解决方法：约束编程、构造性贪婪启发式算法和局部搜索元启发式算法。此外，我们在分布式交互式多智能体导航系统的实际实例中展示了任务变体的使用，结果表明，与局部搜索元启发式算法、贪婪启发式算法和随机解决方案相比，我们最好的解决方法（约束编程）分别将系统的服务质量平均提高了16%、31%和56%。
