논문

Dynamic planning of crowd evacuation path for metro station based on Dynamic Avoid Smoke A-Star algorithm

정지홍 2026. 1. 12. 12:14

0.abstract

  • 지하철역에서 화재가 발생하면 큰 인명 피해가 쉽게 생길 수 있으므로, 군중이 신속하게 대피할 수 있도록 안전하고 효과적인 대피 경로를 제때 제공하는 것이 매우 중요하다.
  • 하지만 기존 연구들에서는 화재 환경을 충분히 고려하지 않거나, 연기·열·유독가스 같은 화재 생성물(fire products) 이 대피 경로에 미치는 실시간 영향을 반영하지 않은 채 대피 경로를 계획하는 경우가 많았다.
  • 그 결과, 실제 대피 상황에 잘 맞지 않는 경로가 산출될 수 있다.

  • 본 연구는 지하철역 화재 시나리오에서 대피 경로를 동적으로(실시간으로) 계획하기 위한 알고리즘을 제안한다.
  • 첫째, 주변 온도, 가시거리, CO(일산화탄소) 농도가 대피 속도에 미치는 영향을 고려해, 경로를 “실제 체감 거리”에 해당하는 등가 길이(equivalent length) 로 환산하고, 이를 바탕으로 화재 위험 모델을 구축한다.
  • 둘째, 이 화재 위험 모델을 A* 알고리즘에 통합하고 A*의 평가 함수(heuristic/evaluation function) 를 개선하여, 탐색된 경로가 화재 위험이 높은 구역을 회피할 수 있도록 한다.
  • 셋째, 시간 요인을 고려한 동적 업데이트 메커니즘을 도입해, 화재 환경이 시간에 따라 변하는 정보를 실시간으로 갱신하면서 동적 경로 계획이 가능하도록 한다(변화하는 화재 상황에 대응 목적).
  • 마지막으로, 위 과정을 통해 A*를 최적화하고 DASA-Star(Dynamic Avoid-Smoke A-Star) 알고리즘을 제안한다.
  • 시뮬레이션 결과, DASA-Star 알고리즘은 지하철 지하역사 화재 시나리오에서 경로의 화재 위험도와 기하학적 거리(단순 최단거리) 사이에서 적절히 트레이드오프(균형) 를 이루며 경로를 선택할 수 있었고,
    FDS(Fire Dynamics Simulator) 화재 시뮬레이션 결과를 기반으로 대피 경로를 동적으로 계획할 수 있음을 보였다.
  • 따라서 이 알고리즘은 화재 조건에서의 경로 계획이 요구하는 실시간성을 만족하며, 화재 영향 하에서 더 효과적으로 최적 대피 경로를 계획할 수 있다.

 

