二维机器人避障问题的案例教学内容设计

九江职业技术学院学报2012.420JournalofJiujiangVocational&TechnicalCollege二维机器人避障问题的案例教学内容设计陈晓江,陈杨林(九江职业技术学院,江西九江332007)摘要:将2012年全国大学生数学建模竞赛D题改编为包括图形绘制和处理、模型建立、算法设计编程、模型应用拓展等能力训练在内的一个案例,从机器人避障的背景描述、问题提出到模型分析、建立和解算,再到给出参考解答,完整地提供了面向高职学生的案例教学内容设计过程。关键词:机器人;避障;案例教学中图分类号:TP242文献标识码:A文章编号:1009-9522(2012)04-0020-03数学应用实践案例的开发是高职数学与专业结合的切入点〔1〕,编制出适当的案例内容有利于探索高职数学课程内容与专业结合的方式方法,内容组织合理的案例教学有利于提升学生的数学应用于专业问题的意识和能力。2012年全国大学生数学建模竞赛D题提出了一个机器人在二维固定场景中的避障问题,更广泛的机器人避障问题常见于二维甚至三维计算机图形处理和机器人自动行走。此类问题的解决尤其适合大多数高职学生的数学应用能力、计算机图形处理能力和算法编程能力的培养和实训,如果考虑障碍物的移动及识别,后续的专业纵深研究空间非常大。下面是一种经过精心改造编制的机器人避障问题案例的教学内容设计。一、案例背景和数学问题1.背景描述〔2〕已知有一个800×800的二维场景图,在原点O(0,0)点处有一个机器人,它只能在该平面场景范围内活动。图中有12个不同形状的区域是机器人不能与之发生碰撞的障碍物,障碍物的数学描述如下表:在平面场景中,障碍物外指定一点为机器人要到达的目标点。规定机器人的行走路径由直线段和圆弧组成,其中圆弧是机器人转弯路径。机器人不能折线转弯,转弯路径由与直线路径相切的一段圆弧组成,也可以由两个或多个相切的圆弧路径组成,但每个圆弧的半径最小为10个单位。为了不与障碍物发生碰撞,同时要求机器人行走线路与障碍物间的最近距离为10个单位,否则将发生碰撞,若碰撞发生,则机器人无法完成行走。编号障碍物名称左下顶点坐标其它特性描述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正方形(540,600)边长13011正方形(640,520)边长8012长方形(500,140)长300,宽60机器人直线行走的最大速度为v0=5个单位/秒。机器人转弯时,最大转弯速度为v=v(ρ)=v0,其+e10-0.121ρ中ρ是转弯半径。如果超过该速度,机器人将发生侧翻,无收稿日期:2012-10-16作者简介:陈晓江(1967-),男,江西省九江市人,九江职业技术学院图书馆馆长、教授,研究方向为高职数学教育和数字化信息资源建设。基金项目:本文为2011年江西省高等学校教学改革研究省级立项课题“高职教育制造类专业的数学应用实践案例开发研究”(课题编号:JXJG-11-30-6)的阶段性研究成果2012.4九江职业技术学院学报(陈晓江:二维机器人避障问题的案例教学内容设计)21法完成行走。2.问题提出针对机器人在案例背景中给出的场景中行走,既要避障又要达到目标位置的要求,请分析并完成如下四个任务:(1)画出该二维场景图,及预处理场景图。(2)计算出机器人从O(0,0)出发,到达A(300,300)最短路径的距离。(3)计算出机器人从O(0,0)出发,到达A(300,300)最短时间路径的时间、距离、各路段起始点坐标以及圆弧圆心坐标和转弯半径,并画出路径图。(4)自行设计若干拓展问题,并提出解决思路。二、模型分析、建立和解算1.模型分析因为机器人圆弧行走的最小半径为10个单位,直线行走避障距离最小为10个单位,因此需要考虑在场景中设置机器人行走的“危险区域”进行预处理,该区域为按照最小距离单位覆盖所有障碍物的包络图。用MATLAB软件编程将二维场景图和预处理场景图绘图在一个平面图形中。由于最短路径和最短时间路径的区别在于机器人走圆弧的转弯速度,而转弯速度又取决于圆弧半径。第(2)问行走速度固定,为达到最短路径要求圆弧半径始终设定为ρ=10个单位,第(3)问则根据问题所给要求,直线行走速度在保持最大速度的条件下,适当增加转弯半径(即ρ10),用以增大圆弧距离,从而提高走圆弧的速度。因为limv0=5,事实上,当ρ取14时,v(ρ)≈2ρ※∞1+e10-0.1ρ4.9997已非常接近最大直行速度,于是搜索最短时间路径时可以考虑条件:10ρ≤14。2.建立模型考虑机器人行走规则,可以建立一个统一的数学模型,模型准备如下:(1)以圆心在第5个障碍物左上顶点,半径为10的圆为一个定圆。(2)以圆心为动点Q(m,n)、半径为ρ的圆为一个动圆,保持动圆始终跟定圆内切(定圆始终在动圆内)。(3)最短路径采用“拉绳法”〔3〕,即用连接O、A之间的一根绳子,以障碍物上的定圆为支撑拉紧绳子,则绳子长度就是从O到A点之间的最短路径。此时,最短路径为两个直线段和一个圆弧段组成,定圆圆心坐标为(80,210)。(4)最短时间路径采用“拉绳法”和“自然下垂法”相结合的办法,其中“拉绳法”原理同上,只是支撑圆弧替换为动圆,而“自然下垂法”是指:当绳子两端O、A拉紧时,动圆可以绕着定圆自然下垂摆动,并保持定圆始终在动圆的上半圆内切(如图1),以实现最短时间路径。此时,在机器人沿着由上述最短路径的基础上,以行走时间最短为目标函数编程搜索出最佳位置的动圆参数:动圆圆心坐标(m,n)、动圆半径ρ。搜索算法模型的优化条件可以根据平面几何中“两个内切圆的圆心距离等于动圆半径与定圆半径的差”的定理可优化减少一个参数,比如ρ;剩下的两个参数m,n可依据动圆半径ρ最大为14,得到两个参数的取值范围。图1建立数学模型如下:设从O到A点总路径为L,总时间为t,支撑圆圆心为Q,则有:|OA|=(30022-0)+(300-0);22|OQ|=(m-0)+(n-0);|AQ|=(30022-m)+(300-n);∠OQA=arcos|OQ|2+|AQ|2-|OA|2;ρ2|OQ||AQ|ρ∠OQC=arcos;∠AQD=arcos;|OQ||AQ|θ=∠CQD=2π-∠OQA-∠OQC-∠AQD。最小目标函数(含路程最短和时间最少)为:MinL=m2+n2-p2+222+pθ;(300-m)+(300-n)-pMint=1(m2+n2-p2+5222+pθ(1+(300-m)+(300-n)-pe10-0.12ρ)且满足条件:80≤m≤84,206≤n≤210,22(m-80)+(n-210)=p-10。3.解算过程计算最短路径时,L中直接代入数值m=80,n=210,p=10即可得到最短路径的距离。计算最短时间路径时,可以根据精度要求,取搜索步长为0.01,编程计算出动圆的三个参数m,n,p即为最佳动圆位置,即得最短时间路径。其中,为了绘出路径需要按照如下方法计算出两个切点坐标:如图1,设切点为C(x,y),由切点在圆弧上有式(1)成立:222(1)(m-x)+(n-y)=p再由切点与起终点所连向量分别垂直于相应切点与圆心所连向量,有式子:OC·CQ=0x(x-m)+y(y-n)=0(2)求解由(1)、(2)联立的方程组,可得切点坐标C(x,y)。九江职业技术学院学报2012.422JournalofJiujiangVocational&TechnicalCollege类似地,另一个切点D坐标也满足如下方程组:(m-x)2+(n-y)2=p2(x-300)(x-m)+(y-300)(y-n)=0同理可求得切点D坐标。三、参考解答考虑到模型建立、精度选取的不同,下面仅给出一种参考解答。案例教学时对学生实际完成的有创新性的模型和方法,哪怕结果有出入,也要予以特别的关注和科学的引导。1.场景图及预处理场景如下图2:图22.机器人从O到达A的最短路径距离为471.0372。3.机器人从O到达A的最短时间路径的时间为94.2283,距离为472.0657。此时机器人转弯路径圆弧的圆心坐标为(82.14,207.92),转弯半径为12.9843。路径从O到A点依次为直线段一、圆弧段、直线段二。直线段一的起点和终点坐标分别为(0,0)和(69.8072,211.9813),圆弧段的起点和终点分别为(69.8072,211.9813)和(77.7492,220.1394),直线段二的起点和终点坐标分别为(77.7492,220.1394)和(300,300)。路径图如下图3:图34.自行设计的问题有较大的发挥空间,比如可以在场景图中设置其他的目标点,如B(100,700),C(700,640),计算出相应的最短行走路径,也可以针对不同模型和算法讨论对最优结果的影响,还可适当考虑直线行走与转弯之间时间延迟的影响以及其他不规则形状障碍物对结果的影响等等。参考文献〔1〕陈晓江.应用实践案例开发:高职数学课改的新探索[J].九江职业技术学院学报.2011(03):26-27.〔2〕2012年高教社杯全国大学生数学建模竞赛赛题:〔3〕机器人行走问题:(JiujiangVocationalandTechnicalCollege,Jiujiang,Jiangxi,332007)Abstract:Thispaperrearrangeoneexerciseofthemathsmodelingcontestin2012aspicturedrawingandpro-ceedingandmodelconstructionapplication.Fromthebackgroundofrobots'obstacleavoidance,problems,calcula-tionandkeys,Whichfullyillustratesthecaseteachingdesignfacedthehighervocationalstudents.Keywords:robots;obstacleavoidance;caseteaching