企业官网建设流程全解析

自学建立网站,ui高级培训机构,php网站开发框架有哪些,wordpress 访问者在自动驾驶领域#xff0c;车辆不仅要应对复杂的静态交通环境#xff0c;还要实时处理动态变化的路况#xff0c;如突然出现的障碍物、交通信号变化等。因此#xff0c;动态环境下的路径重规划能力至关重要。本章将深入探讨动态路径规划算法#xff0c;特别是 D* 算法车辆不仅要应对复杂的静态交通环境还要实时处理动态变化的路况如突然出现的障碍物、交通信号变化等。因此动态环境下的路径重规划能力至关重要。本章将深入探讨动态路径规划算法特别是 D* 算法介绍其背景、原理、实现步骤以及与传统 A* 算法的对比。通过多个实战案例如迷宫中的路径探索、机器人的新家探索以及探险家的行进路线等我们将展示 D* 算法在动态环境中的强大适应性和高效性。本章旨在帮助读者全面理解动态路径规划算法的核心思想及其在实际应用中的实现方法为自动驾驶中的实时路径调整提供理论和实践指导。7.2 D*算法介绍D*算法D-star algorithm是一种路径规划算法用于在有向图中寻找从起点到目标点的最短路径。D*是基于A*算法的改进适用于动态环境下的路径规划问题其中环境可能会随时间变化而改变。D*算法最初由Anthony Stentz于1994年提出用于机器人路径规划。7.2.1 D*算法的背景和发展历程D*算法的背景和发展历程可以追溯到路径规划领域的早期研究和算法发展以下是对D*算法的主要背景和发展历程的具体说明。路径规划领域的早期研究路径规划是人工智能和机器人领域的重要问题之一早期研究主要集中在静态环境下的路径规划。一些经典算法如 Dijkstra 算法被提出来解决这一问题。A*算法的提出A*算法是一种启发式搜索算法由Peter Hart、Nils Nilsson 和Bertram Raphael于1968年提出。它通过估计每个节点到目标节点的代价来导航搜索以在有向图中找到最短路径。D*算法的诞生D*算法是在A*算法的基础上发展而来的旨在解决动态环境下的路径规划问题。Anthony Stentz 在1994年提出了D*算法作为机器人路径规划的一种新方法。D*算法的主要目标是适应环境的动态变化能够在环境变化时快速更新路径。实际应用和改进D*算法的提出引发了许多实际应用和改进研究。人们开始将D*算法应用于机器人导航、自动驾驶、无人机路径规划等领域。此外还出现了许多改进版本和变体如 D* Lite 算法等以进一步提高算法的效率和性能。应用领域的拓展随着技术的进步和对路径规划需求的不断增加D*算法开始在更多领域得到应用如游戏开发、智能交通系统、网络路由优化等。总的来说D*算法作为一种适应动态环境的路径规划算法经过多年的发展和实践应用在人工智能、机器人技术等领域发挥着重要作用并不断得到改进和拓展。7.2.2 D*算法的原理和实现步骤D*算法是一种用于动态环境下路径规划的算法它可以在环境变化时快速更新路径。1. D*算法的原理局部搜索D*算法从目标节点开始向起始节点进行局部搜索以找到当前最优路径。路径更新算法通过将节点的代价向起始节点进行传播逐步更新路径的代价。环境变化处理如果环境发生变化如障碍物移动或代价改变D*算法能够快速根据变化重新规划路径。2. D*算法的实现步骤1初始化设定起点和终点并将终点的代价设为0其他节点的代价设为无穷大。同时将所有节点标记为未访问状态。2更新代价从终点开始按照一定的启发式规则如欧几里得距离向起点搜索路径并根据当前节点邻居节点的代价更新路径代价。具体来说算法会更新节点的 $g$ 值表示从起点到当前节点的实际代价。3路径追溯沿着更新后的路径从终点向起点追溯更新路径上每个节点的邻居节点的代价。这一步骤保证了路径的连续性。4环境变化检测在每次迭代中算法会检测环境是否发生变化如节点代价的改变或者障碍物的移动。5处理环境变化如果环境发生变化算法将重新计算受影响的节点的代价并更新路径。6重复迭代重复前面的步骤2至步骤5直到找到从起点到终点的最短路径或者达到预设的迭代次数。7路径提取最终根据更新后的路径信息提取出从起点到终点的最短路径。需要注意的是D*算法是一种增量式的算法它允许在动态环境中实时更新路径而无需重新计算整个路径。这使得D算法在实际应用中具有很高的效率和实用性。7.2.3 D *算法总体流程及与A*算法的对比同A*算法类似D*算法通过维护一个优先队列OpenList来对场景中的路径节点进行搜索所不同的是D*不是由起始点开始搜索而是以目标点为起始通过将目标点置于Openlist中来开始搜索直到机器人当前位置节点由队列中出队为止当然如果中间某节点状态有动态改变需要重新寻路所以才是一个动态寻路算法。启发式搜索是利用启发函数来对搜索进行指导从而实现高效的搜索。增量搜索是对以前的搜索结果信息进行再利用来实现高效搜索大大减少搜索范围和时间。D*算法采用反向搜索的目的在于后期需要重新规划路径的时候能够用到先前搜索到的最短路径信息减少搜索量。因为以目标向起始点进行搜索得到的最短路径图是以目标点为中心辐射出的最短路径图图上目标点到各点之间都是最短路径为此其在既定路径上遇到问题需要重新路径规划的时候可以很好的利用原先得到的信息。而以起始点向目标点搜索得到的最短路径图其是以起始点为中心辐射出的最短路径图当沿着既定路径前行遇到障碍物之后需要重新进行路径规划之时没有办法很好的利用原先搜索得到的信息。总的来说D * 算法分为两个阶段第一个阶段是使用Dijkstra算法或A *算法找到从目标点到起始点的静态可行路径然后开始从起点向目标点运动。第二个阶段是动态避障搜索阶段主要用于修正若干个受障碍物影响而导致代价值发生变化的那些节点信息。1初始化将目标点放入OpenList 中。这一过程与A * 的对比在A*算法初始化时将起始点放到OpenList 中。2从OpenList 中找到k值最小的节点并将该节点从OpenList 中移除并放到closedlist列表中。在这一过程与A * 的对比A*算法选择拓展点时是从OpenList 列表中选择f值最小的点拓展fgh而D * 算法是从OpenList 列表中选择k值最小的点拓展。在D * 算法中是从目标点向起始点进行搜索我们将从目标点到当前点的代价记为h 其实从原理上来看与这里的h与A * 中 的g更为相似都是从搜索开始的点到当前点累计的代价值在D * 中没有使用从当前点到起始点的估计值也就是没有使用启发信息从这一点上来看D * 与dijkstra算法更为相似。那么D *中的 k值是什么呢 D * 是针对动态环境设计的算法由于环境的改变某点处的h值可能发生改变而某点处的k值其实记录的就是该点的最小h值也就是说对于还未遍历到的点khinf;对于标识为open或closed的点kmin { k , h_new}。注意为什么不选用最小的h值节点来作为拓展点而是使用k值呢在动态环境下假如某个节点变成了障碍物此时其h值会被修改为inf我们需要将这种变化传递下去若采用h值作为选取标准该节点会被置于openList中的最后。也就是说此时路径规划会从openList中剩余的处于OPEN状态的节点开始一直扩张至全图都没有不可达节点之后才会访问该节点。这显然并不合理因为我们的目的就是要在节点状态动态变化的时候减少搜索的空间提高搜索效率。而用最小的h值也就是k值在openList中进行排序表示这里曾有一条捷径那么就会优先在这附近进行搜索。3判断当前拓展点的k值是否与该点的h值相同若kh说明该节点已经受到了动态障碍物的影响那么就遍历该节点的相邻节点看是否能够以某个相邻节点作为父节点来使该节点的h值减小。我们用x表示该节点用y表示其某个相邻节点即若hy k(x),且hx h(y) c(y ,x),则将当前点x的父节点改为y并将该点的h值更改为hx h(y) c(y ,x)其中c(y ,x)代表从y点到x点的代价值。我们试图用上面的操作来减少该点处的h值并期望使其回到Lower态。在这一过程与A * 的对比A * 算法中不考虑动态障碍物从而A*算法中并没有与该步骤对应的操作在D * 算法中每个节点还有Lower态和Raise态两种状态若hk记为Lower态若hk,记为Raise态当该节点处于Raise态时表明有更优的路径。4判断经过第3步的操作后该点的k值是否与h值相等即是否回到了Lower态若不等即k h则按照以下准则进行节点的拓展①该相邻节点从未被拓展过即该相邻节点还未进OpenList。②该相邻节点的父节点是当前点且hy≠ h x c (x,y), 若该相邻节点y是以上两种情况则将该相邻节点的父节点设为当前点并将该相邻节点的h值设为h x c (x,y)放到OpenList中。③若该相邻节点的父节点不是当前点且hy h x c (x,y),则将当前点x加入到OpenList这里为什么不将y的父节点设定为当前点x并对其hy进行更新呢往OpenList里面放到为什么不是y而是x呢我们可以这样理解此时的当前点x处于Raise态即当前x处的代价值不是最优的所以我们将x放到OpenList中等待下一次循环当前点的代价值变成最优的后再对该相邻节点进行处理以此来保证传递下去的代价值是最小的。④若该相邻节点的父节点不是当前点且hx h y c (x,y),且该相邻点y在closedlist中且hy k,则将y重新放到OpenList中怎么理解呢 我们每次从OpenList取点时取得是k最小的既然y已经在closedlist中说明y比当前点先拓展即ky k(x)而现在hy kx说明y受到了障碍物的影响使得hy变大了因此需要将y放到OpenList进行考察。5进行下一轮拓展依次循环往复拓展结束后通过路径回溯找到所需的路径。6动态阶段按照规划的路径进行移动的过程中若当前点为x且探测到要走的下一个节点y存在障碍或者节点y本来存在障碍物但是继续行进到x的时候障碍物被移除。这时就要调用modify_cost(x,y,val)函数将最新的cost(x,y)以及h(y)的值进行变更若此时x已经位于closedlist则需要将其重新放到openlist中并反复执行process_state ()函数以传播节点h值的变更信息并进行路径搜索工作直到process_state()函数返回的openList中所有节点的k值中的最小k值(k_{min}) h(x) 或者openList没有任何节点时表示重新路径规划完成或者无法找到别的路径从x点规划到目标点G。注意为何重新进行路径规划的时候当执行到(k_{min}) h(y)时停止这是因为process_state()函数的功能是用邻居节点来减低自身节点的h值的当所有处于OPEN状态的节点中的k值的最小值(k_{min})也要大于等于h(y)时表示不可能再通过process_state()函数的执行来降低h(y)值了那么自然就没有再搜索的必要且已经完成了路径的修正。相比A-star算法D-star的主要特点就是由目标位置开始向起始位置进行路径搜索当物体由起始位置向目标位置运行过程中发现路径中存在新的障碍时新的障碍不行影响目标位置到新障碍之间的范围内的路径节点新障碍只会影响智能体例如汽车所在位置当前位置到障碍之间范围的节点的路径。在这时通过将新的障碍周围的节点加入到Openlist中进行处理然后向物体所在位置进行传播能最大程度的减少计算开销。路径搜索的过程中跟Dijkstra算法比较像并没有体现A-star所具有的方向感在拓展时没有将当前拓展点与起始点之间的代价估计值作为选取拓展点的考量之一即缺乏类似 A* 算法中那种朝起点方向引导搜索的能力这种搜索更多的是一种由目标位置向四周发散搜索直到把起始位置纳入搜索范围为止。7.2.4 D*算法的常用概念及函数在下面 的内容中列出了D*算法的常用概念及函数的信息。G表示进行路径搜索的目标点。c(x,y)从节点x移动到节点y的代价。t(x)节点的状态。每个节点(作者论文中称为state)都有一个状态其中总共有三种可能NEW,OPEN,CLOSED。NEW表示从未加入到openList中的也就是从未被遍历查找过的。OPEN表示节点在被查找中节点在openList中。CLOSED表示从openList中被移出。OPEN和CLOSED状态会相互转化当节点从openList中移出的时候状态从OPEN变为CLOSED当节点再次加入openList进行 降低节点自身h值或者传播当前节点的h值变更信息给邻居节点让邻居节点进行h值修改变更 操作时状态从CLOSED变为OPEN。h(x)表示地图上的点x到达目标点G的代价。由于D*算法是从目标点开始进行路径规划的为此初始化的时候令h(G) 0。此后其代价的变动可能会在两个地方出现一个是路径搜索的过程中当节点x的邻居节点被执行搜索过程的时候如果其能够让h(x)的代价更小则更新h(x) h(y) cost(y,x)。一个是在路径搜索完成后执行路径搜索结果的过程中遇到障碍物之时通过insert(x,y,val)函数改变障碍物节点y的代价h(y)。k(x)节点最小的h(x)值。随着节点遍历和搜索过程的进行节点的h(x)值会不断的变动。b(x) y用于记录当前节点x的父节点这里b(x) y表示x节点的父节点为y节点。在搜索完成之后能够根据b(x)的值回溯追踪到目标节点。openList存放节点状态为OPEN的节点且其按照节点的k值从小到大进行排序。process_state()该函数用于降低openlist表中的某个节点x(state)的h(x)值或者传播节点x的h(x)值变更信息给邻居节点让邻居节点进行相应变更的同时进行路径搜索查找的。insert(x,val)该函数用于修改节点x的状态以及h(x)值和k(x)值的。modify_cost(x,y,val)该函数用于修改节点x和y之间的移动代价cost(x,y)而且根据节点y的状态t(y)的情况可能对节点y的h(y)值和状态t(y)进行修改。注意本节部分内容参考自https://blog.csdn.net/qq_44339029/article/details/127490956。