采用碰撞测试和回归机制的非完整约束机器人快速扩展随机树运动规划

摘要

An improved rapidly-exploring random trees (RRT) algorithm is proposed to deal with the motion planning for non-holonomic mobile robots. The RRT algorithms using a bias towards the goal while choosing a random config-uration, that will leads to the problem of local minima. Therefore, a novel method called collision-test and regression mechanism (CR) mechanism is presented, in which the collision detection mechanism and the regression testing mechanis-m are combined to enable the robot to escape from the local minima.The CR mechanism takes the global constraints into consideration, avoids exploring the directions which have been explored repeatedly.The repeatedly regression testing and detection for obstacle avoidance to the edge nodes are prevented in the CR.The ultimate goal of the algorithm is to im-prove the real-time performance of the planner, especially in the environment with highly-constraints. Simulation results of several improved RRT algorithms in the environment which is apt to generate local minima problems, verifies the proposed algorithm can improve the real-time performance significantly without obviously negative influences.%本文提出一种改进的快速扩展随机树(rapidly-exploring random trees, RRT)运动规划方法,用于非完整微分约束下的机器人运动规划。针对类似目标偏好与双向RRT(bi-directional RRT, bi-RRT)等目标区域导向的RRT运动规划所存在的局部极小问题,结合回归检测与碰撞检测机制,设计了一种碰撞检测与回归机制(collision-test and regression mechanism, CR)机制。该方法使得机器人在规划过程中能获取到全局障碍物信息,从而避免对已扩展节点的重复搜索,以及重复对边缘节点的回归测试和避障检测。该机制使得机器人可加快跳出局部极小区域,提高运动规划实的时性。将改进的RRT运动算法在容易产生局部极小值的环境中仿真测试,结果表明该算法在不显著影响其他性能的前提下,可以明显提高规划的实时性。