We use cookies to improve your experience with our site.

一种推广的无需配置空间计算的实时机器人障碍物回避方法

A Generalized Real-Time Obstacle Avoidance Method Without the Cspace Calculation

  • 摘要: 机器人规划问题是随着人工智能及机器人这两门学科的发展而提出的,简言之,就是用数学的方法为机器人在多种可行路径中(如果存在)找到一条满足约束 ( 不碰障碍物 ) 的最优解(如路径最短)。机器人规划问题被抽象为下列实际需求:第一,给机器人及障碍物一个数学描述;第二,找出一个数学搜索方法以便发现一条可行的路径从起始点到达终点。第一个需求属于计算机视觉,计算机 CAD 和计算机图形学中的问题,第二个则是优化理论(处理连续变量的运筹学或处理数、图形等的离散数学)要回答的问题。 为解决机器人规划问题,传统方法的一个重要思想是把机器人压缩为一个点,同时把障碍物相应放大,得到一组 Configuration Space 中的障碍物,然后机器人规划问题变为利用图论中的搜索方法寻找最短路径。其根本问题有二:第一,这一方法只适用于机器人及障碍物形状均为 2D 空间的多边形,无法推广到 3D 空间的多面体和其它形状的 3 D 空间物体,从而表现为对机器人及障碍物形状敏感;第二,这一方法只适用于机器人平动,而实际机器人都必然要包括转动的要求。形状敏感问题也是现今诸多新方法研究中无法克服的缺点。 本论文的第一作者与其英国同事在世界上首次提出了把优化方法用于机器人规划问题,即建立一个不等式的约束集合来描述机器人的不碰撞条件,用优化方法进行搜索。他们在早期的系列研究中:1)提出了更一般的非线性优化问题( Generalized constrained optimization problem, 简称 GCOP ),即约束间的逻辑关系不但有 “ 与( AND ) ” 的关系,而且还有“ 或(OR)” 的关系,并给出了在实际应用中可行的数学求解方法;2)利用了计算机图形学中的 Constructive solid geometry (CSG) 方法来构建障碍物的不等式表述;3)将计算机 CAD 中的插值方法与优化理论结合(半无穷维优化),克服了路径规划问题中的局部最小值问题。本论文是在作者以前的研究成果基础上,引人了第二类障碍物的概念及数学不等式 “ 或 ” 表达,将障碍物的表示推向更一般,克服了路径规划方法对机器人及障碍物形状敏感问题。本论文详细介绍了相关的知识背景以及将 GCOP 优化求解方法应用于机器人路径规划(含两类障碍物)的原理和算法设计,并给出了模拟实验结果。 本论文是作者关于机器人规划问题创新研究的重要组成部分。传统的方法都没有突破一个关键概念,即 Cspace 空间障碍物的概念,因此也无法克服概念本身所带来的弊端,本论文与以前的工作结合在一起形成了一套独特的理论体系,避免了 Cspace 空间障碍物的计算,克服了机器人路径规划传统方法诸多难以克服的问题,具有重要的理论和实际意义。

     

    Abstract: An important concept proposed in the early stage of robot path planning field is the shrinking of a robot to a point and meanwhile the expanding of obstacles in the workspace as a set of new obstacles. The resulting grown obstacles are called the Configuration Space (Cspace) obstacles. The find-path problem is then transformedinto that of finding a collision-free path for a point robot among the Cspace obstacles. However, the research experiences have shown that the Cspace transformation is very hard when the following situations occur: 1) both the robot and obstacles are not polygons, and 2) the robot is allowed to rotate. This situation gets even worse when the robot and obstacles are three dimensional (3D) objects with various shapes. For this reason, direct path planning approaches without the Cspace transformation is quite useful and expected. Motivated by the practicalrequirements of robot path planning, a generalized constrained optimization problem (GCOP) with not only logic AND but also logic OR relationships was proposed and a mathematical solution developed previously. This paper inherits the fundamental ideas of inequality and optimization techniques from the previous work, converts the obstacle avoidance problem into a semi-infinite constrained optimization problem with the help of the mathematical transformation, and proposes a direct path planning approach without Cspace calculation, which is quite different from traditional methods. To show its merits, simulation results in 3D space have been presented.

     

/

返回文章
返回