基于启发式群聚算法的机器人全局任务调度策略

A Heuristic Clustering Algorithm Based Dynamical Scheduling Strategy for Global Task Control of Robot

提出了一种基于启发式群聚算法的机器人全局任务调度策略,在任务划分阶段采用一种启发式群聚算法对随机划分的各子任务按能否使总的运行时间缩短进行各子任务间的聚合,以使各子任务粒度和相互之间的通讯量达到一种优化状态,并在此基础上对群聚之后的各子群任务采用集中式动态调度策略,在程序运行过程中实现各处理器的负载平衡,提高各处理器的利用率,缩短总的运行时间.在一个由5个DSP(digital signal processor)处理器组成的同构型松耦合MIMD(multi instruction multi data)并行处理平台上,对平面四自由度连杆机器人在关节锁定下的运动控制任务采用上述先随机划分,再聚合,最后集中式调度的方法进行了并行实时仿真实验,取得了满意的并行性能指标.

This paper presents a heuristic clustering algorithm based scheduling strategy for the global task control of robot. Subtasks partitioned occasionally are clustered according to whether or not the total running time can be reduced, so the subtask granularity and communication consumption between subtasks can be optimized. Based on this algorithm, a centralized dynamical scheduling strategy is used to schedule subtasks clustered to processors,which realizes the load balance of processors, improves the utilization of processors and reduces the total running time. This method is applied to the control of a 4 degree of freedom （DOF） robot in the presence of joint failure. The whole control task is partitioned occasionally into subtasks, then these subtasks are clustered according to the clustering algorithm. Finally all the subtasks are assigned to a simple homogeneous loosely coupled multi instruction multi data （MIMD） parallel process system with five digital signal processors （DSPs） on the basis of the centralized dynamical scheduling strategy. The real-time simulation results show that the algorithm is effective.