Reliable, Distributed Scheduling and Rescheduling for Time-Critical, Multiagent Systems
Reliable, Distributed Scheduling and Rescheduling for Time-Critical, Multiagent Systems
复制标题
DOI：
10.1109/tase.2017.2679278
复制
发表时间：
2018-04
影响因子：
5.6
通讯作者：
Amanda M. Whitbrook;Q. Meng;P. Chung
中科院分区：
文献类型：
--
作者：
Amanda M. Whitbrook;Q. Meng;P. Chung
针对启发式任务分配方法中存在的两个主要问题：陷入局部极小和静态结构。被称为性能影响（PI）的现有分布式任务分配算法被用作开发这些问题的解决方案的车辆，因为它已被证明优于国家的最先进的基于共识的捆绑算法的时间紧迫的最后期限的问题，但都是静态的和次优的倾向于陷入局部极小值。本文介绍了两个额外的模块，很容易与PI集成。第一个扩展的算法，允许动态在线重新调度在真实的时间，和第二次提高性能，通过引入一个额外的软最大动作选择过程，增加了算法的探索性。本文证明了动态重新调度模块的有效性，并表明，执行任务所需的平均时间可以减少高达9%，当使用软最大模块。此外，第二个模块还可以解决基线PI无法处理的一些问题。这些发展代表了一个显着的进步，在最先进的多智能体，时间关键task assignment.Note从业者这项工作的动机是由目前的代理任务分配算法，不使用一个中央服务器进行通信的局限性。在以前发表的工作中，当前最先进的基于共识的捆绑算法在应用于具有关键时间限制的模型任务分配问题时表现出较差的性能，通常无法分配所有任务，特别是当截止日期很紧时。性能影响（PI）算法有一个更好的成功率与这些模型的问题，但将是有缺陷的，当应用到真实的任务，因为它没有在线重新规划的机制时，新的信息变得可用。此外，它在搜索问题解决方案的方式上受到一定的限制，这意味着更有效的计划通常是可用的，但没有被发现。本文解决了这两个缺点。PI算法扩展到包括一个模块，允许重新安排在必要时，和进一步的模块引入，扩大了解决方案搜索的范围。第三个模块也已经开发出来，即使对于涉及许多代理和任务的大型任务，也能够提供稳健的计划，尽管这里没有讨论。本研究的最终目标是实现和测试一个包含所有这三个模块的PI版本。
This paper addresses two main problems with many heuristic task allocation approaches—solution trapping in local minima and static structure. The existing distributed task allocation algorithm known as performance impact (PI) is used as the vehicle for developing solutions to these problems as it has been shown to outperform the state-of-the-art consensus-based bundle algorithm for time-critical problems with tight deadlines, but is both static and suboptimal with a tendency toward trapping in local minima. This paper describes two additional modules that are easily integrated with PI. The first extends the algorithm to permit dynamic online rescheduling in real time, and the second boosts performance by introducing an additional soft-max action-selection procedure that increases the algorithm’s exploratory properties. This paper demonstrates the effectiveness of the dynamic rescheduling module and shows that the average time taken to perform tasks can be reduced by up to 9% when the soft-max module is used. In addition, the solution of some problems that baseline PI cannot handle is enabled by the second module. These developments represent a significant advance in the state of the art for multiagent, time-critical task assignment.Note to Practitioners—This work was motivated by the limitations of current agent-to-task allocation algorithms that do not use a central server for communication. In previously published work, the current state-of-the-art consensus-based bundle algorithm has demonstrated poor performance when applied to model task allocation problems with critical time limits, often failing to assign all of the tasks, especially when the deadlines are tight. The performance impact (PI) algorithm has a much better success rate with these model problems but would be flawed when applied to real missions because it has no mechanism for online replanning when new information becomes available. In addition, it is somewhat restricted in the way it searches for a problem solution, meaning that more efficient plans are often available but are not discovered. This paper tackles both of these shortcomings. The PI algorithm is extended to include a module that permits rescheduling when necessary, and a further module is introduced that widens the scope of the solution search. A third module that is able to offer robust plans, even for large-scaled missions involving many agents and tasks, has also been developed, although it is not discussed here. Implementation and testing of a version of PI that incorporates all three of these modules are the final goal of this research.