Global optimal path planning for robots with improved A* algorithm

doi:10.11772/j.issn.1001-9081.2019020284

Journal of Computer Applications ›› 2019, Vol. 39 ›› Issue (9): 2517-2522.DOI: 10.11772/j.issn.1001-9081.2019020284

• Artificial intelligence • Previous Articles Next Articles

Global optimal path planning for robots with improved A^* algorithm

WANG Zhongyu, ZENG Guohui, HUANG Bo, FANG Zhijun

School of Electronic and Electrical Engineering, Shanghai University of Engineering Science, Shanghai 201620, China

Received:2019-02-21 Revised:2019-05-10 Online:2019-06-03 Published:2019-09-10
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61603242), the Open Project of Jiangxi Collaborative Innovation Center of Economic Crime Investigation, Prevention and Control Technology (JXJZXTCX-030).

改进A^*算法的机器人全局最优路径规划

王中玉, 曾国辉, 黄勃, 方志军

上海工程技术大学电子电气工程学院, 上海 201620

通讯作者: 曾国辉
作者简介:王中玉(1993-),男,江苏徐州人,硕士研究生,主要研究方向:机器人控制、路径规划算法;曾国辉(1975-),男,江西乐安人,副教授,博士,主要研究方向:机器人控制、电力电子及其控制;黄勃(1985-),男,湖北武汉人,讲师,博士,主要研究方向:需求工程、软件工程、人工智能;方志军(1971-),男,江西鄱阳人,教授,博士,主要研究方向:模式识别、智能计算、视频分析。
基金资助:
国家自然科学基金资助项目（61603242）；江西省经济犯罪侦查与防控技术协同创新中心开放课题（JXJZXTCX-030）。

Abstract

Abstract:

There are many redundant points and inflection points in the path planned by the traditional A^* algorithm. Therefore, an efficient path planning algorithm based on A^* algorithm was proposed. Firstly, the specific calculation method of the evaluation function was improved to reduce the calculation amount of the algorithm searching each interval, thereby reducing the path finding time and changing the generation path. Secondly, on the basis of improving the specific calculation method of the evaluation function, the weight ratio of the evaluation function was improved, and the redundant points and inflection points in the generation path were reduced. Finally, the path generation strategy was improved to delete the useless points in the generation path, improving the smoothness of the path. In addition, considering the actual width of the robot, the improved algorithm introduced an obstacle expansion strategy to ensure the feasibility of the planned path. The comparison of the improved A^* algorithm with three algorithms shows that the path of the improved A^* algorithm is more reasonable, the path finding time is shorter, and the smoothness is higher.

Key words: A^* algorithm, path planning, evaluation function, generation strategy, obstacle expansion

摘要：

针对传统A^*算法规划的路径存在很多冗余点和拐点的问题，提出了一种基于A^*算法改进的高效路径规划算法。首先，改进评价函数的具体计算方式，减小算法搜索每个区间的计算量，从而降低寻路时间，并改变生成路径；其次，在改进评价函数具体计算方式的基础上，改进评价函数的权重比例，减少生成路径中的冗余点和拐点；最后，改进路径生成策略，删除生成路径中的无用点，从而提高路径的平滑性；此外，考虑到机器人的实际宽度，改进后算法引入障碍物扩展策略保证规划路径的可行性。将改进A^*算法与三种算法进行仿真对比，实验结果表明，改进后的A^*算法规划的路径更加合理，寻路时间更短，平滑性更高。

关键词: A^*算法, 路径规划, 评价函数, 生成策略, 障碍物扩展

CLC Number:

TP242.6

WANG Zhongyu, ZENG Guohui, HUANG Bo, FANG Zhijun. Global optimal path planning for robots with improved A^* algorithm[J]. Journal of Computer Applications, 2019, 39(9): 2517-2522.

王中玉, 曾国辉, 黄勃, 方志军. 改进A^*算法的机器人全局最优路径规划[J]. 计算机应用, 2019, 39(9): 2517-2522.

References

