Distributed Constraint Satisfaction Problem and its Application for Task Reallocation in Multi-agent Systems

分布式约束满足问题及其在多智能体任务重分配中的应用摘 要许多关于过程控制、规划和调度的实际问题都可以用约束满足问题来描述和求解[1]。虽然约束满足模型适用性很强，它的求解算法也可以相当有效地解决这些NP难题的优化问题，但是这种传统的问题求解的方法与分布式的方法相比，具有计算复杂、稳定性差等缺点。因此，对分布式约束满足问题的研究成为了多智能体系统中的一个重要方向。在多智能体系统中，任务重新分配就是将一个被分解成一系列子任务的全局任务分配到不同智能体的过程。任务的组织结构可以很大程度地影响问题求解的过程，因此任务分配本身就是一个优化问题。任务的重新分配是与多智能体系统中的自组织问题密切相关的。为了更有效地解决因此，本文提出了一种适应性更强的算法，使一个组织结构中的智能体能够动态地协商，而不是由某一个智能体来完成任务分配的工作，通过这种方法找到满意的分配方案。我们首先用求解问题的过程中所需要传递的远程消息的数量作为衡量一个组织结构好坏的的标准。然后我们提出一个更全面的衡量问题求解代价的评价标准，这个标准既考虑到了远程消息的数量，同时也考虑了任务的重新分配导致本地任务复杂性的变化。仿真结果证实了这种动态任务调整的有效性