[科普中国]-网格导航

简介

网格是一种系统，该系统通过标准、开放的通用协议和接口协调分布式资源，以提供最好的服务质量。网格资源表示在网络化环境中可被共享和利用的任何能力，如计算机提供的计算服务、软件提供的应用服务、网络提供的带宽或者存储系统提供的存储空间。网格导航就是利用网格技术的优势，将其应用到导航中来。

背景从载体的运动空间的角度，可以将导航分为一维空间的导航、二维空间的导航和三维空间的导航。在航海领域，作为导航载体的船只的运动空间是一个椭球面，它是一个二维空间，因此可以认为航海领域的导航是一种二维空间的导航。航空航天领域，飞机、人造卫星、宇宙飞船等载体的运动空间是三维的，对于它们的导航是三维空间的导航。而军事领域，对导弹的导航和对潜艇的导航都属于三维空间的导航。在大众导航领域，汽车和行人的运动空间一般都是地面上的道路，道路是一种一维空间，因此对汽车和行人的导航是一维空间的导航。

导航的空间维度在很大程度上决定了对导航系统性能和导航技术的要求，不同空间维度的导航，对导航系统性能和导航技术的要求差别很大。导航最早出现在航海领域，与船只的运动空间是二维的有很大关系。在二维空间，载体运动的自由度很大（同时又局限于平面或椭球面），在载体运行的过程中对定位精度的要求不高，而且二维空间的定位相对比较容易实现。在三维空间，载体运动的自由度最大，但要求导航系统能完成载体在三维空间的定位，三维空间的定位往往比二维空间的定位难度更大。在道路网这样介于一维和二维之间的空间，载体运动的自由度受到限制，要求导航系统有精度较高的二维空间的定位，同时还需要有表示道路网的地图1。

常用方法二维空间常用的表示法有栅格法、四叉树划分法等。栅格法将空间划分为规则的正方形栅格。每个栅格对应一个通行代价，其大小根据地形特征设定。栅格的划分粒度决定着地形描述的准确程度。四叉树划分法将空间递归地划分为4个更小的正方形，直到每个正方形都包含基本一致的地形.这两种方法都不需要建立额外的连通图，直接使用4向或8向的移动方法.在机器人领域常用几何膨胀法，它将场景中的障碍物看作多边形，按照智能体的碰撞半径将其膨胀。膨胀后的顶点作为路点，路点间可视线关系决定边。