路径规划范文第1篇

关键词：智能交通 A*算法 静态路径规划

中图分类号：P285 文献标识码：A 文章编号：1007-9416（2013）09-0117-02

1 引言

城市交通道路的复杂性，固定意识的出行路径引发的严重交通堵塞，使出行者迫切需要获得正确的出行路径；出行过程中，对不熟知地理环境和周围交通状况的把握和了解；车辆及出行者对社会服务的急迫需要；荒野作业过程中的道路迷失。我们可以得出一个重要的结论，就是随着出行者活动范围的不断扩大，人们迫切需要对车辆自身所处的位置及周围环境有更有效的认识，并作出理性的判定[1]。有效调高出行车辆行驶过程中的路径规划效果是解决城市交通堵塞的重要方法。

2 建立静态路径规划数学模型

对于最优道路路径规划策略的研究上来说，道路口节点和路径就可以对智能交通网进行数学逻辑上的描述，这一个基本的数字路网模型图可以表示为：

（2.1）

式中：G为智能交通道路的基本电子路网模型；N为道路网络路口节点的集合，ni为表示道路路网的任意一个节点，xi， yi为该任意节点的横和纵坐标；R为道路路网层路径的ri集合，为道路路网任意一段路径，为两个道路口节点之间或任意一条道路径的权重值。

依据智能交通原始电子地图，创建交通路网的空间拓扑结构相图G，以此为基础建立静态路径规划数学模型，模型具体描述如下：

2.1 定义智能交通路网的权值变量

实际智能交通中的两道路口节点，相关的任意道路径都含有一个权值，依据电路的常用定义规则，称为道路阻抗，描述了车辆行驶过程中通过该道路路径所要消耗的能量变量值，该值可以定义：道路路径的空间距离、通过该道路路径所需时间、车辆行驶路程缴费，依据用户所关心的目标函数可以采用不同的权值测量方法。

最优路径规划的目标函数为：车辆行驶过程中的始末道路最短路径DistanceMin。设，式中为车辆行驶过程中的路径值，。

最优路径规划的目标函数为：车辆行驶过程中的始末道路最短时间DistanceMin。设，式中为道路路径的宽度和等级，，为系数。假设车辆的平均速度与道路路径的宽度和等级成正比。

此外，据用户所关心的目标函数可以采用不同的权值测量方法，最优路径规划的目标函数为车辆行驶路程缴费最小的情况时，需要考虑车辆行驶过程中的道路的收费和油耗，并忽略车辆其他损耗。

2.2 最优路径规划的目标函数T

依据用户所关心的目标函数T，可以采用不同的定义方法。通常在最优路径规划策略考虑，始末道路节点的路径最短、及车辆耗时最小等。

车辆在智能交通网络的行驶过程中，始末道路口节点之间的道路径，分为m条路径，车辆通过每条路径的时间为。最优路径规划的目标函数T定义为：

标函数T为最小路径：

； （2.2）

标函数T为最小路径：

， （2.3）

因为：

（2.4）

则：

（2.5）

3 A-star算法设计

A-star算法是一种路径规划过程中比较经典的预测方式的搜索算法。采用智能交通网的全局信息变量，通过选择合理的预测估计评价函数，预设置优先查询的到路径方向，以减少搜索的道路口节点及路径的路段个数，实现查询的最优效率。以道路口节点之间的欧式距离及道路等级为A-star算法预测启发式的评价指标，定义如下所示：

（3.1）

其中，是始点到当前节点之间实际所产生的通过道路路径的费用，即是始末两节点之间的，每段路径的道路等级乘以道路的路径长度相加的代数和，是当前节点到目的地节点的最小代价值，本文取当前节点到目的地节点的欧式距离，为表智能交通道路分类序号值，取值为0、1、2；选择道路等级作为算法价值的评价指标，主要是考虑智能交通网中的高等级路，道路的路况及安全系数较高，虽然不是车辆行驶过程中的最短路径，但是可以给行车者带来精神放松，提升交通安全指标。A-star算法主程序框图如图3.1所示。

