没有合适的资源?快使用搜索试试~ 我知道了~
机器人避障问题的解题分析(建模集训).doc
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 136 浏览量
2021-10-11
22:28:45
上传
评论
收藏 1.19MB DOC 举报
温馨提示
![preview](https://dl-preview.csdnimg.cn/31522523/0001-9f84e7ce0309c605ed8daa95a4f4dbd2_thumbnail-wide.jpeg)
![preview-icon](https://csdnimg.cn/release/downloadcmsfe/public/img/scale.ab9e0183.png)
试读
27页
机器人避障问题的解题分析(建模集训).doc
资源推荐
资源详情
资源评论
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![](https://csdnimg.cn/release/download_crawler_static/31522523/bg1.jpg)
机器人避障问题的解题分析
摘要:本文对 2012 年全国大学生数学建模竞赛 D 题机器人避障问题进展了全面分析,对最短路的设计进
展了理论分析和证明,建立了机器人避障最短路径的几何模型,对最短时间路径问题通过建立非线性规划
模型,有效地解决了转弯半径、圆弧圆心位置和行走时间等问题。
关键词:机器人避障;最短路径;Dijkstra 算法;几何模型;非线性规划模型
1 引言
随着科学技术的进步和计算机技术的开展,机器人的应用越来越广泛,在机器人的应
用中如何使机器人在其工作围为完成一项特定的任务寻找一条安全高效的行走路径,是人
工智能领域的一个重要问题。本文主要针对在一个场景中的各种静态障碍物,研究机器人
绕过障碍物到达指定目的地的最短路径问题和最短时间问题。
本文以 2012 年“高教社〞杯全国大学生数学建模竞赛 D 题“机器人避障问题〞为例进
展研究。假设机器人的工作围为 800×800 的平面正方形区域〔如图 1〕,其中有 12 个不
同形状的静态障碍物,障碍物的数学描述〔如表 1〕:
图 1 800×800 平面场景图
1 / 27
![](https://csdnimg.cn/release/download_crawler_static/31522523/bg2.jpg)
表 1
编号 障碍物名称 左下顶点坐标 其它特性描述
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
在原点O(0,0)点处有一个机器人,它只能在该平面场景围活动,机器人不能与障碍物
发生碰撞,障碍物外指定一点为机器人要到达的目标点。规定机器人的行走路径由直线段
和圆弧组成,其中圆弧是机器人转弯路径。机器人不能折线转弯,转弯路径由与直线路径
相切的一段圆弧组成,也可以由两个或多个相切的圆弧路径组成,但每个圆弧的半径最小
为10个单位。为了不与障碍物发生碰撞,同时要求机器人行走线路与障碍物间的最近距离
为10个单位,否那么将发生碰撞,假设碰撞发生,那么机器人无法完成行走。机器人直线
行走的最大速度为 个单位/秒。机器人转弯时,最大转弯速度为
〔 是转弯半径〕。如果超过该速度,机器人将发生侧翻,无法完
成行走。
场景图中有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的最短时间路径问题。
2 静态避障问题中机器人行走最短路径的分析
2 / 27
![](https://csdnimg.cn/release/download_crawler_static/31522523/bg3.jpg)
2.1 行走路径的设计
在本例中障碍物有 4 种不同形状:矩形、平行四边形、三角形和圆形。考虑到机器人
本身的形状和大小,为研究方便起见,将机器人视为一个点。机器人与障碍物之间的距离
至少为 10 个单位,因此可以先用包络线画出机器人行走的危险区域〔如图 2〕,包络线是
机器人的禁入区。
图 2 障碍物包络图
对障碍物的一个角点来说,其禁入区的边界应由两条直线和一条圆弧组成,两条直线
分别平行于角点的两条边,间距为 10 个单位,圆弧是以障碍物角点为圆心,半径为 10 个
单位的四分之一圆弧。可以证明具有圆形限定区域的最短路径由两局部组成,一局部是平
面上的自然最短路径〔直线段〕,另一局部是限定区域的局部边界〔即绳子拉到最紧时的
圆弧局部〕,这两局部是相切的,互相连接〔如图 3 所示〕。由 A 绕过半圆形障碍物到达
B 点的路径有多条,其中最短路径为 (E、F 为切点),其他路径与 AB 直线围成的区
域都覆盖这一路径与 AB 直线围成的区域,由此证明
[1]
。
3 / 27
![](https://csdnimg.cn/release/download_crawler_static/31522523/bg4.jpg)
图 3
由此可以确定机器人的行走路径应为线圆结构,那么是否是转弯半径越小,行走路径
就越短呢?为此需要求在两个固定点和圆弧圆心坐标的情况下,圆弧半径 r 为何值,才能
使机器人的行走路径最短。
图 4
如图 4 , 两 个 固 定 点 , 圆 心 ,可 以 求 得 两 切 点 坐 标
,设半径为 ,圆弧 所对的圆心角为 , 的路径长度为
,那么
将路径函数 对 求导,得
因为 , ,所以 .
,那么函数 为单调递增函数,因此当圆弧半径 逐渐增加时,机器人的行走
路径会增大, 逐渐降低时,机器人的行走路径会减小
[2]
,此题规定转弯半径最小为 10 个
单位,所以在路径设定时应将转弯半径设定为最小值 10 个单位。
根据以上分析,对于静态障碍物机器人的行走路径应遵循以下三个原那么:
原那么一:机器人的行走路径为线圆结构,由两条切线和一段圆弧组成;
原那么二:每个路口至多发生一次转弯,并以障碍物顶点为转弯圆弧的中心;
原那么三:机器人转弯圆弧半径为最小允许半径 10 个单位。
2.2 最短路径的选择
4 / 27
![](https://csdnimg.cn/release/download_crawler_static/31522523/bg5.jpg)
从起点到达目标点有多条路径,根据 Dijkstra 算法可以找出从起点到达每一个目标点
的最短路径。本文采用带权的有向图表示机器人的行走路径,途中节点为障碍物的角点,
边表示障碍物之间的联系,权表示线路的长度〔节点之间的直线距离〕。从顶点出发,沿
图的边到达另一顶点所经过的路径中,各边上权值之和最小的一条路径就是所求最短路径,
Dijkstra 算法就是按路径的长度递增次序产生最短路径的算法
[3]
。
下面以 为例,确定 的最短路径。
如图 5 所示,根据障碍物的形状和位置,本文给出了机器人从 O(0,0)出发避过障碍物
到达目标 B 点的 4 条较优路径。
图 5
画出 的非循环网络图〔如图 6〕:
5 / 27
B
621
306
O
230
60
112
171
225 99
216
470
179
78162
238
B
5
B
3
B
6
B
2
B
4
B
1
B
9
B
77
B
8
0
171
112
99
569
237399
705
159
508 329
剩余26页未读,继续阅读
资源评论
![avatar-default](https://csdnimg.cn/release/downloadcmsfe/public/img/lazyLogo2.1882d7f4.png)
![avatar](https://profile-avatar.csdnimg.cn/default.jpg!1)
yunxidzh
- 粉丝: 60
- 资源: 30万+
![benefits](https://csdnimg.cn/release/downloadcmsfe/public/img/vip-rights-1.c8e153b4.png)
下载权益
![privilege](https://csdnimg.cn/release/downloadcmsfe/public/img/vip-rights-2.ec46750a.png)
C知道特权
![article](https://csdnimg.cn/release/downloadcmsfe/public/img/vip-rights-3.fc5e5fb6.png)
VIP文章
![course-privilege](https://csdnimg.cn/release/downloadcmsfe/public/img/vip-rights-4.320a6894.png)
课程特权
![rights](https://csdnimg.cn/release/downloadcmsfe/public/img/vip-rights-icon.fe0226a8.png)
开通VIP
上传资源 快速赚钱
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![voice](https://csdnimg.cn/release/downloadcmsfe/public/img/voice.245cc511.png)
![center-task](https://csdnimg.cn/release/downloadcmsfe/public/img/center-task.c2eda91a.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![dialog-icon](https://csdnimg.cn/release/downloadcmsfe/public/img/green-success.6a4acb44.png)