SIA OpenIR  > 机器人学研究室
三维动态环境下移动机器人路径规划方法研究
Alternative TitleMobile Robot Path Planning in Three-dimensional Dynamic Environment
陈洋1,2
Department机器人学研究室
Thesis Advisor韩建达 ; 赵新刚
ClassificationTP242
Keyword移动机器人 三维路径规划 线性规划 二次规划 增量学习 相对状态树
Call NumberTP242/C49/2012
Pages126页
Degree Discipline模式识别与智能系统
Degree Name博士
2012-05-24
Degree Grantor中国科学院沈阳自动化研究所
Place of Conferral沈阳
Abstract以无人飞机、无人飞艇、无人水下机器人等为代表的具有三维空间运动能力的移动机器人在现代人类生活中扮演越来越重要的角色。此类机器人的路径规划问题是在实际应用中首先需要解决的共性问题之一。路径规划问题通常指的是机器人从初始点出发,运动到目标位置或完成动态目标的追踪任务,同时需要避开任何可能的动态或静态的环境威胁,还要满足机器人本体的各种约束。由于具有三维运动能力的机器人运动轨迹不再局限于一个平面上,而是分布于三维的空间中,而且它们的目标点和障碍物通常也具有三维分布和三维运动的特点,这使得规划难度大大增加,如何规划出一条分布于三维空间的可行运动轨迹,是一个极具挑战性的问题。 目前通常的做法是采用二维规划技术对三维运动环境局部近似,难以考虑外在动态环境的复杂约束,亦很难实现基于已有机器人动力学模型的最优路径规划。另一方面,机器人在规划过程中缺乏对以往经验的记忆能力,即使遇上与过去相似甚至相同的环境,机器人依然需要重复计算路径点,不仅浪费计算资源,也影响了在线规划的实时性。本文针对以上问题展开深入研究,主要研究内容包括三维空间中机器人路径规划的最优化模型,以及在此基础上提出的路径规划经验的自主学习方法。 首先,在相对坐标系下提出一类基于数学最优化模型的三维路径规划方法。主要包括:基于线性规划模型和二次规划模型的三维路径规划方法。以移动机器人为参考点建立了相对坐标系,使用障碍物和目标的外接球推导了机器人在三维空间中运动的避障原则和追踪原则。通过理论分析,提出了避障原则和追踪原则的线性化约束表达式,建立了以追踪过程相对速度的正交分量为代价函数的线性规划模型。该模型使用了线性化技术,具有良好的实时性,有利于在实际系统中的应用。通过仿真和在飞行机器人中的实验研究验证了该方法的有效性。由于线性化过程可能引起计算误差,为了克服该缺点,对目标函数进一步改进,增加了追踪过程中相对距离的二次项,从而提出了基于相对距离和相对速度权重调节的二次规划优化模型。该模型的正确性在仿真实例中得到了验证。 其次,受到人类经验累积能力的启发,本文对机器人路径规划经验的自主学习方法展开了研究,建立了机器人自主学习体系结构,并提出了多种知识学习方法。提出了多种树型结构,详细描述了建立路径规划知识库的方法和过程。其中,采用K均值聚类引导类内搜索的方法建立了单层树型结构的知识库。通过借鉴KD树和IHDR树的快速检索能力,构建了具有多层树型结构的知识库。大量的仿真比较表明,采用IHDR方法具有更好的实时性。但是,无论是聚类引导搜索,还是KD树和IHDR树,这些方法在计算状态向量间的距离时都忽略了不同属性间的差异性,容易引起相似性计算出现较大的误差。为了克服这一不足,本文提出一种基于相对状态树的知识学习方法,通过计算不同属性非均匀离散化后的子状态列表,从而避免相似性计算时出现较大的误差,同时还能够保证树型结构的稳定性。当移动机器人在随机环境中学习时,通过采样当前状态并与各子状态列表进行匹配,从而使相对状态树的节点逐渐生长。无论是学习过程还是检索过程,该方法都具有线性阶的计算复杂度。仿真实验验证了该方法的有效性。
Other AbstractThe 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.
Language中文
Contribution Rank1
Document Type学位论文
Identifierhttp://ir.sia.cn/handle/173321/9402
Collection机器人学研究室
Affiliation1.中国科学院沈阳自动化研究所
2.中国科学院研究生院
Recommended Citation
GB/T 7714
陈洋. 三维动态环境下移动机器人路径规划方法研究[D]. 沈阳. 中国科学院沈阳自动化研究所,2012.
Files in This Item:
File Name/Size DocType Version Access License
三维动态环境下移动机器人路径规划方法研究(3757KB) 开放获取LicenseApplication Full Text
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[陈洋]'s Articles
Baidu academic
Similar articles in Baidu academic
[陈洋]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[陈洋]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.
 

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