《多智能体任务规划》2022博士论文

多智能体系统（MAS）已经在不同的环境和框架中得到了利用，因此已经成功地应用于许多应用中，以实现不同的目标。事实证明，与建立一个具有任务可能需要的所有能力的单一智能体相比，多智能体系统更具有成本效益。此外，成本并不是采用MASs的唯一驱动因素，例如，安全是另一个重要方面。在恶劣或极端的环境中部署一组智能体，而不是一个人类团队，可以减少安全风险。此外，与单一智能体的解决方案相比，MAS提供了更多的灵活性和稳健性。灵活性来自于将资源分成不同的小组，而稳健性则来自于一个智能体的关键错误不一定会危及任务的成功这一事实。请注意，一个任务可能有许多不同的约束和方面，然而，最微不足道的情况是只有一个智能体和一个任务。

这些类型的任务可以由人类操作员计划，监督任务，而不需要自动计划器。另一方面，更复杂的任务，即利用大量的异质智能体和任务，以及约束条件（优先权、同步性等），对人类操作员来说并不是那么简单的计划。这些复杂的问题给制定一个可行的计划带来了巨大的挑战，更不用说是最好的计划了。此外，机器人系统中可用的计算平台的功率增加，允许利用并行任务执行。更具体地说，它允许在传感、计算、运动和操纵任务中可能的并行性。这反过来又有一个好处，即允许创建更复杂的机器人任务。然而，它的代价是增加了优化任务分配问题的复杂性。为了规避这些问题，需要一个自动规划器。这些类型的问题是出了名的难解决，而且可能需要太长时间才能找到一个最佳计划。因此，优化和产生计划所需的计算时间之间的平衡变得非常重要。

本论文涉及两个特殊的多机器人任务分配（MRTA）问题配置的正式定义，用于表示多智能体任务规划问题。更具体地说，本论文的贡献可以归纳为三类：

首先，这项工作提出了一个模型，以结构化的方式表示不同的问题配置，也被称为任务。这个模型被称为TAMER，它还允许以更系统的方式增加新的维度，与以前提出的MRTA分类法相比，扩大了可以描述的问题的数量。

其次，本论文以混合整数线性问题的形式，定义并提供了两种不同的问题形式，即扩展的彩色旅行推销员问题（ECTSP）。这些模型在CPLEX优化工具中对选定的问题实例进行了实施和验证。此外，还设计了一个解决这些复杂问题的次优方法。提出的解决方案是基于遗传算法（GA）的方法，并与最先进的（和实践中的）求解器，即CPLEX获得的解决方案进行比较。与经典方法相比，使用GA进行规划的优势在于它具有更好的可扩展性，使其能够找到大规模问题的解决方案。尽管这些解决方案在大多数情况下是次优的，但它们比其他精确方法获得的速度要快得多。另一个优势体现在 "随时停止 "选项的形式上。在时间紧迫的操作中，重要的是可以选择停止规划过程，并在需要时使用次优的解决方案。

最后，这项工作涉及到MRTA问题的一个维度，这个维度在过去没有引起很多研究的关注。特别是，包括多任务（MT）机器人在内的问题配置被忽视了。为了克服上述问题，首先，对可能实现任务并行的情况进行了定义。此外，还介绍了物理和虚拟任务之间的区别以及它们在并行任务执行方面的相互关系。我们提出并比较了两个模型。第一个模型以ILP的形式表达，并在CPLEX优化工具中实现。另一个被定义为限制性规划（CP）模型并在CP优化工具中实现。两种求解器都在一系列的问题实例上进行了评估。