SIA OpenIR  > 机器人学研究室
动态环境下多移动机器人自主规划方法研究
Alternative TitleResearch on Autonomous Planning Methods of Multiple Mobile Robots in Dynamic Environment
杨丽英1,2
Department机器人学研究室
Thesis Advisor吴成东 ; 韩建达
ClassificationTP242
Keyword多移动机器人 路径规划 任务分配 动态环境
Call NumberTP242/Y28/2011
Pages107页
Degree Discipline模式识别与智能系统
Degree Name博士
2011-06-01
Degree Grantor中国科学院沈阳自动化研究所
Place of Conferral沈阳
Abstract动态不确定环境中多移动机器人自主规划方法是多移动机器人系统研究的重要内容之一。如何将机器人自身的本体(动力学)能力,以及周边动态环境作为约束,使多个机器人以团队的形式,优化的完成系统的所有任务是目前有待深入研究的主要问题。针对这些问题,本文提出能够同时求解路径规划和任务分配的自主规划方法,旨在逐步实现具有本体动力学和动态环境约束情况下的优化算法及分配算法实用性和最优性的统一。 首先,在动态环境下移动机器人的目标追逐避碰问题中,针对基于MILP方法的避障模型,引入整数变量描述类方形障碍物的避碰约束,提出一种选取整变量内点的等高面法求解MILP避障追逐模型,通过判断机器人与障碍物的方位来给出内点0-1整变量,该求解方法使得MILP求解变成LP求解。当车辆与障碍物增加时,该求解方法大大减少了模型的求解变量,提高了问题的求解效率。仿真结果验证了该求解方法的实用性和有效性。 其次,对类圆形障碍物,提出了单一线性规划(LP)切线或切面避障规则。该规则中,对小车与其追逐目标所确定的直线,与障碍物两者之间的方位关系进行分析,确定所需的避障线或面,从而构成线性避障约束,因此,对每个障碍物只需建立一个线性约束,不仅大大简化了二维或三维的避障模型,而且各障碍物的避障约束条件彼此相容。最后,仿真结果验证了算法的实用性和有效性。 第三,对于多机器人自主规划中存在的“机器人-目标”配对问题,提出“代价矩阵”方法描述机器人与目标的分配关系,针对多机器人多目标追逐的典型应用问题,提出一种极大极小任务分配准则,期望系统能够以最短时间完成对所有目标的追逐。对于具有等机器人等目标的追逐问题分配模型,提出一种“矩阵作业法”求解极大极小分配准则下的任务分配问题。对于“机器人数目小于目标数目”和“机器人数目大于目标数目”的两种目标追逐问题分配模型,在求解时,继承了矩阵作业法的求解思想,提出“行优先选取法”求解极大极小分配准则下的机器人与目标数目不相等的任务分配问题。理论分析和数值试验表明这两种求解方法可以对极大极小分配准则下的任务分配问题有效地提供最优解。 最后,以多机器人多目标追逐问题为研究对象,提出一种综合考虑障碍物、目标和机器人本体的全局代价函数,以构成用于求解的代价矩阵。分别对“机器人数目等于目标数目”,“机器人数目小于目标数目”和“机器人数目大于目标数目”的三种任务规划情况从“异质”和“同质”两个角度在MATLAB环境下进行仿真实验,验证路径规划算法和任务分配算法的有效性和实用性。
Other AbstractAutonomous planning of multiple mobile robots in dynamic environment is an important aspect in the multiple mobile robots research. How to complete the whole mission optimally as a team under both the robot’s dynamic constraints and the environments constraints are the main problems to be further studied in multiple robots system. Based on these problems, this paper proposed an autonomous planning method tried to find a way to solve the path planning and task assignment problems optimally and efficiently under the above constraints. Firstly, for obstacle-avoided pursuit problem of moving robots in dynamic environment, in the mixed integer linear programming (MILP) based obstacle-avoided model, the integer variables are introduced to describe the square-shaped obstacle-avoided constraints. In this paper, a method of isometric plane method selecting integer variables of inner point is proposed to solve MILP obstacle-avoided model according to the relative position between vehicles and obstacles. Therefore, the proposed solution method turns the MILP problem into LP problem. So that this method can reduce the variables need to be solved and improve the computational efficiency greatly when increasing the vehicles, obstacles. Secondly, a single linear programming (LP) tangential line or plane obstacle-avoided rule is proposed to avoid the obstacles shaped like circle or ball. In this rule, the obstacle-avoided tangential line or plane is determined by analyzing the location relationship between the line, which is fixed by vehicle, its pursuing target, and the obstacle. After confirming the tangential line or plane, the obstacle-avoided constraints can be constructed. For each obstacle, only one linear constraint is needed, which will simplify the obstacle-avoided model greatly in 2-D and 3-D environment, and each obstacle’s constraints are compatible. Finally, simulation results show the practicability and effectiveness of the proposed method. Thirdly, with respect to the “robot-target” pair assignment problem in autonomous planning of multiple mobile robots, “cost matrix” method is introduced to describe the assignment relationship of robots and targets A minimax assignment criterion is formed to solve the typical problem of multiple robots multiple targets pursuit problem with the expectation of catch all the targets as fast as possible. For an assignment model with equal robots and equal targets, the Operations on Matrix method is proposed to solve this kind of task assignment problem under the minimax criterion. For another two assignment models, “robot number is less than target number” and “robot number is more than target number”, a method of the selection algorithm of precedence rows following the idea of the Operations on Matrix is proposed to solve the above assignment models under the minimax criterion. Theoretical analyses and numerical tests show that the solution methods can find the optimal solution efficiently under the minimax criterion. Finally, in the study of multi-robots multi-target pursuit problem, a global cost function considering the obstacles, the targets and the robots comprehensively is given to construct the cost matrix. From the view point of the homologous and heterogeneous, the simulations are carried out for three kinds of mission planning, which are “robot number equals to target number”, “robot number is less than target number” and “robot number is more than target number” in multiple robots system. The simulation results testify the effectiveness and the practicability of proposed path planning and task assignment methods.
Language中文
Contribution Rank1
Document Type学位论文
Identifierhttp://ir.sia.cn/handle/173321/9374
Collection机器人学研究室
Affiliation1.中国科学院沈阳自动化研究所
2.中国科学院研究生院
Recommended Citation
GB/T 7714
杨丽英. 动态环境下多移动机器人自主规划方法研究[D]. 沈阳. 中国科学院沈阳自动化研究所,2011.
Files in This Item:
File Name/Size DocType Version Access License
动态环境下多移动机器人自主规划方法研究.(9521KB) 开放获取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.