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

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를 도입하며, f는 아래와 같이 세 함수의 곱으로 결정된다.

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

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

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

• 식 (4)로부터, 대피 경로의 등가 길이 L은 화재 위험 비용 계수 ξ에 비례함을 알 수 있다.
• 서로 다른 대피 경로의 실제 길이가 같다면, ξ가 클수록(=위험이 클수록) 화재 영향 하에서의 등가 길이 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) 이며 단위는 1/m이다.

 

 

2-4. CO concentration effect function

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

 

 

 

3. Improved A-Star algorithm

• 본 절에서는 전통적인 A* 알고리즘을 개선하여, 대피 경로를 동적으로 계획하기 위한 알고리즘인 Dynamic Avoid-Smoke A(DASA-Star)* 를 제안하고 그 원리를 소개한다.

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