4 实验研究

车辆的静态最优路径轨迹规划，以复杂情况较大的北京市东城区的三环和四环之间的道路网数据为路径规划源。东西距离10KM，南北距离4KM。技术平台支持：Inter Pentium 4 1.8GHz，512M内存，Microsoft Windows server 2003操作系统。采用道路网道路功能的两层分类：略图层和详图层，细线为略图层网络结构，粗线为详图层网络结构。交通网略图层包含道路的路径段178条，道路口节点数53个，交通管制的转向限制为8条；详图层包括道路路径段2031条，道路口节点1419个，交通管制的转向限制为2307条。在路径规划仿真平台中，任意选择车辆行驶路径的始末点，A*实验结果统计如表4.1所示。

5 结语

在智能交通网中的静态路径规划算法研究中，具有启发式的A*算法能够实现车辆的静态最优路径规划，最优路径规划策略能够直接有效的提高道路的使用效率。减少城市交通堵塞情况的产生，可以做到节能减排的效果，产生更多的经济和社会效益。

参考文献

[1]常青，杨东凯，寇艳红，张其善.车辆导航定位方法及应用[M].北京：机械工业出版社，2005.

[2]陆化普.智能交通运输系统.北京：人民交通出版社，2002.

[3]G.A.Giannopoulos The application of information and communication technologies in transport. European Journal of Operational Research 152（2010）：302-320.

路径规划范文第2篇

【关键词】智能机器人；路径规划；应用

路径规划在嵌入式智能机器人的研究过程中有重要的意义。随着我国科学技术的提高，机器人技术得到了广泛的发展和应用，我国智能机器人技术进步的最显著特征是嵌入式系统与机器人技术的结合，嵌入式系统具体集成度较高、功耗较低等方面的优势，不仅可以充分满足系统的实时性，在一定程度上还能够使控制软件的开发工作变得简化。

1嵌入式智能机器人路径技术的研究

智能机器人路径规划是指处于有障碍物的工作条件下，如何寻找一条适当的运动路径（从给定起点到终点），在运动过程中，使机器人能够安全的规避全部障碍物。

（1）嵌入式智能机器人路径规划的发展趋势

从近些年的研究成果来看，有以下趋势：第一，以功能或行为为基础的智能机器热的路径规划。以功能或行为为基础的机器人具有一种典型的慎思结构，又被称为基于功能的控制体系结构，其主要内容是基于模型自顶向下的感知、建模、规划和动作。智能机器人路径规划问题，建模时，能够设置成为有约束性的规划问题，确保机器人能够完成路径规划、路径规避和定位等方面的任务。由于不同的机器人掌握信息环境的程度存在差异，可将智能机器人的路径规划分为两种，其一是以传感器为基础的局部路径规划，具体是获知了作业环境中的所有信息，主要包括：自由空间法、构型空间法以及神经网络法等；其二是以模型为基础的全局路径规划，具体是指已经全部获知或部分获知作业环境中的信息，主要包括混合法、滚动窗口法、人工势场法等。第二，神经网络、模糊控制等一系列算法不断涌现并相互结合形成新的算法。第三，智能机器人的系统路径规划。智能机器人的工作环境逐渐复杂化，再加上工作任务的增加，单智能机器人无法负荷这样的工作要求。因此，将会出现单个智能机器人路径规划与多智能机器人的合作相结合的发展趋势。

（2）机器人智能规划中的特点

智能机器人路径规划中主要存在以下特点，①复杂性，是指环境复杂，机器人的路径规划复杂，且路径规划过程中需要很大的计算量支持。②随机性，是指工作环境的变化复杂，存在较多的不确定因素和随机性。③约束性，在机器人运动的过程中，其速度、形状等方面均存在约束。

2智能机器人路径规划的算法研究