1. Introduction

  • 지하철역의 설계는 지형 조건, 개발 수준 등 여러 요인에 의해 좌우되며, 일반적으로 깊은 지하에 매설되는 경우가 많다.
  • 지하철역은 지하 깊숙이 위치한 특수한 공공건축물로서, 인구 밀도가 높고 보행자 유동(승객 흐름)이 크며 내부 구조가 복잡하다는 특징이 있다(Li et al., 2016; Zhou et al., 2021).
  • 비상 상황에서 지하철역 이용자를 대피시키는 과정에는 많은 불확실성 요인이 존재한다.
    • 예를 들면, 안전 대피를 위한 시간이 제한적이고, 효과적인 대피 경로 선택이 어렵다는 점 등이 있으며, 이는 대형 인명 피해로 쉽게 이어질 수 있다(Chen et al., 2017; Huang et al., 2022; Li et al., 2020a; Song et al., 2013).
    • 지하철역에는 건축 기준에 따라 비상 대피 시설과 전략(예: 안전 표지, 대피 계획)이 사전에 설계되어 있지만,
      대피 환경이       불확실하고 동적으로 변하기 때문에 실제 비상 상황에서 대피자에게 제공하는 실질적 도움은 제한적일 수 있다(Lo, 1996; Pu and Zlatanova, 2005).
    • 예컨대 화재 시 불꽃과 연기의 확산 및 농도 변화는 여러 대피 경로의 안전성을 낮추거나 아예 사용할 수 없게 만들어, 대피를 지연시키고 고립된 사람에게 치명적인 결과를 초래할 수 있다(Choi and Chi, 2019; Ran et al., 2014).

  • 또한 사람들은 비상 상황에서 주변 환경에 적응하는 능력이 떨어져, 짧은 시간 내에 주변에 대한 충분한 정보를 얻기 어렵고, 행동은 군집 심리(따라가기) 및 익숙한 경로를 선호하는 성향을 보이기도 한다(Helbing et al., 2000).
    • 이러한 현상에서 알 수 있듯이, 보행자 대피의 효율성과 안전이 저하되는 근본 원인은 대피자가 대피 환경 정보를 충분히 얻지 못하고, 그 결과 환경 자원을 충분히 활용하지 못하기 때문이다.

  • 따라서 지하철역 환경과 비상 사건 정보를 바탕으로 보행자 대피 안전 관련 요인을 측정·분석하고,
    관련     경로 계획 알고리즘을 이용해 최적 대피 경로를 동적으로 계획하며,
    역 내 사람들에게 과학적이고 합리적인 대피 경로를 신속히 제공한다면 위 문제들을 보다 효과적으로 해결할 수 있다(Cuesta et al., 2017; Galea et al., 2017; Samah et al., 2015; Zhang et al., 2022a).

  • 화재는 다량의 유독·유해 연기를 동반한다.
    또한 역사는 비교적 밀폐된 공간이며, 열차 운행의 피스톤 효과(piston effect) 가 연기 배출을 더욱 어렵게 만들 수 있다.
    동시에 연기의 확산·집적과 수직 통로에서 발생하는 굴뚝 효과(chimney effect) 는 역사 내 군중 대피를 크게 방해한다(Cai et al., 2022; Seike et al., 2016; Seike et al., 2021).

  • 화재 연기는 지하철역 대피자에게 강한 자극을 주어 공황 심리를 유발할 수 있고, 가시성을 떨어뜨려 대피 과정에서 시야가 크게 제한된다.
    더불어 연기에 포함된 유독 가스와 연기의 열복사(thermal radiation) 효과는 역사 내 재실자의 안전을 위협한다(Coskun et al., 2022; Li et al., 2020b).
    • 그러므로 화재 상황에서 안전하고 효율적인 대피를 보장하기 위해서는, 대피 경로 계획에서 단순히 ‘기하학적으로 가장 짧은 경로’만을 기준으로 삼는 것은 충분하지 않다(Zhang et al., 2019).

  • 일반적으로 군중 대피는 목적성이 강하며, 대피 전략은 고정되어 있지 않고 환경 상태 변화에 따라 계속 조정된다.
    • 따라서 현재 시점의 대피 환경 정보를 활용하는 동시에, 앞으로 변할 대피 환경 상태도 함께 고려해야 한다(Shi et al., 2009).
  • 지하철역 화재 환경에서는 화염의 불규칙한 확산과 연기(연무)의 확산·집적이 시간에 따라 지속적으로 변하므로, 어떤 한 시점의 정적(고정된) 환경 정보만으로는 실제 대피 요구를 만족시키기 어렵다.
    • 또한 대피 과정에서 군중의 행동은 매우 복잡해 대피 경로 계획 자체가 특수성과 복잡성을 띠며(Han et al., 2017), 따라서 지하철역 화재 조건에서의 대피 경로 계획은 일반적인 경로 계획 문제와 다르다.
  • 특히 시간에 민감한 화재 비상 상황에서는, 화재 위험 모델링과 경로 계획 알고리즘의 결합이 안전 대피에 도움이 될 수 있다(Huang et al., 2019).

  • 경로 계획(path planning) 알고리즘은 컴퓨터 기반 대피 시뮬레이션의 핵심 기술 중 하나로, 대피 분야에서 널리 활용된다.
    • 대피 경로 계획은 일반적인 경로 계획과 달리 정적인 환경 제약뿐 아니라 동적으로 변하는 환경 정보까지 고려해야 하며, 결국 다중 제약을 갖는 동적 경로 계획 문제에 해당한다.
    • 예를 들어 Choi와 Chi(2019)는 FDS(화재동역학 시뮬레이터)로 연기 확산을 시뮬레이션하고,
      A* 알고리즘을 이용해 건물 내 각 노드의 안전 상태를 예측하여 더 안전한 대피 경로를 계획했다.
    • Liu 등(2016)은 개미군집최적화(ACO)에서 양자 표현을 이용해 페로몬을 갱신함으로써 장애물을 더 효과적으로 회피하고 경로 안전성을 높였다.
    • 또한 대피 경로 계획의 현실성을 높이기 위해, 일부 연구는 알려진 환경 정보에 더해 실제 상황의 보행자 위치 상태(예: 인원 수, 초기 위치)를 알고리즘에 포함하기도 했다.
    • Wong 등(2015)은 군중을 인원수에 따라 나눈 뒤, 입자 군집 최적화(PSO)로 경로를 계획하여 대피 효율을 높였다.
  • 대피 경로 계획의 목표는 현재 상황에서의 최적 경로를 찾는 것이다.
    • 그 정확도는 결국 획득한 환경 정보의 정확도에 크게 의존한다.
  • 대피 환경은 실시간으로 변화하는 미지 정보(불확실성)를 포함하므로, 현실적인 대피 요구에 맞는 경로 계획 결과를 얻는 것은 더 까다롭고 복잡하다(Peng et al., 2019).
  • 예기치 못한 사건의 영향으로 환경 정보가 동적으로 변하기 때문에, 대피 경로 계획에는 실시간성(real-time) 과 강건성(robustness) 이 요구된다.
  • Xu 등(2022)은 PyroSim 화재 시뮬레이션 결과를 바탕으로 개미군집 알고리즘의 휴리스틱 함수와 페로몬 갱신 전략을 변경해 화재 조건에서 실시간 대피 경로 계획을 구현했다.
  • Zhao 등(2018)은 병렬 구조의 비동기 강화학습 기반 경로 계획 방법을 개발하여, 환경에 따라 행동 전략을 동적으로 바꾸도록 함으로써 재실자 대피의 동적 경로 계획 문제를 다뤘다.
  • 또한 일부 연구는 환경 정보를 일정 주기로 갱신하고, 계획 경로를 주기적으로 수정하는 방식으로 실시간 변화 문제를 해결하고자 했다(He et al., 2022).
  • Khakzad(2023)는 탱크 화재 위협을 고려해 다익스트라(Dijkstra) 알고리즘으로 대피 경로를 계획하고, 수리계획법으로 군중을 합리적으로 배분하여 사상 위험을 줄이는 방법을 제시했다.
  • He 등(2023)은 동적 A*를 기반으로 화재·폭발·독성물질 누출의 다중 위험과 도미노 효과를 고려한 화학산업 다중재난 대피 경로 계획 방법을 제안했다.
  • Huang 등(2021)은 화재 데이터베이스를 구축하고, 인체 허용 한계와 동적 재구성(reconstruction)을 결합한 뒤 A*로 재구성된 장면에서의 대피 경로를 계획해 동적 경로 계획을 구현했다.
  • Gibson 등(2020)은 A* 기반의 동적 경로 계획 알고리즘을 제안했는데, 실제 환경의 상태 피드백으로 일정 주기마다 생성된 경로를 갱신한다.
  • 구조가 단순하고 구현이 쉬운 장점이 있으나, 다른 알고리즘과 비교해 항상 최선이라고 단정하기는 어렵다는 점을 시사한다.
  • Shen 등(2015)은 가우시안 플룸 모델로 염소 확산 농도를 계산하고, 다익스트라 알고리즘을 결합해 최소 독성 노출량이 되도록 대피소까지의 최적 경로를 산출했다.
  • 기존 연구와 대피 경로 계획 문제 분석에 따르면, 동적 경로 계획은 안전성과 실시간 성능을 효과적으로 향상시킬 수 있지만(Kim et al., 2023), 여전히 어려움과 한계가 남아 있다.
  • 효율성과 지능성이 장점인 여러 알고리즘이 희소 환경의 동적 경로 계획에 널리 쓰이지만, 결과가 국소 최적해(local optimum) 에 빠질 수 있다.
  • 반면 휴리스틱 원리에 기반한 A* 알고리즘은 이러한 문제와 직접적으로 연관되지 않는 것으로 언급된다(Zeng and Church, 2009).
  • A*는 다익스트라의 최적화 방향으로 볼 수 있으며, 휴리스틱 함수를 도입해 다익스트라보다 정확하고 빠른 장점이 있다(Hart et al., 1968; Persson and Sharf, 2014; Xu et al., 2007).
  • A*는 다양한 대피 시나리오에서 널리 쓰이며 시작점에서 목표점까지의 최단 경로를 계산함으로써 대피 경로 계획 문제를 푼다.
  • 다만 실제 대피에서는 경로 길이뿐 아니라 대피 시간, 안전, 혼잡도 같은 요소도 고려해야 한다.
  • 그래서 전통적인 A*는 대피의 특수 요구를 반영하도록 개선되어 왔는데, 예를 들면 머신러닝으로 대피 과정의 유동(흐름) 동역학을 예측하거나, 휴리스틱 함수를 개선해 탐색 효율을 높이는 방식 등이 있다.
  • 기술 발전과 대피 요구에 대한 이해가 깊어짐에 따라, A*는 알고리즘 효율 향상, 복잡 환경 적응력 강화, 다른 알고리즘과의 통합을 통해 더 복잡한 대피 경로 계획 문제를 해결하도록 계속 최적화될 것이다.

  • 본 연구는 지하철역 시나리오를 대상으로, 실시간 화재 변화의 영향을 고려한 동적 대피 경로 계획 모델을 최적화된 A* 기반으로 구축한다.
  • 온도, 가시거리, CO 농도가 대피 속도에 미치는 영향을 고려해 화재 위험 모델을 만들고, 이를 알고리즘과 결합해 평가 함수를 변경함으로써 더 안전한 대피 경로를 계산하고 안전 대피 요구를 만족시키도록 한다.
  • 또한 시간 기반 동적 업데이트 메커니즘을 도입해 환경 정보가 동적으로 변하는 상황에 대응한다.
  • 이는 단순히 “어떤 시점의 지도 데이터를 업데이트한 뒤 그 정적 정보로 다시 계획(replanning)”하는 방식과는 다르다.
  • DASA-Star 알고리즘은 탐색 과정에서 환경 정보 변화 자체를 처리한다.
  • FDS로 시뮬레이션한 연기 데이터의 도움을 받아, 인원 이동 시간에 맞춘 실시간 업데이트 알고리즘에 따라 환경 정보 데이터를 갱신하면서 경로를 계속 최적화해 실제 대피 과정에 더 부합하는 최적 탈출 경로의 동적 계획을 달성한다.
  • 이 연구에서 구축한 동적 대피 경로 계획 모델은 지하철역 화재 장면의 대피 경로 계획에 적용될 수 있으며, 지하철역의 비상 대응 의사결정을 지원할 수 있다.

  • 그림 1은 본 연구의 기술 로드맵을 제시한다.
  • 본 논문의 구성은 다음과 같다.
    2장에서는 지하철역 화재 위험 모델을 구축한다.
    3장에서는 동적 회연(연기 회피) A* 알고리즘, 즉 DASA-Star 알고리즘을 제시한다.
    4장에서는 지하철역 화재 시뮬레이션 결과를 이용해 알고리즘 시뮬레이션 실험을 수행한다.
    5장에서는 DASA-Star 알고리즘의 효과를 분석·논의한다.
    6장에서는 결론과 향후 연구를 제시한다.
    마지막으로 7장에서는 본 연구의 한계를 분석한다.

 

