资源描述：
《A_算法在基于道路网的路径规划中的应用》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第4期Vo.l5No.42010年8月JournalofCAEITAug.2010工程与应用*A算法在基于道路网的路径规划中的应用苏浩,李钦富,蔡俊(中国电子科学研究院,北京100041)*摘要:通过分析启发式搜索算法中A算法的特点及沿道路网运动实体机动模型的路径规划需*求,提出了一种以道路网结点为对象的不规则格网栅格化处理方法;在此基础上,给出了构建A算法搜索空间和搜索结果连续化处理的方法和步骤。并结合典型实例,进行了仿真试验分析,验证了所提出算法的可行性与高效性。关键词:路径规划;道路网络;路径搜索;搜索空间中图分类号:
2、TP391文献标识码:A文章编号:16735692(2010)0441904*AAlgorithmApplicationinPathPlanningBasedonRoadNetworkSUHao,LIQinfu,CAIJun(ChinaAcademyofElectronicsandInformationTechnology,Beijing100041,China)*Abstract:ByanalyzingthecharacteristicsofAalgorithmofheuristicsearchandtherequir
3、ementofpathplanningformaneuvermodelofunitbasedonroadnetwork,akindofroadnetworknodestargetingofirregulargridprocessingmethodisproposed,andonthebasisofi,ttheapproachandprocedureforcon*structingAalgorithmsearchspaceandcontinuousprocessingthesearchresultarealsogiven.Withth
4、etypicalinstance,asimulationtestinganalysisisdone,andtheexperimentverifiesthattheproposedalgorithmisefficientandfeasible.Keywords:pathplanning;roadnetwork;pathssearched;searchingspace续化处理,形成新的道路网,即如何组织道路网中的0引言点序列问题。针对以上两个问题,本文结合道路网的拓扑关系模型,提出了一种以道路结点为对象的在基于道路网运动实体的路径规划
5、中,核心问题不规则格网栅格化处理方法。就是最短路径搜索问题。Dijkstra算法是典型的最短路径搜索算法,依据此算法可得出最短路径的最优1路网拓扑关系模型[1]解,但由于它遍历计算的结点很多,所以效率较低。*1.1定义描述A算法是人工智能中一种典型的启发式搜索算法,它通过选择合适的估计函数,来约束搜索的过程,可以在基于地面道路网的路径规划中,主要考虑的克服Dijkstra算法的缺陷,达到提高搜索效率的目的。是点(或称结点)、线(或称弧段)之间的关联关*[2]运用A算法进行路径搜索时需将搜索区域进系。为了便于表述,作如下定义。行栅
6、格化分区以构建搜索空间,对于沿道路网运动(1)结点:在道路网中,每一条弧段的两个端点称*的实体,要使用A算法进行路径规划,需解决以下为结点,例如弧段AB中,A称为首结点,B称为尾结点;两个问题:一是如何将道路网进行栅格化分区以构(2)弧段:组成道路网的基本元素,由一些点序建搜索空间;二是如何对离散化的搜索结果进行连列组成,其中相邻两点连线近似为直线。各弧段中收稿日期:20091207修订日期:201006174202010年第4期的0~5数字表示构成该弧段的点序列的排列顺序,2.1构建搜索空间决定了弧段的方向性,可以用
7、向量的方式来表示,即弧段AB,弧段CB和弧段CD;如果按照传统的栅格化处理方法,则需要将跨(3)路径:若干条弧段首尾结点分别相连接构格网的道路进行打断。在一些道路网交错的地方对成一条路径,路径中各弧段的点序列的顺序要保持道路进行打断是一种非常复杂的操作,需要维护被一致,一条弧段的尾结点是下一条弧段的首结点。打断道路的ID及其交叉结点等之间的一系列复杂道路元素示意图,如图1所示。图1中,改变弧段关系,也可能会造成大量的结点数据增加,使搜索空CB的点序,变为弧段BC,即CB=BC,就构成了一条间变的十分繁琐,从而对路径规划的计算带来负面[4
8、]路径AD,路径也是有方向的,可表示为路径AD=影响。本文以道路网结点为对象进行不规则格{A,B,C,D}或AD=AB+BC+CD。网的栅格化处理。(1)将道路结点看作是一个栅格,通过一条弧段连通的两个结点