（1）局部路径规划算法研究

1）模糊逻辑控制法

在环境模型不完善的情况下，可以使用模糊逻辑算法。这种算法的推理和计算简单，对传感器信息的要求较低，且对机器人的行为有较高的稳定性、一致性以及连续性，能够有效的解决在路径规划过程中遇到的一些问题。虽然这种算法能够圆满的解决未知环境下的规划问题，但仍存在灵活性较差、无法学习的不足之处。

2）遗传算法

遗传算法是解决最佳化的搜索方法，属于进化算法的一种。这种算法最初借鉴了进化生物学中突变、自然选择、交叉和变异等现象而发展起来的，它采用群体搜索技术，实施选择、交叉、变异等一系列遗传操作后，使种群在迭代中不断进化。这种算法的理论推导简单，问题的最优解能够直接得出。遗传算法的基本思想是路径转换为二进制串，首先将路径群体实施初始化操作，然后对路径群体实施选择、复制等一系列遗传操作。通过多次进化后，达到最佳的进化状态，停止进化并将当前存在的最优个体输出。虽然遗传算法得推导理论简单，但路径规划过程中仍存在效率低、个体编码不合理等问题。

（2）全局路径规划算法研究

1）构型空间法

构型空间法主要包括优化算法和可视图法。第一，优化算法。第二，可视图算法。路径图主要由机器人中的一维网络曲线自由空间中的节点构成。因此，在同路径图中，路径初始状态的点一一与目标状态的点相对应，从而促使点间搜索路径问题替代了路径规划问题。这就要求点与点之间的连线是无法穿越障碍物，即机器人与障碍物点、目标点与障碍物点、以及顶点与障碍物顶点之间的连线是可视的，然后，采取有效的搜索方法，搜索最优路径（起始点到目标点），从而使搜索最优路径问题演变为可视直线最短距离的问题。可视图法虽然能够得到最短路径。第二，优化算法。采用优化算法時，为了简化可视图和减少路径搜索时间，有部分可有可无的连线可以删除，最终实现求得最短路径的目的。

2）神经网络法

人工神经网络一种自适应非线性动态系统，主要是由大量神经元组成。在工作环境广泛、精度要求高的条件下，采用神经网络法表示环境，将会取得显著效果。在全局路径规划中应用神经网络法，能够将障碍约束变成惩罚函数，并用神经网络来描述碰撞惩罚函数进而将约束优化问题转变为无约束最优问题，实现全局路径规划。神经网络法具有较强的学习能力，但整体应用于路径规划中的效果不明显，这是因为智能机器人的工作环境复杂，并伴有一定的随机性，数学公式无法进行准确的描述。

3嵌入式智能机器人路径规划算法的应用与实现

嵌入式智能机器人的组成部分主要有驱动控制器和嵌入式微处理器。嵌入式智能机器人的硬件结构有较高的可扩展性、良好的独立性以及较小的功耗等特征，且能够得到嵌入式系统的充分支持。嵌入式智能机器人的主板是机器人的大脑，主要担任机器人运动过程中的实时计算工作。随着嵌入式技术的不断发展，为智能机器人的路径规划算法的实现和运用提供了无限的可能性，再加上以SOC技术为基础的高性能32位嵌入式微处理器的广泛应用，为智能机器人研究领域中，引入实时操作系统提供了强有力的物质基础，同时这将是机电控制系统的未来发展趋势。嵌入式智能机器人路径算法的主要从获取和决策两方面实现，获取是指通过感知系统获取所需要的环境信息，决策是指通过决策运算后，得出的控制数据由伺服控制系统接收，同还能够实现与其他机器人的通讯和人机交互。嵌入式智能机器人路径规划的运用，需要嵌入式操作系统有较好的实时性、可靠性，并对系统成本提出了更高的要求，此外，根据系统拥有的定制和裁减的特点，在开展多任务管理的同时也能够保证工作的实时性能。嵌入式智能机器人路径算法，不需要使用复杂的系统即功能，如文件系统等。嵌入式智能机器人路径技术的研究重点主要在仿人智能和仿生智能两方面，随着我国科学技术的发展，嵌入式智能机器人与多种学科交叉和结合，比如，人工智能、认知科学等，使其智能化的行为程度不断的提升。此外，嵌入式系统还适用于在功能、体积等方面有严格规定的专业计算机系统，使计算机系统具体专用性强、实时性好、微内核精简等优势，由此可见将嵌入式智能机器人路径规划算法与嵌入式技术相结合是未来智能化机器人的重要发展方向。

