基于PG-RRT算法的移动机器人路径规划

doi:10.11896/j.issn.1002-137X.2019.04.039

计算机科学 ›› 2019, Vol. 46 ›› Issue (4): 247-253.doi: 10.11896/j.issn.1002-137X.2019.04.039

基于PG-RRT算法的移动机器人路径规划

郗枫飞¹, 曾晰^1,2, 计时鸣¹, 陈国达¹, 蔡超鹏¹

浙江工业大学特种装备制造与先进加工技术教育部重点实验室杭州310023¹
浙江大学流体动力与机电系统国家重点实验室杭州310027²

收稿日期:2018-03-31 出版日期:2019-04-15 发布日期:2019-04-23
通讯作者: 曾晰(1984－),男,博士后,副教授,硕士生导师,主要研究方向为工业特种机器人研发、智能化装备设计与制造等,E-mail:zengxi@zjut.edu.cn(通信作者)
作者简介:郗枫飞(1993-),男,硕士生,主要研究方向为工业机器人研发、机器人算法研究等,E-mail:kealxff@163.com;计时鸣(1957-),男,博士,教授,博士生导师,主要研究方向为工业机器人研发、数字图像处理、超精密加工等;陈国达(1986-),男,博士,讲师,硕士生导师,主要研究方向为机器人智能装备与精密制造技术;蔡超鹏(1994-),男,硕士生,主要研究方向为机器学习、深度学习、机器视觉、数据挖掘等。
基金资助:
本文受国家自然科学基金(51875526),浙江省自然科学基金(LY18E050023),浙江省大学生科技创新活动计划(新苗人才计划)(2017R403079),2018年度浙江省科协育才工程项目(2018YCGC016)资助。

Path Planning of Mobile Robot Based on PG-RRT Algorithm

XI Feng-fei¹, ZENG Xi^1,2, JI Shi-ming¹, CHEN Guo-da¹, CAI Chao-peng¹

Key Laboratory of Special Purpose Equipment and Advanced Processing Technology of the Ministry of Education,Zhejiang University of Technology,Hangzhou 310023,China¹
The State Key Lab of Fluid Power and Mechatronic Systems,Zhejiang University,Hangzhou 310027,China²

Received:2018-03-31 Online:2019-04-15 Published:2019-04-23

摘要/Abstract

摘要： 路径规划问题是移动机器人领域的重点问题,也是发展移动式机器人智能工厂的基础。快速扩展随机树算法(RRT算法)由于其良好的求解性,广泛应用于移动机器人路径规划。针对RRT算法面对复杂地图时随机采样效率低、路径重复性差的问题,提出一种基于模拟植物生长引导的RRT移动机器人路径规划算法(PG-RRT算法),提升了路径寻优的稳定性和效率。利用植物生长遵循的三大原则(向光性原则、遮挡物影响原则、负向地性原则),结合变步长技术、膨胀技术快速得到用于RRT算法采样的PG膨胀引导域,并得到最终路径。多组不同障碍物地图的仿真实验表明:相比于传统RRT算法和单一PG算法,PG-RRT算法减少了迭代次数,获得了更优的路径距离,而相比于A^*算法,该算法则大大缩短了计算时间。最后通过基于ROS系统机器人平台的实车测试,验证了PG-RRT算法的实用性。

关键词: 快速扩展随机树算法, 路径规划, 植物生长

Abstract: The path planning problem is a vital problem in the field of mobile robots and is the basis for the development of smart factories.Rapidly-expanding random tree algorithm (RRT algorithm) is widely used in path planning because of its excellent solving performance.Aiming at the problem of low execution efficiency and poor path repeatability of the RRT algorithm when faced with complex maps,a plant growth guidance based RRT path planning algorithm (PG-RRT algorithm) for mobile robot was proposed to improve the stability and efficiency of path optimization.By using three principles followed by plant growth (Phototropism,Obstacle influence characteristics and Negative geotropism),combing variable step technique and inflation technique,the PG dilation guide field used for RRT algorithm can be obtained.Finally,the ideal path is obtained by using the RRT algorithm with random sampling characteristics.Abundant simulations show that the PG-RRT algorithm reduces the number of iterations and obtains better path distance compared to the traditional RRT algorithm and the single PG algorithm.It is noteworthy that the search efficiency of the presented path planning algorithm is improved compared with the A^* algorithm.Moreover,the actual vehicle test of robot verifies the practicability of the PG-RRT algorithm.

