[논문]탐욕 알고리즘 기반 다중 출구 대피경로 할당

이민혁; 남현우; 전철민

doi:10.7319/kogsis.2016.24.1.069

탐욕 알고리즘 기반 다중 출구 대피경로 할당
An Evacuation Route Assignment for Multiple Exits based on Greedy Algorithm 원문보기

한국지형공간정보학회지 = Journal of the korean society for geospatial information science, v.24 no.1, 2016년, pp.69 - 80

이민혁 (서울시립대학교 공간정보공학과) , 남현우 (서울시립대학교 공간정보공학과) , 전철민 (서울시립대학교 공간정보공학과)

초록
AI-Helper

재난 발생 시, 실내 공간에서의 신속한 대피를 위해 총 대피시간 최소화를 목적으로 일부 연구들이 진행되었다. 하지만 대부분의 연구가 총 대피시간이 최소화되는 최적 대피경로를 산출하는데 오랜 연산시간이 소요되어 실제 재난 상황에 적용하기 어렵다는 한계를 가지고 있다. 이에 본 연구는 짧은 연산시간으로 총 대피시간을 단축시킬 수 있는 대피경로 할당 알고리즘을 제안하고자 한다. 대피경로 할당 알고리즘은 다수의 출구가 존재하는 건물에서 대규모 인원 대피 시, 각 출구에 적절하게 대피인원을 할당하여 출구들의 교통 정체 상황을 균형적으로 유지함으로써 총 대피시간을 단축시키는 알고리즘이다. 각 출구에 대피인원을 할당하는 방법은 그래프 이론을 기반으로 탐욕 알고리즘의 접근방식을 활용하였다. 본 연구에서는 알고리즘의 검증을 위해 cellular automata 기반 대피 시뮬레이터를 이용하였으며 실제 건물과 유사한 구조에서 다양한 인원분포를 적용한 뒤 실험을 수행하였다. 결과적으로 최단거리 출구 대피보다 알고리즘을 적용하였을 때 총 대피시간이 감소되었고 대형 건물 구조에서도 짧은 연산시간이 소요되는 것을 확인하였다.

Abstract ▼ AI-Helper

Some studies were conducted for the purpose of minimizing total clearance time for rapid evacuation from the indoor spaces when disaster occurs. Most studies took a long time to calculate the optimal evacuation route that derived minimum evacuation time. For this reason, this study proposes an evacuation route assignment algorithm that can shorten the total clearance time in a short operational time. When lots of exits are in the building, this algorithm can shorten the total clearance time by assigning the appropriate pedestrian traffic volume to each exit and balances each exit-load. The graph theory and greedy algorithm were utilized to assign pedestrian traffic volume to each exit in this study. To verify this algorithm, study used a cellular automata-based evacuation simulator and experimented various occupants distribution in a building structure. As a result, the total clearance time is reduced by using this algorithm, compared to the case of evacuating occupants to the exit within shortest distance. And it was confirmed that the operation takes a short time In a large building structure.

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

본 연구는 짧은 연산시간으로 총 대피시간을 최소화하기 위해 대피경로 할당 알고리즘을 개발하였다. 일반적으로 다수의 출구가 존재하는 상황에서, 총 대피시간을 최소화하는 최적 대피경로를 산출하기 위해서는 많은 연산량을 필요로 한다.
(2005) 등의 연구에 의해 다뤄진 바 있다. 본 연구는 총 대피시간의 단축이 목적이기 때문에 이번 장에서는 총 대피시간 최소화와 관련되어 수행된 연구들 위주로 살펴보고자 한다. 앞서 설명한 바와 같이 대부분의 관련 연구가 그래프 기반의 데이터 구조를 이용하기 때문에 본 장에서 언급하는 노드는 보행자들이 머무는 방과 같은 공간을 의미하고 에지는 복도와 같은 이동통로를 의미한다.
이에 본 연구는 짧은 연산시간으로 총 대피시간을 단축시킬 수 있는 대피경로 할당 알고리즘을 제안한다. 대피경로 할당 알고리즘은 다수의 출구가 존재하는 건물에서 대규모 인원 대피 시, 각 출구에 적절하게 대피인원을 할당하여 출구들의 교통 정체 상황을 균형적으로 유지함으로써 총 대피시간을 단축시킨다.

가설 설정

최종적으로 각 출구의 할당량이 균형적으로 유지되어 총 대피시간은 150tick 감소된 결과를 얻었다. 또한 단 하나의 방만 할당받은 C의 대피종료시점이 총 대피시간이 되었음으로 하나의 방의 재실인원들은 모두 동일한 경로로 대피한다는 가정 하에서는 이 결과가 최적해라고 할 수 있다.

