一个会干农活的机器人300

篇一:《2012高教社杯数模竞赛D题——机器人避障问题》

机器人避障问题

摘要

本文研究了在已知区域障碍物分布的情况下，机器人从起点到目标点避障最短路径或最短时间路径的问题，路径必须是由圆弧和与之相切的直线段组成的线圆结构。一开始先对模型预处理，将所有障碍物外扩10个单位长度，划定危险区域，得到障碍扩展图。

针对问题一，经过分析论证，无论起点到目标点间危险区域有多少，最短路径都应该是紧绕危险点的切线圆路径，且可根据需依次绕过的危险点情况划分为N条子路径（见图5.1.2）求解，圆弧段取允许最小转弯半径。模型求解分两步走：一、将实际障碍图转化为加权可视图，利用Dijstra算法搜索出在可视图下的最短路径，主要是找到必须绕过的若干危险点。二、根据障碍扩展图将可视图中的路径修正为实际情况下的切线圆路径，求出最终结果。在求解过程中运用MATLAB数学软件给出路径中每段直线段或圆弧的起点和终点坐标、圆弧的圆心

连接两条切线，使机器人总的行走时间最短。而圆弧可以有圆心坐标和半径唯一确定。由此构建机器人行走总时间的目标函数，将机器人不与障碍物碰撞作为约束条件，将该问题转变为一个非线性规划问题，借助matlab求得最优解为:T=94.3314s。

关键词： 路径规划 最优化模型 切线圆路径 Dijstra算法非线性规划 matlab求解{一个会干农活的机器人300}.

一、问题重述

图1是一个800×800的平面场景图，在原点O(0, 0)点处有一个机器人，它只能在该平面场景范围内活动。图中有12个不同形状的区域是机器人不能与之发生碰

标点与障碍物的距离至少超过10个单位）。规定机器人的行走路径由直线段和圆弧组成，其中圆弧是机器人转弯路径。机器人不能折线转弯，转弯路径由与直线路径相切的一段圆弧组成，也可以由两个或多个相切的圆弧路径组成，但每个圆弧的半径最小为10个单位。为了不与障碍物发生碰撞，同时要求机器人行走线路与障碍物间的最近距离为10个单位，否则将发生碰撞，若碰撞发生，则机器人无法完成行走。

机器人直线行走的最大速度为v05个单位/秒。机器人转弯时，最大转弯速

v0

度为vv()，其中是转弯半径。如果超过该速度，机器人将发生侧 100.12

1e

翻，无法完成行走。

请建立机器人从区域中一点到达另一点的避障最短路径和最短时间路径的数学模型。对场景图中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}.

二、模型假设

（1）假设机器人可以看成抽象的点来处理；

（2）假设机器人无论在直线或圆弧上均以最大速度行走； （3）假设机器人的速度在第一问中不会超过最大转弯速度,即不会发生侧翻而无法行走的情况；

（4）假设机器人在由直线到圆弧过渡时时间忽略不计；

三、符号说明

四、模型预处理

每个障碍物周围已经设出10个单位的安全距离（如图3.1），即先可以用包络线画出机器人行走的危险区域，在危险区域内应没有路径。危险边界在障碍物的顶点（称之为危险点）处为以顶点为圆心、半径为10个单位的圆弧，如果是圆形障碍物就应该是以障碍物的圆心为圆心、障碍物的半径长加上10个单位为半径的圆弧。这样预处理后得到的障碍物分布图称之为障碍扩展图，与之对应的未预处理的障碍分布图称之为实际障碍图。

图4.1{一个会干农活的机器人300}.

五、模型的建立与求解

5.1问题一的求解

5.1.1理论准备

5.1.1.1由平面几何知识知两点之间线段最短。若在平面上两点之间有一危险区域不能通过，则由拉绳原理可知连接这两点的最短路径为切线圆路径，即一部分是平面上的自然最短路径（即直线段），另一部分是危险区域的圆弧边界，这两部分是相切过渡的。

证明：假设在平面中有A(a,0）和B(-a,0)两点，中间有一个危险区域MEFN

B。 （关于y轴对称），证明从A到B的最短路径为AEF{一个会干农活的机器人300}.

H

M

图5.1.1

N

在y轴上取一点C（0，y），折线ACB与危险区域不相交。

f y = ACB =2

分别过A、B两点做切线与危险边界MEFN相切于E、F两点，两切线在y轴上相切于点C1(0,y1)。则当y<y1时，折线ACB必与危险区域相交，不符合要求。所以y≥y1。又当y>0时，f(y)是y的单调增函数，则：

min f(y)=f(y1)

∵0<α<2α<tanα，

= EO α， ， + FB 又∵ EC1 = EO tanα，EH∴ EC1 < EH∴ AC1B < AE +EF{一个会干农活的机器人300}.

下面再考察一条不穿过危险区域的任何一条路径，设其分别与OE和OF的延长 ，显然AP > AP ，又由AE⊥EO,所线交于P、Q两点，记A和P之间的路径长度为AP > AE ,同理可得BQ > BF

以 AP > AE ,从而AP

π

和圆弧EF的长度的大小。若PQ之间的路径可由再来比较PQ之间路径长度PQ

极坐标方程ρ=ρ(θ)确定,则有ρ>10,可得：{一个会干农活的机器人300}.

= dθ≥ dθ−PQ

π

3

−EF

结论：路径APQB的长度超过路径AEFB的长度，所以满足从A到B的最短路径为AEFB的路径。

5.1.1.2在5.1.1.1的证明中，我们可以这样认为，起点到目标点间无论危险区域有多少，最短路径都应该是若干个切线圆路径组成的结构。现分以下三种情况求取两点之间的最短路径。(除特殊说明外，该部分中r=10) （一）两点之间只需绕过一个危险点区域（如图5.1.2）

A

图5.1.2

设O（x1,y1)为起点，A(x2,y2)为目标点，P(x3,y3)和 Q(x4,y4)分别为切线圆路径上的两切点，圆心为T(x5,y5),圆的半径为r，OA的长度为a，OT的长