Key words: Path planning, Plant growth, Rapidly-expanding random tree algorithm

中图分类号:

TP301

郗枫飞, 曾晰, 计时鸣, 陈国达, 蔡超鹏. 基于PG-RRT算法的移动机器人路径规划[J]. 计算机科学, 2019, 46(4): 247-253. https://doi.org/10.11896/j.issn.1002-137X.2019.04.039

XI Feng-fei, ZENG Xi, JI Shi-ming, CHEN Guo-da, CAI Chao-peng. Path Planning of Mobile Robot Based on PG-RRT Algorithm[J]. Computer Science, 2019, 46(4): 247-253. https://doi.org/10.11896/j.issn.1002-137X.2019.04.039

参考文献

[1]CUI M,LIU H,LIU W,et al.An Adaptive Unscented Kalman Filter-based Controller for Simultaneous Obstacle Avoidance and Tracking of Wheeled Mobile Robots with Unknown Slipping Parameters.Journal of Intelligent & Robotic Systems,2018,92(3-4):489-504.
[2]INDRI M,TRAPANI S.LAZZERO I.Development of a Virtual Collision Sensor for Industrial Robots:[J].Sensors,2017,17(5):1148.
[3]KIVELÄ T,MATTILA J,PUURA J,et al.Redundant Robotic Manipulator Path Planning for Real-Time Obstacle and Self-Collision Avoidance[C]∥International Conference on Robotics in Alpe-Adria Danube Region.Springer,Cham,2017:208-216.
[4]KUWATA Y,TEO J,FIORE G,et al.Real-Time Motion Planning With Applications to Autonomous Urban Driving[J].IEEE Transactions on Control Systems Technology,2009,17(5):1105-1118.
[5]XU F.Research on Robot Obstacle Avoidance and Path Planning Based on Improved Artificial Potential Field Method[J].Computer Science,2016,43(12):293-296.(in Chinese) 徐飞.基于改进人工势场法的机器人避障及路径规划研究[J].计算机科学,2016,43(12):293-296.
[6]LV T,FENG M.A Smooth Local Path Planning Algorithm Based on Modified Visibility Graph[J].Modern Physics Letters B,2017,31(19-21):1-6.
[7]KRICHMAR J L.Path Planning using a Spiking Neuron Algorithm with Axonal Delays.IEEE Transactions on Cognitive &Developmental Systems,2018,10(2):126-137.
[8]LAVALLE S M.Rapidly-exploring Random Trees:A New Tool for Path Planning.Ames:Computer Science Department of Iowa State University,1998.
[9]LAVALLE S,KUFFNER J.Randomized Kinodynamic Planning[J].The International Journal of Robotics Research,2001,20(5):378-400.
[10]DONG Y,CAMCI E,KAYACAN E.Faster RRT-based Non- holonomic Path Planning in 2D Building Environments Using Skeleton-constrained Path Biasing[J].Journal of Intelligent & Robotic Systems,2018,89(3-4):387-401.
[11]KARAMAN S,FRAZZOLI E.Sampling-Based Algorithms Foroptimal Motion Planning[J].The International Journal of Robotics Research,2011,30(7):846-894.
[12]QURESHI A H,MUMTAZ S,IQBAL K F,et al.Triangular geometry based optimal motion planning using RRT^*-motion planner∥IEEE International Workshop on Advanced Motion Control.IEEE,2014:380-385.
[13]MA L,XUE J R,KAWABATA K,et al.A Fast RRT Algorithm for Motion Planning of Autonomous Road Vehicles[C]∥2014 IEEE 17th International Conference on Intelligent Transportation Systems.Qingdao,China,2014:1033-1038.
[14]KUFFNER J J,LAVALLE S M.RRT-connect:an efficient approach to single-query path planning∥IEEE International Conference on Robotics & Automation.IEEE,2000:995-1001.
[15]MELCHIOR N A,SIMMONS R.Particle RRT for Path Planning with Uncertainty[C]∥IEEE International Conference on Robotics and Automation.IEEE,2007:1617-1624.
[16]LINDEMANN S R,LAVALLE S.Incrementally Reducing Dispersion by Increasing Voronoi Bias In Rrts[C]∥IEEE International Conference on Robotics and Automation,2004.ICRA,2004:3251-3257.
[17]MOON C B,CHUNG W.Kinodynamic Planner Dual-Tree RRT (DT-RRT) for Two-Wheeled Mobile Robots Using the Rapidly Exploring Random Tree[J].IEEE Transactions on Industrial Electronics,2015,62(2):1080-1090.
[18]HIDALGO-PANIAGUA A,BANDERA J P,RUIZ-DE-QUINTANILLA M,et al.Quad-RRT:A Real-Time GPU-Based Glo-bal Path Planner in Large-Scale Real Environments[J].Expert Systems with Applications,2018,99:141-154.
[19]LI Y,ZHANG F,XU D,et al.Liveness-Based RRT Algorithm for Autonomous Underwater Vehicles Motion Planning[J].Journal of Advanced Transportation,2017,2017(7):1-10.
[20]WEI K,REN B.A Method on Dynamic Path Planning for Robotic Manipulator Autonomous Obstacle Avoidance Based on an Improved RRT Algorithm.[J].Sensors,2018,18(2):1-15.
[21]CHEN J Y,SHI J,DU W Y,et al.Research on UAV Route Planning Algorithm Based on MB-RRT^*[J].Computer Scien-ce,2017,44(8):198-206.(in Chinese) 陈晋音,施晋,杜文耀,等.基于MB-RRT^*的无人机航迹规划算法研究[J].计算机科学,2017,44(8):198-206.