제안 방법

두 번째 부분에서는 알고리즘의 연산시간를 분석하였다. Intel X5650 2.67GHz CPU, 4.00GB RAM의 PC사양에서 실험을 진행하였으며 재난현장에 적용가능한지 검토하기 위해 Wang and Liu(2012)에서 제안된 실시간 대피 알고리즘과 연산시간을 비교해보았다. 대피경로 할당 알고리즘은 편의상 ERAA(Evacuation Route Assignment Algorithm)로 표기하였다.
Table 4는 실제 대학 캠퍼스 건물 단층에 2304명을 복도를 제외한 각 방에 균일한 밀도로 배치한 후 실험한 결과이다. 각 출구에서의 보행흐름은 실제 출구의 폭을 고려하여 A부터 E순으로 4, 3, 5, 3, 3(명/tick)으로 설정하였다.
출구에 할당량을 정하는 방식은 탐욕 알고리즘 기반의 대피경로 할당 알고리즘을 통해 이루어졌다. 그래프 이론을 이용하여 실내 공간을 노드와 에지로 구조화한 뒤, 대기인원이 최소인 출구에 최적이라고 판단되는 노드를 할당하는 방식으로, 전체 노드의 할당이 완료될 때까지 진행하였다.
유사 건물 구조 및 실제 건물 구조에서 실험을 진행하였고 Table 3 and 4가 그 결과에 해당한다. 두 번째 부분에서는 알고리즘의 연산시간를 분석하였다. Intel X5650 2.
대피경로 할당 알고리즘은 대기인원이 최소인 출구가 후보군 중 최적이라고 판단되는 노드를 흡수하는 방식으로 전체 노드의 할당이 완료될 때까지 진행되기 때문에 전체 재실인원 수는 알고리즘 연산에 부담을 주지 않는다. 따라서 노드(source node) 수와 출구 수를 증가시켜가며 연산시간을 살펴보았다. Table 5가 그 결과에 해당한다.
, 1990). 본 연구에서는 Fig. 3에 표시한 활용 부분, 즉, 후보군 중 부분 해 선택, 적용 가능성 검사, 해 집합에 추가 과정을 각 출구에 적용하여 대피경로 할당 알고리즘을 완성하였다.
본 연구에서는 대기인원 계산을 위한 출구의 보행흐름을 출구의 폭만을 고려하였다. 하지만 항상 출구의 최대 폭만큼 인원들이 대피할 수 있는 것은 아니다.
각 출구에 할당할 대피인원을 결정하는 방법은 그래프 이론을 기반으로 탐욕 알고리즘의 접근방식을 활용하였다. 본 연구에서는 제안한 알고리즘의 검증을 위해 CA 기반 대피 시뮬레이터를 이용하였고 실제 건물과 유사한 구조에서 다양한 인원분포를 적용하여 실험 결과를 도출하였다.
(2014)는 다수의 출구가 존재할 때, 각 출구의 교통 정체 상황을 균형적으로 유지함으로써 총 대피시간을 최소화하는 전략을 제안하였다. 이 연구에서는 각 노드에 최단거리에 위치한 출구를 할당한 뒤, 대피종료시간이 가장 오래 걸리는 출구를 할당받은 노드 중 해당 출구로부터 멀리 떨어진 노드부터 대피종료시간이 가장 적게 걸린 출구로 재할당하는 과정을 반복하면서 총 대피시간의 최솟값을 도출하였다. 또한 노드별로 대피 시작 시간에 차등을 주어 출구에서의 교통 혼잡을 최소화하였다.
이 상태에서 각 노드가 할당받은 출구로 대피를 진행한다면, N4의 재실자들은 최단거리에 Exit B가 있음에도 불구하고 Exit A로 대피해야 한다. 이처럼 특정 출구에 과도하게 노드들을 할당하여 발생하는 비합리적인 결과를 방지하기 위해 최대 할당 영역 규칙을 고안하였다.
알고리즘에 대한 실험은 크게 두 부분으로 나누어서 진행하였다. 첫 번째 부분에서는 알고리즘에 의한 대피 결과를 검증하기 위해 최단거리에 있는 출구로 재실인원을 대피시켰을 경우와 비교, 분석해 보았다. 유사 건물 구조 및 실제 건물 구조에서 실험을 진행하였고 Table 3 and 4가 그 결과에 해당한다.

대상 데이터

