中国科学院沈阳自动化研究所机构知识库
Advanced  
SIA OpenIR  > 机器人学研究室  > 学位论文
题名: 三维动态环境下移动机器人路径规划方法研究
其他题名: Mobile Robot Path Planning in Three-dimensional Dynamic Environment
作者: 陈洋
导师: 韩建达 ; 赵新刚
分类号: TP242
关键词: 移动机器人 ; 三维路径规划 ; 线性规划 ; 二次规划 ; 增量学习 ; 相对状态树
索取号: TP242/C49/2012
学位专业: 模式识别与智能系统
学位类别: 博士
答辩日期: 2012-05-24
授予单位: 中国科学院沈阳自动化研究所
学位授予地点: 中国科学院沈阳自动化研究所
作者部门: 机器人学研究室
中文摘要: 以无人飞机、无人飞艇、无人水下机器人等为代表的具有三维空间运动能力的移动机器人在现代人类生活中扮演越来越重要的角色。此类机器人的路径规划问题是在实际应用中首先需要解决的共性问题之一。路径规划问题通常指的是机器人从初始点出发,运动到目标位置或完成动态目标的追踪任务,同时需要避开任何可能的动态或静态的环境威胁,还要满足机器人本体的各种约束。由于具有三维运动能力的机器人运动轨迹不再局限于一个平面上,而是分布于三维的空间中,而且它们的目标点和障碍物通常也具有三维分布和三维运动的特点,这使得规划难度大大增加,如何规划出一条分布于三维空间的可行运动轨迹,是一个极具挑战性的问题。 目前通常的做法是采用二维规划技术对三维运动环境局部近似,难以考虑外在动态环境的复杂约束,亦很难实现基于已有机器人动力学模型的最优路径规划。另一方面,机器人在规划过程中缺乏对以往经验的记忆能力,即使遇上与过去相似甚至相同的环境,机器人依然需要重复计算路径点,不仅浪费计算资源,也影响了在线规划的实时性。本文针对以上问题展开深入研究,主要研究内容包括三维空间中机器人路径规划的最优化模型,以及在此基础上提出的路径规划经验的自主学习方法。 首先,在相对坐标系下提出一类基于数学最优化模型的三维路径规划方法。主要包括:基于线性规划模型和二次规划模型的三维路径规划方法。以移动机器人为参考点建立了相对坐标系,使用障碍物和目标的外接球推导了机器人在三维空间中运动的避障原则和追踪原则。通过理论分析,提出了避障原则和追踪原则的线性化约束表达式,建立了以追踪过程相对速度的正交分量为代价函数的线性规划模型。该模型使用了线性化技术,具有良好的实时性,有利于在实际系统中的应用。通过仿真和在飞行机器人中的实验研究验证了该方法的有效性。由于线性化过程可能引起计算误差,为了克服该缺点,对目标函数进一步改进,增加了追踪过程中相对距离的二次项,从而提出了基于相对距离和相对速度权重调节的二次规划优化模型。该模型的正确性在仿真实例中得到了验证。 其次,受到人类经验累积能力的启发,本文对机器人路径规划经验的自主学习方法展开了研究,建立了机器人自主学习体系结构,并提出了多种知识学习方法。提出了多种树型结构,详细描述了建立路径规划知识库的方法和过程。其中,采用K均值聚类引导类内搜索的方法建立了单层树型结构的知识库。通过借鉴KD树和IHDR树的快速检索能力,构建了具有多层树型结构的知识库。大量的仿真比较表明,采用IHDR方法具有更好的实时性。但是,无论是聚类引导搜索,还是KD树和IHDR树,这些方法在计算状态向量间的距离时都忽略了不同属性间的差异性,容易引起相似性计算出现较大的误差。为了克服这一不足,本文提出一种基于相对状态树的知识学习方法,通过计算不同属性非均匀离散化后的子状态列表,从而避免相似性计算时出现较大的误差,同时还能够保证树型结构的稳定性。当移动机器人在随机环境中学习时,通过采样当前状态并与各子状态列表进行匹配,从而使相对状态树的节点逐渐生长。无论是学习过程还是检索过程,该方法都具有线性阶的计算复杂度。仿真实验验证了该方法的有效性。
英文摘要: The mobile robot, which is able to work in three-dimensional space, plays more and more important roles in modern society. Unmanned aerial vehicles, unmanned balloons and autonomous underwater vehicle are all this kind robots. How to plan the robot path is one of the common problems before they are applied in practices. Generally speaking, path planning is defined that the robot starts from the initial position and gets close to the end point or the moving target, avoiding the potentially static or moving threat, as well as satisfying various constraints of the robot itself. As the fact that the robot trajectory is distributed in three-dimensional space instead of two-dimensional plane, which is the same to their targets and threats, it is a challenging problem to plan a feasible trajectory in three-dimensional space. Currently, the three-dimensional environment is often approximated by two-dimensional planning technology which makes it hard to consider the complex constraints of the external environment. As a result, it becomes impossible to solve the optimal path planning problem only depending on the accurately modeling of the robot dynamics. On the other hand, the robot has no memory during the planning process which is a nightmare that the robot has to re-plan its path points exactly even if it faces the similar environment, or much more, the same as that before encountered. Consequently, the re-planning not only takes up the computer resources, but also undermines the real time planning to a large extent. To solve the above problems, the study lays emphasis on two aspects, i.e., the robot optimal model of the path planning in three-dimensional space and the autonomous learning algorithm of the path planning knowledge. First, this paper proposes a kind of mathematic optimal model of path planning in three-dimensional space based on the relative coordination, including the linear program and quadratic program. Relative coordination is established on the robot point. The avoidance principle and the pursuit principle, as well as their linearizations are derived based on the external ball of the obstacles as well as the target through theoretical analysis. The final linear program is formulated on the orthogonal decomposition of the velocity relative to the target. As linearization has been adopted in the model, the algorithm shows high efficiency which has been verified by simulations and experiments. However, the linearization is likely to incur computational errors. In order to overcome the shortcomings, quadratic term of the distance relative to target has been added into the objective function. Then, a quadratic program model is built on the trade-off adjustment between the relative distance and relative velocity. The model is verified by simulations. Second, inspired by human intelligence of empirical accumulation, this paper has investigated the robot autonomous learning of the three-dimensional path planning. Based on robot autonomous planning framework, several tree structures have been proposed to establish the path planning knowledge library. K-mean-clustering is used to guide the search strategy in order to build a single-level-tree-based knowledge base. Besides, taking advantage of the capabilities of KD tree and IHDR tree in fast retrieving, the multi-level-tree-based knowledge base is built. Several simulations prove that the method based on IHDR tree has higher efficiency than others. However, not only the searching algorithm guided by clustering, but also the algorithms of KD tree and IHDR tree ignore the differences among the different attributes in the similarity calculation between state vectors. Those approaches frequently incur large errors on similarity calculating. In order to overcome the deficiency, this paper proposes a method called Relative State Tree which is able to overcome the problem and achieve stable tree structure by computing the sub-state lists of different attributes in the manner of non-uniform discretization. When the robot learning in dynamic environment, the current relative states are sampled and then matched in the corresponding sub-state list. After that, a new node is generated in the relative state tree. Both the learning and retrieving procedures have linear computing complex. A large number of simulations demonstrate the validity of the method.
语种: 中文
产权排序: 1
内容类型: 学位论文
URI标识: http://ir.sia.cn/handle/173321/9402
Appears in Collections:机器人学研究室_学位论文

