计算机科学 ›› 2021, Vol. 48 ›› Issue (11): 327-333.doi: 10.11896/jsjkx.200900170

• 人工智能 • 上一篇    下一篇

基于人工势场的A*算法的移动机器人路径规划

陈继清1,2, 谭成志1, 莫荣现1, 王志奎1, 吴家华1, 赵超阳1   

  1. 1 广西大学机械工程学院 南宁530004
    2 广西制造系统与先进制造技术重点实验室 南宁530004
  • 收稿日期:2020-09-23 修回日期:2021-01-18 出版日期:2021-11-15 发布日期:2021-11-10
  • 通讯作者: 陈继清(cjq_gz@163.com)
  • 基金资助:
    国家自然科学基金(61703116);广西自然科学基金(2017GXNSFBA198228);广西科技基地和人才专项(AD19110034)

Path Planning of Mobile Robot with A* Algorithm Based on Artificial Potential Field

CHEN Ji-qing1,2, TAN Cheng-zhi1, MO Rong-xian1, WANG Zhi-kui1, WU Jia-hua1, ZHAO Chao-yang1   

  1. 1 School of Mechanical Engineering,Guangxi University,Nanning 530004,China
    2 Manufacturing System and Advanced Manufacturing Technology Key Laboratory,Nanning 530004,China
  • Received:2020-09-23 Revised:2021-01-18 Online:2021-11-15 Published:2021-11-10
  • About author:CHEN Ji-qing,born in 1984,Ph.D,lecturer,postgraduate supervisor.His main research interests include robot motion control,machine vision,special robot system.
  • Supported by:
    National Natural Science Foundation of China(61703116), Natural Science Foundation of Guangxi Province,China(2017GXNSFBA198228) and Guangxi Science and Technology Base and Talent Project (AD19110034).

摘要: 为了解决传统A* 算法规划路径时未考虑到障碍物分布对路径选取的影响,文中提出了一种改进的A* 算法。将人工势场的思想与传统的A*算法相结合,对栅格地图中的障碍物赋予斥力场函数并计算周围栅格的斥力大小,进行路径搜索时将栅格的斥力大小引进到A* 算法的评价函数当中以改进A* 算法的搜索能力。通过MATLAB仿真和Turtlebot机器人的实验结果表明,与传统的A* 算法相比,改进后的新算法与人工势场算法相结合,规划出了更优的路径,提高了路径规划效率,且搜索速度提高了13.40%~29.68%,路径长度缩短了10.56%~24.38%,路径节点数减少了6.89%~27.27%,因此,改进的A* 算法的优化效果明显,具有有效性和可行性。

关键词: A* 算法, MATLAB, 路径规划, 人工势场, 移动机器人

Abstract: In order to solve the traditional A* algorithm is not taken into account when planning path obstacle distribution on the influence of the path selection,this paper puts forward an improved A* algorithm,the artificial potential field of thought and the traditional A* algorithm,the combination of the obstacles in grid map gives repulsive force function and the repulsive force around the grid size calculation,in order to improve the searching ability of A* algorithm,the repulsive force of the grid is introduced into the evaluation function of A* algorithm.The results of MATLAB simulation and Turtlebot experiments show that,compared with the traditional A* algorithm,the new improved algorithm combined with artificial potential field algorithm can plan a better path,improve the efficiency of path planning,and increase the search speed by 13.40%~29.68%.The path length is shortened by 10.56%~24.38%,and the number of path nodes is reduced by 6.89%~27.27%.The experimental results show that the improved A* algorithm has obvious optimization effect and is effective and feasible.

Key words: A* algorithm, Artificial potential field, MATLAB, Mobile robot, Path planning

中图分类号: 

  • TP242