2. Fire risk modeling for metro stations

  • 지하철역 화재 상황에서는 단순 최단거리 경로를 찾거나 대피 시간을 최소화하는 것만으로는 사람들을 안전하게 대피시키는 요구를 충족하기 어렵다.
  • 화재 상황에서는 대피 경로의 ‘안전성’이 더 중요해진다.
    따라서 화재와 화재 생성물(예: 연기, 열, 유독가스)이 대피 경로의 안전에 미치는 영향을 표현할 수 있도록, 이를 반영하는 화재 위험(fire risk) 모델을 구축해야 한다.
  • 이때 핵심은 환경 내 화재 생성물을 식별하고, 화재 및 생성물이 대피에 미치는 영향을 정량화(수치화) 하는 것이다.

 

2-1. Fire risk model

  • 실제 화재 상황에서는 화재로 발생하는 고온뿐만 아니라, 다양한 화재 생성물(연기, 유독가스 등) 이 재실자의 대피에 일정 수준 영향을 줄 수 있다(예: 생리적·심리적 영향)(Fang et al., 2012; Lo and Fang, 2000).
  • 화재 생성물이 대피에 미치는 영향에 관한 기존 연구를 바탕으로, 본 연구는 대피 환경에서 온도(temperature), 가시성(visibility), 일산화탄소(CO) 농도의 세 가지 요인을 고려하고 이들이 대피 속도에 미치는 영향을 분석한다.
  • 또한 세 요인과 대피 속도 간의 관계를 나타내기 위해 온도 영향 함수 , 가시성 영향 함수 , CO 농도 영향 함수를 도입한다(Xu et al., 2022).

  • 더 나아가, 화재 생성물들이 대피 경로에 미치는 복합 효과를 나타내는 화재 연기 영향 함수 f를 도입하며, 는 아래와 같이 세 함수의 곱으로 결정된다.

  • 따라서 화재의 영향을 고려한 유효 대피 속도 v_t는 다음과 같이 표현된다.
    • 여기에서 v_0은 정상 조건에서의 이동 속도, v_t는 화재 영향 하에서의 등가(유효) 대피 속도를 의미한다.

  • 화재 생성물 관련 변수들이 대피 속도에 미치는 영향을 고려하면, 화재 영향 하에서 대피 경로의 등가 길이(equivalent length) 은 다음과 같다.
    • 여기서 은 대피 경로의 실제 기하학적 길이, L은 화재 영향을 반영한 유효(등가) 길이이다.

  • 화재의 영향으로 경로마다 이동 속도가 달라지면(연기/열/CO 조건이 달라짐), 동일한 실제 길이의 경로라도 등가 길이는 달라질 수 있다.
    이를 반영하기 위해 본 연구는 이 효과를 화재 위험 비용 계수 로 표현하며 다음과 같이 정의한다.

  • 식 (4)로부터, 대피 경로의 등가 길이 은 화재 위험 비용 계수 에 비례함을 알 수 있다.
  • 서로 다른 대피 경로의 실제 길이가 같다면, 가 클수록(=위험이 클수록) 화재 영향 하에서의 등가 길이 L도 길어진다.
  • 즉, 화재 및 화재 생성물이 대피 경로에 미치는 영향이 클수록 화재 위험이 커진다.
  • 따라서 를 화재 시나리오에서 대피 경로의 화재 위험을 나타내는 지표로 사용할 수 있다.
  • 지하철역 대피 장면에서 화재 위험을 더 잘 표현하기 위해, 는 극차(최대-최소 범위) 를 이용해 정규화한다(일종의 min-max 스케일링).
  • 또한 대피 장면의 어떤 위치가 다음 조건 중 하나라도 만족하면, 
    1. 온도 >120 C 
    2. CO 농도 >0.1%
    3. 가시거리 <3m
    해당 위치의 화재 위험은 안전 대피의 임계값에 도달한 것으로 간주하며(Xu et al., 2022), 대피에 사용할 수 없는 구역으로 본다.

