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

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

中图分类号：t，242    文献标识码：a

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

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

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

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

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

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

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

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

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

    在研究中发现，当障碍物分布比较稀疏，而且当环境中分布着一些体积比较小的障碍物时，不确切栅格搜索算法有一个比较严重的缺点，即由于这些障碍物的存在，使得栅格必须得不断的分解，以此来完成图的构建，这样就大大增加了计算的复杂度以及存储量。基于此，作者认为可以采用分层搜索的方法来解决这个问题。具体来说，是将搜索过程分为两层进行：第一层，将零星分布的障碍物先加以忽略，视其为自由