基于偏置采样和包围优化的移动机器人路径规划方法
陈彦杰1,4*,梁景林1,张智星1,喻 骁2,王耀南3,4

(1.福州大学机械工程及自动化学院,福建 福州 350108; 2.厦门大学航空航天学院,福建 厦门 361102; 3.湖南大学电气与信息工程学院,湖南 长沙 410082; 4.机器人视觉感知与控制技术国家工程研究中心,湖南 长沙 410082)

路径规划; 移动机器人; 批处理知情搜索树; 路径优化; 偏置采样

Mobile robot path planning based on biased sampling and wrapping optimization
CHEN Yanjie1,4*,LIANG Jinglin1,ZHANG Zhixing1,YU Xiao2,WANG Yaonan3,4

(1.School of Mechanical Engineering and Automation,Fuzhou University,Fuzhou 350108,China; 2.School of Aerospace Engineering,Xiamen University,Xiamen 361102,China; 3.College of Electrical and Information Engineering,Hunan University,Changsha 410082,China; 4.National Engineering Research Center of Robot Visual Perception and Control Technology,Changsha 410082,China)

path planning; mobile robot; batch informed trees; path optimization; biased sampling

DOI: 10.6043/j.issn.0438-0479.202204037

备注

批处理知情搜索树(batch informed trees,BIT*)作为一种先进的采样规划方法通常被应用于移动机器人的路径规划.针对BIT*在初始路径获得后存在路径代价降低速度不快、规划效率有待提高的问题,提出了一种基于偏置采样和包围优化的BIT*(wrapping-based biased BIT*,WB-BIT*)方法.该方法首先通过批量采样进行节点和连接的扩展,在获得可行路径后,利用包围优化策略从目标点到起始点逐步使路径靠近至障碍物周围,快速减少现有可行路径的长度.同时,根据可行路径上的路径点计算启发式函数以构建偏置采样区域,结合偏置采样和知情集采样,在保证均匀性的前提下有效运用现有路径信息,提高方法的规划效率.最后,将所提出的WB-BIT*方法与主流采样路径规划方法进行仿真实验对比,结果表明所提出的路径规划方法具备更高的规划效率.

Objective: As a sampling-based method for mobile robot, Batch informed tree (BIT*) can explore a feasible path effectively. It obtains collision-free nodes by multiple batch sampling, and uses heuristic to sort edge connections for tree expansion. However, BIT* often encounters the problem of slow cost reduction and low planning efficiency after finding the initial path. By analyzing characteristics of the BIT*, we focus on designing existing path optimization and sampling strategies for BIT*. Furthermore, different maps are employed to test the proposed method, and other popular sampling-based planning methods are also tested for comparison.
Methods: The proposed path-planning method is based on wrapping optimization and biased sampling (wrapping-based biased BIT*, WB-BIT*). It first expands nodes and connections through batch sampling. After obtaining a feasible path, the wrapping optimization strategy is adopted to allow the feasible path to approach closely to obstacles. Then, based on path points of the current feasible path, a novel heuristic function is introduced to construct the biased sampling area. Biased sampling and informed set sampling are balanced by a ratio. Furthermore, three different types of environments are built to test the proposed WB-BIT* and comparison methods.
Results: Under the condition of the same number of samples, all WB-BIT*, BIT*, fast matching tree (FMT*) and Informed rapidly-exploring random tree (Informed RRT*) can find a feasible path. Among them, the cost of the path planned by WB-BIT* is the lowest. In addition, we stop searching when the convergence effect (current path length cost/theoretical optimal path cost) of each method becomes less than 1.05. From the recorded time spent and sample number, it can be found that WB-BIT* requires the least sample number and consumes the least time in three different maps. In the map with surrounding obstacles, BIT * and Informed RRT* endure redundant exploration problems due to the large informed set area. The path wrapping optimization of WB-BIT* can allow the path to closely approach obstacles, use biased sampling to improve the path, and finally approach the theoretical optimal path with fewest samples. In maps with multiple feasible paths, WB-BIT* can quickly reduce the cost of the existing path to decrease the informed set area, and use biased sampling to search for the potentially optimal path. Results show that the time spent and the sample number of WB-BIT* appear more satisfactory than those of comparison methods. To further analyze the planning efficiency of the proposed method, we record the relationship between sampling numbers and path cost of different maps. WB-BIT* secures a fast reduction speed in the path cost during the planning process. In the map with surrounding obstacles, WB-BIT* must use 300 samples to obtain the path with the cost within 1% of the theoretical optimal solution in 3.316 seconds. However, other comparison methods require more samples and time to achieve similar convergence effects.
Conclusions: Experiments show that the wrapping optimization can quickly reduce the path cost when WB-BIT* finds a path. The biased sampling strategy can speed up the exploration of potential optimal paths, especially in scenarios in which multiple feasible paths exist. WB-BIT* can obtain a path with lower costs than other comparison methods under the limitation of the same number of samples. In addition, under the condition of similar convergence effects, WB-BIT* secures the least number of samples and time spent to approach the theoretical optimal path in these three maps. In summary, results indicate that WB-BIT* can efficiently complete path planning in different maps, and secures a faster path cost reduction speed and higher path-searching efficiency than similar sampling-based planning methods can.
·