D044机器人避障问题.doc
《D044机器人避障问题.doc》由会员分享,可在线阅读,更多相关《D044机器人避障问题.doc(30页珍藏版)》请在文库网上搜索。
1、机器人避障问题摘要针对机器人避障问题,本文分别建立了机器人从区域中一点到达另一点的避障的最短路径、最短时间路径的非线性0-1整数规划模型。同时,本文为求带有NP属性的非线性0-1整数规划模型,构建了有效启发式算法,利用MATLAB软件编程,求得了OA、OB、OC、OABAC的最短路径,同时得到了OA的最短时间路径,求得的各类最短路径均是全局最优。针对区域中一点到达另一点的避障的最短路径问题,首先,本文证明了圆弧位置设定在需要绕过障碍物的顶角上,且圆弧半径为10个单位时,能够使得机器人从区域中一点到达另一点的行进路径最短;其次,本文将最短路径选择问题转化成了最短路径的优选问题,根据避障条件,建立
2、了具有较高普适性的避障最短路径的优化模型。为便于求解,本文巧妙地将此优化模型转化成了以可行路径不与障碍物边界相交、不与圆弧相交为约束条件,以机器人从区域中一点达到另一点避障路径最短为目标的0-1规划模型;再次,本文构建了两种有效的启发式算法,利用MATLAB软件编程求得了OA、OB、OC、OABAC的最短路径,最短路径长分别为471.0372、853.7001、1088.1952、2725.1596,其中O-A的最短路径为(0,0)(70.5063,213.1405) (75.975,219.1542)(300,300),对应圆弧的圆心坐标为(80,210),OB的最短路径,对应圆弧的圆心坐标
3、:(60,300)、(150,435)、(220、470)、(220,530)、(150,600), OC经过的圆心:(410,100)、(230,60)、(720,520),(720,600),(500,200), OABCO经过的圆心:(410,100),(230,60), (80,210),(220,530),(150,600),(270,680),(370,680), (430,680),(670,730),(540,730),(720,520),(720,600),(500,200)。针对最短时间路径问题,我们建立了从o点出发到任意目标点的0-1非线性整数规划模型,同时针对题意要求,
4、具体构建了从o点出发到A的最短时间路径的0-1非线性整数规划模型,利用LINGO软件求解,获得了机器人从o点出发,到达A的最短时间路径,求得最短时间路径下转弯半径为12.9885 ,同时最短时间路径时间长为94.2283个单位。相应圆弧的圆心坐标为(82.1414,207.9153),两切点坐标分别为(69.8045,211.9779)、(77.7492,220.1387)。关键字:机器人避障 启发式算法 0-1规划模型 一、问题重述在一个800800的平面场景图,在原点O(0, 0)点处有一个机器人,它只能在该平面场景范围内活动。图中有12个不同形状的区域是机器人不能与之发生碰撞的障碍物,障
5、碍物的数学描述如下表:编号障碍物名称左下顶点坐标其它特性描述1正方形(300, 400)边长2002圆形圆心坐标(550, 450),半径703平行四边形(360, 240)底边长140,左上顶点坐标(400, 330)4三角形(280, 100)上顶点坐标(345, 210),右下顶点坐标(410, 100)5正方形(80, 60)边长1506三角形(60, 300)上顶点坐标(150, 435),右下顶点坐标(235, 300)7长方形(0, 470)长220,宽608平行四边形(150, 600)底边长90,左上顶点坐标(180, 680)9长方形(370, 680)长60,宽12010
6、正方形(540, 600)边长13011正方形(640, 520)边长8012长方形(500, 140)长300,宽60在图1的平面场景中,障碍物外指定一点为机器人要到达的目标点(要求目标点与障碍物的距离至少超过10个单位)。规定机器人的行走路径由直线段和圆弧组成,其中圆弧是机器人转弯路径。机器人不能折线转弯,转弯路径由与直线路径相切的一段圆弧组成,也可以由两个或多个相切的圆弧路径组成,但每个圆弧的半径最小为10个单位。为了不与障碍物发生碰撞,同时要求机器人行走线路与障碍物间的最近距离为10个单位,否则将发生碰撞,若碰撞发生,则机器人无法完成行走。机器人直线行走的最大速度为个单位/秒。机器人转
7、弯时,最大转弯速度为,其中是转弯半径。如果超过该速度,机器人将发生侧翻,无法完成行走。请建立机器人从区域中一点到达另一点的避障最短路径和最短时间路径的数学模型。对场景图中4个点O(0, 0),A(300, 300),B(100, 700),C(700, 640),具体计算:(1) 机器人从O(0, 0)出发,OA、OB、OC和OABCO的最短路径。(2) 机器人从O (0, 0)出发,到达A的最短时间路径。注:要给出路径中每段直线段或圆弧的起点和终点坐标、圆弧的圆心坐标以及机器人行走的总距离和总时间。二、问题分析2.1求取最短路径的分析本问题要求机器人从区域中一点到达另一点的避障最短路径。机器
8、人只要做到转弯时的圆弧半径最小为10个单位、与障碍物最近距离单时刻保持大于10个单位,那么可行走的路径就有无数条,若想求得机器人从区域中一点到达另一点的避障最短路径,则需要建立避障的最短路径模型,而建立避障的最短路径模型有一定难度。根据对问题的分析,我们认为可以从简单做起,先确定小范围内最短路径条件,如圆弧位置的影响,圆弧半径的大小,避免与障碍物碰撞条件等,通过确定最短路径条件来建立避障的最短路径模型。对于最短路径的求取,我们可以通过确定穷举原则,利用穷举法来求解,当然也可以通过构建启发式算法的进行求解。2.2最短时间路径的分析对于要建立最短时间路径模型来说,我们容易知道影响的因素有直线行走速
9、度、转弯速度,同时还需要考虑使得最短时间路径条件,如圆弧位置(坐标)的影响,圆弧半径的大小,避免与障碍物碰撞条件等。对于直线行进,我们希望行进速度越大越好,对于机器人转弯时,转弯速度要有约束,要保证机器人不能发生侧翻。我们发现圆弧半径的大小与转弯速度紧密相连,从转弯速度公式来分析,当转弯半径增大时,最大转弯速度也增大,为在更短时间内行进到目标点,我们希望转弯速度为机器人的最大转弯速度较好,但有很大的可能是行进的路径不是最短的,即行进路径有很大可能在增加。于是,我们需要做的工作是,在满足最短时间路径条件时,找到一个圆弧的坐标位置,同时确定半径的大小,以求得最短时间路径。三、模型假设1.将机器人看
10、成一个质点;2.半径不变时,机器人在行进、转弯过程中能一直保持最大的速度;3.四、符号说明:避障最短路径;:圆弧切点到圆弧切点的直线距离,即机器人从圆弧切点到圆弧切点的直线路径,;:机器人从圆弧行进至圆弧切点时的转弯路径,;:圆弧的横坐标,;:圆弧的纵坐标,:圆弧对应圆心角;:圆弧的半径;五、最短路径模型建立与求解5.1模型准备5.1.1确定圆弧位置与转弯半径在建立机器人从区域中一点到达另一点的避障最短路径数学模型之前,我们需要考虑两个问题:问题一:机器人从区域中一点到达另一点过程中,若中间有障碍物,则需要通过转弯来绕过障碍物,那么,在转弯半径一定的情况下,怎样设定最佳圆弧位置,使得绕行路径最
11、短?问题二:绕行路径是最短时,转弯半径的大小为多少?针对考虑的问题一,我们取机器人从到点的行走过程来说明问题。在行走过程中要求机器人行走线路与障碍物的最短距离为10个单位,圆弧(转弯)半径最小为10个单位。我们先令机器人转弯半径为10个单位,根据机器人行走过程中的要求,我们易得两条极端的行走路径,如图1。将路线II中圆弧3两切点线延长,两延长交路线I,两交点处分别作半径为10个单位的圆弧,由此我们可得机器人从到点的行走时转弯中心坐标的范围,如图2中四边形。 图1 两条极端路径 图2 转弯中心坐标的范围图1中路线I是理想化路线,机器人不能沿平面区域边界行走,平面区域边界也可以看成是一个障碍物,且
12、有要求机器人行走线路与障碍物的最短距离为10个单位,实际上作这样的处理并不会影响我们说明问题。我们假设在平面中有和两点,中间有一正方形的障碍物,将图2进行转化,如图3.图3 最短路径证明图图3中,为切点,为圆弧圆心,四边形为圆弧中心点的范围。对于最佳圆弧位置确定,我们采用“覆盖法”。我们容易知道,若路线II与构成的区域II能够完整覆盖线I与构成的区域I,即区域I属于区域II,那么区域II的周长一定大于区域I,否则。图3中路线I与构成的区域I周长为直线段长度、圆弧长、长之和,区域I周长为机器人沿路线I的路径长可表示为路线II与OA构成的区域II周长为直线段长度、圆弧长、长之和,区域II周长为机器
13、人沿路线II的路径长可表示为显然我们知道区域II能够覆盖区域I,即可得,进而可得到 同理,在圆弧中心点的范围任意取一点作为机器人转弯圆弧中点,并作路线,再将路线与路线I做比较,可得到由此,我们可得出结论:机器人从区域中一点到达另一点过程中,当圆弧位置设定障碍物顶角上时,绕行路径最短,此时圆弧中心点坐标为障碍物顶角坐标。针对考虑的问题二,为了更清晰说明绕行路径是最短时,转弯半径的大小为多少,我们基于最小圆弧半径条件下使圆弧半径增大。为了保证机器人与障碍物不发生碰撞,所以,需要保证大圆弧能够覆盖小圆弧对应圆的1/4圆弧。在设定好最佳圆弧位置情况下,增加圆弧半径,比较最短路径的变化。假设圆弧半径为(
14、),对应最短路线如图4。(1) (2)图4 圆弧半径为R最短路径图4(1)中为两圆弧公共切点,为小圆弧切点(),为大圆弧切点。图4(2)中、为大圆弧切点,、为小圆弧切点。针对图4(1)(2),根据“覆盖”思想与得出的结论,我们容易发现,当圆弧半径为()时,行进路线与构成的区域显然是能够完全覆盖圆弧半径为时构成的区域,由此,可说明在圆弧位置设定为最佳的条件下,圆弧半径越小行进路径越短,而圆弧半径最小为10个单位,进而说明圆弧的半径为10个单位时,绕行路径最短。根据考虑的两个问题与证明结果,我们可得出结论:要使得机器人从区域中一点到达另一点的行进路径最短,应使圆弧位置设定在需要绕过障碍物的顶角上最
15、佳,此时圆弧中心点坐标为障碍物顶角坐标,并且此时圆弧的半径为10个单位。5.1.2问题的转化在模型准备中我们已得出要使得机器人从区域中一点到达另一点的行进路径最短,应使圆弧位置设定在需要绕过障碍物的顶角上最佳,此时圆弧中心点坐标为障碍物顶角坐标,并且此时圆弧的半径为10个单位。因此,我们将的平面场景图进行处理,处理原则有:1. 每个障碍物的顶角都设定一个圆弧;2.圆弧坐标为障碍物顶点坐标;3.圆弧的半径设定为10个单位;4.给每一段圆弧从2.标号,O点标记为1、36。根据处理原则,得图5。图5 处理后的平面场景图在原问题中,若没进行确定圆弧位置与转弯半径以及平面场景的处理,原问题求解将会很难,
16、并且所有的转弯点均是未知,经处理后,我们将问题转化为在已知转弯点,寻找合适的转弯点,使得路径最短,即我们将问题转化为了最短路径的优化问题。 5.2避障最短路径模型的建立问题转化为最短路径的优化问题后,我们易知优化的目标函数为机器人在行进过程中最短路径,通过0-1变量来选取经过的转弯点,因此可建立0-1规划模型。 5.2.1目标函数目标函数为机器人出区域中一点到达另一点的避障最短路径,避障最短路径为行进过程中直线路径与转弯路径之和,于是有 (1)其中,为圆弧切点到圆弧切点的直线距离,即机器人从圆弧切点到圆弧切点的直线路径;为机器人从圆弧行进至圆弧切点时的转弯路径;为0-1变量,表示若选择行走圆弧
17、后行走圆弧,为1,否则为0,。我们设为圆弧的切点坐标,为各圆弧的编码,为切点的次序,如表示为圆弧的第一个切点坐标。机器人从圆弧切点到圆弧切点的直线路径为 (2)机器人从圆弧行进至圆弧切点时的为 其中(3)为转弯半径,。5.2.2约束条件1.避障条件的约束在本问题中,障碍物边界可分为直线段与圆弧两种情况,针对障碍物边界不同的两种情况,我们列出避障条件的约束:(1)避障约束条件1任意一条可行路径与所有障碍物的边界线段间的最短距离大于10个单位. 设平面内有两条线段和,点的坐标为 ,点的坐标为 ,点的坐标为,点的坐标为,其中、可视为圆弧的切点坐标,、为圆弧的切点坐标线段两圆弧的切点的连线,视为障碍物
18、的某一条边界线段。 设是直线上的一点,点的坐标可以表示为当参数时,是线段 上的点;当参数时,是延长线上的点;当参数时,是延长线上的点。设是直线上的一点,点的坐标 可以表示为 当参数时,是线段上的点;当参数时,是延长线上的点;当参数 时,是延长线上的点。,两点之间的距离为 距离的平方为要求直线,之间的最短距离,也就是要求函数的最小值。对分别求关于,的偏导数,并令偏导数为零:展开并整理后,得到下列方程组:如果从这个方程组求出的参数,的值满足,说明点落在线段上,点落在线段上,这时的长度为此时就是线段与的最短距离。如果从方程组求出的参数,的值不满足,说明不可能在线段 内部找到一点,在线段内部找到一点,
19、使得的长度就是线段与 的最短距离。这时,还需要进行考虑的是:平面中一个点到一条线段的最短距离。设编号为的障碍物的圆心坐标和一条线段,设点的坐标为,点的坐标为,点的坐标为。此时,直线的参数形式的方程为 直线上的点,当参数时,是线段上的点;当参数时,是延长线上的点;当参数 时,是延长线上的点。 通过点,与直线垂直的平面方程为下面求这个平面与直线的交点。显然,所以点也是从点向直线作垂线的垂足点。将代入平面方程,化简后解得 然后,将上面得到的的值代入直线方程,得到其中,为垂足点的坐标。 此时线段的长度,也就是点到直线的垂直距离为 如果前面求出的参数的值满足,说明垂足点落在线段上,这时 的长度就是点到线
20、段的最短距离。如果前面求出的参数的值满足,说明垂足点不落在线段上,而是落在的延长线上,这时点到线段的最短距离,就是点到点的距离,即 。如果前面求出的参数的值满足,说明垂足点不落在线段上,而是落在的延长线上,这时,点到线段的最短距离,就是点到点的距离,即 。综上所述,即有平面内有两条线段最短距离为因此,我们可得到任意一条可行路径与所有障碍物的边界线段间的最短距离大于10个单位的约束条件(4)其中,(2)避障约束条件2对于标号为2的圆形障碍物,它与机器人行走路线的最近距离为10个单位,为使满足与机器人行走路线的最近距离为10个单位要求,我们可以转化为圆形的圆心与障碍物间的最近为80个单位的问题,即
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- D044 机器人 问题