基于双向A-算法的城市无人机航路规划

《基于双向A-算法的城市无人机航路规划》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、文章编号：2095-1248（2016）04-0055-06信息科学与工程*基于双向Ａ算法的城市无人机航路规划林娜，李天啸（沈阳航空航天大学计算机学院，沈阳110136）摘要：应用双向Ａ*算法对在城市环境中的无人机进行航路规划，对比传统的Ａ*搜索算法，双向Ａ*搜索算法提高了搜索的效率，大大缩短了航路规划的时间。同时针对双向Ａ*算法现有的不足，对双向Ａ*算法进行改进，提出了同步双向Ａ*搜索算法思想，通过编程实现双向Ａ*算法正向搜索和反向搜索同步进行，并且采用栅格法对无人机的飞行环境进行建模，在建模时充分考虑城市环境确定栅格的大小。通过实验验证，同步双向Ａ*算法可以快速为无人机规划出航路，

2、且航路可飞，对比改进前的双向Ａ*算法，同步双向Ａ*算法的航路规划速度更快，效率更高。关键词：无人机；双向Ａ*；栅格法；城市环境；航路规划中图分类号：ＴＰ391．9文献标志码：Ａdoi：10．3969／ｊ．ｉｓｓｎ．2095-1248．2016．04．010*UrbanUAVrouteplanningbasedonbidirectionalAalgorithmＬＩＮＮａ，ＬＩＴｉａｎ-ｘｉａｏ（ＣｏｌｌｅｇｅｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅ，ＳｈｅｎｙａｎｇＡｅｒｏｓｐａｃｅＵｎｉｖｅｒｓｉｔｙ，Ｓｈｅｎｙａｎｇ110136，Ｃｈｉｎａ）*Abstract：Ｔｈｅｂｉｄｉｒｅｃｔｉｏｎ

3、ａｌＡａｌｇｏｒｉｔｈｍｗａｓａｐｐｌｉｅｄｉｎｔｈｅｕｒｂａｎＵＡＶｒｏｕｔｅｐｌａｎｎｉｎｇ．Ｃｏｍｐａｒｅｄｗｉｔｈｔｈｅ**ｔｒａｄｉｔｉｏｎａｌＡｓｅａｒｃｈａｌｇｏｒｉｔｈｍ，ｔｈｅｓｙｎｃｈｒｏｎｏｕｓｂｉｄｉｒｅｃｔｉｏｎａｌＡｓｅａｒｃｈａｌｇｏｒｉｔｈｍ，ｔｈｅｉｍｐｒｏｖｅｄｂｉｄｉｒｅｃｔｉｏｎ-*ａｌＡｓｅａｒｃｈａｌｇｏｒｉｔｈｍ，ｈａｓｈｉｇｈｅｒｓｅａｒｃｈｅｆｆｉｃｉｅｎｃｙ，ａｎｄｓａｖｅｓｇｒｅａｔｔｉｍｅｏｆｒｏｕｔｅｐｌａｎｎｉｎｇ．Ｅｘｐｅｒｉｍｅｎｔｗａｓｂｕｉｌｔｔｏｒｅａｌｉｚｅｔｈｅｆｏｒｗａｒｄｓｅａｒｃｈａｎｄｔｈｅｂａｃｋｗａｒ

4、ｄｓｅａｒｃｈｗｏｒｋｉｎｇｏｎｔｈｅｓａｍｅｔｉｍｅｂｙｕｓｉｎｇｔｈｅｇｒｉｄｍｅｔｈ-ｏｄｔｏｂｕｉｌｄｔｈｅｅｎｖｉｒｏｎｍｅｎｔｍｏｄｅｌｆｏｒＵＡＶｓ．Ｉｔｗａｓｆｕｌｌｙｃｏｎｓｉｄｅｒｅｄｔｈａｔｔｈｅｕｒｂａｎｅｎｖｉｒｏｎｍｅｎｔｔｏｄｅｔｅｒｍｉｎｅｔｈｅｇｒｉｄｓｉｚｅｗｈｉｌｅｂｕｉｌｄｉｎｇｔｈｅｅｎｖｉｒｏｎｍｅｎｔｍｏｄｅｌ．Ｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｈｏｗｓｔｈａｔｔｈｅｓｙｎｃｈｒｏｎｏｕｓｂｉｄｉｒｅｃｔｉｏｎａｌ*Ａａｌｇｏｒｉｔｈｍｉｓｍｏｒｅｅｆｆｉｃｉｅｎｔｓｉｎｃｅｉｔｃａｎｍａｋｅｔｈｅｒｏｕｔｅｐｌａｎｎｉｎｇｆａｓｔｅｒ

5、ｆｏｒＵＡＶｓａｎｄｔｈｅｒｏｕｔｅｆｌｙａｂｌｅ．*Keywords：ｕｎｍａｎｎｅｄａｅｒｉａｌｖｅｈｉｃｌｅ（ＵＡＶ）；ｂｉｄｉｒｅｃｔｉｏｎａｌＡ；ｇｒｉｄ；ｔｈｅｕｒｂａｎｅｎｖｉｒｏｎｍｅｎｔ；ｒｏｕｔｅｐｌａｎｎｉｎｇ*Ａ算法是一种经典的启发式搜索算法，并广围缩小，缩短了算法的时间，提高了算法的搜索效**［2］泛应用于路径搜索问题中。Ａ算法的思想最早率；何雨枫、曾庆化等提出了无记忆Ａ算法的*由Ｐ．ＥＨａｉｔ和Ｎ．ＪＮｉｌｓｓｏｎ提出，在以后的应用中思想，针对Ａ算法的ＯＰＥＮ表和ＣＬＯＳＥ表进行得到了不断的改进与发展。如：Ｊ．Ｓｚｃｚｅｒｂａ提出改进，使ＯＰＥＮ表中的节点数

6、每次都保持最小，**［1］了稀疏Ａ算法（ＳｐａｒｓｅＡＳｅａｒｃｈ，ＳＡＳ），其主从而提高算法的计算速度。**要思想为通过一个约束函数将Ａ算法的搜索范而以上方法都是基于单一方向的Ａ算法，收稿日期：2015-10-28基金项目：辽宁省自然科学基金联合基金（项目编号：2015020008）；辽宁省自然科学基金（项目编号：20102175）；辽宁省高等学校优秀人才支持计划（项目编号：ＬＪＱ2012011）。作者简介：林娜（1977-），女，辽宁沈阳人，副教授，主要研究方向：无人机航路规划，智能交通，Ｅ-ｍａｉｌ：ｌｉｎｎａ2000@163．ｃｏｍ。56沈阳航空航天大学学报第33卷即从起始节点

7、向目标节点搜索。而本文将应用双障碍节点；若栅格空间内不包含障碍物，则将其视*向Ａ算法对无人机的航路进行搜索，并针对传为自由节点。*统双向Ａ算法存在的不足，提出了同步双向启目前，无人机可分为固定翼无人机和旋翼无*发式Ａ算法，将其应用于栅格建模环境中。人机两大种类，旋翼无人机相比于固定翼无人机［3］*栅格思想由Ｍ．Ｂ．Ｍｅｔｅａｓ提出，而Ａ算来说，其机动性及其可悬停性更适合在城市环境法便是基于栅格空间的一个经典的路径规划算中飞行和执行任务。*法。应