摘    要：分析比较了经典的全局路径规划算法，针对移动机器人运动路径规划的优化问题，将A、人工势场、栅格等多种算法的优势加以综合考虑，提出一种基于栅格的分层搜索概念：该方法采用栅格法进行建模，以分层搜索为核一心思想，外层采用A算法将复杂的图元模糊化以简化环境，内层则采用人工势场算法将具体的栅格还原以解模糊，具有一定的理论意义与应用前号。其仿真实验表明，该方法能达到较好的路径规划效率和实时性。

关键词：移动机器人；路径规划；分层搜索；全局优化

中图分类号：T，242    文献标识码：A

  移动机器人不仅在军事上有特殊的应用价值，而且在工业生产、交通运输等方面都有广泛的应用前景。路径规划是移动机器人自动化技术的重要组成部分，是机器人智能化的重要标志。按照机器人对环境信息的知晓的程度，可以将路径规划分为局部路径规划和全局路径规划两种。

  局部路径规划是在环境信息未知或者部分已知的情况下进行的路径规划，适用于动态环境，但计算量较大。局部路径规划的算法包括遗传算法、神经网络、模糊逻辑算法等。全局路径规划是在环境信息完全已知的情况下进行的路径规划，适用于静态环境，但计算效率较高。全局路径规划的算法包括可视图法、人工势场法和栅格法等。

  本文主要针对全局路径规划，首先对已有的一些经典算法进行总结和分析，然后提出基于栅格的分层搜索算法，最后是实验仿真以及结论。

  下面对移动机器人全局路径规划的常用算法做简要综述与分析。

    1)人工势场法人工势场法首先由Khatibi7:提出，其基本思想类同于物理学中场的概念。把移动机器人的运动环境抽象成人工力场，障碍物对机器人产生斥力场，目标点对机器人产生引力场。势场下降的方向就是机器人的运动方向。随着这个下降方向，机器人将有可能搜索到目标点。人工势场法的优点如下：搜索到的路径远离障碍物，路径比较光滑，计算量小，但是缺点是完备性比较差，即有时候搜索不到路径，比如当障碍物非常靠近目标点的时候，有可能出现斥力大于引力的情况，此时机器人就无法到达目标点，又例如当场中存在局部最小点时，机器人将无法脱离。

    2)栅格法根据图形建模过程的不同，栅格搜索算法分为确切栅格搜索和不确切栅格搜索。

    确切栅格搜索将机器人所处的运动环境分割成固定大小的栅格，然后将栅格分为障碍物栅格和自由栅格，分别表示有无障碍物，最后用BFS-9（广度优先搜索）、（深度优先搜索）或者启发式搜索在栅格图上搜索从出发点到目标点的****路径。该算法中，所选取的栅格大小将直接影响算法信息的存储量和计算量，同时也影响着算法搜索到路径的完备性。不确切栅格搜索与确切栅格搜索的****不同在于其栅格大小是可变的，而确切栅格搜素栅格的大小是不可变的。不确切栅格搜索算法在环境建模完成之后，同确切栅格搜索算法一样，也利用BFS，DFS或者启发式搜索技术，搜索****路径。

    A 算法一启发式搜索算法，与BFS，DFS有着自然而紧密的联系，其思想的本质在于启发，从而有效地避免了BFS，DFS方法在应用过程中的盲目性。

  栅格搜索算法构造简单，在处理障碍物的边界信息时避免了复杂的计算，而且易于存储有行到结构构成的栅格图，这些优点都为本文的研究提供了基础。

    在研究中发现，当障碍物分布比较稀疏，而且当环境中分布着一些体积比较小的障碍物时，不确切栅格搜索算法有一个比较严重的缺点，即由于这些障碍物的存在，使得栅格必须得不断的分解，以此来完成图的构建，这样就大大增加了计算的复杂度以及存储量。基于此，作者认为可以采用分层搜索的方法来解决这个问题。具体来说，是将搜索过程分为两层进行：第一层，将零星分布的障碍物先加以忽略，视其为自由结点，以相对于机器人较大的固定大小的图元建立确切栅格图，利用已有的搜索技术（BFS，DFS或者启发式搜索）搜索****路径；第二层，在第一层所确定的大栅格内搜索进出该大栅格的****路径，以实现路径搜索的完备性。当然，从算法实现上，这两层是交替进行的，并非是先完成第一层搜索，然后再进行第二层搜索。该算法实现的结构，如图l所示。

   

