A＊的改进路径规划算法

《A＊的改进路径规划算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第7卷第4期信息与电子工程VO1．7．No．42009年8月INFORMATIONANDELECTRONICENGINEERINGAug．，2009文章编号：1672-2892(2009)04-0326-04A冰的改进路径规划算法漆阳华，杨战平，黄清华(中国工程物理研究院电子工程研究所，四川绵阳621900)摘要：通过对地图数据的预处理和启发函数的设计，对A算法进行了改进。利用VC++编程实现改进算法，并在实际城市地图上对改进算法进行了验证，结果表明改进算法提高了搜索最优路径的成功率，同时解决了原算法易出现搜索死循环的问题，可适应不规则的城市路网。关键词：路径规划；A{算法；启

2、发函数中图分类号：TUl98．1文献标识码：AImprovedpathplanningalgorithmbasedonA术algorithmQIYang—hua，YANGZhan—ping，HUANGQing—hua(InstituteofElectronicEngineering，ChinaAcademyofEngineeringPhysics，MianyangSichuan621900，China)Abstract：Aalgorithmwasimprovedbypre—beatingmapdataandselectingappropriatedevelopmentalfun

3、ction．AnexperimentwascarriedoutbycodingwithVC++．Theresultshowedthattheimprovedalgorithmincreasedsuccessrateofoptimalpathsearching，andsolvedrepetitionproblemofAalgorithm．Thisalgorithmcouldadaptwelltoirregularcitypathnetwork．Keywords：pathplanning；Aalgorithm；developmentalfunctionA算法是建立在Dijkstra

4、算法基础上的启发式搜索算法【l】，其主要特点在于选择下一个路径节点时引人了已知的路网信息，特别是目标点信息，计算所有候选节点到目标点之间的某种目标函数(比如最短距离、最小时间等等)，以此作为评价候选节点是否属于最优路径节点的指标，优先选择具有最优目标函数的候选节点作为下一个路径节点。根据实际路径规划目的，可以设计多种目标函数的最优路径，比如距离最短、时间最少、运输成本最低和拥挤程度最小等等。尽管不同优化目标可对应不同优化算法，但它们或多或少都与路段距离相关。不失一般性，本文以起点与目标点之间的最短路径作为优化目标，探讨对A+算法的改进。A算法被证明是最佳优先算法【2】，然而实际

5、城市路网的拓扑关系纷繁复杂，与理想网络差别较大，利用A+算法进行最短路径规划时常会出现“死循环”【3】，找不到起点与目标点间路径，以至影响其实用性【4J。本文拟对A·算法加以改进，使之适应路网复杂的城市导航应用。lA算法简介及其分析1．1A·算法基本思想及实现步骤A+算法的关键是确立如下形式的启发函数，()g(”)+(")(1)式中：g(n)是从起点到候选节点实际花费的代价；h(n)是从候选节点到目标点的估计代价。通过比较f(n)，选取代价最小的候选节点作为下一路径节点。A算法的实现步骤如下：1)以起点为第1个路径节点，寻找与之相连的候选节点；2)对与之相连的每一个候选节点，计

6、算其启发函数值，选出函数值最小的节点作为下一个路径节点；3)如果该节点是目标点，则终止规划，否则，进入第2步，以新的路径节点为起点继续规划，并记录搜索到的最短路径。收稿日期：2008．12．24；修回日期：2009．02．05第4期漆阳华等：A水的改进路径规划算法3271．2A算法存在的问题A算法在搜索过程中通过引入启发信息来实现向目标节点移动的判别，无需遍历地图，使得计算复杂度相对较小，实现了快速、高效。但是，这也导致了搜索的过程中就删除了大量节点，而由于经验及实际问题的复杂性，引入启发信息的代价函数无法做到完全正确，这些被删除的节点可能就是最优路径的节点之一，其过早的删除，

7、使得最终搜索到的路径可能是一个次优的结果【4；还可能引起最坏的状况：使得搜索过程形成环路而限人“死循环”，最终无法搜索到目标路径。2A算法的改进2．1区域划分通过对中国城市地图的研究，发现它们多被弯曲并且交汇的河道分隔成数块，使得这些城市的道路网络分布不规则：在某个区域的道路网络密集，而在另外一个区域的道路网络稀疏。根据文献[3】和文献[4】的算法介绍，采用候选节点到目标节点的直线距离作为估价函数，在仿真中发现，对于这种不规则的道路网络，如果不采取任何处理，就会使A算法陷入“死循环”。为提高