迎宾机器人机器人路径规划的传统路径规划方法:几何法 单元分解法 人工势场法 数学分析法 路径搜索算法 枚举技术

路径规划技术是智能机器人研究领域中的一个核心问题，也是机器人学中研究人工智能问题的一个重要方面，研究路径规划技术的目的是希望未来 的智能机器人能具有感知、规划和控制等高层能力：它们能从周围的环境中收 集信息，构建一个关于所在环境的模型，并且利用这个模型来规划和执行高层任务。

1)几何法

几何法是抽取环境的几何特征，把自由位姿空间映射到一个 加权图上，这样就把原问题转换成一个简单的图搜索问题。基于几何法的路径规划Z具代表性的是可视图法和自由空间法(环境分割法)。该方法适用于 环境中的障碍物是多边形的情况。先构造一个可视图 VG,VG 由一系列的 节点和节点间的连接值组成，其中节点是由各障碍多边形的D点组成的。如 果在VG 中将起点s 和目标点g 也看成特殊的D点。就可以使用动态规划法 或者A* 算法搜索一条从s 到 g 的Z短路径。由VG 法得到的路径是具有Z短 长度的，但是往往路径过于靠近障碍物而得不到路径的安全性能。环境分割 方法采用预先定义的基本形状构造自由空间，并且将这些基本单元及它们之 间的联系组成一个连通图，然后运用图搜索方法进行路径的搜索。这些方法 在某些情况下路径会距离目标太远，而且路径会因复杂多折不利于智能机器 人的行走。

2)单元分解法

Brook 和 Lozano 在1983年提出了考虑旋转物体的路径 规划单元分解法(Sub-division 算法),他们讨论的基本问题是具有两个平移自由度和一个旋转自由度的物体在多边形障碍物环境中的运动。算法的思想很 简单，把状态空间分解为许多矩形或者立方体，称为单元(cell), 其中每个单元 都标记为：①如果单元内每一点均与状态空间中的障碍物不相交，则单元为空 的；②如果单元内每一点均与状态空间中的障碍物相交，则单元为满的；③如 果单元内点既有与状态空间中的障碍物相交的，也有不相交的，则单元为混 合的。 寻找一条由空的单元组成而且包含起点和目标点的连通路径，如果这样 的路径在初始化分的状态空间中不存在，则要找出所有混合的单元，将其进一 步细分，并且将划分的结果进行标记，然后在空的单元中进行搜索，如此反复， 直至成功。如果非空的单元划分到预设的Z小值，则问题无解。该算法的一 大特征是划分空间与路径搜索是交叉进行的。使用该算法可以解决比较复杂 的问题，但是其计算量也会相应地变得很大。单元分解法研究得Z多的是栅 格解耦法，它也是目前研究Z广泛的路径规划方法。

3)人工势场法

传统的人工势场法把智能机器人在环境中的运动视为一 种在抽象的人造受力场中的运动，目标点对智能机器人产生“引力”,障碍物对智能机器人产生“斥力”,Z后通过求合力来控制智能机器人的运动。但是，由 于人工势场法把所有信息压缩为单个合力，这样就抛弃了有关障碍物分布的 有价值信息的缺陷，而且易陷入局部Z小值。

4)数学分析法

数学分析法用一个依赖位姿空间参数的不等式组来表示智能机器人躲避障碍物的要求，路径规划由起始位姿到目标位姿寻找路径时 Z小化一个标量函数而转化成数学优化问题，通过数学分析方法可以求解这 个数学优化问题。

5)路径搜索算法

给定一种智能机器人工作空间的表示方法和自由位姿 空间的表示方法后，路径规划问题就转变为从给定的表示中找到一个从起始 位姿到目标位姿的连续位姿序列的问题。

6)基于微积分的搜索技术

该技术使用优化问题的解来满足一组充分必 要条件，这种技术一般只能用于求解较简单的问题。

7)枚举技术

枚举技术搜索目标函数的域空间中的每一个节点，它们的 实现简单，但是可能需要大量的计算。动态规划是其中一种很好的方法。路 径规划技术常用的有深度优先搜索、广度优先搜索、A*搜索、反复加深搜索、Z 优搜索和Dijkstra 搜索。

8)有指导的随机搜索技术

有指导的随机搜索技术以枚举技术为基础， 但是附加了一些指导搜集过程信息。它们的应用范围很广，并且能解决十分 复杂的问题，其两个主要的子集是模拟退火算法和进化算法。