人工智能技术在机器人运动规划中的应用
1 引言
机器人运动规划(Motion Planning of Robot)问题主要研究机器人在三维工作空间中如何构建一条从起点到终点，或者从起始位姿(位置+姿态)到终止位姿的无碰、高效的运动序列。机器人的运动规划问题不但是机器人学的基础问题，而且，关于机器人运动规划的研究已经扩展到所有刚体、非刚体在空间中的运动问题，在计算机动画、数字化演员、智能装配、蛋白质及基因分子运动研究等领域得到了充分的应用。
然而，机器人运动规划问题却是机器人科学及人工智能领域中一个十分具有挑战性的问题。长期以来，人们为了解决高自由度的机器人在运动规划过程中指数爆炸问题做了很多工作，提出了一系列运动规划算法，应用了现代人工智能技术的一些最新进展。现在的研究工作，使得自由度在7~100之间的单机器人及多机器人的运动规划问题得到了较好的解决，并且具有了实时应用的可能。但是对于具有非完整性约束的运动体、柔性运动体、可自配置的机器人，以及极高自由度(>100)的几何体等的运动规划现在还没有得到较好的解决。
在机器人运动规划中，许多AI技术，如产生式系统、神经网络、Case系统、模糊逻辑、Agent系统等等，都得到了广泛的应用。
2 机器人规划问题简介
机器人的运动规划包括两类：机器人整体的运动规划和涉及到机器人各个关节角的运动规划。机器人整体的运动规划把机器人看作是一个整体，对其实行规划，即在一个充满障碍的环境里，给定移动机器人的初始位置以及期望的最终位置，试确定是否存在躲过障碍的运动路径，使从给定位置安全到达期望的最终位置。机器人整体的运动规划一般又称为路径规划，由于机器人整体看作是一个点或者是一个固定的几何体，自由度比较少，因此路径规划问题相对比较简单。传统的机器人运动规划算法已经能较好地解决路径规划问题。
涉及到机器人各个关节角的运动规划则不再把机器人视作某个点或者固定的几何体，而看作是一个由若干杆件组成的动力学链。由于每多一个杆件，机器人的自由度就增加1~3个(由相应的关节角结构而定)，所以当机器人杆件比较多时。这种类型的运动规划要比路径规划困难得多。本文主要讨论这种类型的运动规划问题。
然而这两种类型的运动规划问题由于Lozano-Perez在20世纪80年代初的工作而结合在一起了。通过引入“位姿空间”(Configuration Space或者C-Space)的概念，后一种类型的机器人运动规划问题可以转换成C-Space中的路径规划问题。机器人的位姿(Configuration)是由机器人的基座坐标、方位角以及各个关节角共同组成的一个向量。机器人的位姿惟一确定了机器人在工作空间中的位置和形态。由位姿向量组成的空间就是C-Space。把工作空间映射到C-Space后，C-Space中分成两个区域：自由空间和禁止空间。C-Space中的自由空间是指机器人不会与障碍物相撞的位姿集合，禁止空间是相撞的位姿集合。引入C-Space以及自由空间的概念以后，机器人的运动规划问题转换成如何在C-Space的自由空间中找出一条从起始位姿点到目标位姿点的无碰撞路径。但由于在实际应用中，C-Space的维数往往比较高，如何避免高维数带来的指数爆炸问题就成了机器人运动规划的关键。而且C-Space又有特殊的拓扑性质(如关节角00 与3600 等价，使得C-Space有了“粘连”的情况)，进行运动规划中要考虑C-Space的拓扑性质以防止遗漏可能解。
映射到C-Space后，机器人的运动规划表示为
求解这个优化问题得到一个顺序点列，连接这些点得到目标路径。
所谓满足动力学约束条件是指求得的路径易于机器人控制系统进行跟踪，即可以较容易地根据求得的顺序点列生成相应的机器人各个驱动电机的控制数据，并且这些控制数据在机器人动力系统的允许范围之内。动力学约束条件包括：关节角的调节范围，角速度、角加速度限制，速度、加速度限制等等。动力学约束条件有两种类型：完整性约束和非完整性约束。
求解上述的机器人运动规划一般有两种思路：
(1)全局规划。它大致分成两个步骤：完成从工作空间到C-Space的部分或者全部的映射；在C-Space中进行路径搜索。
①难点在于C-Space的维数一般很高，因而转换时间复杂度很大。另外，从工作空间映射到C-Space。要作大量的碰撞检测，所以设计高效的碰撞检测算法是运动规划的一个研究热点。②难点同样在于C-Space的高维数带来的运算复杂性，如何设计启发式搜索算法是运动规划算法的关键之一。
(2)局部规划。它分成三个步骤：完成从工作空间到C-Space的映射；在C-Space中构造一个势场函数；根据势场函数引导C-Space中的路径从高势能到低势能运动，直到到达目标位姿为止，同时避开局部最小点。
3 全局搜索策略中的AI技术
3.1 基于传统搜索技术的机器人运动规划算法
传统的全局搜索策略应用了Al中的经典搜索算法。最早提出的一个运动规划算法就是，把C-Space离散成栅格，在搜索可能路径时使用了A*搜索算法。这个算法能够求得最优解，而且是完全的，不会遗漏掉可能解。然而由于C-Space维数高时，??算法会由于复杂度过大而失效，因此，这种运动规划算法一般只适用于维数较低的情形。
3.2 基于产生式系统的运动规划方法
对于多自由度机器人运动规划问题就是，直接在C-Space中搜索需要在高维的C空间进行大量计算，因而无法实用。一种可行的办法是构造一个产生式系统，建立规则库，把原来的整个运动规划问题，包括从开始、避撞到抓取的整个过程，分成若干个子目标进行规划。
一般而言，可以对多自由度机械臂定义如下行为：
(1)导向目标。该行为用来控制杆件的方向角，以指向一个给定的目标。
(2)移向目标。该行为用来将机械手的末端移向目标点。
(3)躲避障碍。该行为用来避免机械手臂和障碍物相碰撞。
(4)跟踪边沿。用来控制机械手的一个臂沿着障碍物的边沿运动。
(5)收缩手臂。用来控制机械手的一个臂收缩，以使机械手的末端从狭窄的通道中出来。
(6)伸展手臂。该行为用来控制机械手的一个臂伸展，以指向目标点。
(7)达到目标。用来移动机械手的末端以达到目标，如果目标位于最后两个杆件形成的子空间中。
所有上面描述的行为都可通过机械手的姿态空间中的规划算法来实现。对于以上行为建立规则库如下：
- 规则1 如果(由杆件k-1和k组成的子机械手能够指向目标)则(k-1和k导向目标)
- 规则2 如果(机械手的末端前面没有障碍物或远离障碍物)则(k-1和k移向目标)
- 规则3 如果(杆件i与障碍物相碰撞)则(杆件i躲避障碍)
- 规则4 如果(k-1和k不能导向目标)则(k和k跟踪边沿)
- 规则5 如果(k-1和k不能移向目标；并且杆件l，…，i-1都己收缩)则(收缩杆件i)
- 规则6 如果(末端和目标点之间障碍物较少，并且杆件i+l，…，i十2，k都已伸展)则(伸展杆件i)
- 规则7 如果(存在到达目标的路径)则(达到目标)
应用这些规则，可把本来难以解决的C-Space中的路径搜索问题分解成若干子问题，而每个子问题的复杂度较原问题大大降低，因而可以使用传统的搜索技术如A*算法来实现。
3.3 基于Case系统的运动规划方法
在机器人运动规划中引入Case系统的基于两个考虑:(1)由于机器人运动规划器通常要在同样的工作空间中反复运算，因此过去的规划结果可以用来指导新的运动规划。(2)运动规划算法非常之多，每一种都有其适用范围，如果能在路径规划器应用多种规划算法，并且在学习阶段和案例库中把各种算法的性能记录下来，就可以发现每种算法的适用场合，并在将来的规划中使用最适合的算法。
运动规划中的Case系统要解决的两个关键问题是案例索引的建立和解答的修改。对于前一个问题，机器人运动规划良好的问题定义使得案例索引的建立比较方便。机器人运动规划的每一次查询，输入是起始位姿和终止位姿。如果工作空间不变的话，这两个参数构成的索引就足够了。如果工作空间有变化，则要把工作空间的信息也加人到案例索引中去，一个常用的方法是使用分解模型，使用四/八叉树给工作空间进行建模。四/八叉树的编码可以与起始位姿和终止位姿结合在一起成为案例索引。案例的解答就是这个成功的案例下求得的路径的某种形式的编码。
当根据给定的输入，检索到相应的解答后，需要对解答进行修改以得到合适的结果。解答的修改有一系列的方法，其中比较直观和简单的一种是不断地进行检测—修改—检测直到找到一个答案为止。一开始使用原来解答的路径，如果这条路径合法，则这条路径就是所求得的答案。如果不合法，则先求出在原来解答路径上哪些部分越出了自由空间，然后再对这部分重新进行一次规划。重新规划时可以应用案例，也可以直接用搜索算法来求解。对修改以后的路径再一次进行检测，若不合法，则再次进行修改。最后求得的新的解答作为新案例存入案例库。
4 局部搜索策略中的AI技术
在机器人运动规划中，除上述的全局策略外，还常用到局部搜索策略，其中最典型的是人工势场法。人工势场法关键是在C-Space中构造一个势场函数。势场函数有两个基本特征：
(1)离目标越近，势能越低，目标点对势能函数的影响是局部的；
(2)离障碍物越近，势能函数急剧增加，但离开障碍物一定距离后，势能函数基本不变，即障碍物的信息对势能函数的影响(惩罚函数)是局部的。
构造出势场函数后，运动规划器使机器人的位姿在C-Space中沿势场函数下降的方向运动。人工势场法的两个难点是势场函数的快速计算和势场函数局部最小点的处理。这两个方面，应用神经网络技术都可以得到较好的解决。
势场函数的快速计算主要涉及到计算点到各个障碍物的距离，从而得到障碍物的罚函数。一种可能的方案是在路径规划学习阶段构建一个BP前向神经网络。如图即表达了这样一个网络的可能结构。图1中底层的两个节点分别表示给定路径点的坐标x，y，中间层的每个节点相应于障碍物的一条边的不等式限制条件，底层和中间层的连接权系数就等于不等式中x，y前面的系数，中间层每个节点的阈值等于相应不等式中的常数项。中间层到顶层的连接权为1，表示各条边对罚函数的影响相同。经过一段时间的训练后，障碍物的信息在神经网络中得到很好的表达，而且由于神经网络运算内在的并行性，可以用来作为势场函数的快速生成算法。
图1 一个点到一个障碍物的罚函数的神经网络
势能函数局部极小点的存在是影响人工势能法应用的最严重的问题之一。当位姿点运动到局部极小点时，无法再使势场函数减小，从而使势场法失效。神经网络中的模拟退火算法被提出可用来解决局部极小点的问题。由于模拟退火策略以一定的几率跳出局部极小点，应用模拟退火方法可使位姿点有可能跳出势场函数的局部极值点，达到全局极小点(目标)。
5 基于采样的搜索策略及改进
上面所述的各种搜索算法，不管是各种全局搜索方法，还是局部搜索方法，都需要完成工作空间到C-Space的转换，当C-Space维数比较高(>7)时，这种转换的算法复杂度是极其惊人的，使得上述算法都无法满足应用要求。
基于采样的搜索策略的提出，给高维度的机器人运动规划开辟了一条新路。基于采样的搜索策略的基本思想是不给出C-Space的全部描述，而改为在C-Space中按照一定的策略选取一定数量的采样点。采样点可能在自由空间内部，也可能在禁止区域。保留在自由空间内的采样点作为路标(Milestone)，然后找出各个路标与附近路标之间的连通关系(检测连接两个路标的线段是否都落在自由空间中)，构成一个无向图(Roadmap )。对每次查询，规划器首先试图把起始和终止位姿点连到某个附近的路标上，然后在这无向图上的两个路标之间找出一条最短路径。当然，这种方法是不完全的，存在着遗漏掉可能解的可能。然而可以证明，当采样点数量增加时，遗漏掉解的概率以指数速度趋向于0。
基于随机采样的运动规划算法具有一些其他算法没有的优点。首先，它不用预先把工作空间映射到C-Space，大大减少了计算量，因此能很好地解决高维度C-Space中的运动规划问题。其次，算法具有良好的可扩展性。当精度要求提高，或者系统运算能力提高时，可以简单地通过增加采样点来提高系统性能。因此，我们现在的研究方向是以基于采样的运动规划算法为主。
由于采样策略的不同，基于采样的运动规划算法有很多种。最基本的是Roadmap算法。图2给出了Roadmap算法的一个示意图。在这个算法中，采样点的选择是均匀采样。算法在一般情况下性能良好。但当C-Space的自由空间中有“狭窄通道”时，由于采样点位于通道内或者采样点之间的连线通过通道的可能性较小，因此算法遗失可能解的几率大大增加。而且，均匀采样往往使得许多采样点的计算成为冗余。为了解决这些问题，在基本Roadmap算法的基础上提出了各种算法。例如Gildardo Sanchez和Jean-Claude Latombe提出的SBL算法，T.Simeon, J.P Laumond和Nissoux提出的基于可视性的采样算法，V.Boor，M.H.Overmans，和A.F.van den Stappen提出的基于高斯采样(Gaussian sampling)的算法，等等。这些算法在一定程度上使得基本Roadmap算法的缺点得以克服。
图2 Roadmap算法示意图
然而，这些改进的算法只适用于各自的一定场合，对于一般情形，它们的效率并不是很高。而且，在采样过程中，它们没有充分利用已有的采样点的信息来指导新的采样过程，因而采样策略并不是十分高效，有许多采样点是冗余的。我们现在的研究方向是把人工智能领域的一些成果引入到采样策略中。比如基于规则库的采样策略，将以前的采样结果保留下来，在进行新的采样时根据规则库选择最有“价值”的采样区域进行采样。另外，尽管基于采样的运动规划算法族已经大大减少了作碰撞检测的数量，碰撞检测还是占了整个规划运算量的95%以上。所以我们考虑结合应用神经网络和Case系统来减少每次碰撞检测的运算时间，从而提高整个规划器的性能。通过利用神经网络的并行性来加快碰撞检测的速度，而Case系统则把以前的碰撞检测成功或者失败的案例存放到案例库中。由于相近的两个位姿点，它们很可能同时在碰撞检测中通过或者失败。通过检索案例库，我们可以在作碰撞检测前知道检测通过的大致概率，从而作出相应的决策。而且，案例库还提供了C-Space的一些特殊信息，如上述“狭窄通道”的存在，等等挖掘案例库的这些蕴藏信息，相信会给运动规划算法提供新的思路。