常见的图形算法主要有以下几种:栅格法,拓扑法,自由空间法和可视法。栅格法根据特定分辨率将外部环境离散为相同大小的网格。每个栅格由状态表示,即占用状态和空闲状态,指示栅格位置是否是障碍物。路径规划算法占用一个栅格,并通过搜索自由栅格并避开障碍物来规划由多个栅格组成的路径。拓扑方法将机器人的工作环境图规划成几个小空间,并通过小空间之间的连接线建立拓扑网络结构,路径规划算法搜索拓扑网络以规划由拓扑连接线组成的路径。自由空间法将实际环境规划成两个区域,即可移动区域和不可移动障碍区域。组合连接可移动区域中每个线段的中点形成地图模型,移动机器人在其中进行路径规划。视觉方法将初始位置,障碍的各个转折点和目的地两两相连,组成多线段路径结构。通过路径规划算法,可以在这些线段上规划从起始位置到目的地的完整路径。
1