协同任务规划中基于约束满足的资源冲突检测与消解

资源的有限性以及活动的并发执行导致协同任务中极易发生资源冲突,需施加时间约束以限定活动执行时间从而避免冲突的出现。在分析多机协同任务的基础上,将任务过程转化为带有多容量资源的任务调度模型,根据模型时间特性给出资源冲突定义及其判断准则。提出基于最小冲突集的资源冲突检测算法,其中利用时间交叠关系的特点,将资源冲突的检测与消解问题转化为连通图中闭团的检查与消除问题。进而从约束满足的角度研究了基于最小承诺策略的消解算法。实验结果表明方法的有效性。

Constraint satisfaction based resource conflicts detection and resolution in collaborative mission planning

The finitude of resources and parallel execution of actions will result in resource conflicts in collaborative missions.The paper introduces a technique for solving this problem,which restricts the execution time of actions by adding temporal constraints on actions.Firstly,the mission plan is transformed into scheduling model with multi-capacitated resources,and the definition of resource conflicts and rules for conflict judgement are given based on the model’s temporal properties.Then a resource conflict detection algorithm is presented based on the minimal critical sets,which makes use of the properties of overlaps between temporal bounds,and the resource conflicts are detected and resolved as particular cliques in connected graph.From the perspective of constraint satisfaction,the least-commitment strategy based conflicts resolution algorithm is also developed.Experimental results indicate the effectiveness of the approach.