机器人避障问题
(全国竞赛2012年D题)
图1是一个 $800\times800$ 的平面场景图,在原点$O(0,0)$点处有一个机器人,它只能在该平面场景范围内活动。图中有12个不同形状的区域是机器人不能与之发生碰撞的障碍物,障碍物的数学描述如下表:
编号 | 障碍物名称 | 左下顶点坐标 | 其它特性描述 |
1 | 正方形 | (300, 400) | 边长200 |
2 | 圆形 | 圆心坐标(550, 450),半径70 | |
3 | 平行四边形 | (360, 240) | 底边长140,左上顶点坐标(400, 330) |
4 | 三角形 | (280, 100) | 上顶点坐标(345, 210),右下顶点坐标(410, 100) |
5 | 正方形 | (80, 60) | 边长150 |
6 | 三角形 | (60, 300) | 上顶点坐标(150, 435),右下顶点坐标(235, 300) |
7 | 长方形 | (0, 470) | 长220,宽60 |
8 | 平行四边形 | (150, 600) | 底边长90,左上顶点坐标(180, 680) |
9 | 长方形 | (370, 680) | 长60,宽120 |
10 | 正方形 | (540, 600) | 边长130 |
11 | 正方形 | (640, 520) | 边长80 |
12 | 长方形 | (500, 140) | 长300,宽60 |
在图1的平面场景中,障碍物外指定一点为机器人要到达的目标点(要求目标点与障碍物的距离至少超过10个单位)。规定机器人的行走路径由直线段和圆弧组成,其中圆弧是机器人转弯路径。机器人不能折线转弯,转弯路径由与直线路径相切的一段圆弧组成,也可以由两个或多个相切的圆弧路径组成,但每个圆弧的半径最小为10个单位。为了不与障碍物发生碰撞,同时要求机器人行走线路与障碍物间的最近距离为10个单位,否则将发生碰撞,若碰撞发生,则机器人无法完成行走。
机器人直线行走的最大速度为 $v_0=5$ 个单位/秒。机器人转弯时,最大转弯速度为 $v=v(\rho)=\frac{v_0}{1+e^{10-0.1\rho}}$,其中 $\rho$ 是转弯半径。如果超过该速度,机器人将发生侧翻,无法完成行走。
请建立机器人从区域中一点到达另一点的避障最短路径和最短时间路径的数学模型。对场景图中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 800×800平面场景图