cumcm2012D-谭永基-机器人避障问题评述-数模讲座31

2012D题评述复旦大学谭永基yjtan@2024/4/26题目背景华中科技大学梅正阳提供专家组修改完善基于场景的全局路径规划2024/4/26评阅过程3位专家158份其中82份申报1等76份申报2等申报1等3人评阅申报2等至少2人评阅计划评出1等25

2等108淘汰25最后评出1等24?

2等87?淘汰45海军航空工程学院获高教社杯2篇优秀论文（江西应用职业技术学院）2024/4/262012D题2024/4/26图1是一个800×800的平面场景图，在原点O(0,0)点处有一个机器人，它只能在该平面场景范围内活动。图中有12个不同形状的区域是机器人不能与之发生碰撞的障碍物，障碍物的数学描述如下表：2024/4/26编号障碍物名称左下顶点坐标其它特性描述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，宽602024/4/262024/4/26在图1的平面场景中，障碍物外指定一点为机器人要到达的目标点（要求目标点与障碍物的距离至少超过10个单位）。规定机器人的行走路径由直线段和圆弧组成，其中圆弧是机器人转弯路径。机器人不能折线转弯，转弯路径由与直线路径相切的一段圆弧组成，也可以由两个或多个相切的圆弧路径组成，但每个圆弧的半径最小为10个单位。为了不与障碍物发生碰撞，同时要求机器人行走线路与障碍物间的最近距离为10个单位，否则将发生碰撞，若碰撞发生，则机器人无法完成行走。2024/4/26机器人直线行走的最大速度为

个单位/秒。机器人转弯时，最大转弯速度为

其中

是转弯半径。如果超过该速度，机器人将发生侧翻，无法完成行走。2024/4/26请建立机器人从区域中一点到达另一点的避障最短路径和最短时间路径的数学模型。对场景图中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:最短路径路径离开障碍不得小于r=10单位，须预处理最短路由直线和最小转弯圆弧相切构成从起点到终点有多条符合条件路径,如何选优有多个目标点的情形需特别处理2024/4/262024/4/26

障碍预处理扩大障碍区域—禁区2024/4/26直线圆弧相切连接最优2024/4/26其他连接方式2024/4/26各种连接方式都不难计算出切点坐标、切线长度和圆弧长度等。2024/4/26AOT最短路模型2024/4/26从所有出发点到目标点的”可行”路径中选出最短路径找出所有“可行”路径生成赋权无向图构造邻接矩阵用最短路算法（Dijkstra）找出最短路径最短路算法2024/4/26最短路算法2024/4/26OA计算结果2024/4/262024/4/26OB计算结果2024/4/262024/4/26OC计算结果2024/4/262024/4/26多目标点情形以单目标点为基础注意中间目标点处的光滑连接。2024/4/26OABCO计算结果2024/4/262024/4/262024/4/262024/4/26误区人工选取最短路，无最短路算法多目标点时路径连接出现尖点2024/4/26问题2最速路径A至B最速路径仍由2段直线和1段圆弧相切构成圆弧段半径大于最小转弯半径圆弧段与障碍OFFSET相切关键是确定圆弧段的圆心O与半径R2024/4/262024/4/262024/4/26CDOdd1d2L1L2S2024/4/262024/4/26ABCDOL1L2SO12024/4/26模型2改变圆弧段的表达增加切点C，D坐标为优化变量2024/4/262024/4/26ABCDOS2024/4/26模型3：优化变量为切点和半径最速路径中圆弧与障碍OFFSET圆角相切切点T同时落在小圆上切点纵坐标由横坐标决定化为2变量优化问题2024/4/262024/4/26大圆半径2024/4/26过T，O1直线的参数方程用OT距离为R决定O点参数2024/4/26MATLAB程序2024/4/26functiony=tcoms(u)xl=80;yl=210;xa=0,ya=0;xb=300;yb=300;rs=10xt=u(1);r=u(2);yt=y1+sqrt(rs^2-(xt-x1)^2);t=r/rs;x0=(1-t)*xt+t*xl;y0=(1-t)*yt+t*yl;d1=sqrt((x0-xa)^2+(y0-ya)^2);d2=sqrt((x0-xb)^2+(y0-yb)^2);d=sqrt((xb-xa)^2+(yb-ya)^2);L1=y=sqrt(d1^2-r^2);L2=sqrt(d2^2-r^2);af=acos(r/d1);bi=acos(r/d2);gm=acos((d1^2+d2^2-d^2)/2/d1/d2);S=r*(2*pi-af-bi-ga);y=L1+L2+S*(1+exp(10-0.1*r^2));用命令调用Fminsearch(‘tcoms’,[75,11])数值结果2024/4/26AC:

(0,0)—(69.8045)

DB:(77.7492,220.1388)—(300,