[1] 陆新华,张桂林.室内服务机器人导航方法研究[J].机器人,2003,25(1):80-87.(LU X H, ZHANG G L. Summarization on indoor service robot navigation[J]. Robot, 2003, 25(1):80-87.)
[2] CHEN D, LU Q, YIN K, et al. A method for solving local minimum problem of local path planning based on particle swarm optimization[C]//Proceedings of the 2017 Chinese Automation Congress. Piscataway, NJ:IEEE, 2017:4944-4949.
[3] JEDDISARAVI K, ALITAPPEH R J, PIMENTA L C A, et al. Multi-objective approach for robot motion planning in search tasks[J]. Applied Intelligence, 2016, 45(2):1-17.
[4] 张超超,房建东.基于定向加权A^*算法的自主移动机器人路径规划[J].计算机应用,2017,37(S2):77-81.(ZHANG C C, FANG J D. Path planning of autonomous mobile robot based on directional weighted A^* algorithmm[J]. Journal of Computer Applications, 2017, 37(S2):77-81.)
[5] HAO Z-B, HONG B-R, HUANG Q-C. Study of coverage path planning based on grid-map[J]. Application Research of Computers, 2007, 24(10):56-58.
[6] PAN H, GUO C, WANG Z. Research for path planning based on improved astart algorithm[C]//Proceedings of the 2017 4th International Conference on Information, Cybernetics and Computational Social Systems. Piscataway, NJ:IEEE, 2017:225-230.
[7] GUO Y, WANG W, WU S. Research on robot path planning based on fuzzy neural network and particle swarm optimization[C]//Proceedings of the 2017 29th Chinese Control and Decision Conference. Piscataway, NJ:IEEE, 2017:2146-2150.
[8] MONTIEL O, SEPULVEDA R, OROZCO-ROSAS U. Optimal path planning generation for mobile robots using parallel evolutionary artificial potential field[J]. Journal of Intelligent and Robotic Systems, 2015, 79(2):237-257.
[9] 韩明,刘教民,吴朔媚,等.粒子群优化的移动机器人路径规划算法[J].计算机应用,2017,37(8):2258-2263.(HAN M, LIU J M, WU S M, et al. Path planning algorithm of mobile robot based on particle swarm optimization[J]. Journal of Computer Applications, 2017, 37(8):2258-2263.)
[10] NI J, WANG K, HUANG H. Robot path planning based on an improved genetic algorithm with variable length chromosome[C]//Proceedings of the 2016 12th International Conference on Natural Computation, Fuzzy Systems and Knowledge Discovery. Piscataway, NJ:IEEE, 2016:145-149.
[11] 吴天羿,许继恒,刘建永.基于改进蚁群算法的越野路径规划[J].计算机应用,2013,33(4):1157-1160.(WU T Y, XU J H, LIU J Y. Cross-country path planning based on improved ant colony algorithm[J]. Journal of Computer Applications, 2013, 33(4):1157-1160.)
[12] LIU K, ZHANG M. Path planning based on simulated annealing ant colony algorithm[C]//Proceedings of the 2016 9th International Symposium on Computational Intelligence and Design. Piscataway, NJ:IEEE, 2016:461-466.
[13] LI Y, ZHANG H, ZHU H. IBAS:index based a-star[J]. IEEE Access, 2018, 6:11707-11715.
[14] JEDDISARAVI K, ALITAPPEH R J, GUIMARAES F G. Multi-objective mobile robot path planning based on A^* search[C]//Proceedings of the 2016 6th International Conference on Computer and Knowledge Engineering. Piscataway, NJ:IEEE, 2016:7-12.
[15] WANG Z, XIANG X. Improved astar algorithm for path planning of marine robot[C]//Proceedings of the 2018 37th Chinese Control Conference. Piscataway, NJ:IEEE, 2018:296-300.
[16] WANG Q, ZHANG A, QI L. Three-dimensional pathplanning for UAV based on pmproved PSO algorithm[C]//Proceedings of the 2014 26th Chinese Control and Decision Conference. Piscataway, NJ:IEEE, 2014:3982-3986.
[17] 林娜,李天啸.基于双向A^*算法的城市无人机航路规划[J].沈阳航空航天大学学报,2016,33(4):55-60.(LIN N, LI T X. Urban UAV route planning based on bidirectional A^* algorithm[J]. Journal of Shenyang Aerospace University, 2016, 33(4):55-60.)
[18] 高民东,张雅妮,朱凌云.应用于机器人路径规划的双向时效A^*算法[J].计算机应用研究,2019,36(3):792-795.(GAO M D, ZHANG Y N, ZHU L Y. Bidirectional time-efficient A^* algorithm for robot path planning[J]. Application Research of Computers, 2019, 36(3):792-795.)
[19] 陈瑶.变电站智能巡检机器人全局路径规划设计与实现[D].济南:山东大学,2015:94.(CHEN Y. Design and implementation of global path planning for substation intelligent patrol inspection robot[D]. Jinan:Shandong University, 2015:94.)
[20] 向光海.变电站巡检机器人路径规划系统设计与实现[D].成都:西南交通大学,2015:77.(XIANG G H. Design and implementation of path planning system for substation inspection robot[D]. Chengdu:Southwest Jiaotong University, 2015:77.)