4总结

随着我国科技水平的不断提高，遥感技术、控制技术等诸多技术的进一步发展，在智能机器人研究领域，嵌入式智能机器人路径技术也已经取得了显著的成就。在未来的机器人系统中，遗传算法、神经网络法、模糊逻辑控制法等将会进一步应用于嵌入式智能机器人的研究中，使机器人的各方面性能得到显著提升。

【参考文献】 

[1]王思德.基于Cortex A9平台的双目立体视觉机器人路径规划研究[D].山东大学，2016. 

路径规划范文第3篇

关键词：限制搜索区域；多比例尺；最优路径规划算法；Dijkstra算法

为了提高大区域路网路径规划的效率,国内外很多专家学者做了大量的研究工作，提出了一些新的算法。这些算法大多数采用路网分级技术或分解技术来减少大规模路网的存储需求和计算的开销，如文献[1~3]中提出的算法。然而现有的路网分级分解技术存在着一些问题,主要表现在[4]:路网分解没有统一的标准；路网分级处理时,大多按照道路的属性,如主干道、次干道等,对路网进行分级,要求属性信息非常完整,否则无法分级；若提取出的每一级路网不连通时将无法处理；在涉及到几百甚至几千幅地图时,从每幅地图中提取主干道、次干道路网再拼接成多级路网,其工作量巨大,可行性不强；等等。针对以上问题，本文提出一种限制搜索区域的多比例尺最优路径规划算法（multiscaleoptimalrouteplanningalgorithmwithinrestrictedsearchingarea，MORPARSA）。

1MORPARSA

1．1路网的空间分布特性

与普通的平面网络图相比,描述实际城市路网的拓扑图通常具有以下特点[5,6]：每个节点相连的路段数一般不超过5，多为2、3或4；网络结构相对比较规则(特别是经过规划的现代化都市)；网络中有表示供车辆调头的专门换向节点,而且一般距当前路口500m左右。

1．2区域限制的思想

Dijkstra算法求解的是某个源点到其余各节点的最短路径，它按节点距起始点距离递增的顺序产生最短路径，因此该算法在最短路径的搜索过程中具有很大的盲目性，随时都准备向四面八方展开[5]。该算法搜索的区域是整个路网平面，时间复杂度为O(n2)。其中n为路网中的节点数。

由于实际城市路网结构相对比较规则(特别是经过规划的现代化都市，如西安市)[5~7]中，最短路径一般都会落入以起始点S和目标点D的连线为对角线的矩形区域中，如图1中的小矩形。应该说明的是，在靠近两节点的附近，有时可能会出现短距离的反向路径(指在线段SD的两端点外，沿SD或DS延长线方向的路径，反映在实际系统中，通常代表车辆为转入合适车道行驶所走过的路径)[5]，此时最短路径显然不会落在以S和D的连线为对角线的矩形区域中，因此将以S和D的连线为对角线的矩形四边向外各扩展500m，形成一个更大的矩形作为限制区域，如图1所示。

如果路网中的节点在整个路网平面内均匀分布(即节点数与其所占区域的面积成正比，即使局部节点的分布不均匀)，那么搜索过程中实际所需访问的节点数就可用搜索扫过区域的面积C表示，进而搜索的时间复杂度可表示为O(C2)[5]。假设图1中整个路网平面的面积为C1，大矩形的面积为C2。由于C2＜＜C1,合理限制搜索区域理论上可以提高路径规划的效率。

