没有合适的资源?快使用搜索试试~ 我知道了~
基于A*搜索的无人机防撞研究
需积分: 0 8 下载量 23 浏览量
2014-01-18
22:29:59
上传
评论
收藏 2.31MB PDF 举报
温馨提示
试读
53页
一篇关于无人机防撞的硕士论文,详细介绍了目前的防撞算法,采用A*改进算法,并在无人机平台了验证了有效性
资源推荐
资源详情
资源评论
UAV Collision Avoidance using A* Algorithm
by
Tingsheng Liao
A thesis submitted to the Graduate Faculty of
Auburn University
in partial fulfillment of the
requirements for the Degree of
Master of Science
Auburn, Alabama
May 7, 2012
Keywords: UAV, collision avoidance, A* algorithm, heuristic
Copyright 2012 by Tingsheng Liao
Approved by
Thaddeus Roppel, Co-Chair, Associate Professor of Electrical and Computer Engineering
Saad Biaz, Co-Chair, Associate Professor of Computer Sicence and Software Engineering
John Hung, Professor of Electrical and Computer Engineering
Abstract
Collision avoidance is the essential requirement for unmanned aerial vehicles (UAVs) to
become fully autonomous. Several algorithms have been proposed to do the path planning
in a simulated environment, but only few can make them effectively survive in a dynamic
environment. This issue keeps UAVs from commercial and other applications because when
the UAVs fly autonomously, the inability to reliably sense and avoid other aircraft in the air
can cause serious hazards.
In this thesis, we review several approaches including A∗ algorithm, total field sensing
approach, and Markov decision process. Then, a modification of A∗ algorithm is proposed.
Typically, A∗ algorithm is implemented in a mobile robot system for the path planning in
a static environment. We introduce some approaches to allow us using A∗ algorithm in
a dynamic environment. The evaluation of this algorithm is based on the simulation of
different scenarios, and the comparison between two heuristic functions will be detailed. We
discuss the performance of our approach, the suitable condition for it to work reliably, and
what issues could affect its performance. We also investigate the limitation of our approach
in the extreme scenarios to provide useful suggestions for improvement.
ii
Table of Contents
Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii
List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
2 Literature Review . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.1 Geometric Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.1.1 Free Flight . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.1.2 Point of Closest Approach . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 Stochastic Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2.1 Markov Decision Process . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.3 Linear Programming Approach . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.3.1 Mixed Integer Linear Programming . . . . . . . . . . . . . . . . . . . 8
2.4 Potential Fields Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.4.1 Total Field . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.4.2 Force Field . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.5 Grid-based Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.5.1 Search Trees Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.5.2 Heuristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.5.3 A
∗
Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3 UAVs Collision Avoidance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.1 Easy Star . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.2 Conflict Detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.2.1 Intruder Awareness . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
iii
3.2.2 Conflict Determination . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.3 Collision Avoidance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.3.1 A
∗
algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.3.2 Dangerous Grids . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.3.3 Heuristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
4 Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
4.1 The Simulation Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
4.2 Simulation in a 500 m × 500 m field . . . . . . . . . . . . . . . . . . . . . . . 30
4.3 Simulation in a 1000 m × 1000 m field . . . . . . . . . . . . . . . . . . . . . 34
4.4 Relation Between Number of UAVs and Metrics . . . . . . . . . . . . . . . . 36
4.5 Extreme cases for UAVs collision avoidance . . . . . . . . . . . . . . . . . . . 39
4.6 Comparison with Other Algorithms . . . . . . . . . . . . . . . . . . . . . . . 40
5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
iv
List of Figures
2.1 Illustration of free flight protected and alert zones. [24] . . . . . . . . . . . . . . 4
2.2 Illustration for Point of Closest Approach method. [32] . . . . . . . . . . . . . . 5
2.3 Magnetic flux density around a magnetic dipole [38] . . . . . . . . . . . . . . . 10
2.4 (a) Surrounding field along the x-axis (b) Surrounding field along the y-axis [38] 10
2.5 Shakey, the mobile robot system. 1966 through 1972 [1](Photograph courtesy of
SRI International.) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.6 Illustration of Shakey’s navigation problem[31](Original image from SRI Interna-
tional) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.7 A
∗
path search around an obstacle.[40] . . . . . . . . . . . . . . . . . . . . . . . 16
3.1 Easy Star, the Unmanned Aerial Vehicle . . . . . . . . . . . . . . . . . . . . . . 18
3.2 Illustration of intruder awareness. . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.3 Classification of protected zones, including Traffic Advisory Zone, Resolution
Advisory Zone, and Autonomous Avoidance Zone. . . . . . . . . . . . . . . . . 21
3.4 Collision avoidance architecture . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.5 Illustration of A∗ path finding algorithm.[27] . . . . . . . . . . . . . . . . . . . 23
3.6 The dangerous grids changes with the different time step. . . . . . . . . . . . . 25
v
剩余52页未读,继续阅读
资源评论
柳无非
- 粉丝: 0
- 资源: 1
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功