| Multi-Bug全局路径规划算法研究 |
| |
| 引用本文： | 彭艳,鲍凌志,瞿栋,解杨敏.Multi-Bug全局路径规划算法研究[J].农业机械学报,2020,51(6):375-384. |
| |
| 作者姓名： | 彭艳 鲍凌志 瞿栋 解杨敏 |
| |
| 作者单位： | 上海大学无人艇工程研究院,上海200444;上海大学上海市智能制造与机器人重点实验室,上海200444 |
| |
| 基金项目： | 国家自然科学基金项目(91648119)、上海市科委项目(17DZ1205001）和上海市科技创新行动计划启明星项目（19QA1403500) |
| |
| 摘 要： | 提出一种基于Multi-Bug思想的非搜索全局路径规划算法。在Multi-Bug算法中,借用传统Bug算法的寻路逻辑,加入遇到障碍物时的爬虫分裂规则及爬虫死亡条件判断规则,直至其中一只爬虫以相对最优路径抵达终点,从而实现多路径并行运算的局部最优寻路策略。利用栅格法对多类障碍物、迷宫类地图等环境进行建模,并与Dist-Bug算法、RRT*和A*算法进行路径长度及运算时间的对比仿真实验,结果表明,采用Multi-Bug算法获得的路径长度和用时都表现得更加稳定;与获得最短路径的A*算法相比,Multi-Bug算法获得的平均路径长度仅增加了16.8%,平均用时减少了86.5%。经理论分析及仿真验证,Multi-Bug算法时间复杂度为O(n),具有路径较短、时效性强、算法通用性和稳定性好的路径规划性能。
|
| 关 键 词： | 路径规划 Multi-Bug算法 Dist-Bug算法 栅格法 |
| 收稿时间： | 2019/10/31 0:00:00 |
Global Path Planning Algorithm of Multi-Bug |
| |
| PENG Yan,BAO Lingzhi,QU Dong,XIE Yangmin.Global Path Planning Algorithm of Multi-Bug[J].Transactions of the Chinese Society of Agricultural Machinery,2020,51(6):375-384. |
| |
| Authors: | PENG Yan BAO Lingzhi QU Dong XIE Yangmin |
| |
| Institution: | Shanghai University |
| |
| Abstract: | Path planning is one of the key technologies to realize its ability of autonomous action in complex environment.A non-search global path planning algorithm called Multi-Bug was proposed.It combined the merits of short path length of global path planning and small computation cost of the Bug algorithms,which generated better overall performance compared with traditional path planning methods.This method had great advantages in the situation of high timeliness and general path requirements.In the Multi-Bug algorithm,the simple path-finding logic that followed the wall in the Bug algorithm was adopted,and bug splitting and death rules were added into the framework.The algorithm was ended when one of the bugs arrived at the target or all of the bugs met the death rules and dead,which permitted multi-path parallel computation for local optimal planning solution.Grid maps,including multiple types of obstacles and various mazes,were used to testify the Multi-Bug algorithm.In order to ensure the reliability of operation results,each algorithm in the same grid map was run 10 times,and its operation time was averaged.Compared with Dist-Bug algorithm,RRT*and A*algorithms,it showed much better performance stability in terms of the path length and the computational time cost.Especially when compared with the A*algorithm,which provided the shortest path length,it decreased the calculation time by more than four fifths with grid map size as 50×50 and only increased the path length by less than one fifth.In 500×500 grid map,the time was less than one ten-thousandth of that of A*algorithm.By the theoretical analysis and the simulation verification,Multi-Bug algorithm had a time complexity as O(n),provided relatively short path,required less computational cost,and had good stability and versatility for various environments. |
| |
| Keywords: | path planning Multi Bug algorithm Dist Bug algorithm grid method |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《农业机械学报》浏览原始摘要信息 |
| 点击此处可从《农业机械学报》下载免费的PDF全文 |
|