2-2. Temperature effect function

  • 온도는 단계별로 대피자의 이동(대피) 속도에 서로 다른 영향을 준다.
  • 또한 화재 초기에는 비교적 낮은 온도에서 “빨리 피하려는 자극” 때문에 대피 속도가 오히려 증가하는 긍정적 유인 효과가 나타날 수 있다.
  • 그러나 시간이 지나 연기가 축적되고 주변 온도가 일정 수준 이상으로 상승하면 대피 속도는 부정적(감속) 영향을 받는다.
  • 주변 온도가 임계값 120 °C에 도달하면 사람은 이동 능력을 완전히 상실하게 된다.
  • Milke(2000)가 제안한 관계식에 따라, 온도가 대피 속도에 미치는 영향 함수 R1(T)는 다음과 같이 정의된다.

 

 

2-3. Visibility effect function

  • 화재 연기는 고체 입자, 액체 입자, 유독·유해 화학물질 등으로 구성되며,
    연기가 만드는 차광(시야 가림) 정도는 이러한 물질의 농도와 직접적으로 관련된다.
  • 기존 경험(연구)을 바탕으로, 화재 연기의 차광 정도를 평가하기 위해 소광계수(=시야감쇠계수) K_c를 사용하며, K_c값은 대피 환경에서 사람의 가시성(시야) 에 직접적인 영향을 준다(Nguyen et al., 2013; Wang and Zheng, 2013).
  • K_c가 클수록 시야가 더 나빠져 주변 환경 관찰이 어렵고, 결과적으로 대피 효율이 감소한다.
  • Fridolf et al.(2019)을 참고하여, 가시성이 대피 속도에 미치는 영향 함수 R_2(K_c)는 다음과 같이 표현된다.
    • 여기서 K_c는 소광계수(obscuration/extinction coefficient) 이며 단위는 이다.

 

 

