全国大学生数学建模竞赛-机器人避障行走的最短路径问题.doc

PAGE

PAGE1

机器人避障行走的最短路径问题

摘要

本文研究机器人避障问题，针对一个正方形平面区域内存在12个不同几何形状的障碍物，由出发点到达目标点的避障最短路径和避障最短时间路径的两个问题。

我们采用“拉绳法”解决避障最短路径问题，即问题一的解决思路为：对于11个凸多边形障碍物，都以其几何图形的所有顶点为圆心，10为半径设定障碍限定区域，对于唯一的圆形障碍物，则设定其半径增大10个单位的同心圆作为障碍限定区域。那么，在该存在圆形限定区域的行走最短路径，必定是由若干个线圆结构组成，每个线圆结构都是由直线段和圆与之相切的采用最小转弯半径转过障碍物顶点的圆弧构成，这些线圆结构之间也都是相切的。对于途中遇到内公切线、外公切线、圆形障碍物等三种变形线圆结构时，我们都将它们变换成基本线圆结构来处理。对于途中经过若干个节点再到达目标点的情况，我们考虑在每个节点位置设计一个过节点的动圆，依然采用最小转弯半径的圆弧方式通过这些节点，使得这些节点恰好处于该转弯弧段（优弧）的中点位置。

我们采用“自然下垂法”和“拉绳法”相结合的方式解决避障最短时间路径问题，即问题二的解决思路为：由于问题一已经找到了从O到A最短路径，如果要缩短行走时间，只能适当增加转弯半径（即），用以增大圆弧行走距离，从而提高走圆弧时的速度。因此，我们设计一个圆心坐标、半径（略大于10）的动圆，保持自然下垂方式，使其始终跟圆心在第5个障碍物左上顶点，半径为10的定圆内切（定圆始终在动圆的上半圆内内切），从而转化为可以用“拉绳法”解决的问题了。然后在，和的条件下求时间目标函数最小。

问题一，我们通过比较可能的有效路径的长度，得到各个最短路径。

O→A的最短路径距离：471.0372

O→B的最短路径距离：861.3865

O→C的最短路径距离：1091.3

O→A→B→C→O的最短路径距离：2773.023

其中，线圆结构路径上的各起终点坐标见正文中表格一。

问题二，我们通过简单编程优化计算，得到最短时间路径，并采用MATLAB严格做出路径图，吻合度非常好。

O→A：最短总时间为94.2283，总距离为472.0657。

起点坐标

终点坐标

圆心坐标和半径

直线段一

O(0，0)

(69.8072，211.9813)

圆弧段

(69.8072，211.9813)

(77.7492，220.1394)

（82.14,207.92）、12.9843

直线段二

(77.7492，220.1394)

A(300,300)

【关键词】避障最短路径最短时间路径拉绳法自然下垂法

一、问题重述

图1是一个800×800的平面场景图，在原点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个单位，否则将发生碰撞，若碰撞发生，则机器人无法完成行走。

机器人直线行走的最大速度为个单位/秒。机器人转弯时，最大转弯速度为，其中是转弯半径。如果超过该速度，机器人将发生侧

翻，无法完成行走。

请建立机器人从区域中一点到达另一点的避障最短路径和最短时间路径的数学模型。对场景图中4个点O(0,0)，A(300,300)，B(100,700)，C(700,640)，具体计算：

(1)机器人从O(0,0)出发，O→