Files in This Item:
File Name/ File Size Content Type Version Access License
三维动态环境下移动机器人路径规划方法研究.pdf(3757KB)----限制开放 联系获取全文

Recommended Citation:
陈洋.三维动态环境下移动机器人路径规划方法研究.[博士学位论文].中国科学院沈阳自动化研究所.2012
Service
Recommend this item
Sava as my favorate item
Show this item's statistics
Export Endnote File
Google Scholar
Similar articles in Google Scholar
[陈洋]'s Articles
CSDL cross search
Similar articles in CSDL Cross Search
[陈洋]‘s Articles
Related Copyright Policies
Null
Social Bookmarking
Add to CiteULike Add to Connotea Add to Del.icio.us Add to Digg Add to Reddit
所有评论 (0)
暂无评论
 
评注功能仅针对注册用户开放,请您登录
您对该条目有什么异议,请填写以下表单,管理员会尽快联系您。
内 容:
Email:  *
单位:
验证码:   刷新
您在IR的使用过程中有什么好的想法或者建议可以反馈给我们。
标 题:
 *
内 容:
Email:  *
验证码:   刷新

Items in IR are protected by copyright, with all rights reserved, unless otherwise indicated.

 

 

Valid XHTML 1.0!
Copyright © 2007-2016  中国科学院沈阳自动化研究所 - Feedback
Powered by CSpace