6에서 N4가 할당되기 전 Exit A의 할당노드 집합은 {N1, N7, N2, N8, N3, N9}이다. 따라서 후보군은 {N4, N10}이며 각각 Exit B와 Exit D의 인접 노드이다. 여기서 Exit A에 어떠한 노드를 할당하더라도 B와 D 중 하나는 자신의 인접 노드를 모두 잃게 된다.
첫 번째 부분에서는 알고리즘에 의한 대피 결과를 검증하기 위해 최단거리에 있는 출구로 재실인원을 대피시켰을 경우와 비교, 분석해 보았다. 유사 건물 구조 및 실제 건물 구조에서 실험을 진행하였고 Table 3 and 4가 그 결과에 해당한다. 두 번째 부분에서는 알고리즘의 연산시간를 분석하였다.

이론/모형

, 2014). 각 출구에 할당할 대피인원을 결정하는 방법은 그래프 이론을 기반으로 탐욕 알고리즘의 접근방식을 활용하였다. 본 연구에서는 제안한 알고리즘의 검증을 위해 CA 기반 대피 시뮬레이터를 이용하였고 실제 건물과 유사한 구조에서 다양한 인원분포를 적용하여 실험 결과를 도출하였다.
대피경로 할당 알고리즘의 최종적인 흐름은 Fig. 13과 같고 알고리즘의 검증을 위해 CA 기반 대피 시뮬레이터를 이용하였다. CA 기반 대피 시뮬레이터는 개별 보행자의 이동을 묘사하기 때문에 알고리즘에 의한 대피 결과를 보다 미시적으로 확인할 수 있는 장점이 있다.
건물구조 그래프는 대피경로를 산출하는데 사용된다. 본 연구에서는 다익스트라 알고리즘을 이용하여 서로 다른 노드 간의 최단거리를 계산한다. 각 방과 출구는 벽을 공유하거나 근거리에서 서로 마주보는 혹은 대각에 위치하는 관계에 따라 인접성을 가지게 된다.
시뮬레이션의 실행은 각 노드의 재실인원과 CA 보행모델에 대한 파라미터를 입력한 후 진행된다. 본 연구에서는 총 대피시간 단축을 위한 알고리즘 개발에 중점을 두었기 때문에 CA 보행모델(Nam et al., 2014)에 대한 자세한 설명은 생략하였다.
출구에 할당량을 정하는 방식은 탐욕 알고리즘 기반의 대피경로 할당 알고리즘을 통해 이루어졌다. 그래프 이론을 이용하여 실내 공간을 노드와 에지로 구조화한 뒤, 대기인원이 최소인 출구에 최적이라고 판단되는 노드를 할당하는 방식으로, 전체 노드의 할당이 완료될 때까지 진행하였다.

성능/효과

노드 당 재실인원을 100명으로 하고 출구를 4개로 제한한 상태에서 노드 수를 증가시켜가며 연산시간을 살펴본 결과, 노드 500개의 연산에는 1초가 걸리지 않았고 3000개의 노드에서는 약 16초의 연산시간이 소요되었다. 재실인원은 그대로 적용하고 노드 수를 1000개로 제한한 상태에서 출구 수만 늘렸을 경우에는 출구 수를 10개씩 증가시킬 때마다 약 0.
적용 테스트 결과, 최단거리 출구로 실내 인원들을 안내할 경우보다 총 대피시간이 많이 감소된 결과를 획득할 수 있었으며 각 출구에서의 대피시간도 균형적으로 나타났다. 또한 네트워크 사이즈가 작은 경우, 실시간으로 결과 획득이 가능하였으며 극단적인 상황에서도 비교적 짧은 연산시간이 소요되었다.
알고리즘을 적용한 후에는 각 출구의 대피시간 차이가 많이 줄어든 것을 확인할 수 있다. B와 C의 경우, 거의 동시에 대피가 종료되었으며 D의 대피시간이 많이 증가하였다.
이 모델은 총 대피시간의 최대 범위를 예측한 뒤, 전체 노드(source)와 출구(sink) 사이의 가능한 모든 경로에 대하여 시간 전개형 네트워크를 생성한다. 이 후, 시간 전개형 네트워크상에서 각 노드별 최소 비용 경로를 탐색하여 대피경로를 산출하고 산출된 대피경로의 총 대피시간이 최대 범위보다 작을 경우 최적해로 판단한다. 이와 같은 방법은 대상 공간 전체의 인원분포를 고려한 최적해 산출이 가능하다는 장점이 있다.
노드 당 재실인원을 100명으로 하고 출구를 4개로 제한한 상태에서 노드 수를 증가시켜가며 연산시간을 살펴본 결과, 노드 500개의 연산에는 1초가 걸리지 않았고 3000개의 노드에서는 약 16초의 연산시간이 소요되었다. 재실인원은 그대로 적용하고 노드 수를 1000개로 제한한 상태에서 출구 수만 늘렸을 경우에는 출구 수를 10개씩 증가시킬 때마다 약 0.7초의 연산시간이 증가하는 것을 확인하였다.
적용 테스트 결과, 최단거리 출구로 실내 인원들을 안내할 경우보다 총 대피시간이 많이 감소된 결과를 획득할 수 있었으며 각 출구에서의 대피시간도 균형적으로 나타났다. 또한 네트워크 사이즈가 작은 경우, 실시간으로 결과 획득이 가능하였으며 극단적인 상황에서도 비교적 짧은 연산시간이 소요되었다.
(2012)는 임의의 인원분포 상황에서 최적의 대피결과를 도출하기 위해 CA 기반 보행모델에 유전자 알고리즘을 적용한 연구를 수행하였다. 총 대피시간 최소화 뿐만 아니라 미시적 관점에서 대피의 전개상황을 파악할 수 있었다. 그러나 시뮬레이션으로 인해 다소 긴 연산시간이 소요된다는 한계가 여전히 존재하였다.
최종적으로 각 출구의 할당량이 균형적으로 유지되어 총 대피시간은 150tick 감소된 결과를 얻었다. 또한 단 하나의 방만 할당받은 C의 대피종료시점이 총 대피시간이 되었음으로 하나의 방의 재실인원들은 모두 동일한 경로로 대피한다는 가정 하에서는 이 결과가 최적해라고 할 수 있다.