1．3多比例尺路网数据模型

人们习惯于用比例尺的概念来描述地图对现实世界不同详尽程度的表达，比例尺越大，对现实世界的描述就越详细，对空间对象几何形的描述也越详细。可以用比例尺来描述不同重要程度的道路，如图2所示。

我国基础地理信息的比例尺系列包括1∶100万、1∶50万、1∶25万、1∶10万、1∶5万、1∶1万等，多比例尺自然就起到了分级的作用。

多比例尺信息的这种分级特性与道路的属性信息相关，主要道路存在于小比例尺地图中，次要道路存在于大比例尺地图中，而且大比例尺地图中包含了小比例尺地图中的道路，显示了更为详细的道路信息。因此，可以采用多比例尺数据构建多级路网结构处理大区域的路径搜索问题[4,8],如图3所示。

基于多比例尺数据构建的多级路网模型解决了原有的分级分解算法中存在的一些问题,主要改进的问题如下[4,8]:根据道路属性对道路进行分级时，需要作一些处理,很难保证提取的同一级路网是连通的，采用多比例尺数据构建的多级路网,多比例尺本身起到了分级的作用，在每一比例尺下,路网数据具有连通性。现有的分级分解算法一般按照道路的属性对路网进行分级,因而在道路属性信息不完整的情况下无法处理；在大区域范围内,即使属性信息齐全,提取构建多级路网工作量繁重、不易实施。在全国基本比例尺地形图库已经建立的情况下,采用多比例尺数据构建多级路网显然是可行的。

1．4算法描述

设多级路网一共有W级(W≥1)。

输入：多比例尺路网数据，起始点S、目标点D为路网中任意指定的两个节点。

输出：S和D之间的一条最优路径。

3结束语

本文提出的MORPARSA可以提高路径规划的效率。多级路网中,低级网络一般为主要干道,符合驾驶者首先选择行驶在主干道的愿望,避开了交通不方便的次要道路,合理性较高。

参考文献：

[1]彭飞,柳重堪,张其善.车辆定位与导航系统中的快速路径规划算法[J].北京航空航天大学学报,2002,28(1):70-73.

[2]陈则王,袁信.基于分层分解的一种实时车辆路径规划算法[J].南京航空航天大学学报,2003,35(2):193197.

[3]JAGADEESHGR,SRIKANTHANT.Heuristictechniquesforacceleratinghierarchicalroutingonroadnetworks[J].IEEETransonIntelligentTransportationSystems,2002,3(4):301-309.

[4]陈玉敏,龚健雅,史文中.多级道路网的最优路径算法研究[J].武汉大学学报,2006,31(1):70-73.

[5]付梦印,李杰,邓志红.限制搜索区域的距离最短路径规划算法[J].北京理工大学学报,2004,24(10):881-884.

[6]严寒冰,刘迎春.基于GIS的城市道路网最短路径算法探讨[J].计算机学报,2000,23(2):210-215.

[7]王晓丽,杨兆升,吕旭涛，等.平行四边形限制最短路径算法及其在道路网络中的应用[J].吉林大学学报,2006,36(1):123127.

路径规划范文第4篇

关键词：动态规范 路径图 多阶段决策

一、动态规划简介

动态规划是运筹学的一个分支，它是解决多阶段决策过程的最优化的一种数学方法。美国数学家贝尔曼（R.Bellman）等人在1951年根据一类多阶段决策问题的特点，把多阶段决策问题变换为一系列互相关联的单阶段问题，然后逐个加以解决，从而创建了解决最优化问题的一种新的方法。动态规划的方法在工程技术、企业管理、工农业生产及军事部门中都有广泛的应用，并且获得了显著的效果。可以用来解决最优路径问题、资源分配问题、设备更新问题、生产调度问题、库存问题、装载问题、排序问题、货郎担问题、采购与销售问题、限期采购问题、生产过程最优控制问题等。

