5.2.1 环境建模方法
环境建模的主要方法有栅格法（grid）、可视图法、自由空间法（frees pace approach）和voronoi方法。
1）栅格法。
栅格法是由W.E.Howden在1968年提出的。栅格法将机器人的工作环境分解成一系列具有二值信息的网络单元，如图5.3所示。工作空间中障碍物的位置和大小一致，并且在机器人运动过程中，障碍物的位置和大小不发生变化。用尺寸相同的栅格对机器人的二维工作空间进行划分，栅格的大小以机器人自身的尺寸为准。若某个栅格范围内不含任何障碍物，则称此栅格为自由栅格；反之，称为障碍栅格。自由空间和障碍物均可表示为栅格块的集成。栅格的标识方法有两种：直角坐标法和序号法。直角坐标法以栅格左上角第一个栅格为坐标原点，水平向右为x 轴正方向，竖直向下为y轴正方向，每一个栅格区间对应于坐标轴上一个单位长度。序号法就是从栅格阵左上第一个栅格开始，按照先从左至右，后从上至下的顺序给每一个栅格一个编号。多采用四叉树或八叉树表示工作环境，并通过优化算法完成路径搜索。该方法以栅格为单位记录环境信息，栅格粒度越小，障碍物的表示越精确，但同时会占用大量的存储空间，算法的搜索范围将按指数增加。栅格的粒度太大，路径的规划会很不精确。所以栅格粒度大小的确定，是栅格法的主要问题。
利用栅格法进行任务规划的目的是建立数字地图，在地图中存储移动机器人的运动轨迹和障碍物等相关信息。机器人的运动轨迹被分解为单个的运动，这些单个的运动被记录在每个栅格上。每个栅格上的运动信息规定了机器人在这个栅格上的运动方向，在实际运用时一般只定义为八个方向：前、后、左、右、右前、右后、左后、左前。
图5.3 栅格法
2）可视图法。
如图5.4所示，在C 空间中，运动物体缩小为一点，障碍物边界相应地向外扩展为C-空间障碍。在二维的情况下，扩展的障碍物边界可由多个多边形表示，用直线将物体运动的起点S和所有C-空间障碍物的定点以及目标点C连接，并保证这些直线段不与C-空间障碍物相交，这样就形成了一张图，称之为可视图。对可视图进行搜索就可以找到最短无碰撞安全运动路径。2D空间运用A* 或Dijkstra算法搜索可视图是路径规划中最广泛的环境建模手段。
3）自由空间法。
自由空间法应用于机器人路径规划，采用预先定义的如广义锥形和凸多边形等基本形状构造自由空间，并将自由空间表示为连通图，然后通过搜索连通图来进行路径规划。该法比较灵活，起始点和目标点的改变不会造成连通图的重构，但算法的复杂程度与障碍物的多少成正比，且不是任何情况下都能获得最短路径。用栅格法建模受到了空间分辨率和内存容量的限制。而自由空间法建模解决了这一矛盾。但自由空间法的分割需构造想象边界，想象边界本身具有任意性，于是导致路径的不确定性。一些研究者给出的结构基自由空间网络法综合了栅格法和自由空间法的基本思想，通过确定环境结构信息来解决自由空间分割过程中构造想象边界的任意性问题，以消除路径的不确定性。
4）Voronoi图法。
如图5.5所示，Voronoi图又称Thiessen多边形、Dirichlet图，是在其组成点集中连接两个邻点直线的垂直平分线构成的一组连续多边形。1850年Dirichlet对2D和3D下Voronoi图进行了研究，使得该方法得到广泛的应用，尤其是在最优性不是一个关键的要求时，Voronoi图可以减少碰撞概率。但是在高维度的空间中，构造Voronoi图十分耗时，因此较高维度的空间中的规划不适用此方法。
图5.4 可视图法
图5.5 Voronoi图法
由上面的介绍可以看出不同的环境建模方法各有其优缺点，此外不同的航迹规划方法对环境模型的处理方式不同，所以选择哪种环境建模方法还要根据具体选择的算法类型来确定。