机器人避障问题。
摘要。我们了解到我们需要解决的是机器人从o→a、o→b、o→c和o→a→b→c→o的最短路径以及o→a的最短时间问题，但与传统的问题相比因为有了障碍物的制约使得部分区域无法通过，而且物体的运动轨迹也会对其速度造成制约，联系现实生活我们知道对于无法以最短直线路径通过时如果两点间有一根足够长的绳子，在绕开障碍物及其所影响的范围后绳子绷紧状态下所形成的轨迹即为最短路径，在最短的路径和最快的速度间找制约点可获得最短时间，该题时间制约因素为。受此启发，在分析问题后我们建立了数学模型来合理解决如何使机器人避障的优化问题。
针对问题一；问题一中o→a可简化为两点避开单个障碍物的问题、o→b、o→c为。
两点避开多个障碍物的问题、对于o→a→b→c→o是一个回路的多点避开多个障碍物的问题，运用几何的求解方式证明 。
针对问题二；问题二是时间最优的问题，我假设存在个半径为最优时间半径，然后我们找到个最优圆弧圆心的位置，圆心在两点连线为x轴的最高障碍点作x轴的该条垂线上。
关键词最短路径最优化模型几何求解最短时间。
一、问题重述。
1.1、基本情况：
在给定的平面场景中，要求机器人绕开障碍物到达指定的目标点（要求目标点与障碍物的距离至少超过10个单位）。规定机器人的行走路径由直线段和圆弧组成，其中圆弧是机器人转弯路径。机器人不能折线转弯，转弯路径由与直线路径相切的一段圆弧组成，也可以由两个或多个相切的圆弧路径组成，但每个圆弧的半径最小为10个单位。
为了不与障碍物发生碰撞，同时要求机器人行走线路与障碍物间的最近距离为10个单位，否则将发生碰撞，若碰撞发生，则机器人无法完成行走。
1.2、相关信息：
1) 机器人直线行走的最大速度为个单位/秒。
2) 机器人转弯时，最大转弯速度为，其中是转弯半径。如果超过该速度，机器人将发生侧翻，无法完成行走。
1.3、需要解决的问题：
1) 机器人从o(0, 0)出发，o→a、o→b、o→c和o→a→b→c→o的最短路径。
2) 机器人从o (0, 0)出发，到达a的最短时间路径。
注：要给出路径中每段直线段或圆弧的起点和终点坐标、圆弧的圆心坐标以及机器人行走的总距离和总时间。
二、模型假设。
假设一：机器人的长宽小于10个单位，且可以把小车看成一个质点。
假设二：地面平整且处处的摩擦程度一样对机器人无影响。
假设三：机器人在行走的过程中不受其他因素（如风速，电源等）影响，保持匀速。
三、符号说明。
障碍物（i=1,2..n两点之间的连线集合（j=1,2,3..n）
a点和b点避开障碍物的最优圆弧半径 : 两点的连线和第i个障碍物交点。
四、问题的分析。
问题一：机器人从o点出发分别到a点、b点、c点、d点和从o到a到b到c回o点的最短路径。在平面中两点的直线相连为两点的最短的路径，所以在机器人的的行走的最短路径中。
所以存在三个问题，两点单障碍物体、两点多障碍物体和多目标点多障碍物的求解。
1） 两目标点单障碍物问题分析，路径中存在着单个障碍物。由题意可以得知机器人行走路径必须距离障碍物的大于10个单位，所以图中障碍物需要画一个外边为10个单位的轮廓，以及最转弯弧度半径为10个单位，且折线处顶点做10单位半径的圆过渡，所以两点避开一个圆最短路径的问题，可以从几何的方式求解。
2） 两个目标点多障碍物问题分析，本问题是上一个问题的深入。可以利用两点过单障碍物的结论，在运用过程中必定存在多条路径。避开第一个障碍物的选择优化路径。
3） 多目标点多障碍物问题分析，本问题是问题上述两个问题的综合，本问题存在中间目标点的过渡问题。
问题二：机器人在转弯的速度和转弯圆弧半径有关系，半径越大机器人的速度越大，题目中给出了机器人的直线速度和，转弯速度。要求建立时间最优模型并且求出o->a时间最优路径。
由于走直线与走圆弧的速度不同，问题一中最短距离路径可能不是时间的最优路径，我们可以假设存在已知最优圆弧的半径，在图中证明确定最优圆弧圆心的位置来求解最优圆弧的半径。
五、模型建立与求解。
问题一：机器人从o点出发分别到a点、b点、c点、d点和从o到a到b到c回o点的最短路径。可以看出点为两点避开单个障碍物的问题，和都为两点避开多个障碍物的问题，而这个问题为为上面三个问题的综合为多点避开多个障碍物的问题。
所以我们先考虑两点避开单个障碍物的问题。
首先观察下面两个图形：
图一。在图中三角形为障碍物，从图中可以看出机器人以一定距离经过障碍物的问题实际上可以简化为绕过半径为的圆形障碍物的问题。
下面证明一个定理：
定理：从一定点出发绕过一个圆形障碍物到达另一定点的最短路径由圆的两段切线以及与它们相连的一段圆弧构成，如下图段：
图二。证明：如图。
图三。设曲线aegfb为从a绕过圆到达b的任一条路径，点e,f分别为oc及od延长线与曲线的交点，同时设ae及bf段为直线（若这两段不为直线，则路径更长）。
以圆的圆心为起点引入极坐标，设曲线egf段的极坐标方程为：
再设时的最小值为，设为曲线egf的长度，则有。
即线段egf的长大于的长，又，，由此可知路线是由a点到b点的最短路径。
根据两点避开单障碍物的结论我们继续考虑两点避开多个障碍物的问题：
首先我们观察下图可得知：
图四。下面证明一个定理：
定理二：起点到目标点无论中间障碍物有多少，最短路径都是若干个线圆所组成。
图五。如上图，设为起点，为目标点，和分别为机器人经过。
拐点分别于隔离不可行走的拐角的切点，圆心为，圆的半径长为r,ab的长度为a，bo的长度为c，角度，。求的长度，设路径总长度为l：
而对下图两种情况我们不能直接采用上述结论来解决：
情况一： 图六。
我们假设两圆坐标分别为和，半径为为r,m点坐标为，那么我们容易可以求得：
先求得a到m，再求m到b，这样分两段求解。
情况二：图七。
这里我们依次设圆心坐标分别为和，半径为r,这样可以得到：
由于图上可平行线可得到：
那么把公切线的方程于圆方程联立，可以求得到d和e点。这样我们就可以求和上面情况一样的转弯了。
多目标点多障碍点的求解答问题：
对于起点经过若干点然后再达到目标点的状况，因为不可以走折线所以中间目标点需要圆弧过度。
定理三：要过度中间点的时候中间目标点在个圆环上，当圆心和切线焦点以及目标点在一条直线上的时候其为最短路径。
下面给出证明：
图八。由图三可以得知，连接ab，以ab为x轴，可以得到e点为最高点，当在一条线上时，可以得到，若圆向左水平偏移可以得知，必须向上偏移才可以穿过最高点e。
根据等腰三角形的特性可以得知：
设af的斜率为，ac的斜率为，bc的斜率为，bg的斜率为，l为总长。
即定理三得证。
求的长度为：
的最短路径：利用模型结论一可以得到：
图九。利用结论一以及题目意机器人的路径必须离障碍物10个单位的距离所以我们得到上图。我们得到，两条路径。圆弧cd的圆心为障碍物5的左上角点为圆心。
连接内正方形对角线hj可以得到o、a点在对角线hj上方所以只需计算路径的总长即为最小路径。
设c（x,y），由c点和圆心点的长度等于半径和两条垂线的斜率乘积等于-1可得c的坐标点：
同理可得d的坐标点。
求解得，根据题意取：//
根据求得的c,d和圆点，用余弦定理可得：
解得，反解出。
由，得l=8.849
根据两点间的距离可求得：
则由o到a的最短路径为：min= 461.8217
利用结论一和结论二我们可以得到的路径如图所示：
图十。由图六得：求切点a用公式。
解得，根据分析取。同理可得；
易证b,c在同一直线上，且圆心在三角形6的两个顶点上，故由勾股定理和点到圆心的距离等于半径可得，解得，取。
同理可得。由点到圆心的距离等于半径相交垂线的斜率乘积为-1,对d可得：
解得，根据分析取，依次同理可得。
由o到b的最短路程min=161.6335+ 97.9795+60+ 161.6335+ 305.7777+59.717= 846.7412
可以利用结论二对的最短路径求解：可得如下图路线。
图十一。下面对各个点的坐标以及总长求解。
令，易得，解得，，根据实际情况取，同理可得， ，两点间的距离公式：
如，, 可以求得：,由余弦定理和反三角函数以及弧长公式可得：,由o到c的最短路径min=1002.17
利用结论三以及结论二可以得到的线路图：
图十二。在图九中我们求得u(540.00，730.000),
同样，依据余弦定理和反三角函数以及弧长公式我们可以求得全程最优路程min=2513
问题二：考虑到机器人转弯的速度和转弯的半径有关系所以最短路程的路径可能不是机器人最短时间的路径。
同样最短时间最优也是可以简化成两点过一个障碍物的问题。最短路程转弯时候用到的弧度半径必定是最小即为10. 同样也可以在把机器人看成光线在真空中传播，在圆弧不同路径中行走的问题转换成光线在不同密度介质传播的问题。
所以可以得到下面公式：
计算上面圆弧的长度可以由上式代替重新使得时间最优问题转化为路程最短的问题。可以把问题简化成路径从a点越过过可见区域和不可以见区域的交点路程的路程优的问题：
模型二：证明同样圆弧半径时存在一点为圆心，已知两点避开单个障碍物体物时间最优必定存在一个劣弧作为两点避开障碍物z。所以我们可以假设最优圆弧的半径为。
2019D数学建模试题
d题公交车调度。公共交通是城市交通的重要组成部分，作好公交车的调度对于完善城市交通环境 改进市民出行状况 提高公交公司的经济和社会效益，都具有重要意义。下面考虑一条公交线路上公交车的调度问题，其数据来自我国一座特大城市某条公交线路的客流调查和运营资料。该条公交线路上行方向共14站，下行方向共13站，...
2019D数学建模试题
d题空洞探测。山体 隧洞 坝体等的某些内部结构可用弹性波测量来确定。一个简化问题可描述为，一块均匀介质构成的矩形平板内有一些充满空气的空洞，在平板的两个邻边分别等距地设置若干波源，在它们的对边对等地安放同样多的接收器，记录弹性波由每个波源到达对边上每个接收器的时间，根据弹性波在介质中和在空气中不同的...
2019数学建模D题
2014年 认证杯 数学中国数学建模网络挑战赛。第二阶段。d题幼儿园园长的苦恼。本题仅限中学组和专科组选用 某幼儿园，有130名孩子，有15名老师，由于园内的空间不足，为了让孩子们能够充分活动，需要将孩子们带到一块长50米，宽35米的矩形空地上去活动。每天大约要活动30分钟。在空地上活动是安全的，空...