张 俊 陈伟利

（吉林建筑大学电气与计算机学院，吉林 长春 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 算法是先在最初的环境地图集中反向搜索并规划一条最佳路径。……