2-4. CO concentration effect function

  • 화재 연기에는 완전히 연소되지 않은 물질에서 비롯된 다량의 유독 가스가 포함된다.
  • 지하철역은 지하에 위치한 비교적 밀폐된 공간이기 때문에 이러한 유독 가스를 환기·배출하기가 어렵고, 그 결과 대피 과정에 큰 영향을 미친다.
  • 또한 여러 위험 요인 중에서도 일산화탄소(CO) 는 재실자의 안전 대피에 가장 큰 위협 요인으로 간주된다.
  • Milke(2000)는 실험을 통해, CO가 대피에 미치는 영향은 주로 사람들의 대피 속도 저하로 나타난다고 결론지었다. Milke(2000)의 연구를 바탕으로 CO 농도가 대피 속도에 미치는 영향 함수는 다음과 같이 정의된다.
    • t는 사람이 CO에 노출된 시간 ( s )
      ρ_co​는 CO의 체적 농도( % )

 

 

 

3. Improved A-Star algorithm

  • 본 절에서는 전통적인 A* 알고리즘을 개선하여, 대피 경로를 동적으로 계획하기 위한 알고리즘인 Dynamic Avoid-Smoke A(DASA-Star)* 를 제안하고 그 원리를 소개한다.
  • 먼저 전통적인 A* 알고리즘을 설명하고, 최단 경로 문제를 어떻게 다루는지 분석한다.
    다음으로, 앞서 구축한     화재 위험 모델을 A* 알고리즘에 대입하여 알고리즘의 의사결정 원리(평가 기준) 를 변화시킨다.
    마지막으로, 화재 환경 정보가 시간에 따라 계속 변하는 특성을 반영하기 위해     동적 업데이트 메커니즘을 도입하여, 변화하는 화재 환경에 대응할 수 있는 Dynamic Avoid-Smoke A* 알고리즘을 구축한다.

 

