基于D*Lite 算法的逃生最佳路径规划设计

张 俊 陈伟利

（吉林建筑大学电气与计算机学院，吉林 长春 130000）

火灾是现如今最常威胁国家公共安全和社会稳定的重大灾害之一，据统计近几年来，我国每年发生火灾就有十多万起，死亡2000 多人，伤3000 到4000 人，造成直接损失高达10 亿多元人民币，严重威胁人民群众生命财产安全。随着高层建筑的日益增多，建筑群日益密集，这样的环境复杂人员流量多，当发生火灾时，人员往往都是随波逐流，更容易发生意外，而且建筑物本身结构和材料具有复杂性，建筑内部装饰大多易燃，导致烟雾扩散快、火势大、火灾扑救困难等特点，如何实现安全、快速、高效的进行逃生，以及救援人员如何快速明确的救援被困人员，这是对于公共安全的一个重大挑战。

生成路径的算法有很多种，比如Dijkstra 算法、A*算法、D*算法、LDP*算法等，其中Dijkstra 算法是其中的经典算法之一，许多算法都是由此算法演变，A* 算法[1]正是如此，改善了Dijkstra 算法的盲目式搜索，运用启发式搜索，使得搜索范围缩小，提高了效率。而当环境信息时刻变化时（例如火灾现场），重复调用静态环境路径规划算法已经不太适用，在1994 年Anthony Stentz 提出动态的A*算法，即D*算法，拟解决在未知环境下的寻路问题。后在2004 年Koenig 和Likhachev 受到“增量式”搜索的启示，提出了LDP*算法，它通过收集之前寻路产生的信息，从而在重新规划路径时节省时间。后他们俩又在LDP*的基础上提出D*lite 算法，解决起点实时变化、终点固定的寻路问题。

D*lite 算法是先在最初的环境地图集中反向搜索并规划一条最佳路径。在其接近目标点的过程中，通过在局部范围的搜索去应对动态障碍点的出现。通过增量搜索的数据再利用直接在受阻碍的当前位置重新规划出一条最优路径，然后继续前进。增量式(启发式)搜索算法利用以往问题的经验加快对当前问题的搜索，从而加快对相似搜索问题序列的搜索。本文就结合建筑里固定传感器反馈的信息，形成一个细粒度的栅格化的“路径场”，再通过D*lite 算法，做出最优的路径规划。

1 D*Lite 路径规划算法

D*Lite 算法是由Sven Koenig 和Maxim Likhachev 基于LDP*(Lifelong Planning A*)算法并且结合A*算法的思想和动态SWSF-FP 的增量启发式搜索算法，适合面对周围环境未知或者周围环境存在动态变化的场景。

算法初始化把所处环境分为一个个合适的小栅格。算法利用启发函数计算平面上栅格的代价估计值，每个小栅格都可作为一个小节点，每次都选择代价估计值最小的节点作为拓展的最佳节点，并搜索计算其最近相邻的8 个栅格的代价估计值，以此类推，直到找到目标位置。当中途遇到障碍物，进行二次规划时，D*Lite 算法从目标节点展开搜索计算周围节点，可以利用前一次路径规划所计算出的节点信息，以此减少重复计算次数，提高二次规划效率。

在首次规划路径时，用g（s）表示从当前节点到终点位置的实际代价值，用启发函数h（s）表示从当前节点到起点位置的估计值。当在对当前节点相邻8 个栅格做拓展时，g（s）的值会被重新考量，这样可以保证其为最小代价值。一个点的rhs 值是它的父代节点中g 值加上这两点之间的代价中的最小值，相当于一个点从父代节点到达这个点的最小代价。其实在算法的大部分过程中，g 值和rhs 值是相等的。当计算出一个格子的rhs（s），把rhs（s）值赋给g（s），方程如下[2]：

D* Lite 中引入的rhs(right-hand side)，表示相对目标点的估计值，当一个点的g=rhs 值时称这个点为局部一致的点，否则称这个点为局部不一致。其中局部不一致的情况还可细分成为局部过一致和局部欠一致：当一个点的g＞rhs 值时，这个点为局部过一致，通常是有障碍物删除；当一个点的g＜rhs 值时，这个点为局部欠一致，通常是检测到了新增的障碍物。通过一个点的局部一致性来判断当前点是否需要计算。它的定义公式如下：

D*Lite 中，需要通过两个k 值来判断一个点的优先级，k 值越小优先级越高，先判断第一个k1 值，如果第一个k1 值相等再判断第二个k2 值，算法会优先选择距离终点近的点。它们的公式如下：

km表示人移动距离的叠加，初始化时km设置为0，如果不引入这个参数的话，当检测障碍物时就需要把优先队列中的全部节点都重新计算一遍k 值，增加了计算量。引入之后就可以一定程度上保证k 值的一致性，减少计算量。当k1=k2时，路径规划完成，算法规划流程如图1 如所示。

图1 D*lite 算法流程图

2 建立栅格及实验

面对环境信息，采用栅格法建模将受困人员所处环境分解成一个个固定大小的栅格，栅格的密度影响了路径规划的精度，但精度过高会导致计算量大幅增加，影响规划效率，精度过低容易导致规划出来的路径粗糙，也容易造成穿墙的情况。本文建立了一个20×20 的栅格模型为例，模拟火灾场景如图2 所示。若某一栅格内不存在障碍物称为自由栅格，反之称为障碍栅格(用黑色格子表示)。栅格法将受困人员抽象为位于栅格中心的一点，将障碍物扩展得到障碍边界栅格[3]。红色表示目标点，黄色表示起始点，绿色表示规划的路径，紫色表示地图上突然出现的障碍物（突发的火情点，人员通过危险系数大）。

图2 初始地图栅格场景

图3 是D*lite 初始状态下的路径规划，当受困人员在前进过程中，不断检查该路径上的栅格是否发生变化，当火情发生变化，且蔓延到该路径上时，D*lite 将第一次重新规划路径，绕过火情严重点如图4 所示，而当火情再次蔓延，封住之前规划路径的前进通道时，D*lite 将第二次规划，选择另一方向前进抵达目标结点如图5 所示。

图3 初始路径规划

图4 第一次重规划

图5 第二次重规划

3 仿真测试

本文将学校公共教学馆为模拟环境，利用Unity3D 游戏引擎与BIM构建视景仿真系统[4]实现对受困人员逃生规划路径的模拟测试如图6 所示。设置了2 个受困人员为模型，右侧深色部分表示火情严重区，实验使用D*lite 算法自动寻路，结果分别为两位受困人员成功规划了最短逃生路径。

图6 公共教学馆仿真测试

4 结论

通过对比常用路径规划算法，D*Lite 算法能很好地适用于起点时刻变化，终点不变的未知环境的路径规划。得力于它的增量启发式搜索，使它能在环境变化时减少重规划次数以及较小的重规划影响节点数。当发生火灾时它能以较短的时间高效的规划逃生及救援路径，一定程度上大幅度减少人员伤亡。也能将受困人员换成救援人员，目标位置为无法正常移动的受困人员，使在救援时救援人员准确判断浓烟滚滚的高层建筑的复杂环境，避免黑箱式救援而误入“死路”，在降低救援人员的伤亡概率的同时，提高救援效率。