후속연구

따라서 센서 네트워크가 구축되어 실내 공간의 재실인원 분포를 감지할 수 있는 건물이라면, 재난 발생 시, 본 연구에서 제안하는 알고리즘을 활용하여 총 대피시간 단축 및 실시간 대피 안내가 가능할 것으로 판단된다.
따라서 대기인원 계산에 대한 보다 정교한 수식이 필요하다. 또한 알고리즘의 실험이 단층 구조에서만 수행되었으므로 다층 구조에 적용하였을 경우 발생할 수 있는 문제점 및 할당규칙 등을 보완하는 향후 연구가 필요할 것으로 판단된다.
일반적으로 다수의 출구가 존재하는 상황에서, 총 대피시간을 최소화하는 최적 대피경로를 산출하기 위해서는 많은 연산량을 필요로 한다. 하지만 본 연구에서는 그리드 셀이 아닌 그래프 구조를 이용하였으며, 목적함수를 대피시간으로 설정하지 않고 각 출구의 할당량 균형적으로 유지하는 방법으로 대피문제에 접근하여 보다 적은 연산량이 소요된다.

질의응답

핵심어	질문	논문에서 추출한 답변
	총 대피시간을 최소화하기 위해 재난현장의 인원 분포를 고려하여 대피 안내를 해야 하는 이유는 무엇인가?	대형 쇼핑몰 및 영화관 등에서는 대피시간의 단축을 위해 영상물이나 게시판 등을 이용하여 최단거리에 위치한 출구를 안내하고 있다. 그러나 건물 내 다수의 출구가 존재하고 인원분포가 불균형적인 상황에서 단순히 최단거리에 있는 출구로 재실자들을 유도하게 되면, 특정 출구에 많은 인원이 집중되어 오히려 총 대피시간을 지연시킬 수 있다. 따라서 총 대피시간을 최소화하려면, 재난현장의 인원분포를 고려하여 대피 안내가 이루어져야 한다.
	일반적으로 무엇을 활용하여 최소 대피시간을 탐색하는가?	일반적으로 그래프 이론을 이용하여 실내공간을 모델링하고(Chalmet et al., 1982) 수학적 기법(Hamacher and Tjandra, 2001) 및 network flow(Pursals and Garzón, 2013), 휴리스틱 기반의 최적화 알고리즘(Yusoff et al., 2008) 등을 활용해 최소 대피시간을 탐색하고 있다. 최근에는 모델의 검증을 위해 cellular automata(CA)와 같은 보행모델을 적용한 미시적 시뮬레이션도 활용되었다(Kwak et al.
	대피경로 할당 알고리즘은 무엇인가?	이에 본 연구는 짧은 연산시간으로 총 대피시간을 단축시킬 수 있는 대피경로 할당 알고리즘을 제안하고자 한다. 대피경로 할당 알고리즘은 다수의 출구가 존재하는 건물에서 대규모 인원 대피 시, 각 출구에 적절하게 대피인원을 할당하여 출구들의 교통 정체 상황을 균형적으로 유지함으로써 총 대피시간을 단축시키는 알고리즘이다. 각 출구에 대피인원을 할당하는 방법은 그래프 이론을 기반으로 탐욕 알고리즘의 접근방식을 활용하였다.

참고문헌 (19)

Cormen, T. H., Leiserson, C. E., Rivest, R. L. and Stein, C., 1990, Introduction to Algorithms, MIT Press, p. 329.
Chalmet, L. G., Francis, R. L. and Saunders, P. B., 1982, Network models for building evacuation, Fire Technology, Vol. 18, No. 1, pp. 90-113.

상세보기
Chen, P. H. and Feng, F., 2009, A fast flow control algorithm for real-time emergency evacuation in large indoor areas, Fire Safety Journal, Vol. 44, No. 5, pp. 732-740.

상세보기
Fruin, J. J., 1992, Designing for pedestrians, Public Transportation United States, http://ntl.bts.gov/DOCS/11877/Chapter_8.html
Gwynne, S., Galea, E. R., Owen, M., Lawrence, P. J. and Filippidis, L., 1999, A review of the methodologies used in the computer simulation of evacuation from the built environment, Building and Environment, Vol. 34, No. 6, pp. 741-749.

상세보기
Hamacher, H. W. and Tjandra, S. A., 2001, Mathematical modelling of evacuation problems: A state of art, Fraunhofer-Institut fur Techno-und Wirtschaftsmathematik, Fraunhofer (ITWM), pp. 1-44.
Kim, S., Shekhar, S. and Min, M., 2008, Contraflow transportation network reconfiguration for evacuation route planning, Knowledge and Data Engineering, IEEE Transactions on, Vol. 20, No. 8, pp. 1115-1129.

상세보기
Kisko, T. M. and Francis, R. L., 1985, EVACNET+: a computer program to determine optimal building evacuation plans, Fire Safety Journal, Vol. 9, No. 2, pp. 211-220.

상세보기
Kuligowski, E. D., Peacock, R. D. and Hoskins, B. L., 2005, A review of building evacuation models, MD: US Department of Commerce, National Institute of Standards and Technology, pp. 1-29.
Kwak, S. Y., Nam, H. W. and Jun, C. M., 2012, An Optimal Model for Indoor Pedestrian Evacuation considering the Entire Distribution of Building Pedestrians, Journal of the Korean Society for Geospatial Information Science, Vol. 20, No. 2, pp. 23-29.
Lovas, G. G., 1995, On performance measures for evacuation systems, European Journal of Operational Research, Vol. 85, No. 2, pp. 352-367

상세보기
Li, Q., Feng, Z., Li, Q. and Zong, X., 2010, Multiobjective evacuation route assignment model based on genetic algorithm, Proc. of the 18th International Conference, Geoinformatics, pp. 1-5.
Lu, Q., George, B. and Shekhar, S., 2005, Capacity constrained routing algorithms for evacuation planning: A summary of results, Advances in spatial and temporal databases, Springer Berlin Heidelberg, pp. 291-307.
Nam, H. W., Kwak, S. Y. and Jun, C. M., 2014, Developing a Cellular Automata-based Pedestrian Model Incorporating Physical Characteristics of Pedestrians, Journal of Korea Spatial Information Society, Vol. 22, No. 2, pp. 53-62.
Pursals, S. C. and Garzon, F. G., 2009, Optimal building evacuation time considering evacuation routes, European Journal of Operational Research, Vol. 192, No. 2, pp. 692-699.

상세보기
Pursals, S. C. and Garzon, F. G., 2013, Building evacuation: Principles for the analysis of basic structures through dynamic flow networks, Journal of Industrial Engineering and Management, Vol. 6, No. 4, pp. 831-859.
Wang, X. and Liu, H., 2012, An evacuation algorithm for large buildings, Proc. of the 10th World Congress, Intelligent Control and Automation (WCICA), pp. 2497-2502
Xie, J., Li, Q., Wan, Q. and Li, X., 2014, Near optimal allocation strategy for making a staged evacuation plan with multiple exits, Annals of GIS, Vol. 20, No. 3, pp. 159-168.

상세보기
Yusoff, M., Ariffin, J. and Mohamed, A., 2008, Optimization approaches for macroscopic emergency evacuation planning: a survey, Proc. of the ITSim 2008, Information Technology, Vol. 3, pp. 1-7.

저자의 다른 논문 :

LOADING...

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증