3-1. traditional a* algorothm

  • G는 start position에서 현재 노드까지의 실제 비용함수.
  • H는 현재 노드에서 goal position까지의 예측 비용 함수(휴리스틱)을 의미.

식 8

 

 

3.2. A-star algorithm considering fire risk

  • 지하철역 대피 경로 계획에서는 경로의 기하학적 길이(최단거리) 보다 경로의 안전성이 더 중요하게 고려된다.
    • 화재가 어느 수준에 도달하면, 불꽃이 타고 있는 구역뿐 아니라 연기 및 기타 가스 또한 대피 중인 사람들의 안전을 위협하여 안전한 대피를 방해한다.
  • 본 절에서는 2장에서 구축한 화재 위험 모델을 A* 알고리즘과 결합하고, 화재 영향 하에서의 경로 등가 길이(equivalent length) 를 알고리즘의 새로운 의사결정 기준으로 사용한다.
    • 이를 통해 경로 계획 과정에서 화재 및 화재 생성물이 대피에 미치는 영향을 함께 고려하여, 화재가 부정적 영향을 미치는 구역을 회피할 수 있는 대피 경로를 계획하는 것을 목표로 한다.
  • 화재 위험을 결합한 A* 알고리즘에서는 대피 경로 계획 시 더 이상 실제 기하학적 최단거리를 결정 기준으로 삼지 않고, 대신 화재 영향 하에서의 등가 대피 경로 길이를 기준으로 경로를 선택한다.
  • 따라서 평가 함수(식 (8))에 포함된 실제 비용 함수를 최적화하고,
    화재 위험 비용 계수 ξ를 실제 비용 함수 G(P[i])에 대입한다.
  • 그 결과 새로운 G(P[i])는 식 (9)와 같이 정의된다

식 9. k는 현재 노드에서 start node까지 거슬러 올라가는 노드의 개수를 의미. ξ ( n ) 은 현재 n노드에서의 화재 위험 비용 계수를 나타냄.

  • 실제 기하학적 거리 l(n)은 식 (10)같이 정의

식 10

  • 예측 비용 함수 H( p[i] )는 현재 노드 P[i]에서 goal node까지의 shortest path cost를 예측하는 값이다.

dest는 goal position을 의미. 이는 유클리드 거리를 이용함.

  • 화재 위험을 결합한 최적화 A*의 평가 함수 F( P[ i ] )
    • 화재 위험을 결합한 최적화 A*알고리즘에서 평가함수는 아래와 같이 표현한다.

 

3.3. Dynamic avoid-smoke A-Star algorithm

  • 전통적인 A* 알고리즘은 정적(변하지 않는) 환경 정보를 전제로 하는 경로 계획 알고리즘으로, 탐색 환경 정보가 시간에 따라 변하지 않는다고 가정한다.
    • 그러나 지하철역 화재 상황에서는 화재의 발생과 그 영향이 시간에 따라 지속적으로 변화한다. 따라서 특정 시점의 정적 환경 정보만을 기반으로 해서는 대피 안전 요구를 충족시키기 어렵다.
  • 그러므로 화재 상황에서의 대피 경로 계획 알고리즘은 동적으로 변하는 화재 환경 정보를 처리할 수 있는 능력을 갖춰야 한다.
  • 이를 위해 본 연구에서는 동적 업데이트 메커니즘을 도입하고,
    3.2절의 내용을 바탕으로 지하철역 화재 시나리오에서 대피 경로를 동적으로 계획하기 위한 Dynamic Avoid-Smoke A(DASA-Star)* 알고리즘을 제안한다.

