机器人 ×∂ √
文章编号222
一种基于任务的机器人全局并行算法研究及实现
沈悦明陈启军
同济大学信息与控制工程系上海
Ξ
摘 要本文提出了一种基于任务的机器人全局并行算法结合主从结构的⁄并行处理平台将机器人控将划分好的子任务统一用工作池方式实现全局制中的运动学!动力学!控制律等基本计算任务分别进行任务划分
采用流水线及集中式动态调度策略在一个由个⁄≥°处理器组成的同构型松耦合⁄并行处理平的动态调度
取得了满意的并行性能指标台上对平面机器人进行了并行实时仿真实验
关键词全局并行算法流水线动态调度工作池中图分类号 ×° 文献标识码
ΡΕΣΕΑΡΧΗΑΝΔΙΜΠΛΕΜΕΝΤΑΤΙΟΝΟΦΑΤΑΣΚ2ΒΑΣΕΔΓΛΟΒΑΛ
ΠΑΡΑΛΛΕΛΑΛΓΟΡΙΤΗΜΦΟΡΡΟΒΟΤΧΟΝΤΡΟΛ
≥∞≠∏2≤∞±2∏
(ΔεπαρτμεντοφΙνφορματιονανδΧοντρολΕνγινεερινγ,ΤονγϕιΥνιϖερσιτψ,Σηανγηαι,Χηινα)
τραχτ:×2≤⁄∏2 Αβσ
∏∏∏⁄∏√√∏∏∏∏∏⁄∏√⁄≥°•∏∏2 Κεψωορδσ:
1 引言(Ιντροδυχτιον)
高性能微处理器的发展为并行算法的实施提供
近年来国内外学者对并行算法在机器了物质基础
人控制中的应用作了大量研究取得了很多成果
2∞∏递推公式的逆动力提出了基于
学并行算法≈等研究了正运动学及逆运动学的并行算法并在个×∏组成的系统上实现≈等提出了基于⁄ƒ≥深度优先隐式启发搜索方法及⁄ƒ≥深度优先最小代价启发搜索方法的静态调度策略并用在机器人轨迹规划!运动学!逆动力学等的计算上采用个≤处理器实现了仿真≈∏在一个由个×∏组成的立方体结构并行平台上采用
Ξ
静态与动态调度策略结合的方式进行了的机器人并行仿真≈但这些研究大多集中在解决一个局部问题的并行算法上如运动学!动力学!或某种控制算法等的并行化这些算法只在其特定领域内具有可调性很难实现全局的功能扩展≈机器人技术的不断发展要求在机器人性能提高的同时其控制程序易于编写且能适应功能扩展及控制系统规模的调整这就需要采用基于任务的全局并行控制算法本文在一个由个×≥≤浮点⁄≥°处理器
组成的全连同构型松耦合⁄多指令流多数据流并行处理平台上采用流水线及集中式动态调度策略实现了基于任务的全局并行计算并对平面机器人进行了实时仿真实验结果证明了本文理论和
基金项目国家自然科学基金资助项目收稿日期
机 器 人年月
方法的有效性2 算法描述(Δεσχριπτιονοφτηεαλγοριτημ)
机器人控制通常需要进行轨迹规划!正运动学!逆运动学!逆动力学!控制律等基本任务的计算若是仿真还需要正动力学的计算基本任务之间的关系如图
不同于以往在局部对具体问题进行并行化基于任务的全局并行算法充分考虑了基本任务之间的并行性将基本任务划分为更小的子任务并统一对这些子任务进行全局调度算法可充分利用处理器资源
且具有功能扩展容易!代码重用性好等优点以下结合主从结构的⁄并行处理平台具体介绍任务的划分和调度
图 基本任务关系图
ƒ ∏
21 任务划分
任务划分的目的是根据并行处理平台的结构将规模为Ν的总计算工作划分为若干任务,以便按某种调度策略将任务映射到Π个处理机上.对于
⁄并行处理平台而言,处理器间通信的开销相对
计算开销大很多,因此应在充分考虑任务并行程度的同时尽量减小通信开销,以缩短总任务完成时间;主从结构的并行平台适合运行集中式调度策略,为了减小调度开销,需要减少任务数量.基于以上原因,应采用较大粒度的任务划分方式.显然基本任务内部存在着并行性,可根据其具体的计算量再次划分子任务,一般若机器人有Κ个关节就可将该基本子任务划分为Κ个子任务.所有基本任务都进行划分后需要建立子任务关系表以记录子任务之间的通信联系.
在这种两级任务划分方法中,基本任务模块之间相对独立,当某一模块需要变动(如改变轨迹规划方式!采用更好的控制算法等)时,其它模块的代码可基本不变(只需改变子任务关系表);各个基本任务模块划分出的子任务组成全局的子任务拓扑图,由一定的调度策略统一分配给各个处理器.这样既
满足了基于任务的功能扩展又充分利用了处理器资源,且代码的重用性和可移植性好.
2.2 任务调度
任务调度是指将划分好的任务按一定的策略映射到Π个处理机上[].任务调度有静态和动态两种,前者的任务在运行前就指定要运行的处理机并在其生命期内永久驻留在该处理机上;后者的任务只有在执行过程中才确定在哪一个处理机上运行以及在处理机间如何移动,以得到更高的处理效率,它又分为集中式和非集中式.
静态调度算法相对简单,但由于不能准确估计每个任务的运行时间及任务间的通信量而使系统的并行处理效率不高;动态调度算法虽然可以合理利用资源,但会引起更多的系统开销.对于静态任务调度,每一子任务均与某一固定的处理器建立了联系,每个处理器上运行的程序都有很大的差别.当系统的功能需要扩展或处理器数目需调整时,必须对每一处理器重新进行编程,费时费力且代码的重用性和可移植性差.而对于动态任务调度,子任务只有在程序运行的过程中才根据具体情况分配给某一处理
器,绝大部分处理器的程序代码都是相同的,代码的重用性和可移植性好且当系统功能扩展或处理器数
目调整时代码的改动极小(只需更新相应的子任务或子任务关系表).
集中式动态调度策略实现起来比分布式动态调度策略简单很多,系统开销也较少,适用于具有主从结构且规模较小的并行处理平台,采用集中式工作池[]方法加以实现,其原理如图所示.每一任务根据其所处的运行过程都有等待!准备好!运行!完成等四种状态,任务队列负责存储处于准备好状态的任务.主处理器上运行调度程序,负责管理所有的任务.主处理器持有要执行的任务集,任务由主处理器从任务队列中取出并发送给从处理器,当从处理器空闲(完成了一个任务的计算)时它就通知主处理器并请求另一个任务,同时主处理器根据任务关系表更新各个任务的状态并将处于准备好状态的任务放入任务队列中.对于一个计算,当下面两项都满足时计算就会停止:
#任务队列为空;
#每个从处理器已经请求了另一任务,而又没
有任何新任务变为准备好状态.
工作池技术可容易地用于简单的分治问题,也可用于那些任务很不相同!大小不同的问题.一般最好先分配较大或最复杂的任务,如果在计算中分配
第卷第期沈悦明等 一种基于任务的机器人全局并行算法研究及实现
大任务较晚,完成小任务的从处理器会空闲,以等待大任务的完成.这特别适合调度按以上介绍的方法划分出的机器人控制子任务,因为按此方法进行任务划分时是在充分考虑并行性的同时尽量减小任务间通信量,子任务的大小相差较大,如动力学计算基本任务模块中的子任务计算量比其余模块的子任务大很多.
本文将集中式工作池作了以下改进:
()在每个从处理器上均保留一份所有任务的
备份,主处理器向从处理器发送任务时只需发送相应的任务号,可有效减少通信量;
()主处理器在每一任务完成时均记录下其所
在的从处理器号,在发送执行某一任务所需的数据到从处理器时就只需发送该任务的所有未在此从处理器上运行过的父任务产生的数据,减少了通信量.
图 集中式工作池
ƒ ≤
3 算法实现(Ιμπλεμεντατιονοφτηεαλγο2
ριτημ)
3.1 实验平台介绍
本系统的硬件平台由德国≥°≤∞公司开发的⁄≥°2≤×系列型和型⁄≥°板组成≈
含个≤⁄≥°
含个≤⁄≥°×的×≥≤系列是专为并行处理而进行优化的处理
器⁄≥°浮点运算速度可达到ƒ°≥
有个高速并行通信端口通信速率可达它非常适合于一些大运算量的有实时要求的场合它们利用并行通讯口进行通信构成全连接同构型松耦合
∏2∏2∏⁄∏∏∏⁄多处理器系统32 任务划分
本文以一平面两关节机器人为实时仿真对象,采用滑模变结构控制律使其以一定的速度跟踪一给
定圆,需要进行轨迹规划!逆运动学!滑模变结构控制律!正动力学等的计算.
机器人动力学方程为
Η(θ)&θ+η(θ,¾θ)+Γ(θ)−ϑΤ(θ)Φε=Σ()
正动力学问题是已知Σ,Φε,θ,¾θ,要计算&θ,再得到θ¾,θ.令β=η(θ,¾θ)+Γ(θ)−ϑΤ(θ)Φε
()称β为偏置力矩.则可得到
Η(θ)&θ=Σ−β
()
对于这个方程组我们只要求得Η(θ)和β,就可求出θ&.因而正动力学的计算可分为以下几个步骤:).求取偏置力矩β;
由动力学方程可知,当θ&时,Σβ,故可通过逆动力学(用牛顿2欧拉迭代公式)求出β.
).求取惯性矩阵Η(θ);
由动力学方程,如果令Φε,Γ(θ),¾θ,以及θ&εϕ[,,,,,,]Τ再利用逆动力学我们就可以得到Η(θ)的第ϕ列向量.
).解线性方程组得θ&,并利用数值积分得出¾θ和θ.
变结构控制律的计算公式为
⊥Σβ−[⊥υ
+κ(σ)],无控制信号平滑ι=
⊥β−[υ⊥
+κ(σ/Υ)],有控制信号平滑()
其中Κθ.
⊥υ&θδιφι,κ(Β)⊥υΒ(Φ
Γ),ΥΚκ以及.σθιΚθι.针对本并行处理系统,根据上一节的划分原则,
将总的计算任务划分为如下子任务,任务拓扑图如图.
图 任务拓扑图
ƒ ×
各子任务的计算量列于表
Τ:利用梯形速度规划法进行轨迹规划的计算,
机 器 人年月
求出Σ和Σ#
δδ;
Τ:进行逆运动学计算,求出θδ!¾θδ和&θδ;
Τ:运用上述方法计算Η(θ)的第一个列向量;
Τ:计算Η(θ)的第二个列向量;Τ:计算偏置力矩β;
Τ:根据公式计算第一个关节的控制力矩Σ;Τ:根据公式计算第二个关节的控制力矩Σ;Τ:计算Η(θ);
Τ:根据公式解方程组得&θ,并利用数值积分
得出θ¾和θ,再进行正运动学计算,求出机械手实际末端位置Σ.
表1 计算量
Ταβλε1 Χομπυτατιονλοαδ
任务
乘法
加法
×××××××××
33 任务分配
从以上的任务划分可看出子任务×和×的计
算量相对较少且并行程度不高而其余子任务中大部分都要依赖×和×的计算结果
又由于整个实时仿真系统的帧时间由≥×∞处理器上的时钟定时中
断产生
因此将实验室现有的由五个⁄≥°处理器构成的并行处理系统天然的分为两级结构第一级由2
与其它处理器组成流水线结构≈负责进行轨迹规划及机器人逆运动学的计算
其余四个处理器负责逆运动学!
控制律!正动力学!正运动学的计算工作它们又组成具有主从关系第二级采用集中调度的动态负载平衡策略并用工作池方式实现其中2
处理器为主处理器负责运行调度程序!⁄!为从处理器
负责具体的计算工作331 流水线
将要处理的计算任务分为两大部分,第一部分由子任务Τ!Τ组成(Τ.),其余子任务为第二部分
(Τ.).将个处理器划分为两组执行设备,其中
处理器为设备一(Β)负责处理Τ.,其余处理
器组成设备二(Β)负责处理Τ..流水线时序如图
所示,图中的数字表示所执行计算任务的序号.2
处理器通过硬件时钟定时产生中断,周期为Σ..从τ开始启动流水线,第一个计算任务首先从Β进入流水线开始运行Τ.,经过时间Σ后完成.在τ时刻将第一个计算任务送入Β去执行Τ.,同时
第二个计算任务进入Β,此时流水线已装满,Β在执行Τ.,Β在执行Τ.,二者同时进行.到τ时刻就可输出第一个计算任务的结果,如此类推,以后每隔一个采样周期Σ输出一个计算任务的结果.
图 流水线时序
ƒ ≥∏
332 集中式动态调度
本文运用≤语言对节划分的任务用工作池
方式实现了集中式动态调度将各子任务都以函数的形式表示
在每个从处理器上都保留这些函数的备份并建立一个指向函数的指针数组用以存储这些函数的入口地址主处理器需要某个从处理器执行子任务时只需传递子任务号从处理器在数组中找到相应的任务函数入口地址就可执行该子任务
主调度程序
主处理器负责运行主调度程序循环检测从处理器的状态当从处理器空闲时主调度程序就按一定的策略给从处理器分配任务伪代码如下
∏3不满足退出条件则循环3
3循环检测第零到二个从处理器3
√3从处理器空闲则3
∏3读任务队列3 3若任务队列非空则3
√
3从处理器的状态设为忙3 第卷第期沈悦明等 一种基于任务的机器人全局并行算法研究及实现
3循环3
3向从处理器送运行子任务所需的数据3
3向从处理器送待运行的子任
3检测是否有主处理器
务号3
3从处理器有发送任务结束
来的消息3
3有消息且为数据消息则读
数据3
¬3有消息且为送子任务号的
消息则3
3更新任务状态3∏∏∏3更新任务队列3∏3读任务队列33若任务队列非空则3
√3从处理器的状态设为忙33向从处理器送运行子任务2所需的数据3
3向从处理器送待运行的子任务
则执行子任务3
3无消息3
333 仿真结果
本文分别采用个⁄≥°!个⁄≥°和个⁄≥°进行了两关节机器人以一定速度跟踪给定圆的实时仿真实验跟踪误差如图单个⁄≥°的计算时间如图个⁄≥°的计算时间如图个⁄≥°的计算时间如图由于采用了动态负载平衡策略
⁄≥°系统的程序相对⁄≥°系统只作了微小的改
号3
√3从处理器的状态设为空闲3
动实现起来极为方便从表表中相关定义见附录
的运行结果比较中可看出采用个⁄≥°包含三个
从处理器时各项性能指标都较为满意而采用个
⁄≥°包含两个从处理器时的性能指标就差了很多
从调度程序
因为子任务是根据⁄≥°系统进行划分的任务粒度较大适当减小任务粒度就可缩小两者性能指标的差距
从调度程序在从处理器上运行负责接收主处理器发送的消息并转向相应的操作伪代码如下
图 仿真结果
ƒ ∞¬∏
机 器 人年月
∏∏⁄ƒ≥∏≈∞∞∞×≥≤19
≈∏≠°∏∏∏∏2
22∏∏2∏≈∏≥≥°≈≤
≈⁄&×°
≈°∞∞∞≥∏∞≥∞.≈≤∏°∏√
表2 运行结果比较
Ταβλε2 Χομπαρισονοφτηεεξπεριμεντρεσυλτσ
⁄≥°
⁄≥°
单个计算时间×并行计算时间×
加速度≥效率∞
ƒ
并行处理技术≈南京南京大学出版社≈张德富编著
4 结论(Χονχλυσιον)
本文研究了基于任务的机器人全局并行算法运用该算法在由个⁄≥°构成的⁄并行处理平
台上对两关节机器人进行了实时仿真实验并取得了满意的效果通过实验可得如下结论
基于任务的全局并行算法实现了规划与控
陆鑫达等译并行程序设计≈北≈美威尔金森美艾伦著
机械工业出版社京
≈≥°≤∞∏≥°≤∞
附录1(Αππενδιξ1)
并行算法性能指标定义如下:
()加速度:ΣΠΤ/ΤΠ()效率:ΕΠΣΠ/Π()⁄∏提出的函数:
制的集成和并行化功能扩展能力较强是开放式!高性能机器人控制系统的新探索
动态调度策略根据程序运行过程中的具体
ΦπΣπ/(Π.Τπ)Επ/ΤπΕπ.Σπ/Τ
情况调度任务可以合理利用处理机资源提高并行处理系统性能指标将其运用于机器人并行控制是一种有益的尝试
集中式动态调度策略实现较方便!系统规
其中Τ表示串行算法在单处理器上的执行时
间,ΤΠ表示并行算法在Π个处理器上的执行时间,
Π为处理器数目.显然,Σπ[Π,Επ[,Ε,Σ.
模可调!代码可移植性好特别适合处理器较少的机器人并行控制系统
参考文献 (Ρεφερενχεσ)
≈≠∏2
√≈≤°ƒ≤≈≤4
≈ƒƒ⁄×∏22
≈13
≈≥∏
如果以ΣΠ度量算法的并行性对计算时间的改
进程度,通常Π越大,ΣΠ也越大,但处理器利用效率ΕΠ不一定很高.因而Δ.ϑ.Κυχκ提出以Φπ为性能指标,通常Φπ越大越好.
沈悦明(2),男,工学硕士.研究领域:机器人控制与
作者简介:
智能控制.
陈启军(2),男,工学博士,教授.研究领域:机器人控
制,智能控制.
(上接第页)
≈方海军等基于≤总线的自主式仿人型机器人控制系统≈
参考文献 (Ρεφερενχεσ)
≈周旭升等一种蛇形机器人的研制≈机器人24
≈陈丽等蛇形机器人机构设计与运动机理的研究≈机器人
24
≈张建军等基于现场总线的分布式智能机器人感知系统研究
≈机器人24
≈≤×⁄2
≥∞2ƒ¬2×≤⁄.≤2≥2
机器人24
作者简介
男中科院沈阳自动化所硕士研究生研 汪 洋2
蛇形机器人控制系统究领域
男中科院沈阳自动化所研究员研究领 李 斌2
仿生机器人域
女中科院沈阳自动化所博士研究生研 陈 丽2
蛇形机器人机构设计与运动控制算法究领域
因篇幅问题不能全部显示，请点此查看更多更全内容