第七章-机器人规划

东南大学远程教育,机器人技术,第十三讲,主讲教师：王兴松,机器人规划Robotplanning,7.1机器人规划的作用与任务7.2积木世界的机器人规划7.3STRIPS规划系统7.4具有学习能力的规划系统7.5基于专家系统的机器人规划7.6太空构件装配顺序分层规划系统7.7机器人轨迹规划,Robotplanning,7.1机器人规划的作用和任务1.规划的作用与问题分解途径（1）规划的概念及作用概念：在执行一个问题求解程序中的任何一步之前，计算该程序几步的过程，是一个行动过程的描述。蕴涵排序。步骤含糊。具有分层结构。,Robotplanning,7.1机器人规划的作用和任务1.规划的作用与问题分解途径（1）规划的概念及作用作用：缺乏规划可能导致不是最佳的问题求解。规划可用来监控求解过程。如发射火箭。,Robotplanning,7.1机器人规划的作用和任务1.规划的作用与问题分解途径（2）问题分解的途径：途径一：只考虑状态中可能变化了的那些部分。途径二：把单一的问题分割成为几个子问题。,Robotplanning,7.1机器人规划的作用和任务1.规划的作用与问题分解途径（3）域的预测和规划的修正：产生一个有希望成功的规划。规划失败，从现有状态从新开始规划。非期望结果并不使余下部分失败。使规划失败的影响限制在局部内。记录规划执行步骤及理由，便于回溯。,Robotplanning,7.1机器人规划的作用和任务2.机器人规划系统的任务与方法（1）机器人规划系统的任务：根据最有效的启发信息，选择应用于下一步的最好规则。应用所选取的规则来计算生成的新状态。对所求得的解答进行检验。检验空端，并舍弃。检验殆正确的解答，并应用具体技术使之完全正确。,Robotplanning,7.1机器人规划的作用和任务2.机器人规划系统的任务与方法（2）机器人规划系统的方法：选择和应用规则：方法一，对每个动作都叙述起所引起的状态表示的每一个变化。另用某些语句来描述所有其它维持不变的事物。优点：只需一个机理消解。缺点：若问题状态复杂，则需很多的公理条数。,Robotplanning,7.1机器人规划的作用和任务2.机器人规划系统的任务与方法（2）机器人规划系统的方法：方法一例：谓词集合描述状态：如图动作影响到的状态：用框架公理规则描述不受操作符影响的状态：,Robotplanning,7.1机器人规划的作用和任务2.机器人规划系统的任务与方法（2）机器人规划系统的方法：选择和应用规则：关于框架公理使用初始表，删除表和添加表。优点：减少提供给操作符的信息。操作后不必推演所有信息。便于回溯。如图：,Robotplanning,7.1机器人规划的作用和任务2.机器人规划系统的任务与方法（2）机器人规划系统的方法：检验解答与空端：求得能将初始状态变换为目标状态的操作符序列，即得解。空端，从它无法到达目标的端点。正向推理及反向推理。,Robotplanning,7.1机器人规划的作用和任务2.机器人规划系统的任务与方法（2）机器人规划系统的方法：修正殆正确解的各种方法：检查求得的状态，并把它与期望目标加以比较。注意有关出错的知识，然后加以直接修正。不修正，不完全确定地让差别保留到最后的可能时刻。,Robotplanning,7.2积木世界的机器人规划1.积木世界的机器人问题（1）积木世界：几个有标记的一样大小的积木。（2）机器人动作：unstack(a,b)stack(a,b)pickup(a)putdown(a)状态描述：ON(a,b)ONTABLE（a）CLEAR(a)HOLDING(a)HANDEMPTY,Robotplanning,7.2积木世界的机器人规划1.积木世界的机器人问题（2）机器人例：初始状态：CLEAR（B）CLEAR（C）ON（C，A）ONTABLE（A）ONTABLE（B）HANDEMPTY目标状态：ON（B，C）ON（A，B）,Robotplanning,7.2积木世界的机器人规划2.用F规则求解规划序列（1）先决条件（2）删除表（3）添加表例move(x,y,z)先决条件CLEAR（x），CLEAR（z），ON（x,y）删除表ON(x,y),CLEAR(z)添加表ON(x,z),CLEAR(y),Robotplanning,7.2积木世界的机器人规划2.用F规则求解规划序列表示图4的所有状态空间,Robotplanning,7.3STRIPS规划系统1.STRIPS系统的组成（1）世界模型。为一阶谓词演算公式。（2）操作符（F规则）。包括先决条件，删除表，添加表。（3）操作方法。应用状态空间表示和中间结局分析。,Robotplanning,7.3STRIPS规划系统2.STRIPS系统规划过程例7.1,要求机器人到邻室去取回一个箱子。,Robotplanning,7.3STRIPS规划系统提供两个操作符：gothru(d,r1,r2)pushthru(b,d,r1,r2)这个问题的差别表：,Robotplanning,7.3STRIPS规划系统初始状态M0：INROOM（ROBOT，R1）INROOM（VOX1，R2）CONNECTS（D1，R1，R2）目标状态G0：INROOM（ROBOT，R1）INROOM（BOX1，R1）采用中间结局分析方法来逐步求解经gothru(C1，R1，R2)中间状态M1：INROOM（ROBOT，R2）CONNECTS（D1，R1，R2）经pushthru中间状态M2：M2=G0,Robotplanning,7.3STRIPS规划系统例7.1的搜索图及与或图,Robotplanning,7.3STRIPS规划系统3.含有多重解答的规划例7.2,要求机器人将不同区域的三个箱子移到同一区域内。,Robotplanning,7.3STRIPS规划系统3.含有多重解答的规划操作符：push(k,m,n)goto(m,n)初始模型M0：ATR(a),AT(BOX1,b),AT(BOX2,c),AT(BOX3,d)目标模型G0：(BOX1，x）（BOX2，x）（BOX3，x）,Robotplanning,7.3STRIPS规划系统采用消解反演和中间结局分析。解1：goto(a,c),push(BOX2,c,b),goto(b,d),push(BOX3,d,b),Robotplanning,7.3STRIPS规划系统3.含有多重解答的规划解2：goto(a,b),push(BOX1,b,c),goto(c,d),push(BOX3,d,c)解3：goto(a,b),push(BOX1,b,d),goto(d,c),push(BOX2,c,d),Robotplanning,7.4具有学习能力的规划系统PULP系统普渡大学，19761979，S.Tangwongsan&傅京孙一种管理式（监督式）学习系统。优点：输入的目标语句表示为英语语句。应用辅助物体改善了系统对物体的操作能力。,Robotplanning,7.4具有学习能力的规划系统1.PULP系统的结构与操作方式字典：英语词汇的集合。模型：部分包括模型世界内物体现有状态的事实。过程：集中了预先准备好的知识。方块：集中了LISP程序。SENEF程序：用语义网络来表示知识。操作如图。,Robotplanning,7.4具有学习能力的规划系统2.PULP的世界模型和规划结果。一个具体任务下的世界模型。,Robotplanning,7.4具有学习能力的规划系统2.PULP的世界模型和规划结果。对STRIPS，ABSTRIPS和PULP三个系统的规划速度进行比较。,Robotplanning,7.5基于专家系统的机器人规划1.系统结构和规划机理采用基于规则的专家系统。（1）系统结构和规划机理。五部分知识库。控制策略。推理机。知识获取。解释与说明。一定的工具：支援软件和硬件。,Robotplanning,7.5基于专家系统的机器人规划1.系统结构和规划机理（2）任务级机器人规划三要素建立模型。对物体和机器人的几何，运动，物理描述。任务说明。说明各物体所期望的空间关系。程序综合。,Robotplanning,7.5基于专家系统的机器人规划2.ROPES机器人规划系统。RobotPlanningExpertSystems(1)系统简化框图。,Robotplanning,7.5基于专家系统的机器人规划2.ROPES机器人规划系统。(2)世界模型,Robotplanning,7.5基于专家系统的机器人规划2.ROPES机器人规划系统。(3)规划与执行结果共使用15条规则。规则14：表示机器人用小车把重型零件（object）从某工段areaRb的位置(Xb,Yb)推移(push)到其目的位置(Xg,Yg)工段的位置所应具备的条件和必须遵循的操作。,Robotplanning,7.5基于专家系统的机器人规划2.ROPES机器人规划系统。(3)规划与执行结果例，物体在第1工段，运送至第4工段第8工作台。应具备的条件：4条已知零件位置。at(Object,Rb,(Xb,Yb)已知目标工段。at4(Goal,Rg,(Xg,Yg)零件两位置关系。diff(Rb,R4),diff(R4,Rb),diff(Rg,R1),diff(R1,Rb),diff(Rb,Rg),diff(R4,R1),(connects(D2,R1,Rb)；connects(D1,Rb,R1),Robotplanning,7.5基于专家系统的机器人规划2.ROPES机器人规划系统。(3)规划与执行结果例，接上(connects(D2,Rg,R1)；connects(D2,R1,Rg),(connects(D3,Rb,R4)；connects(D3,R4,Rb),(connects(D3,R4,Rg)；connects(D3,Rg,R4),(neighbors(Rb,R4)；neighbors(Rg,R4)已知推零件过程中所经过的两个门道的位置。at6(D1,Rb,(X2,Y2),at6(D1,R1,(X3,Y3),at6(D2,R1,(X4,Y4),at6(D2,Rg,(X5,Y5),Robotplanning,7.5基于专家系统的机器人规划2.ROPES机器人规划系统。(3)规划与执行结果动作序列push(Rb,(Xb,Yb),(Rb,(X2,Y2),pushthru(D1,(Rb,(X2,Y2),(R1,(X3,Y3),push(R1,(X3,Y3),(R1,(X4,Y4),pushthru(D2,(R1,(X4,Y4),(Rg,(X5,Y5),push(Rg,(X5,Y5),(Rg,(Xg,Yg),transfer(Object,cart1,Goal),Robotplanning,7.5基于专家系统的机器人规划2.ROPES机器人规划系统。(3)规划与执行结果一个具体任务：处在工段3的机器人把工段2的重型零件part10搬移至工段5的工作台5上。用户输入数据：area3,a,b,area6,_,_,area2,0,2,area5,4.5,1,part10,table5.,Robotplanning,7.5基于专家系统的机器人规划2.ROPES机器人规划系统。(3)规划与执行结果一个具体任务：作业任务的图解。,Robotplanning,7.5基于专家系统的机器人规划2.ROPES机器人规划系统。(3)规划与执行结果本系统最大可能解为8个。例：原处于工段1的机器人，使用工段6的小车把工段1内的一个重型零件送至工段6的某处。,Robotplanning,7.5基于专家系统的机器人规划2.ROPES机器人规划系统。(4)比较表7.2比较4个系统的复杂性,Robotplanning,7.5基于专家系统的机器人规划2.ROPES机器人规划系统。(4)比较比较4个系统的规划速度。,Robotplanning,7.5基于专家系统的机器人规划2.ROPES机器人规划系统。(4)比较表7.3仔细地比较了PULP1和ROPES的规划速度,Robotplanning,7.5基于专家系统的机器人规划2.ROPES机器人规划系统。(5)结论与讨论更好的规划性能和更快的规划速度。可输出某任务的所有解。将概率，可信度，模糊理论运用于不确定任务。C-PROLOG语言简单，有效。操作符数目增大时，规划时间增加得很少。,Robotplanning,7.6太空构件装配顺序分层规划系统1.太空构件装配及其分层顺序规划（1）拆开顺序规划器的可行性准则a,几何可行性的定义：任何支梁如果在下一个执行装配操作点，机器人臂和末端装置可达的，则称为支梁几何可行性。凸形外壳的定义：如果一组顶点处在所建立的三维容积空间的端点上，那么这组顶点就是顶点集合的凸形外壳。,7.6太空构件装配顺序分层规划系统1.太空构件装配及其分层顺序规划（1）拆开顺序规划器的可行性准则几何可行性的一般定义：3D（N，S），CH（N）N：结点数S：支梁数3D：结点和支梁组成的三维空间CH：结点的凸形外壳检验所有处于凸形外壳上的支梁，并放入活动表(activelist)A-。,具有：结束。,Robotplanning,Robotplanning,7.6太空构件装配顺序分层规划系统1.太空构件装配及其分层顺序规划（1）拆开顺序规划器的可行性准则b,结构可行性的定义：如果移动一个支梁导致最大稳定和刚性结构，则该支梁具有满足结构可行性条件的特性。三维空间结构的两个层次：支梁和结点相互连接，形成完整的上层结构。形成互连刚性子结构的支梁和结点集合，建立完整结构。,Robotplanning,7.6太空构件装配顺序分层规划系统1.太空构件装配及其分层顺序规划（1）拆开顺序规划器的可行性准则C，连接关系，稳定性和可行性准则结构容积单元（SVE）：StructuralVolumeElement是支梁和结点的集合，它们以规定的方法互连，形成结构上刚性和稳定的状态。,Robotplanning,7.6太空构件装配顺序分层规划系统1.太空构件装配及其分层顺序规划（1）拆开顺序规划器的可行性准则非结构容积单元（NSVE）：是不形成结构单元的支梁和结点的任务集合。,Robotplanning,7.6太空构件装配顺序分层规划系统1.太空构件装配及其分层顺序规划（1）拆开顺序规划器的可行性准则SVE和NSEV结构提供了空间构件装配的分层表示。SVE的3种互连关系：点连接0（1）阶线连接0（2）阶面连接,Robotplanning,7.6太空构件装配顺序分层规划系统1.太空构件装配及其分层顺序规划（2）规划规则的表示与搜索状态和规划表示分层表示。底层部分包括支梁和结点。高层部分包括SVE和NSEV。由上述两部分组成的关系图表示三维装配约束。,Robotplanning,7.6太空构件装配顺序分层规划系统1.太空构件装配及其分层顺序规划（2）规划规则的表示与搜索分层搜索策略搜索空间限制在可能导致可行解的范围内。分层方法由两层拆装组成。第一层应用SVE约束决定SVE单元的顺序。SVE被定序后，就开始第二层拆装规划。由保证子目标最优解，从而保证全局最优。,Robotplanning,7.6太空构件装配顺序分层规划系统1.太空构件装配及其分层顺序规划（2）规划规则的表示与搜索第一层SVE级算法：开始。SVE确定3D空间的所有SVE单元。SVEvalid确定所有有效的SVE单元。SVEminface确定含有最少面数的SVE单元。如果SVEminface=1SVEnextSVEminface,否则SVEease确定从SVEminface拆装的最容易SVE单元。SVEnextSVEease3DREMOVE(SVEease)DISASSEMBLEsve(3D),Robotplanning,7.6太空构件装配顺序分层规划系统1.太空构件装配及其分层顺序规划（2）规划规则的表示与搜索第一层SVE级确定顺序之准则：移动应当影响最少的面连接数。移动必须是最容易的。中间不稳定态尽可能少。移动必须是有效的。前后两个SVE必须相连。,Robotplanning,7.6太空构件装配顺序分层规划系统1.太空构件装配及其分层顺序规划（2）规划规则的表示与搜索第二层支梁级：选择具有最小总代价的有效支梁。确定几何可行的支梁。运用启发代价函数。例：图7.26四面体6，5，4，3，2，1五面体7，3，2，1，6，4，8，5,Robotplanning,7.6太空构件装配顺序分层规划系统2.三维结构装配顺序规划示例例7.33D(10,24),7个SVE单元，3个五面体。步骤：13，（7，19，18）（24，12，17），（11，23，16）（22，10，15），（20，8，14，9）,Robotplanning,7.6太空构件装配顺序分层规划系统2.三维结构装配顺序规划示例例7.43D（31，102）,Robotplanning,7.7机器人轨迹规划轨迹：机械手的位移，速度和加速度。轨迹规划：由任务要求，计算出预算的运动轨迹。轨迹规划器：简化了编程手续。1.轨迹规划应考虑的问题机器人规划方式的分类,Robotplanning,7.7机器人轨迹规划1.轨迹规划应考虑的问题机械手常用的两种轨迹规划方法：方法一，给出插值点上一组显式约束。方法二，给出运动路径的解析式。轨迹规划可在关节空间或直角空间中。规划器的任务：解变换方程，运动学反解和插值运算。,Robotplanning,7.7机器人轨迹规划2.关节轨迹的插值计算（1）三次多项式插值四个约束条件：由上确定了一个三次多项式：,Robotplanning,7.7机器人轨迹规划2.关节轨迹的插值计算（1）三次多项式插值关节速度和加速度：关于四个系数的线性方程：,Robotplanning,7.7机器人轨迹规划2.关节轨迹的插值计算（1）三次多项式插值解得四个系数的表达式：,Robotplanning,7.7机器人轨迹规划2.关节轨迹的插值计算（2）过路径点的三次多项式插值将速度约束条件(7.2)变为：重新求得三项式的系数：,Robotplanning,7.7机器人轨迹规划2.关节轨迹的插值计算（2）过路径点的三次多项式插值确定路径点上关节速度的三种方法：根据工具坐标在直角坐标空间中的瞬时线速度、和角速度来确定。采用适当的启发式方法，有控制系统自动地选择。要保证每个路径点上的加速度连续。,Robotplanning,7.7机器人轨迹规划2.关节轨迹的插值计算（3）高阶多项式插值五次多项式：6个约束条件：,Robotplanning,7.7机器人轨迹规划2.关节轨迹的插值计算（3）高阶多项式插值其解为：,Robotplanning,7.7机器人轨迹规划2.关节轨迹的插值计算（4）用抛物线过渡的线性插值将线性函数与两段抛物线函数平滑地衔接在一起形成一段轨迹。,Robotplanning,7.7机器人轨迹规划2.关节轨迹的插值计算（4）用抛物线过渡的线性插值：tb处的速度：tb处的关节角度：过渡域内加速度令t=2th，由式13，14得t：所要求的运动持续时间,Robotplanning,7.7机器人轨迹规划2.关节轨迹的插值计算（4）用抛物线过渡的线性插值任意给定，和，选择相应的和，得到路径曲线。需满足条件：,Robotplanning,7.7机器人轨迹规划2.关节轨迹的插值计算（5）过路径点的用抛物线过渡的线性插值j,k,l：连续的三个路径点。：k点过渡域的持续时间。：j,k之间线性域的持续时间。：连接j和k的路径段的全部持续时间。：j,k点之间线性域的速度。：j点过渡域的加速度。,Robotplanning,7.7机器人轨迹规划2.关节轨迹的插值计算（5）过路径点的用抛物线过渡的线性插值任意给定，和，可得。对于内部路径点：,Robotplanning,7.7机器人轨迹规划2.关节轨迹的插值计算（5）过路径点的用抛物线过渡的线性插值对于第一个路径段：从而求得，进而求得和：,Robotplanning,7.7机器人轨迹规划2.关节轨迹的插值计算（5）过路径点的用抛物线过渡的线性插值对于最后一个路径段：根据上式便可求得：,Robotplanning,7.7机器人轨迹规划3.笛卡儿路径轨迹规划（1）物体对象的描述在给出物体的几何图形及固接坐标后，其相对于参考系的位姿则可用与它固接的坐标系来表示。,Robotplanning,7.7机器人轨迹规划3.笛卡儿路径轨迹规划（2）作业的描述作业的运动可用手部位姿结点序列来规定。每个结点是由工具坐标系相对于作业坐标系的齐次变换来描述。相应的关节变量可用运动学反解计算。,Robotplanning,7.7机器人轨迹规划3.笛卡儿路径轨迹规划（3）两个结点之间的“直线”运动如图7.37所示，从到的运动可表示为，从到：工具坐标系T相对于末端连杆系6的变换。：分别为两个结点和相对于坐标系B的齐次坐标。,Robotplanning,7.7机器人轨迹规划3.笛卡儿路径轨迹规划（3）两个结点之间的“直线”运动从到的运动可由“驱动变换”D()来表示：D()：归一化时间的函数。t：自运动开始算起的时间。T：走过该轨迹的总时间。,Robotplanning,7.7机器人轨迹规划3.笛卡儿路径轨迹规划（3）两个结点之间的“直线”运动在，t=0，则=0，D(0)是44的单位矩阵，则式26与式23相同。在，t=T，则=1，有得,Robotplanning,7.7机器人轨迹规划3.笛卡儿路径轨迹规划（3）两个结点之间的“直线”运动,Robotplanning,7.7机器人轨迹规划3.笛卡儿路径轨迹规划（3）两个结点之间的“直线”