3.3.1. Dynamic update mechanism

  • 전통적인 A* 알고리즘은 정적 장애물(static obstacle) 문제만 해결할 수 있다.
    • 경로 계획에서 현재 노드 P[i]가 다음 노드를 선택할 때, 먼저 주변의 8개 인접 자식 노드(이웃 노드)의 상태 정보를 판단한다.
    • 그런데 전통적 A*에서는 이렇게 얻은 주변 노드의 상태 정보가 시간이 지나도 고정되어 변하지 않는 것으로 취급된다.
  • 하지만 지하철역 화재 시나리오에서는 화염이 확산하면서 역사 내부에 새로운 연소 구역이 형성되고,
    이러한 구역은 시간에 따라 동적으로 변한다.
    • 대피 경로 계획 관점에서 이 새로운 연소 구역은 사람들이 지나가는 것을 막는 동적 장애물(dynamic obstacle) 로 작용한다.
      • 따라서 지하철역 대피 경로 계획 알고리즘은 동적 장애물에 대응할 수 있어야 한다.
  • 동적 장애물을 다루기 위해서는, 계획된 경로가 시간적 특성을 가져서 시간-공간 차원에서 동적 장애물을 제때 회피할 수 있어야 하며, 알고리즘이 생성한 경로의 궤적이 동적 장애물의 변화 궤적과 교차하지 않도록 해야 한다.
  • 본 연구는 전통적인 A* 알고리즘을 최적화하는 방향을 따른다.
  • A*는 현재 선택된 구간/노드 P[i]를 기준으로 탐색을 진행한다.
  • 동적 업데이트 메커니즘의 핵심은 시작점 P[start]에서 현재 노드 P[i]까지 도달하는 데 걸리는 시간 T_i를 결정하는 것이다.
  • 이를 수행하는 서브루틴을 ‘Dynamic-update’라고 하며, 그 의사코드는 표 3에 제시되어 있다.

 

  • 격자 지도(raster map)에서 직선(수평/수직)으로 이동할 때와 대각선으로 이동할 때는 소모 비용이 다르기 때문에(대각선 이동이 더 큰 비용을 소모), 이동에 걸리는 시간도 달라진다.
  • 따라서 현재 노드 P[i]의 시간 T_i는 단순히 “몇 칸 이동했는가(격자 수)”로 결정할 수 없고,
    시작점에서 현재 노드까지의 이동 거리 ÷ 속도로 결정해야 한다.
  • Dynamic-update 서브루틴은 각 이동(step)의 시간을 누적(합산)하여 현재 노드 P[i]의 시간 T_i를 계산한다.
  • 주의할 점은, 어떤 노드의 부모 노드가 바뀌면(더 좋은 경로로 갱신되면) 그 노드에 도달하는 시간도 바뀐다는 것이다. 또한 서로 다른 노드라도 도달 시간이 같은 경우가 있을 수 있다.
  • 화염 확산은 새로운 장애물을 만들기 때문에, 본 연구는 동적 업데이트 메커니즘을 결합한 A* 로 경로 계획을 수행한다.
  • 경로 계획 과정에서 현재 노드 P[i]가 다음 노드를 선택할 때, 현재 시각 T_i에서 현재 노드의 자식 노드들이 “지금 시점의 새로운 연소 구역”에 해당하는지 판단한다.
    • 만약 해당한다면 그 노드는 장애물 노드 D_n[T_i]로 간주하여 closed list에 넣는다.
  • 반대로 나머지 자식 노드들은 open list에 넣고 F(P[i])값을 계산한 뒤,
    open list에서 값이 가장 작은 노드를 다음 현재 노드로 선택한다.
  • 관련 경로 계획 과정은 그림 4에 제시되어 있다.
  • 그림 4(a)에서는 화염 연소 범위가 작고 (2,3) 노드가 현재 노드이며 현재 시간은 T*_1이다.
  • 현재 노드의 자식 노드들의 F 값을 계산해 open list에 추가하고,
    화원 위치인 (2,4) 노드는 다음 노드 선택 시 장애물로 간주되어 closed list에 추가된다.
  • 이어서 open list에서 가장 작은 F 값을 갖는 (3,3) 노드가 현재 노드가 되고,
    현재 시간은 T*_2가 된다.
  • 이 시점에서 연소 범위가 확장되어 (1,4), (2,4), (3,4) 노드가 포함된다(그림 4(b)).
  • 이 결과는 장애물 노드로 간주되어 closed list에 추가된다. 그 다음 현재 노드의 자식 노드들의 F값을 계산하여 다음 선택을 위해 open list에 추가한다
  • 이때 (3,4) 노드는 이미 화염에 포함되어 경로 노드가 될 수 없으므로, open list에서 가장 작은 F 값을 가진 노드는 (2,2)가 된다.
  • (2,2)의 부모 노드는 시작점 (1,2)이며, 현재 노드 (2,2)의 시간 업데이트는 T_1로 표현된다(그림 4(c)).
  • 이후 동일한 방식으로 현재 노드의 자식 노드들을 평가해 open list에 넣는다.
  • 그 결과 open list에서 가장 작은 F값을 가진 (3,2) 노드가 현재 노드가 되며 현재 시간은 T_2가 된다(그림 4(d)).
  • 마찬가지로 (그림 4(e)) 같은 방식으로 다음 노드 선택을 반복한다.
  • 그림 4(f)에서는 화재가 더 진행되어 T_4시점에서 (2,2)가 화염에 포함되더라도, 현재 노드 (6,5)는 포함되지 않으므로 다음 노드를 계속 선택할 수 있다.
  • 동적 업데이트 메커니즘을 적용한 A* 알고리즘의 의사코드는 표 4에 제시되어 있으며,
    알고리즘은 최종적으로 역추적(backtracking) 을 통해 최종 경로 계획 결과를 도출한다.

 

