，，

(哈尔滨工业大学机器人技术与系统国家重点实验室，哈尔滨 150001)

Research on Path Planning Algorithm for Mobile RobotBased on Square Nodes in Topological Map

LI Minglei，ZHAO Jie，LI Ge

(State Key Laboratory of Robotics and System，Harbin Institute of Technology，Harbin 150001，China)

面向方形节点拓扑地图下的移动机器人路径规划算法研究

李明磊，赵杰，李戈

(哈尔滨工业大学机器人技术与系统国家重点实验室，哈尔滨 150001)

ResearchonPathPlanningAlgorithmforMobileRobotBasedonSquareNodesinTopologicalMap

LIMinglei，ZHAOJie，LIGe

(StateKeyLaboratoryofRoboticsandSystem，HarbinInstituteofTechnology，Harbin150001，China)

摘要：针对方形节点拓扑地图下的移动机器人的特性，采用了A*算法来实现路径规划，并对传统的A*算法进行改进，一是在启发函数中引入了位移和角度2个因素，提高了函数的启发性；二是引入堆的方法优化了数据结构，提高了列表中代价最小节点的搜索速度。仿真实验结果表明，改进后的A*算法节点的最短路径节点相对减少，算法效率明显提高，具有良好的可行性和有效性。

关键词：移动机器人；拓扑地图；轨迹规划；A*算法

中图分类号：TP301.6

文献标识码：A

文章编号：1001-2257(2015)10-0067-04

收稿日期：2015-05-28

Abstract：In order to achieve the goal，according to the characteristics of the mobile robot based on square nodes in topological map，the paper improved the A* algorithm as follow. First，the new heuristic function took consideration of two factors：Distance and angle，improved the heuristic ability of A*；Then，the slowest part of the A* pathfinding algorithm is finding the node in the list with the lowest F score，the paper used the binary heaps to make it faster. Simulation results showed that the improved A* decreased the number of result nodes and took less time，demonstrated the feasibility and validity of the algorithm.

作者简介：李明磊(1990-)，男，山东潍坊人，硕士研究生，研究方向为机器人技术。

Keywords：mobilerobot；topologicalmap；pathplanning；A* algorithm

0引言

在移动机器人技术相关的研究中，路径规划算法是一个重要的领域，其核心是按照某一性能指标(如距离、时间等)，快速高效地在有障碍的工作环境中找到两个或者多个节点之间的最优或次优路径。现有的路径规划算法有很多，例如Dijkstra算法、遗传算法等。Dijkstra算法不考虑目标信息，需要遍历计算所有节点，虽然可以找到最短路径，但求解时间长，效率非常低。遗传算法也存在求解效率低，难以解决大计算量，容易陷入“早熟”等问题。

A*算法是一种典型的启发式搜索算法，一般适用于环境信息已知的全局路径规划中。……