基于回溯的室内机器人完全遍历路径规划

Full Traversal Path Planning for Indoor Robot Based on Backtracking Method

完全遍历路径规划算法得到越来越多的关注。提出一种基于回溯的双向完全遍历路径规划算法,根据工作环境的纵横比,选择合适的局部遍历优先级采用牛耕法完成局部覆盖,采用改进的A*算法规划出从临界点到回溯点的无碰撞路径完成区域转移,实现工作环境的全覆盖,当回溯点个数为零时,机器人就完成了对地图的完全覆盖。仿真表明,与BA*和B-Theta*算法相比,在横向距离大于纵向距离如30×50的地图上,转弯次数减少15%,且能实现完全覆盖,回溯点的个数减少81%,重复路径长度减少5%。新算法有较好的参考和应用价值。

More and more attention has been paid to the full traversal path planning algorithm.Aiming at the problems of existing algorithms,this paper proposes a bi-directional full traversal path planning algorithm based on backtracking.According to the aspect ratio of the working environment,the algorithm selects the appropriate local traversal priority,uses the cattle ploughing method to complete the local coverage,and uses the improved A*algorithm to plan the collision free path from the critical point to the backtracking point to complete the area transfer,so as to realize the optimization of the working environment full coverage,when the number of backtracking points is zero,the robot completes the complete coverage of the map.Simulation results show that,compared with BA*and B-Theta*algorithms,the number of turns is reduced by 15%,the number of backtracking points is reduced by 81%,and the length of repeat path is reduced by 5%,when the horizontal distance is greater than the vertical distance,such as 30×50.The new algorithm has good reference and application value.