基于MAC的动态回溯算法优化

针对基于MAC的动态回溯算法在求解约束满足问题时,不仅需要大量空间存储删除解释,而且回溯机制过于复杂,对经典的删除解释及动态回溯算法的回溯机制进行优化,优化后的动态回溯算法减少了存储删除解释的空间,并可仅使用一次回溯操作返回到可能导致冲突的关键变量.在最差情况下,存储删除解释的空间复杂度由O(n2 d)改进为O(nd+n2).通过结合restart技术使优化后的动态回溯算法成为完备算法.实验结果表明,优化后的完备动态回溯算法在大部分问题求解中,整体效率明显优于标准回溯算法.

分布式约束满足问题及其在MAS任务分配中的应用

针对多智能体系统(MAS)任务分配问题中多个任务与MAS两者的分布式特征,将任务分配问题形式化为分布式约束满足问题(DCSP)进行求解,分别建立了以任务为中心和以agent为中心两种MAS任务分配模型,基于改进的DCSP分布式并行求解算法,提出了基于DCSP的MAS任务分配问题求解框架。该方法适合求解agent间通信有随机延迟以及agent间存在多约束的问题,应用实例的求解表明了其实用性与有效性。