机器人壁障问题——数学建模

1机器人避障问题摘要：当今科学技术日益发达，高科技产品尤其是机器人在我们日常生活中运用的越来越广泛，它能够代替人类完成许许多多的工作，但如何能让机器人自动化的完成人类交给的任务成为设计机器人的关键。我们做此题就是为了更好的利用机器人为我们提供方便，提高生活质量，若机器人程序设计不当不仅不会给人类带来方便，还很有可能给我们的生活带来更多的麻烦。本题中提出了如何让机器人能够自动识别障碍物，保证机器人能够在合理区域行走，并设计出如何能让机器人自动判断最短路程于最短时间下行走路线的问题。所以解决好本题可以为我们的生活提供帮助。本文通过运用两点之间直线最短理论，优化问题，最短路问题，图论，以及运用matlab软件编程及作图的方法，阐述了机器人避障问题的相对优化方案的解决办法，即“两点之间直线最好，转弯半径最小”的理论，通过计算中的比较与选择把四条最短路径都求出了相对最优解，论证了转弯速度不会随着r的增加一直增大或减小，而是有一个最小极点的思想。从而求出了r，以及最短的时间。问题一，通过对最短路问题的分析，我们很容易分解成线圆结构来求解，然后把可能路径的最短路径采用穷举法列举出来，最终得出最短路径：OA最短路径为：471.0372OB最短路径为：838.0466OC最短路径为：1085.7531O→A→B→C→O最短路径为：2834.6591问题二，通过建立时间t与r的关系式，得出r在11.504时，从O到A的时间相对最短，最短时间为98.606004。我们可以利用此篇论文解决生活中实际的问题，在计算时可以节省大量的时间，使机器人又准确又完善的完成我们给定的任务，从而进行拓展，给定区域内任何两个点，我们都可求出其最短路径和走完全程的最快时间。从而可以让机器人帮助我们给家里打扫卫生或设计自动吸尘器等，也可使机器人在最短的时间完成工作，提高效率，延长机器人的使用寿命。关键字：最短路问题优化问题matlab2一问题重述随着现代科学技术日新月异的发展，机器人越来越多的出现在日常生活中,它既可以通过运行预先编排的程序为人类服务，根据人工智能程序自动处理一些生活中问题，进而协助或者相应地取代人类的工作，可以说机器人的创新与改进正一步步影响着人类的发展。如图1所示，该图是一个800×800的平面场景图，在原点O(0，0)点处有一个机器人，它只能在该平面范围内活动。机器人在活动中不能碰到障碍物及其向外延伸10个单位的区域，障碍物由12个不同形状的图形组成，障碍物的数学描述如下表：在图1中，在障碍物外指定一点为机器人要到达的目标点，机器人的行走路线由直线和与直线相切的圆弧组成，也可以由两条及以上圆弧组成。机器人不能折线转弯，必须经过与直线相切的圆弧转弯。每条圆弧的直径不小于10个单位。机器人直线行走的最大速度为50v个单位/秒。机器人转弯时，最大转弯速度为21.0100e1)(vvv，其中是转弯半径。如果超过该速度，机器人将发生侧翻，无法完成行走。要解决机器人从区域中一点到达另一点的避障最短路径和最短时间路径，请建立数学模型，以达到最短路径和时间。对场景图中4个点O(0,0)，A(300,300)，B(100,700)，C(700,640)，具体计算：(1)机器人从O(0,0)出发，O→A、O→B、O→C和O→A→B→C→O的最短路径。(2)机器人从O(0,0)出发，到达A的最短时间路径。编号障碍物名称左下顶点坐标其它特性描述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，宽603注：要给出路径中每段直线段或圆弧的起点和终点坐标、圆弧的圆心坐标以及机器人行走的总距离和总时间。图1二问题分析2.1问题一问题一中要求机器人从O（0,0）出发，按照上述规则求绕过障碍物到达目标点的最短路径，我们可以先设想机器人所走过的路径的各种情况。通过设想然后采用两点之间直线最短的原理寻找可能的最短路径（比如求O和A之间的最短路径，我们就可以连接O和A，发现OA的对角线在OA的下方，所以从OA对角线的上方行走比下方距离短。在第一问求路径最短时尽量少走圆弧，所以在可能的情况下拐弯时最好走10为半径的圆弧）。之后采用穷举法列出O到每个目标点的可能路径的最短路径，最短路径由圆弧和直线组成，求出圆弧和直线的长就能求得路径，通过建立优化模型可求出最短路径。进而联立切线和圆的方程组及运用matlab软件求出各点坐标。42.2问题二问题二需要求O到A的最短时间，这让我们考虑的就不仅仅是路长的问题，还有了速度的问题。已知公式50v和21.0100e1)(vvv得出直线比转弯的速度快且转弯速度与圆弧半径有关。我们可通过建立路程和速度的关系方程求得时间的最优解。三模型假设1、假设机器人能够抽象成点来处理。2、假设机器人能完整的走到终点，中途不会发生故障。3、假设机器人在离路障10个单位处不会发生故障，可以正常行走。四符号说明符号符号解释切点iD：表示5号图形包络线上的点.i=1,2,3Ei：表示6号图形包络线上的点i=1,2,3,4Fi：表示7号图形包络线上的点i=1,2,3,4,5Gi：表示8号图形包络线上的点i=1,2,3,4Hi：表示9号图形包络线上的点i=1,2,3,4Ii：表示10号图形包络线上的点i=1,2,3,4Ji：表示11号图形包络线上的点i=1,2,3,4Ki：表示2号图形包络线上的点i=1,2Li：表示3号图形包络线上的点i=1,2五模型建立5.1证明点到直线距离最短理论在最短路问题中起重要作用5通过起点与终点的连线，判断哪边路径离这条连线距离较近，进而选择出最优路径。如果中间有较多路障的话也可采取分步判断的方法，判断由较近路障附近的点决定。如图二，求O到A最短路径。正方形对角线为BC，EE’，DD’分别为E,D到OA的距离，显然EE’DD’,所以从OA的上方通过为最短路径。5.2基本模型求路径（1题）5.2.1线圆模型已知O(为起点,B（为目标点,D（和E（分别为机器人经过拐点分别于隔离危险线拐角小圆弧的切点，圆心为O1（，圆的半径为r，OB的长度为a，OO1的长度为b，BO1的长度为c，角度BOO1DOO11EOO11，DEO11.通过余弦定理可算出，弧长=圆心角*r，可求出OEDB的长度。6由此解法在matlab编程，可求出已知起点与终点及圆心和半径的所有最短路（见附录10.1）5.2.2相交切线模型当两圆半径相同时，由于半径已知以及K(,M（,L（我们很容易求得12312322xxxyyyL点的坐标已知后用上述线圆模型即可求出弧长当两圆半径不同时，根据半径比值可算出斜边比值，斜边端点已知，即可求出H坐标，再利用附录10.1求解可得。75.2.3平行切线模型当两圆半径相同时，其中已知O1(O2（,P（,半径已知，2121OOyyKxx，所以切线方程为11()OOyKxxyC再利用matlab运算出弧长（详见附录10.1）21OOCrK当两圆半径不同时，两圆心斜率k可知，KO120=a，切线斜率akaktan1tan8再利用上述方程式即可求得C，切线方程与圆联立方程即可求得切点（见附录10.2和10.3），再用线圆模型即可求出路径。5.3基本模型求拐点（1题）已知条件为O(O1（DO1=r设D(xy)，由于两直线垂直即有0))(())((2121yyyyxxxxD点在圆上，与圆的方程联立即可求出D点。此处先运用matlab中expand函数将方程式化解成多项式形式，再用solve函数求出方程的根即D点坐标。（详见附录10.2和10.3）5.3时间模型的建立（2题）根据线圆模型我们可以知道：若一个机器人穿过的圆弧所在圆的半径已知，则机器人行走的路程就是可求得。由于机器人在转弯时的速度是关于半径（r）的函数，再根据“时间（T）=路程（S）/速度（V）”，我9们可以求出时间（T）关于半径（r）的函数关系式。已知直线行走的速度和转弯行走速度的关系式，50v21.0100e1)(vvv，可以建立一个自变量为r的关于时间的函数，通过求导让函数值等于0，可以得出r的解，从而确定最短时间。我们根据对前面路程的求解，可以判断机器人在转弯时所走的弧形路程相对于直线路程是很小的，那么我们可以断定：当机器人以最短的时间走到目标点时，它所经过的路线与它以最短的路程所走的路线大致一样。求函数表达式具体过程：如图：已知O（x1,y1）B=(x2,y2)O1=(x3,y3),点D，点E分别为圆的切点，设圆的半径为r,求出O--B的时间。求解过程：L1^2=(x2-x1)^2+(y2-x1)^2L2^2=(x3-x2)^2+（y3-y2^2L3^2=(x3-x1)^2+(y3-y1)^2设O,O1,B为a,D,O1,O为b，E,O1,B为c，cos(a)=(L3^2-L2^2-L1^2)/2*L1*L2a=arccos(L3^2-L2^2-L1^2)/2*L1*L2b=arccos(r/L1)c=arcos(r/L2)弧长DE=r*(2*pi-a-b-c)V=v0/5*(1+e^(10-0.1^2))时间T1=(L1^2-r^2)^(1/2)/v010T2=(L2^2-r^2)^(1/2)/v0T3=弧长DE/VTzong=T1+T2+T3在求出时间关于半径的方程后，我们可数值解法求解最短时间。我们知道半径的大小影响了时间的长短，半径的长度是大于10的实数，我们可以先让自变量（半径）比较大范围的有序变化（因为自变量的范围不大），求出对应的时间。再观察时间随半径变化的规律，得出最短时间时所对应的时间，就可以确定最短时间就在所得时间点的附件摆动。为了能更精确的求出最短时间，我们继续以比上次取值小的值在所求的点的附近做有序的加减。以此类推，经过多轮对时间的取值，就可以解出比较精确的解。六、模型求解6.1.1O——A的最短距离如图：D1(70.5060,213.1406)D2(76.6064,219.4066)弧OA的长等于两条切线（OD1，D2A）与弧（D1，D2）的和通过用matlab计算可知：11O——A的最短距离为471.03726.1.2O——B的最短距离如图E1(50.1353,301.6396)E2(52.198,306.252)E3(142.198,441.252)E4(147.709,444.733)F1(222.29,406.264)F2(230,470)F3(230,530)F4(225.4967,538.3538）G1(144.5033,591.6462)G2(140.6916,596.3458)同理如上，通过用matlab计算可知：OB的最短距离为838.04666.1.3O——C的最短距离12如图D1(70.5060,213.1406)D3(75.736,219.044)L1(395.798,339.055)L2(397.709,339.736)K1(568.331,372.115)K2(600.019,387.588)J1(727.7178,710.2822)J2(730,600)J3(730,520)J4(727.802,606.252)同理如上，通过用matlab计算可知：O_C的最短距离为1085.753113如图G3(270.5862,689.9828)G4(2