非完整移动机器人运动规划算法研究

【作者】 徐娜；

【导师】 孔庆生；

【作者基本信息】 复旦大学 ， 电路与系统， 2012， 硕士

【摘要】 移动机器人运动规划研究如何设计适当的控制输入使系统安全无碰的从起始点运动到目标点的问题。由于非完整约束广泛存在于轮式机器人、空间机器人等移动机器人系统中,运动规划除了需要考虑位姿空间中由障碍物引起的约束外还需要考虑非完整性引起的运动受限问题,因此非完整约束给移动机器人运动规划问题带来了很大的挑战。本文以受非完整约束的移动机器人为研究对象,主要研究满足非完整约束条件的运动规划算法。具体工作和创新点如下：1.详细阐述非完整约束的定义、非完整系统的判定准则及建立非完整系统模型的方法；给出车型机器人、带推力器的平面板、差分驱动机器人等典型非完整移动机器人的运动学模型,为后续运动规划算法的研究建立基础。2.对基于随机采样的快速搜索随机树算法(Rapidly-exploring Random Trees, RRT)进行详细分析,针对其全局均匀搜索导致算法收敛速度较慢问题引入目标偏向思想,并选择计算复杂度低的距离参数对最近邻域搜索进行近似,提高算法的搜索速度。提出基于栅格划分的搜索空间自由度估算因子概念,指引随机树搜索无障碍空间。改进控制输入的选择机制,提高树的搜索效率。改进后的RRT算法对于易陷入局部最小、存在狭窄通道等复杂环境中的运动规划问题也能有效解决。3.针对全局环境未知的运动规划问题,将滚动窗口算法与改进的RRT算法结合,提出简化的子目标映射法则提高算法效率,通过选择关键状态点解决滚动窗口法易产生振荡的问题。通过仿真实验比较了本文提出的改进算法与相关传统算法的性能,证明本文提出算法的有效性和高效性。更多还原

【Abstract】 Motion planning for mobile robot is the problem of how to design an appropriate control-input to make the system move from the starting point to the goal point safely and collision-freely. Nonholonomic constraints are widely present in the mobile robot system, like wheeled robots, space robots and so on. For this kind of robot, the limited range of motion caused by nonholonomic constraints should be taken into account in addition to the need of considering the configure-space constraints caused by obstacles. Therefore nonholonomic constraints have brought great challenges to the mobile robot motion planning problem.This paper is focused on solving motion planning problem for mobile robot under nonholonomic constraints. The main contribution of this work is:1. Elaborated on the definition of nonholonomic constraints and how to establish the kinematic model for non-complete system. Several typical models of mobile robots under nonholonomic constraints are given for the research of motion planning algorithm follow-up.2. Analyzed the Rapidly-exploring Random Trees (RRT) algorithm and proposed four improvements to this algorithm. In order to reduce unnecessary costs caused by uniformly random searching, the idea of goal bias is introduced in this paper; A new distance parameter of low computational complexity is selected to advance the calculation speed; An preprocessing stage is proposed to provide the estimate index on the workspace’s free volumes which can lead the tree to explore free space tendentiously and improve the extensibility; Selection mechanism of control-input is improved to advance the exploring speed. The improved RRT algorithm is valid and efficient even when other planners get into scrapes in some complex environment.3. Combined the improved RRT algorithm and the rolling windows method to solve motion planning in globally unknown environment. A simplified sub-goal determination strategy is proposed to improve the efficiency of the algorithm. The idea of critical state is used to solve the problem that the rolling window method might cause oscillations sometimes.Compared the improved algorithm to some traditional methods; the simulation results verified the validity and advantage of the proposed algorithm.更多还原