下面是对算法实现的具体介绍。

    1)环境建模用确切栅格法对地图进行建模，将机器人所处环境用一个大的矩形表示，同时环境通过0：1矩阵进行抽象描述，1表示为障碍物，0表示通路，矩阵的像素值根据机器人体积确定，以机器人的尺寸为最小像素。为不失一般性，地图的左上角设为机器人出发点，右下角设为机器人到达终结点。

  2)基于大栅格的路径搜索路径搜索分为两层，首先进行的一层是将搜索栅格放大，即以地图像素的倍数（例如，100倍）为一个搜索栅格，如图2所示。

   

    图中，将8x8的栅格模糊化处理成4x4的栅格。然后，在这些搜索栅格上采用A 4算法搜索最短路径，A 8算法的具体实现步骤如下：

    ①A 8算法的估价函数首先给出算法实现估价函数：

 

式中，f(n)为估价子函数，是无法预知的；g+(n)为起始点到任意节点n,的移动耗费。

  ②A算法的规划在路径规划过程中应用数据结构原理创建2个表OPEN和CLOSED，OPEN表存放所有已生成但还未考察过的结点，CLOSED表存放所有已访问过的结点。算法规划流程图，如图3所示。

  3)基于小栅格的路径搜索在每一个大栅格内的搜索算法采用人工势场法，称之为小栅格化处理法。人工势场的源在所进人大栅格的人口，即在每次A 4算法循环中从表头取出的结点n，然后从n点扩散开来，计算大栅格内每一个小栅格到n点的距离，从这些结点中取计算结果最小的结点作为这个大栅格的出口。

  具体执行过程如下：

  ①将起点人栈，设置起点c值为o。

  ②出栈获得栈首元素，比较该元素上下左右元素，以右元素right为例，若有：

    则重新设置该元素G值为(G+1)。将right人栈，并设置right的前向属性。

  ③当出栈元素超出低像素栅格范围或栈列为空则继续向下执行，否则重复②。

  ④若下一低像素搜索栅格为右元素，则在栅格内右边搜索(G+H)值最小的高像素栅格，设其为栅格内终点。

  ⑤从终点出发，依从前向属性找到起点，并将经过路径作为设置路径。如前向属性值，则表示路径寻找失败。

    在本算法中，虽然②和③步骤分开罗列，但在具体执行过程中并非是先进行②再执行⑧，而是②和③交替进行。即以②中选出合适的大栅格后，马上转移到③，确定能从③走出去，然后再转到②步骤，再确定下一个大栅格，如此交替进行，直到找到最终目标结点为止。

  4)算法推广分层搜索的实质是先将复杂的图元模糊化以达到简化环境的目的，再将具体的栅格解模糊以还原算法处理的过程。实际执行中正如上文所描述的那样尽管各步骤分开罗列，但后台的处理是交替进行的。

    正因为这样，显然不局限于仅仅分两层来进行处理。理论上讲，只要你的硬件条件允许，就可以分4层、8层、16层等来进行不断地模糊化、解模糊。在实际中，已做到了8层，随着研究的不断深入，还会进行更多的尝试。

    由于A算法是机器人路径规划中比较经典与普遍采用的方法，因此将基于栅格的分层搜索算法与经典的A算法在计算效率以及搜索时间上做一比较。

    1)计算效率在输入规模为n；n栅格情况下，A算法的最坏情况复杂度为D(n2)，平均情况为0(n)。

    在同样输入规模情况下，采用分层栅格搜索算法，令分层栅格比为m：1，其最坏复杂度平均复杂度为。

    经过参数具体化验证，尽管分层搜索算法在最坏情况下并不占优，但在平均情况下，分层搜索算法在计算效率上具有明显优势。

    2)搜索时间借助Java平台进行了规模地图仿真以验证搜索时间，分别设置栅格规模生成地图并将分层搜索算法与A 4算法的实时性进行对比，结果，见表1。

 

    从表l可以看出，随着栅格规模的逐渐增大，分层搜索算法在搜索时间上的优势较之A 3算法愈来愈明显。

    因此，分层搜索算法特别适合于各类移动机器人比赛、网格化移动机器人避障以及机器人智能化指标测试等场合。

  本文采用栅格法进行建模，以分层搜索为核心思想，结合A 4以及人工势场算法，将多种算法的思想融合到一起，以达到发挥各种算法优越性的目的。

  栅格法使得建模过程清晰并且便于后续过程的数据处理；A 8算法按照启发式搜索的原则，相对于DFS和BFS降低了搜索空间的阶数，提高了搜索效率；人工势场法使得在小栅格内的搜索效率大大提高。

  此外，采用分层搜索算法的额外好处是，不需要处理一些无用的数据，而只需集中精为于那些A-算法搜索到的部分，这就大大缩短了搜索时间，提高了搜索效率，使得路径规划算法得以优化。

    总体来说，基于栅格的分层搜索算法构造简单且容易执行，对于上位机的运算要求不高，在地形条件不是十分复杂的情况下可获得相当高的搜索效率，对于移动机器人的路径规划来讲不失为一种理想的优化方案。