前言：
当前我们对“六边形最短路径问题”都比较重视，同学们都想要了解一些“六边形最短路径问题”的相关知识。那么小编同时在网络上收集了一些对于“六边形最短路径问题””的相关内容，希望大家能喜欢，各位老铁们快快来了解一下吧！【能源人都在看，点击右上角加'关注'】
可阅读全文
原文发表在《工矿自动化》2020年第8期，欢迎品读。
在研究矿井机器人的路径规划时，通常将其运动区域抽象简化成若干个形状规则、大小相同的栅格，以栅格的特征信息描述实际地形。在传统正方形栅格地图中，存在机器人遇到障碍物时沿对角线方向移动易与障碍物碰撞，其绕障和平稳性等方面的能力较差且实时探测过程中每步消耗的时间无法唯一确定等问题。针对上述问题，提出了以正六边形栅格化的工作环境为基础，结合改进的启发式路径搜索算法对多个并行移动的机器人进行路径优化的方法。从绕障转角、绕障能力以及最优路径3个方面，对单个机器人在正方形和正六边形栅格地图中进行比较分析。在正六边形栅格地图中，遇到静态障碍物转弯时，转角和绕行时间都减小，提高了运动的安全性、平稳性及绕障能力，且最优路径长度有所减小。正六边形栅格地图与改进的启发式路径搜索算法的结合，实现了对多个并行移动的矿井机器人路径的优化，达到了个机器人路径最短的优化目标，同时避免了机器人之间及机器人与静态障碍物之间发生碰撞，提高了机器人的安全性；随着机器人数量增多，改进的启发式路径搜索算法对正六边形栅格地图下的机器人路径和算法运行时间的优化作用更加明显。
引用格式
王鹤，陈静，滕瑛瑶.基于新型栅格启发式算法的矿井机器人的路径规划[J].工矿自动化,2020,46(8):64-69.
WANG He,CHEN Jing,TENG Yingyao.Path planning of mine robot based on a novel heuristic algorithm with regular hexagon grids[J].Industry and Mine Automation,2020,46(8):64-69.
作者联系方式
王鹤（1981-），女，河南人，硕士，讲师，研究方向为智能机器人技术，Email:wanghejxr@163.com。
责任编辑联系方式
王 晖，E-mail：wanghui@cari.com.cn
郑海霞，E-mail：191043803@qq.com
基于新型栅格启发式算法的矿井机器人路径规划
Path planning of mine robot based on a novel heuristic algorithm with regular hexagon grids
【作者】王鹤，陈静，滕瑛瑶
【Author】 WANG He,CHEN Jing,TENG Yingyao
【作者机构】河南工程学院 机械工程学院， 河南 郑州451191
【Unit】Mechanical Engineering Department, Henan University of Engineering, Zhengzhou 451191, China
【摘要】在传统正方形栅格地图中，存在机器人遇到障碍物时沿对角线方向移动易与障碍物碰撞，其绕障和平稳性等方面的能力较差且实时探测过程中每步消耗的时间无法唯一确定等问题。针对上述问题，提出了以正六边形栅格化的工作环境为基础，采用改进的启发式路径搜索算法对多个并行移动的矿井机器人进行路径优化的方法。从绕障转角、绕障能力及最优路径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.
【关键词】 矿井机器人路径规划；路径优化；启发式路径搜索算法；正六边形栅格；静态障碍物；动态障碍物
【Key words】path planning of mine robot; path optimization; heuristic path search algorithm; regular hexagon grid; static obstacle; dynamic obstacle
【基金项目】河南省科技攻关项目（182102310769）
信息提供：郑海霞 图文编辑：张聚
审 核：王 晖
免责声明：以上内容转载自工矿自动化，所发内容不代表本平台立场。
全国能源信息平台联系电话：010-65367702，邮箱：hz@people-energy.com.cn，地址：北京市朝阳区金台西路2号人民日报社