二、建立动态规划模型的步骤

动态规范模型在日常生产、生活中应用广泛，建立动态规范模型一般遵循以下步骤：

（1）将问题的过程划分成恰当的阶段（一般按时间或空间的先后顺序）；

（2）正确选择状态变量SK ，使它既能描述过程的演变，又要满足无后效性；

（3）正确设立决策变量uk ，明确每阶段的允许决策集合Dk（Sk ）；（通常选择所求解问题的关键变量作为决策变量）

（4）根据第K阶段的状态变量和决策变量正确写出状态转移方程

（5）正确写出指标函数

指数函数应满足下面三个性质：①是定义在全过程和所以子过程上的数量函数； ② 要具有可分离性，并满足递推关系。③函数对变量 Vk+1，n要严格单调。

（6）写出动态规划的基本方程包括边界条件。

（7）求解模型。

三、用路径图求解动态规划问题应用举例

用动态规划的方法求解实际问题通常可以按上面的步骤来建立模型，有部分问题可以化为（最短）路径问题，用路径图能直观的理解上面的算法。

如某建筑公司新购置了四台挖掘机，准备分给甲、乙、丙三个公司，事先请专家调查了各分公司的经营情况，并对各种分配方案进行了经济效益的估计，见下表，其中机器数为0时的收益，是指已有的经营收益，问应如何分配这四台机器，使总的收益为最多？

本题用动态规划的常规方法建模求解可参看[1]，下面采用本文要讲的路径图的方法来求解，更直观易懂。

具体解答过程如下：

解：由于有三个公司，所以划分为三个阶段，状态变量 表示第k阶段初分配者手中拥有的机器总数，决策变量 表示第k阶段分配给第k个用户的机器数，状态转移方程为： Sk+1=sk-uk

阶段指标函数： vk（sk，uk）=gk（uk）表示k阶段公司k利用所分到的资源（机器）产生的收益；最优值函数fk（sk） 表示将机器数sk 分配给公司k到公司丙所获得的最大收益：

表示状态变量所取的值，状态连线上小于5的数字表示决策变量所取的值，[数字]表示该阶段的指标值（收益）， 表示该状态到最后一个公司的最大收益，粗线条表示最优策略路径，从上图很容易看出最大收益为164万元，最优策略是：u1=3，u2=0，u3=1 ，即分给甲3台，乙不分，丙1台时，总收益164万元最大。

结束语：

对于最段路径问题、资源分配问题、生产与存储计划问题，只要阶段不是太多，状态变量的取值不超过6个，一般可以采用路径图直观的求解出模型的解。

参考文献：

[1]岳宏志，蔺小林，运筹学[M]，东北财经大学出版社，2012.8.

路径规划范文第5篇

【关键词】虚拟场景；路经规划；八叉树；A*算法

中图分类号：TP39文献标识码A文章编号1006-0278（2013）06-172-01

一、引言

随着虚拟现实技术的日益成熟，只有景色、建筑物等一般视景信息的虚拟场景已不能满足人们的视觉需求，迫切需求一个有生命的对象引入到虚拟场景中，增加浏览者的沉浸感。虚拟场景中虚拟人的路径规划是虚拟现实研究中的一项关键技术。目前，研究者们已经把研究的重心放在如何为虚拟人规划出一条行走的最优路径，使虚拟人的路径导航更具有真实感和可信度。

由于虚拟环境中的模型多由三角面网格组成，通过使用基于空间多层次划分的八叉树方法，充分发挥了其空间划分的优势，加快了场景的渲染速度，减少了确定对象的处理时间以及存储空间①。

文章采用八叉树和A*算法相结合的方法，对路径进行规划，并对A*算法做了改进，以适应八叉树的存储结构。

二、密集型区域八叉树划分算法

