机器人避障模型建立
摘要
本文对机器人避障问题进行研究, 建立路径或时间的最优模型.
对问题一: 首先对粗选路径的依据进行证明, 然后针对机器人行走路线与圆弧相切的三种情况进行分析, 并得出相应的切点、切线段长度、弧线长度的计算方法. 其次根据粗选路径的依据选出可能的线路图, 将该线路图看作有向图. 运用Dijkstra算法在可能的路线图中选择一条最短路径, 并由此计算出O→A的最短路线长为471.04个单位, 总时间为96.06秒; O→B的最短距离为853.7个单位, 总时间为179.08秒; O→C的最短距离为1088.1个单位, 总时间为221.71秒. O→A→B→C→O的最短路径采用分段优化，并对路线经过的A、B、C三个尖点作了简单处理, 同时计算出最短距离为2713.56个单位, 总时间为542.71秒.
对问题二: 结合问题一中O-A路径, 针对机器人从O点避开障碍物到达A点的最短时间路径的问题进行分析, 建立圆弧半径与时间函数关系, 再根据实际情况对圆弧半径进行约束. 通过Matlab画出半径与时间的关系图, 并得到当半径为11.50个单位时, 0-A路线的最短时间为94.56秒.
关键词: 避障问题、有向图、最短路径、Dijkstra算法
1
1、问题重述
有一个800×800的平面场景图, 在原点O(0, 0)点处有一个机器人, 它只能在该平面场景范围内活动. 如图1中有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 在平面场景中, 障碍物外指定一点为机器人要到达的目标点(要求目标点与障碍物的距离至少超过10个单位). 规定机器人的行走路径由直线段和圆弧组成, 其中圆弧是机器人转弯路径. 机器人不能折线转弯, 转弯路径由与直线路径相切的一段圆弧组成, 也可以由两个或多个相切的圆弧路径组成, 但每个圆弧的半径最小为10个单位. 为了不与障碍物发生碰撞, 同时要求机器人行走线路与障碍物间的最近距离为10个单位, 否则将发生碰撞, 若碰撞发生, 则机器人无法完成行走.
机器人直线行走的最大速度为v0?5个单位/秒. 机器人转弯时, 最大转弯速度为
v?v(?)?v01?e10?0.1?2, 其中?是转弯半径. 如果超过该速度, 机器人将发生侧
翻, 无法完成行走.
请建立机器人从区域中一点到达另一点的避障最短路径和最短时间路径的数学模型. 对场景图中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的最短时间路径. 注: 要给出路径中每段直线段或圆弧的起点和终点坐标、圆弧的圆心坐标以及机器人行走的总距离和总时间.
2
图1: 800?800平面场景图
2、符号说明
L: 表示路径的总长度. d: 表示切线的长度. l: 表示圆弧的长度. r: 表示转弯半径. t: 路径所花费的时间.
3、模型假设
1、假设机器人为一个质点.
2、假设机器人在行走时不发生故障.
4、问题分析
在一个平面场景中, 对机器人避开12个障碍物到达指定的目标点, 所需路径最短或最短时间路径进行分析.
问题一: 首先将机器人行走路线分割成几小段直线与圆相切的情况, 并对这几种情况进行分析得出关系式. 并对圆弧半径取何值时达到最短路径. 然后针对粗选路径依据的证明, 并粗选出路线图. 将该图看成有向图，通过Dijkstra算法选择一条最短路径. 然后通过Matlab软件优化得出O点到各个目标点的相应值.
问题二: 综合问题一对O→A最短路径的基础上, 针对机器人从O点避开障碍物到达A点的最短时间路径的问题进行分析，运用极坐标确定两个切点的坐标, 再通过勾股定理和两点之间距离公式确定角度与圆弧半径与的关系，建立函数式, 最后根据障碍物5左上顶点与平面场景左边界的距离对圆弧半径最大值的约束. 将半径与时间的函数式, 通过Matlab软件模拟出半径与时间关系图.
本文主要运用LINGO、Matlab软件对最值的求解, 约定所有数据保留小数点后两位.
5、模型的建立与求解
5.1 模型建立的准备
3
5.1.1 对定理的证明
1 定理: 如果两个三角形有公共边且公共边对应的角越大, 则另两条边之和越小.
AB为直径, C为圆上一点(不与A, B重合)相互连接得到?ABC. 做C?AB于点E,再在CE之间取一点D. 连接AD, BD又得到?ABD. 最后在另一半任意取一点F连接AF, BF得到?ABF. (????????), (GF 图2 证明: AC+BC>AD+BD>AF+BF 由直角三角形勾股定理得: AF?BF?AG2?FG2?BG2?FG2 AD?BD?AE2?DE2?BE2?DE2 AC?BC?AE2?CE2?BE2?CE2 ?AB?AE?EB?AG?GB为公共边 又?GF ?AC+BC>AD+BD>AF+BF ??2 定理: OB?BD?OA?AE 4