Global optimal path planning for robots with improved A^* algorithm

改进A^*算法的机器人全局最优路径规划

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	Tian MA, Runtao XI, Jiahao LYU, Yijie ZENG, Jiayi YANG, Jiehui ZHANG. Mobile robot 3D space path planning method based on deep reinforcement learning [J]. Journal of Computer Applications, 2024, 44(7): 2055-2064.
[2]	Runze TIAN, Yulong ZHOU, Hong ZHU, Gang XUE. Local information based path selection algorithm for service migration [J]. Journal of Computer Applications, 2024, 44(7): 2168-2174.
[3]	Jianqiang LI, Zhou HE. Hybrid NSGA-Ⅱ for vehicle routing problem with multi-trip pickup and delivery [J]. Journal of Computer Applications, 2024, 44(4): 1187-1194.
[4]	Haixin HUANG, Guangwei YU, Shoushan CHENG, Chunming LI. Full coverage path planning of bridge inspection wall-climbing robot based on improved grey wolf optimization [J]. Journal of Computer Applications, 2024, 44(3): 966-971.
[5]	Ziyang SONG, Junhuai LI, Huaijun WANG, Xin SU, Lei YU. Path planning algorithm of manipulator based on path imitation and SAC reinforcement learning [J]. Journal of Computer Applications, 2024, 44(2): 439-444.
[6]	Jian SUN, Baoquan MA, Zhuiwei WU, Xiaohuan YANG, Tao WU, Pan CHEN. Joint optimization of UAV swarm path planning and task allocation balance in earthquake scenarios [J]. Journal of Computer Applications, 2024, 44(10): 3232-3239.
[7]	Yongdi LI, Caihong LI, Yaoyu ZHANG, Guosheng ZHANG. Mobile robot path planning based on improved SAC algorithm [J]. Journal of Computer Applications, 2023, 43(2): 654-660.
[8]	Lin HUANG, Qiang FU, Nan TONG. Solving robot path planning problem by adaptively adjusted Harris hawk optimization algorithm [J]. Journal of Computer Applications, 2023, 43(12): 3840-3847.
[9]	Chen LIU, Yang CHEN, Hao FU. UAV path planning for persistent monitoring based on value function iteration [J]. Journal of Computer Applications, 2023, 43(10): 3290-3296.
[10]	Houming FAN, Shuang MU, Lijun YUE. Collaborative optimization of automated guided vehicle scheduling and path planning considering conflict and congestion [J]. Journal of Computer Applications, 2022, 42(7): 2281-2291.
[11]	Zhonghua ZHANG, Fuyuan ZHAO, Junfeng GUO, Gaochang ZHAO. Integrated prediction model of Cauchy adaptive backtracking search and least square support vector machine [J]. Journal of Computer Applications, 2022, 42(6): 1829-1836.
[12]	Sheng CHEN, Jun ZHOU, Xiaobing HU, Ji MA. Optimization of airport arrival procedures based on hybrid simulated annealing algorithm [J]. Journal of Computer Applications, 2022, 42(2): 606-615.
[13]	LI Kairong, LIU Shuang, HU Qianqian, TANG Yiyuan. Improved ant colony optimization algorithm for path planning based on turning angle constraint [J]. Journal of Computer Applications, 2021, 41(9): 2560-2568.
[14]	TANG Andi, HAN Tong, XU Dengwu, XIE Lei. Path planning method of unmanned aerial vehicle based on chaos sparrow search algorithm [J]. Journal of Computer Applications, 2021, 41(7): 2128-2136.
[15]	ZHANG Kang, CHEN Jianping. Path planning algorithm in complex environment using self-adjusting sampling space [J]. Journal of Computer Applications, 2021, 41(4): 1207-1213.

Global optimal path planning for robots with improved A* algorithm

改进A*算法的机器人全局最优路径规划

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Global optimal path planning for robots with improved A^* algorithm

改进A^*算法的机器人全局最优路径规划