八叉树是由四叉树推广到三维空间而形成的一种三维栅格数据结构，它作为一种场景组织方法，广泛应用于虚拟现实系统，可显著减少对场景中多边形进行排序的时间。

由于传统八叉树对空间的划分是均匀的，导致了最终生成一个结构不平衡的八叉树，从而增加整个八叉树的存储空间以及各结点的遍历时间。文章采用了对传统八叉树算法进行改进，采用基于密集型区域八叉树划分方法。密集型区域八叉树的网格划分算法是对每一子空间重新建立最小包围盒，这样避免了在建立顶点树时，由于该部分顶点在空间上分布不均匀而导致树的深度的增加，进而减少了存储空间，加快了网格模型数据的读取速度。另外，由于建立了顶点的最小包围盒，在误差较小时，只有空间距离比较近的顶点才会聚合在一起；而相距较远的顶点只有在深层次简化时才会聚合，这些特点在一定程度上保证了简化时网格模型的逼真度。

密集型区域八叉树划分方法的算法描述如下：

步骤1使用OBB包围盒方法建立模型的最小包围盒。

步骤2以包围盒的X轴、Y轴、Z轴方向的中分面作为分割基准，将包围盒平均划分为八个子包围盒。

步骤3如果每个子空间内存在物体的属性不相同或未达到规定的限差，则重新从步骤1开始进行划分。否则，划分结束，并对划分后的每一个结点记录下结点编号、划分标志、结点在顶点树中的深度以及它所含的景物面片表的入口指针。

三、A*算法

A*算法是建立在典型的Dijkstra算法上的，是由Hart，Nilsson，Raphael等人首先提出的。该算法的创新之处在于选择下一个被检查的节点时引入了已知的全局信息，对当前节点距终点的距离做出估计，作为评价该节点处于最优路线上的可能性的量度，这样就可以首先搜索可能性较大的节点，从而提高了搜索过程的效率。

下面是对A*算法的介绍，我们首先来介绍一下启发式搜索中的估计函数。因为在启发式搜索中，对位置的估价是十分重要的。估价函数的表示如下：

其中是节点的估价函数，是已知的，指在状态空间中从初始节点到节点的实际代价；是从结点到目标节点最佳路径的估计代价，它体现了搜索的启发信息，启发信息决定着算法的启发能力。启发信息越多，估价函数就越好，即约束条件越多，则排除的节点就越多，说明这个算法越好。这种做法存在一个平衡的问题，也会使算法的准确性下降。具体的说，代表了搜索的广度优先趋势，当时，可以省略，这样就提高了搜索效率。

A*算法是一个可采纳的最好优先算法。A*算法的估价函数可表示为：

这里，是估价函数，是起点到终点的最短路径值，是到目标的最短路经启发值。由于这个其实是无法预先知道的，所以我们用前面的估价函数做近似。代替，但需要满足（在大多数情况下都满足时，可以不用考虑）。代替，并满足。可以证明应用这样的估价函数是可以找到最短路径的。

四、基于密集型区域八叉树的A*算法改进

由于使用八叉树存储结构存储的环境地图扩展步长不一致，采用传统的A*算法效率较低，因此对A*算法做了改进，以适应八叉树结构的搜索。改进的办法是从叶节点开始搜索并为Open表设置两个优先队列，命名为队列1和队列2（队列1中存放的节点总是高于队列2），在两个队列中分别存放相邻层次的全部节点，层次越高的优先级越高。通过这种分层次的搜索，也大大缩小了搜索的空间并缩短了搜索时间，这样一来大大提高了搜索效率。

五、结束语

针对于复杂的3D环境，文章根据八叉树适合虚拟场景划分的特点，采用了一种适合密集型区域的八叉树划分方法，进行场景划分。为适合八叉树的存储结构，对A*算法做了改进，引入优先级队列并采用了分层结构，采用了从叶节点到根节点的搜索方法，规划出了虚拟人行走的最优路径。