相关文章 15

[1]	王兵, 吴洪亮, 牛新征. 基于改进势场法的机器人路径规划 Robot Path Planning Based on Improved Potential Field Method 计算机科学, 2022, 49(7): 196-203. https://doi.org/10.11896/jsjkx.210500020
[2]	谭任深, 徐龙博, 周冰, 荆朝霞, 黄向生. 海上风电场通用运维路径规划模型优化及仿真 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
[3]	杨浩雄, 高晶, 邵恩露. 考虑一单多品的外卖订单配送时间的带时间窗的车辆路径问题 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
[4]	沈彪, 沈立炜, 李弋. 空间众包任务的路径动态调度方法 Dynamic Task Scheduling Method for Space Crowdsourcing 计算机科学, 2022, 49(2): 231-240. https://doi.org/10.11896/jsjkx.210400249
[5]	陈镜宇, 郭志军, 尹亚昆. 基于混合算法的智能割草机全遍历路径规划及其系统设计 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
[6]	杜婉茹, 王潇茵, 田涛, 张越. 面向未知环境及动态障碍的人工势场路径规划算法 Artificial Potential Field Path Planning Algorithm for Unknown Environment and Dynamic Obstacles 计算机科学, 2021, 48(2): 250-256. https://doi.org/10.11896/jsjkx.191100170
[7]	郭启程, 杜晓玉, 张延宇, 周毅. 基于改进鲸鱼算法的无人机三维路径规划 Three-dimensional Path Planning of UAV Based on Improved Whale Optimization Algorithm 计算机科学, 2021, 48(12): 304-311. https://doi.org/10.11896/jsjkx.201000021
[8]	赵杨, 倪志伟, 朱旭辉, 刘浩, 冉家敏. 基于改进狮群进化算法的面向空间众包平台的多工作者多任务路径规划方法 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
[9]	曹波, 陈锋, 成静, 李华, 李永乐. 基于全向路口模型的非结构化道路重复节点路径规划 Route Planning of Unstructured Road Including Repeat Node Based on Bidirectional Search 计算机科学, 2021, 48(11A): 77-80. https://doi.org/10.11896/jsjkx.201200193
[10]	陈继清, 谭成志, 莫荣现, 王志奎, 吴家华, 赵超阳. 基于人工势场的A^算法的移动机器人路径规划 Path Planning of Mobile Robot with A^ Algorithm Based on Artificial Potential Field 计算机科学, 2021, 48(11): 327-333. https://doi.org/10.11896/jsjkx.200900170
[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]	曾伟良, 吴淼森, 孙为军, 谢胜利. 自动驾驶出租车调度系统研究综述 Comprehensive Review of Autonomous Taxi Dispatching Systems 计算机科学, 2020, 47(5): 181-189. https://doi.org/10.11896/jsjkx.190400031

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

基于PG-RRT算法的移动机器人路径规划

Path Planning of Mobile Robot Based on PG-RRT Algorithm

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

Metrics

本文评价

推荐阅读 0