没有合适的资源?快使用搜索试试~ 我知道了~
Inself算法论文1
需积分: 0 0 下载量 16 浏览量
2022-08-04
15:33:42
上传
评论
收藏 1.2MB PDF 举报
温馨提示
试读
28页
摘要i第一章 项目简介 11.1 项目背景 11.2 项目制作的目的与意义 11.3 项目创新点 2第二章 常见栅格地图算法简介 22.1 广度优先搜索(BFS
资源详情
资源评论
资源推荐
第二十九届“冯如杯”学生学术科技作品竞赛
项目论文
Inself 多机协同路径规划
——基于栅格化地图的启发式寻路算法
i
摘要
本文主要设计一种路径规划算法以及多机协控策略,针对二维和三维情景下
的较长距离寻路问题,以栅格化地图方案进行规划、最后优化为非栅格化路径。
主要瞄准无人机等运算时空开支小的路径导航,在牺牲小的长度优势、换取时间
和空间上开支的大大减少,为了适应现实中模拟地图寻路,最后将栅格化路径再
次优化得到方向角度任意的模拟路径;同时以十架无人机为例描述一种多机协控
移动的策略。
在栅格路径规划方面,我们借鉴了 A*的启发式算法,将启发式搜索应用在
时空消耗较小但长度没有保证的深度优先搜索(DFS)中得到第一级路径,再利
用视线导引法对所得路径进行优化修正,提出 Inself 算法,能够快速、省空间地
得到较优路径结果。并以游戏界常用的 A*算法以及 Dijkstra 算法甚至广度优先搜
索(BFS)算法作为靶算法进行对比,分析并测试二维和三维栅格地图下路径规
划的速度和空间优势。结果表明,在 600*600 地图下,Inself 的平均时间为 A*的
8.26%、BFS 算法的 0.025%,开拓点数为 A*算法的 69.18%、BFS 算法的 1.11%,
而路径长度平均增长为最短路径的 0.26%。在低牺牲路径长度情景下,有效减少
了运算时空开支。最后基于最大三角形的思想,将栅格化地图路径还原到模拟地
图中。
而在多机协控方面,首先以二维和十架无人机为例,提出了一种弹性绕圈式
的编队策略,在多种遇障和阻碍情境下给出解决的调度策略,尽可能保持队形移
动;而三维时则仍采用二维的队形,在其基础上多增加一个维度且优先保持同一
水平面的编队移动策略。
关键字:规划算法,栅格地图,多机协同。
ii
Abstract
This paper mainly designs a path planning algorithm and multi-machine
co-control strategy, The rasterized map scheme is used to plan and optimize the
rasterized path for the problem of long distance pathfinding in 2d and 3d scenarios. In
order to adapt to the reality of simulated map pathfinding, the rasterized path was
optimized again to obtain the simulation path with arbitrary direction and Angle.At the
same time, ten planes are taken as an example to describe a multi-machine co-control
movement strategy.
In the planning of the grid path, we draw lessons from the A * heuristic algorithm,
the heuristic search application in space and time consumption but smaller length,
there is no guarantee that the depth first search (DFS) of the first level path, reusing the
line of sight guidance method to optimize the path correction, Inself algorithm, was
able to get A better path quickly and save space. After Analyzing and test the speed and
spatial advantage of path planning in 2d and 3d raster maps, we found that under the
600*600 map, the average time of Inself is 8.26% of A*, 0.025% of BFS algorithm,
69.18% of A* algorithm and 1.11% of BFS algorithm, and the average growth of path
length is 0.26% of the shortest path. In the case of low sacrifice path length, the
computation time and space cost can be reduced effectively. Finally, based on the idea
of maximum triangle, the rasterized map path is restored to the simulated map.
In the aspect of multi-aircraft co-control, firstly, taking the two dimensional and
ten planes as an example, a flexible formation strategy is proposed, and the scheduling
strategy is given under various obstacles and obstacles to keep the formation moving
as far as possible. In the case of 3d, the formation is still in the form of 2d. The
formation movement strategy is to add one more dimension on the basis of the
formation and keep the same horizontal plane in priority.
Keywords
Planning algorithm, Raster map, Multiple cooperating
iii
目录
摘要 ..................................................................................................................................... i
Abstract ............................................................................................................................... ii
第一章 项目简介 .............................................................................................................. 1
1.1 项目背景 .............................................................................................................. 1
1.2 项目制作的目的与意义 ...................................................................................... 1
1.3 项目创新点 .......................................................................................................... 2
第二章 常见栅格地图算法简介 ...................................................................................... 2
2.1 广度优先搜索(BFS) ....................................................................................... 2
2.2 Dijkstra 算法 ........................................................................................................ 4
2.3A*算法 .................................................................................................................. 5
2.4 深度优先搜索(DFS) ....................................................................................... 6
第三章 Inself 算法 ............................................................................................................ 6
3.1 栅格地图规划 ...................................................................................................... 6
3.1.1 第一级:启发式深搜 ............................................................................... 7
3.1.2 第二级:视线导引法 ............................................................................... 8
3.1.3Inself 算法栅格地图部分伪代码 ............................................................ 10
3.2 回归模拟地图 .................................................................................................... 10
第四章 Inself 算法性能测试分析对比 .......................................................................... 12
4.1 复杂度分析对比 ................................................................................................ 12
4.2 蒙特卡洛仿真测试对比 .................................................................................... 13
4.2.1 二维情况测试对比 ................................................................................ 13
4.2.2 三维情况测试对比 ................................................................................ 16
第五章 多机协同 ............................................................................................................ 17
5.1 协控调度策略 .................................................................................................... 17
5.1.1 二维栅格地图情景 ................................................................................. 17
5.1.2 三维栅格地图情景 ................................................................................. 18
5.2 多机演示效果 .................................................................................................... 19
5.2.1 路径规划实测效果 ................................................................................. 19
iv
5.2.2 多机协同实测效果 ................................................................................. 20
结论 .................................................................................................................................. 22
参考文献 .......................................................................................................................... 23
剩余27页未读,继续阅读
人亲卓玛
- 粉丝: 30
- 资源: 329
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0