https://www.emerald.com/insight/content/doi/10.1108/IR-04-2020-0073/full/html

多机器人/多智能体 动态环境 任务分配 决策 动态任务调度策略

该文章主要是想对目前state of the art多机器人动态任务调度策略做一个全面的评价，注意定语挺多的，里面的方法也较多为近几年的智能调度那些算法。衡量方法主要考虑到了应用场景、限制、目标方程以及对不确定性处理方式。

Introduction

多机器人协作系统是最近的研究热点。多机器人任务执行效率高，能够执行复杂的任务。
在多机器人系统领域主要有两种协作模式：中心式和分布式。在中心式中，一个服务器控制了系统中的主要参数并且对任务进行分配。这种系统依赖一个中心服务器确保任务成功分配，但是当中心崩溃时系统将瘫痪，这就意味着系统要有可靠的信息交换系统。在分布式中，每个机器人个体独立安排自己任务。这种系统中，每个个体观察视野中周围个体，并且计算自身对任务的竞争力来做独立任务决策。分布式系统很适合大规模机器人在弱联网环境中运行。尽管中心式的系统需要严格可靠的通讯网络，但是它能够保证任务分配的一致性。而分布式系统很难达到任务分配一致性的要求。MRS系统要求每个机器人都有任务执行能力以及协作性coordination，其中协作方式对MRS成功任务分配和执行是核心问题。
多机器人任务分配（MRTA）可分成8类。也可以用iTax分成四类。


但是目前任务分配主流的两种策略是auction-based以及optimization-based（拍卖机制以及最优化理论），而最优化理论的任务分配在复杂约束下能做到更快更好。
文章研究了近些年发展的动态不确定环境下复杂约束的任务分配策略。文章以MRS在实际应用为评价指标，包括算法应用场景、限制约束条件、目标函数、算法时间以及对不确定性应对策略。文章中算法范围为2010~2020年发表的，只选取了顶会和顶级期刊上关于多机器人任务固化、调度或者最优化的文章。

Multi-robot task allocation problem definition

这部分是多机器人任务规划定义，很简洁明了，不再打公式了。
下表是多机器人问题中限制条件，动态环境下多机器人任务分配问题主要包含资源和时间的限制。

常见的目标函数有：最小化路径，最小化等待时间，最大化任务完成率：

Dynamic task allocation strategies

多机器人任务分配目标就是在满足约束条件前提下将任务分配达到最小化损失函数。主要问题就在是实际生产环境里约束条件是不规则并且多样的。下面展示了四种主要的多机器人动态环境任务分配策略。

Market-based task allocation

这种策略模仿了市场交易，其主要流程如图所示：

拍卖机器人向团队中的其他机器人发布任务信息并要求出价。 每一个机器人在团队中根据其执行任务的能力进行出价，然后将出价转发给拍卖机器人。 拍卖机器人将任务分配给报价最少的机器人。

Optimization-based task allocation

现实世界中的多机器人系统具有多个不确定约束。 因此对动态环境任务分配问题进行数学建模是艰巨的。然而，使用启发式算法建模能够给动态环境任务分配问题提供连续最优解。比如粒子群优化（PSO）、蚁群算法（ACO）及其各种变种。 动态任务分配问题的目标函数是：最小化任务完成时间、最小化机器人行程距离、最小化电池资源利用、最大化任务分配率和任务完成率。下表展示了目前的算法

Behaviour-based task allocation

基于行为的动态任务分配是一种独特的策略。 该策略使用多个按比例分配的解决方案来解决单个应用程序中发生的不同问题实例。 在策略中的单个应用程序可以是是任何形式的数学模型，启发式算法或优化函数。这个策略受不同的问题而具体来定义。

Clustered task allocation

集群任务分配策略将相似或附近的任务分组为集群，然后将集群分配给机器人，而不是单个任务分配。 这种策略降低了机器人团队的平均运行距离。集群任务分配策略的关键是确定每个集群的最优任务数

Discussion

本文详细回顾了最先进的MMR动态任务分配策略。 尽管文献中的每一项任务分配技术都经过了分析和模拟验证，但是他们缺乏实际实验来验证。