[1]JEDDISARAVI K,ALITAPPEH R J,PIMENTA L C,et al.Multi-objective approach for robot motion planning in search tasks[J].Applied Intelligence,2016,45(2):1-17.<br /> [2]HAN J,SEO Y.Mobile robot path planning with surrounding point set and path improvement[J].Applied Soft Computing,2017,57(8):35-47.<br /> [3]LIU Q Z,WU F.Research Progress of Multi-Agent Path Planning[J].Computer Engineering,2020,46(4):1-10.<br /> [4]DUCHOŇ F,BABINEC A,KAJAN M,et al.Path planning withmodified a star algorithm for a mobile robot[J].Procedia Engineering,2014,96:59-69.<br /> [5]ZHANG H M,LI M L,YANG L.Safe path planning of mobile robot based on improved A<sup>*</sup> algorithm[J].Computer Simulation,2018,35(4):319-324.<br /> [6]ZHAO X,WANG Z,HUANG C K,et al.Mobile robot path planning based on an improved A<sup>*</sup> algorithm[J].Robot,2018,40(6):903-910.<br /> [7]WANG W,PEI D,FENG Z.The shortest path planning for mobile robots using improved A<sup>*</sup> algorithm[J].Journal of Computer Applications,2018,38(5):1523-1526.<br /> [8]WU P,SANG C J,LU Z H,et al.Research on mobile robot path planning based on improved A<sup>*</sup> algorithm[J].Computer Engineering and Applications,2019,55(21):227-233.<br /> [9]LU W L,LEI J S,SHAO Y.Path planning for mobile robot based on an improved A<sup>*</sup> algorithm[J].Journal of Ordnance Equipment Engineering,2019,40(4):197-201.<br /> [10]ZHOU C,GU Y H,REN B.Research on Path Planning of Mobile Robot Based on An Improved A<sup>*</sup>Algorithm[J].Journal of Chongqing University of Technology(Natural Science),2021,35(5):127-134.<br /> [11]WANG F,LI K P,YUAN M X.Ant colony algorithm based on optimization of potential field method for path planning[J].Computer Science,2014,41(S2):47-50.<br /> [12]WANG Y C,DAI Z X,LI T.UAV path planning based on A-Star algorithm and artificial potential field method[J].Journal of Yangzhou University(Natural Science Edition),2019,22(3):36-38.<br /> [13]WANG H B,HAO C,ZHANG P,et al.Path planning of mobile<br /> robots based on A<sup>*</sup> algorithm and artificial potential field algorithm[J].China Mechanical Engineering,2019,30(20):2489-2496.<br /> [14]HONG I,MURRAY A.Assessingraster GIS approximation for euclidean shortest path routing[J].Transactions in GIS,2016,20(4):507-584.<br /> [15]PANOV A I,YAKOVLEV K S,SUVOROV R.Grid path planning with deep reinforcement learning:preliminary results[J].Procedia Computer Science,2018,123:347-353.<br /> [16]KARDOS P,PALÁGYI K.On topology preservation of mixedoperators in triangular,square,and hexagonal grids[J].Discrete Applied Mathematics,2015,216(2):441-448.<br /> [17]XIONG H,GUO J M,LIU L.A study of improvement of D<sup>*</sup> algorithms for mobile robot path planning in partial unknown environments[J].Kybernetes,2010,39(6):935-945.<br /> [18]ALEJANDRO H P,MIGUEL A R,JOAQUÍN F.Applying the MOVNS (multi-objective variable neighborhood search) algorithm to solve the path planning problem in mobile robotics[J].Expert Systems with Applications,2016,58(10):20-35.<br /> [19]WANG Z Y,ZENG G H,HUANG B,et al.Global optimal path planning for robots with improved A<sup>*</sup> algorithm[J].Journal of Computer Applications,2019,39(9):2517-2522.<br /> [20]WANG P,GAO S,LI L,et al.Obstacle avoidance path planning design for autonomous driving vehicles based on an improved artificial potential field algorithm[J].Energies,2019,12(12):1-14.<br /> [21]PAN Z,LI J Q,HU K M,et al.Intelligent vehicle path planning based on improved artificial potential field method[J].Applied Mechanics & Materials,2015,742:349-354.<br /> [22]HARABOR D,GRASTIEN A.Online graph pruning for path-finding on grid maps[C]//Aaai Conference on Artificial Intelligence.DBLP,2011.
[1] 王兵, 吴洪亮, 牛新征.
基于改进势场法的机器人路径规划
Robot Path Planning Based on Improved Potential Field Method
计算机科学, 2022, 49(7): 196-203. https://doi.org/10.11896/jsjkx.210500020
[2] 杨浩雄, 高晶, 邵恩露.
考虑一单多品的外卖订单配送时间的带时间窗的车辆路径问题
Vehicle Routing Problem with Time Window of Takeaway Food ConsideringOne-order-multi-product Order Delivery
计算机科学, 2022, 49(6A): 191-198. https://doi.org/10.11896/jsjkx.210400005
[3] 谭任深, 徐龙博, 周冰, 荆朝霞, 黄向生.
海上风电场通用运维路径规划模型优化及仿真
Optimization and Simulation of General Operation and Maintenance Path Planning Model for Offshore Wind Farms
计算机科学, 2022, 49(6A): 795-801. https://doi.org/10.11896/jsjkx.210400300
[4] 陈博琛, 唐文兵, 黄鸿云, 丁佐华.
基于改进人工势场的未知障碍物无人机编队避障
Pop-up Obstacles Avoidance for UAV Formation Based on Improved Artificial Potential Field
计算机科学, 2022, 49(6A): 686-693. https://doi.org/10.11896/jsjkx.210500194
[5] 沈彪, 沈立炜, 李弋.
空间众包任务的路径动态调度方法
Dynamic Task Scheduling Method for Space Crowdsourcing
计算机科学, 2022, 49(2): 231-240. https://doi.org/10.11896/jsjkx.210400249
[6] 陈镜宇, 郭志军, 尹亚昆.
基于混合算法的智能割草机全遍历路径规划及其系统设计
Full Traversal Path Planning and System Design of Intelligent Lawn Mower Based on Hybrid Algorithm
计算机科学, 2021, 48(6A): 633-637. https://doi.org/10.11896/jsjkx.201100002
[7] 杜婉茹, 王潇茵, 田涛, 张越.
面向未知环境及动态障碍的人工势场路径规划算法
Artificial Potential Field Path Planning Algorithm for Unknown Environment and Dynamic Obstacles
计算机科学, 2021, 48(2): 250-256. https://doi.org/10.11896/jsjkx.191100170
[8] 郭启程, 杜晓玉, 张延宇, 周毅.
基于改进鲸鱼算法的无人机三维路径规划
Three-dimensional Path Planning of UAV Based on Improved Whale Optimization Algorithm
计算机科学, 2021, 48(12): 304-311. https://doi.org/10.11896/jsjkx.201000021
[9] 赵杨, 倪志伟, 朱旭辉, 刘浩, 冉家敏.
基于改进狮群进化算法的面向空间众包平台的多工作者多任务路径规划方法
Multi-worker and Multi-task Path Planning Based on Improved Lion Evolutionary Algorithm forSpatial Crowdsourcing Platform
计算机科学, 2021, 48(11A): 30-38. https://doi.org/10.11896/jsjkx.201200085
[10] 曹波, 陈锋, 成静, 李华, 李永乐.
基于全向路口模型的非结构化道路重复节点路径规划
Route Planning of Unstructured Road Including Repeat Node Based on Bidirectional Search
计算机科学, 2021, 48(11A): 77-80. https://doi.org/10.11896/jsjkx.201200193
[11] 赵晓薇, 朱小军, 韩周卿.
面向定位应用的无人机的悬停位置和飞行路径优化
Hover Location Selection and Flight Path Optimization for UAV for Localization Applications
计算机科学, 2021, 48(11): 345-355. https://doi.org/10.11896/jsjkx.201000105
[12] 王梓强, 胡晓光, 李晓筱, 杜卓群.
移动机器人全局路径规划算法综述
Overview of Global Path Planning Algorithms for Mobile Robots
计算机科学, 2021, 48(10): 19-29. https://doi.org/10.11896/jsjkx.200700114
[13] 杨德成, 李凤岐, 王祎, 王胜法, 殷慧殊.
智能3D打印路径规划算法
Intelligent 3D Printing Path Planning Algorithm
计算机科学, 2020, 47(8): 267-271. https://doi.org/10.11896/jsjkx.190700184
[14] 姜辰凯, 李智, 盘书宝, 王勇军.
基于改进Dijkstra算法的AGVs无碰撞路径规划
Collision-free Path Planning of AGVs Based on Improved Dijkstra Algorithm
计算机科学, 2020, 47(8): 272-277. https://doi.org/10.11896/jsjkx.190700138
[15] 马虹.
基于5G的视觉辅助BDS移动机器人融合定位算法
Fusion Localization Algorithm of Visual Aided BDS Mobile Robot Based on 5G
计算机科学, 2020, 47(6A): 631-633. https://doi.org/10.11896/JsJkx.190400156
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!