基于典型路径库的移动机器人智能路径规划算法的研究与实现

发布时间：2018-07-03 12:45

本文选题：路径规划 + 移动机器人　；参考：《北京交通大学》2017年硕士论文

【摘要】：路径规划是移动机器人完成任务过程中需要解决的主要问题之一。所谓路径规划是根据所处环境和运动约束条件生成一条或几条从起始位置到终止位置之间的最优路径。对于大规模路径规划问题,需要快速生成多条符合要求的路径，而传统的全局路径规划算法执行效率较低,不能够满足上述问题的要求。通过分析,我们发现移动机器人所处的不同场景间存在相似或者部分相似的情况,相似区域中移动机器人的运动方式和运动轨迹大致相同。这使得利用已有场景信息和路径信息,优化生成新路径成为可能。本文围绕相似场景下的路径规划问题展开研究，提出了一种基于典型路径库的移动机器人智能路径规划算法。该算法基于已有的场景和路径信息,分析路径的特征属性形成知识,在给定的新场景中,利用路径知识快速生成多条符合期望的路径。算法由场景建模、场景相似性度量、相似路径特征提取、路径优化生成、路径评价等多个模块组成。本文的主要工作包含以下几个方面:(1)针对场景建模问题,本文研究了相似场景的特征属性,采用聚类算法根据场景内站位的聚集程度进行区域划分,将场景划分结果作为场景描述的主要依据。(2)针对场景相似性度量问题,本文将场景抽象为多边形区域，，利用多边形顶点匹配算法的思想,计算场景间的相似度,并使用动态规划的方法求解出两个场景间最大相似区域匹配序列。(3)针对典型路径库建立问题,本文提出“三段式”路径构建模型。本文从相似区域中提取相似路径,通过局部与全局坐标映射关系,结合车式移动机器人的运动学特性,确定需求场景中的关键坐标点,从而建立典型路径库。(4)针对最优路径选择问题,本文综合考虑多种因素,提出路径评价函数模型。通过实验验证,确定各个参数的权重比例,从而对典型路径库中的多条参考路径进行评价排序。本文根据所提出的算法,搭建了场景布局和路径规划实验平台。通过大量仿真实验,验证了该算法的可行性。实验结果表明本文提出的算法对于相似场景中大规模路径规划问题,能够显著提高效率,解决实际问题。
[Abstract]:Path planning is one of the main problems that need to be solved in the process of mobile robot task completion. The so-called path planning is to generate one or more optimal paths from the starting position to the terminating position according to the environment and motion constraints. For the large-scale path planning problem, it is necessary to quickly generate many paths that meet the requirements. However, the traditional global path planning algorithm is inefficient and can not meet the requirements of the above problems. Through analysis, we find that there are similar or partial similarities between different scenes of mobile robot, and the motion mode and trajectory of mobile robot in similar region are approximately the same. This makes it possible to optimize the generation of new paths using existing scenario information and path information. In this paper, an intelligent path planning algorithm for mobile robots based on typical path library is proposed. Based on the existing scene and path information, the algorithm analyzes the characteristic attributes of the path to form knowledge. In a given new scenario, the path knowledge is used to quickly generate multiple paths that meet the expectations. The algorithm consists of several modules, such as scene modeling, scene similarity measurement, similarity path feature extraction, path optimization generation, path evaluation and so on. The main work of this paper includes the following aspects: (1) aiming at the problem of scene modeling, this paper studies the characteristic attributes of similar scenes, and uses clustering algorithm to divide the regions according to the degree of aggregation of the stations in the scene. The result of scene partitioning is regarded as the main basis of scene description. (2) aiming at the problem of scene similarity measurement, this paper abstracts the scene into polygon region and calculates the similarity between scenes by using the idea of polygon vertex matching algorithm. Dynamic programming is used to solve the matching sequence of the two scenes. (3) aiming at the problem of establishing a typical path library, a "three-segment" path construction model is proposed in this paper. In this paper, the similarity path is extracted from the similar region, and the key coordinate points in the requirement scene are determined by mapping the local and global coordinates and combining the kinematics characteristics of the vehicular mobile robot. In order to establish a typical path library. (4) aiming at the problem of optimal path selection, this paper proposes a path evaluation function model considering a variety of factors. Through experimental verification, the weight ratio of each parameter is determined, and then the multiple reference paths in the typical path library are evaluated and sorted. According to the proposed algorithm, a scene layout and path planning experimental platform is built in this paper. The feasibility of the algorithm is verified by a large number of simulation experiments. Experimental results show that the proposed algorithm can significantly improve the efficiency and solve the practical problems for large-scale path planning problems in similar scenarios.
【学位授予单位】：北京交通大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP242

【参考文献】