3.3.2. Principle of Dynamic Avoid-Smoke A-Star algorithm

  • 본 절에서는 3.2절에서 구축한 화재 위험 결합 A* 알고리즘에 동적 업데이트 메커니즘을 결합하여, 지하역사 화재 시나리오에서 대피 경로를 동적으로 계획하는 알고리즘을 구축한다. 알고리즘의 원리는 다음과 같다.
  • 화재 환경에서 온도, 가시성, CO 농도는 시간에 따라 변하므로, 화재의 영향을 반영한 경로 등가 길이 역시 시간에 따라 변한다. 즉, 화재 위험 비용 계수는 시간 속성(time attribute) 을 갖게 된다. 따라서 화재 위험 비용 계수는 시간 t에 대해 다음과 같이 갱신된다.

  • 여기서 ξ_t는 시각 에서의 화재 위험 비용 계수, L_t는 시각 t에서 대피 경로의 등가 길이, f_t(T,Kc,ρco)는 시각 에서의 화재(연기) 영향 함수이다.
  • 이제 DASA-Star 알고리즘의 평가 함수에서, 시간에 따라 변하는 경로 화재 위험을 고려하기 위해 실제 비용 함수를 다음과 같이 정의한다.
    • 여기서 t_i는 현재노드 P[ i ]에 해당하는 시간, t_0은 start node P[ start ]의 시간을 의미한다.

  • DASA-star알고리즘의 평가함수 F_t( P[ i ] )는 아래와 같이 정의한다.

  • DASA-Star는 알고리즘5에 나타나있음.

 

4. Case study

  • 본 절에서는 제안한 DASA-Star 알고리즘의 효과를 검증하기 위해 시뮬레이션 실험을 수행한다. 시뮬레이션 플랫폼으로는 Intel i5 1.8 GHz 프로세서, 8 GB 메모리를 사용하였고, 소프트웨어는 Windows 10 환경에서 MATLAB R2016b와 FDS 6.7.1을 사용하였다.
  • 먼저 화재 시뮬레이션 소프트웨어인 FDS를 이용해 지하철역 모델을 구축하고, 역사 홀(대합실)에서 화재 시뮬레이션을 수행하여 연기 관련 데이터를 획득한다.
    다음으로 FDS 시뮬레이션 결과를 기반으로 지하철역 화재 시나리오에서 각각 전통적인 A* 알고리즘, 화재 위험 결합 A* 알고리즘, DASA-Star 알고리즘을 적용하여 대피 경로 계획을 수행한다.
    마지막으로 여러 알고리즘이 산출한 대피 경로 계획 결과의 차이를 비교하고, 서로 다른 알고리즘의 경로 계획 결과를 평가함으로써 제안 알고리즘의 유효성을 검증한다.

 

 

 

4-1. Metro station fire simulation

  • 그림 5는 지하철역 로비(대합실) 층의 건물 구조 배치를 보여준다.
  • 해당 층의 총 면적은 3039.75 m²(남–북 방향 기준)이며, 안전 출구 4개, 층고 3 m를 갖는다.
  • 격자(grid) 크기는 0.5 × 0.5 × 0.2 m로 설정했고, 전체 격자 수는 182,385개이다.
  • 화원(크기 1 m × 1 m)은 지하철역 유료 구역(paid area) 의 한쪽 끝에 설치하였다.
  • 연소 물질은 승객이 반입한 수하물로 설정했으며, 주요 성분은 폴리우레탄(polyurethane) 이다.
  • 화원 열방출률(HRR) 증가는 빠른 성장형(fast type) 으로 설정했고, 성장 계수 α\alpha는 0.04689로 두었다.
  • 최대(설정) 열방출률은 6 MW로 설정했으며, HRR 방정식에 따르면 화원은 357초(s) 에 최대 열방출률에 도달한다(Kadokura et al., 2012; Yan et al., 2023).
  • 사람의 평균 눈높이는 1.6 m로 가정하였다(Xu et al., 2022). 재실자의 안전 대피를 확보하기 위해, 본 연구에서는 1.8 m 높이에서의 온도, CO 농도, 가시성의 수치 변화를 모니터링하였다.