摘要
针对快速搜索随机树(rapidly-exploring random tree,RRT)算法在避障路径规划中存在的对地图适应性弱、采样质量差、无效节点多、规划时间长及路径质量差等问题,提出了一种改进RRT算法。首先,在传统RRT算法的基础上,基于地图复杂程度评估策略计算得到合适的步长及偏置概率,以实现对不同地图的自适应。然后,通过采样区域动态更新策略,使随机树在有效区域内进行采样,以确保随机树的正向生长;在确定采样区域后,利用采样点优化策略来提高采样点的有效性,使得随机树朝目标点附近生长。最后,采用节点重连策略对规划的初始避障路径进行优化,以获得一条弯折次数较少的避障路径。在Python及MATLAB环境中对改进RRT算法的可行性进行验证。结果表明,在面向复杂程度不同的地图和应用于机械臂时,改进RRT算法均能快速规划出一条无碰撞的高质量路径。研究结果可为提高机器人避障路径的规划效率提供参考。
Aiming at the problems of rapidly-exploring random tree(RRT)algorithm in obstacle avoidance path planning,such as weak adaptability to maps,poor sampling quality,many invalid nodes,long planning time and poor path quality,an improved RRT algorithm was proposed.Firstly,on the basis of the traditional RRT algorithm,the map complexity evaluation strategy was used to calculate the appropriate step size and bias probability,so as to realize the self-adaptation to different maps.Then,through the dynamic update strategy of sampling area,the random tree was sampled in the effective area to ensure the positive growth.After the sampling area was determined,the sampling point optimization strategy was adopted to improve the effectiveness of sampling points and make the random tree grow near the target points.Finally,the node reconnection strategy was used to optimize the planned initial obstacle avoidance path,and an obstacle avoidance path with fewer bending times was obtained.The feasibility of the improved RRT algorithm was verified in Python and MATLAB environments.The results showed that the improved RRT algorithm could quickly plan a collision-free high-quality path for maps with different complexity and when applied to robotic arms.The research results can provide reference for improving efficiency of robot obstacle avoidance path planning.
作者
冯垚
周志峰
沈亦纯
王立端
FENG Yao;ZHOU Zhifeng;SHEN Yichun;WANG Liduan(School of Mechanical and Automotive Engineering,Shanghai University of Engineering Science,Shanghai 201620,China;Shanghai Institute of Satellite Engineering,Shanghai 200240,China;ComNav Technology Ltd.,Shanghai 201801,China)
出处
《工程设计学报》
CSCD
北大核心
2023年第6期707-716,共10页
Chinese Journal of Engineering Design
基金
上海市2022年度“科技创新行动计划”优秀学术/技术带头人计划项目(22XD1433500)。
关键词
路径规划
快速搜索随机树算法
采样区域动态更新
采样点优化
节点重连
path planning
rapidly-exploring random tree algorithm
dynamic update of sampling area
sampling point optimization
node reconnection
