Path planning of mine robot based on a novel heuristic algorithm with regular hexagon grids
-
摘要: 在传统正方形栅格地图中,存在机器人遇到障碍物时沿对角线方向移动易与障碍物碰撞,其绕障和平稳性等方面的能力较差且实时探测过程中每步消耗的时间无法唯一确定等问题。针对上述问题,提出了以正六边形栅格化的工作环境为基础,采用改进的启发式路径搜索算法对多个并行移动的矿井机器人进行路径优化的方法。从绕障转角、绕障能力及最优路径3个方面,对单个机器人在正方形和正六边形栅格建模环境中的运动性能进行比较分析,结果表明:就单个机器人来说,正六边形栅格地图下的路径长度代价小于正方形栅格地图的路径长度代价;从单个机器人的路径规划来看,正六边形栅格地图更有利于获得最短路径,从而得出正六边形栅格比传统正方形栅格更适合于机器人工作环境的建模。针对多个协同操作的机器人并行移动的路径规划问题,在正六边形栅格化的工作空间建模基础上,采用改进的启发式路径搜索算法对多个机器人的路径进行优化:采用改进的启发式估计函数规划多个协同操作的机器人路径,该函数决定了当前机器人所在位置周围所有相邻栅格中哪一个即将被机器人遍历。依据机器人已经遍历的栅格数和候选栅格与该机器人目标栅格之间的变形曼哈顿距离,该启发式估计函数可评估出相邻栅格的适应度值。仿真结果表明:正六边形栅格地图在路径总长及算法运行时间上均比正方形栅格地图减少了10%以上,且有效避免了机器人与静态障碍物之间及机器人之间发生碰撞,提高了机器人的安全性;随着机器人数量的增多,改进的启发式路径搜索算法对正六边形栅格地图的机器人路径和算法运行时间的优化作用更加明显。Abstract: In the traditional square grid map, when robot encounters an obstacle, it is easy to collide with the obstacle when moving along diagonal direction, has poor capability in obstacle-avoiding and stability, and time consumed in each step during real-time detection cannot be uniquely determined. In view of the above problems, based on working environment of regular hexagon grid, a path optimization method for multiple parallel mobile mine robots by using improved heuristic path search algorithm is proposed. In this paper, a comparative analysis of single robot in square and regular hexagon grid modeling environment is carried out from three aspects of obstacle-avoiding angle, obstacle-avoiding ability and optimal path. The results show that for a single robot, path length cost under regular hexagon grid map is less than that in square grid map, and from path planning of a single robot, regular hexagon grid map is more conducive to obtain the shortest path, so it is concluded that regular hexagon grid is more suitable for robot working environment modeling than traditional square grid. Aiming at path planning problem of parallel movement of multiple robots in collaborative operation, an improved heuristic path search algorithm is used to optimize path of multiple robots on the basis of working environment of regular hexagon grid:Multiple collaborative robot paths are planned by use of improved heuristic estimation function, which determines the one of all adjacent grids around the current robot location to be traversed by the robot. The improved heuristic estimation function is used to plan the path of multiple cooperative robots. According to the number of grids traversed by robot and deformed Manhattan distance between candidate grid and target grid of the robot, the heuristic estimation function can evaluate fitness value of adjacent grids. The simulation results show that total path length and running time of the algorithm are reduced by more than 10% compared with the square grid map, collision between the robot and static obstacles and among the robots is effectively avoided, and safety of the robot is improved. With increase of the number of robots, the improved heuristic path search algorithm has more obvious optimization effect on robot path and algorithm running time under the regular hexagon grid map.
点击查看大图
计量
- 文章访问数: 92
- HTML全文浏览量: 10
- PDF下载量: 11
- 被引次数: 0