摘要
提出一种结合莱维飞行和概率路线图法(Lévy-probabilistic roadmap,LPRM)的路径规划算法。将莱维飞行方法应用于窄道采样,障碍物中的随机点通过莱维飞行走至自由空间,并延长碰撞测试来确保采样点位于窄道内,提升狭窄区域的采样质量与效率;为避免大量无效点的生成,在采样前先对地图进行预处理,膨胀障碍并对其进行边界提取,根据边界信息计算狭窄区域采样点数量,保证了全图采样的合理分布;进一步考虑移动机器人的实际工作情况,采用分段贝塞尔曲线对路径轨迹进行优化使其符合运动学约束,提高移动机器人的机动性。仿真实验在不同环境地图下对比了LPRM、传统概率路线图(PRM)和桥测试3种算法,结果表明LPRM算法相较两者在单一窄道环境下规划效率分别提升35.1%和32.2%,在复杂环境下其规划效率分别提升32.9%和15.5%,且提前400和100个采样点达到收敛,规划效率和成功率显著提高,总体耗时更短、路径更优,能减少移动机器人本身的能耗,提高整体工作效率。
A path planning algorithm combining Lévy flight and probabilistic roadmap methods(LPRM) is proposed. The Lévy flight method is applied to narrow area sampling, random points in obstacles are walked to free space by Lévy flight, and the collision test is extended to ensure that the sampling points are located in the narrow area, which improves the sampling quality and efficiency in narrow areas. To avoid the generation of invalid points, the map is pre-processed before sampling, the obstacles are inflated and their boundaries are extracted, and the number of sampling points in narrow areas is calculated based on the boundary information, ensuring a reasonable distribution of sampling across the map. Further, considering the actual working condition of the mobile robot, the path trajectory is optimized by using segmented Bessel curves to conform to its kinematic constraints and improve the mobility of the mobile robot. The simulation experiments compare three algorithms, LPRM, traditional PRM and bridge test, under different environment maps, and the results show that the LPRM algorithm improves the planning efficiency by 35.1% and 32.2% respectively compared to both in a single narrow area environment, and its planning efficiency improves by 32.9% and 15.5% respectively in a complex environment, and reaches convergence 400 and 100 sampling points earlier, the planning efficiency and success rate improved significantly, with shorter overall time consumption and better paths, which can reduce the energy consumption of the mobile robot itself and improve the overall work efficiency.
作者
徐大也
胡立坤
王小勇
刘恒佳
Xu Daye;Hu Likun;Wang Xiaoyong;Liu Hengjia(School of Electrical Engineering,Guangxi University,Nanning 530004,China)
出处
《国外电子测量技术》
北大核心
2023年第2期1-8,共8页
Foreign Electronic Measurement Technology
基金
国家自然科学基金(61863002)项目资助
关键词
路径规划
轨迹优化
窄道采样
概率路线图法
莱维飞行
path planning
trajectory optimization
narrow area sampling
probabilistic roadmap algorithm
Lévy flight
