本文研究了机器人避障的最短路径和最短时间问题

本文研究了机器人避障的最短路径和最短时间问题，主要研究了在一个区域内存在12个不同形状的障碍物，由出发点到达目标点避开障碍物的最短路径和最短时间两个问题。

首先，利用已学的数学知识证明了具有圆形限定区域的最短路径是由线圆结构组成的，并且机器人转弯时的圆弧是以障碍物的顶点为圆心，10个单位为半径的圆弧时，路径最短。

其次，对于途中需要多次转弯到达目标点的状况，适当扩大拐点处的转弯半径，使得机器人能够沿直线通过途中的目标点，从而减少转弯次数。

再次，我们针对问题一的四种路径给出了每种路径的所有可能的行走方案，然后运用绘图工具软件几何画板和matlab等进行图示和运算，得出最短路径如下

距离 距离 距离 距离 O?A O?B O?C O?A?B?C?O470.96 853.55 1088.78 2756.03 最后，在最短时间问题中，我们建立了所需时间t关于转弯时圆弧的圆心坐标?x,y?和半径r的一般模型，然后通过前面的猜想，分析出了从O?A的最短时间路径所经过的圆弧的圆心必然在正方形障碍5的对角线上，并且圆弧通过点(80?50,210?50)，然后运用MATLAB软件，通过编程计算出了最短时间为94.2283。

关键词：最短路径 最优化模型 最短时间 几何画板画图 MATLAB

一、问题重述

1.1 背景材料：

在一个800×800的平面场景，在原点（0，0）点处有一个机器人，他只能在该平面场景内活动，图中12个不同形状的区域是机器人不能碰撞的障碍物，障碍物描述如下： 编号 障碍物名称 正方形 圆形 平行四边形 三角形 正方形 三角形 长方形 平行四边形 长方形 正方形 正方形 长方形 左下顶点坐标 (300, 400) (360, 240) (280, 100) (80, 60) (60, 300) (0, 470) (150, 600) (370, 680) (540, 600) (640, 520) (500, 140) 其它特性描述 1 2 3 4 5 6 7 8 9 10 11 12

边长200 圆心坐标(550, 450)，半径70 底边长140，左上顶点坐标(400, 330) 上顶点坐标(345, 210)，右下顶点坐标(410, 100) 边长150 上顶点坐标(150, 435)，右下顶点坐标(235, 300) 长220，宽60 底边长90，左上顶点坐标(180, 680) 长60，宽120 边长130 边长80 长300，宽60 图一 800*800平面场景图

1.2 问题提出：

问题一：建立机器人从区域中一点到达另一点的避障最短路径和最短时间路径的数学

模型。对场景图中4个点O(0, 0)A(300, 300)B(100, 700)C(700, 640)中计算机器人从O(0, 0)出发O→A、O→B、O→C和O→A→B→C→O的最短路径。 问题二：机器人从O(0,0)出发到达A的最短时间路径。 注：要给出路径中每段直线段或圆弧的起点和终点坐标、圆弧的圆心坐标以及机器人行走的总距离和总时间。

二、 问题分析

1、问题一中要求由定点O（0, 0）按照一定的行走规则绕过障碍物到达单一目标点的最短

路径，我们可以先用线段和半径为10个单位的小圆画出机器人行走的危险区域，这样的话，拐角处就是一个半径为10的圆弧。在生活中我们有这样的常识，在空间中求两点（如A,B）间的最短路径，我们就可以连接B和A之间的一段绳子，以拐角处的圆弧为支撑,然后拉紧绳子，那么这段绳子的长度便是B到A的一条可能的最短路径，我们如今采用的就是这种办法。同理，我们用软件画出由点O到目标点的每种路程最短的可能路径，然后比较其大小便可得出O到目标点的最短路径。

图二 考虑边界以后的障碍物图形

2、问题一的第二问中要求由定点O（0， 0）经过中间的若干目标点到达最终目标点，这

使我们考虑就不仅仅是经过障碍物拐点的问题，也应该考虑经过路径中的目标点处转弯的问题，这时简单的线圆结构就不能解决这种问题，我们在拐点及途中目标点处都采用最小转弯半径的形式，也可以适当的变换拐点处的拐弯半径，使机器人能够沿直线通过途中的目标点，然后建立优化模型对这两种方案分别进行优化，最终求得最短路径。

三 模型假设与符号说明

3.1模型假设

1.假设机器人为一个质点。

2.假设障碍物的数学描述准确无误。

3.假设机器人的速度不受其他外部因素影响。

3.2 符号说明

符号 L 符号说明 路径的总长度 第段切线的长度 第段圆弧的长度 转弯半径 第i个特征顶点符号 第i个点x轴坐标 第i个点y轴坐标 机器人是否从i顶点到j顶点 第i个顶点到第j个顶点的距离 d

vi xi yir xij l ij 四 模型的建立与求解

4.1 猜想证明

猜想：具有圆形限定区域的最短路径是由两部分组成的：一部分是平面上的自然最短路径（即直线段），另一部分是限定区域的部分边界，这两部分是相切的，互相连接的。

证明：

如上图所示，AK，BL分别与圆O相切于KL两点，AD，AD,EF,GH,BI分别为对应圆的切线。

两点之间线段最短，很明显图中外环路径比内环路径长，从而易得任意隔着障碍物两点间最短距离都是和障碍物边界相切时最短。

由此可得，亦即路径AEHB的长度超过路径AKLB的长度。以上证明足以说明了AKLB

本文来源：https://www.bwwdw.com/article/395h.html