선내 재난상황 시 구조자 진입경로 탐색을 위한 유전 알고리즘 적용 방안
Copyright © The Korean Society of Marine Engineering
This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License (http://creativecommons.org/licenses/by-nc/3.0), which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.
초록
화재 등의 재난 상황 시 대피 경로를 안내하기 위해 대부분의 건물, 선박 등의 구조물에서는 중앙통제센터나 안전요원의 안내나 대피 경로 유도등을 통해 대피 경로를 안내하고 있다. 하지만 규모가 커지고 갈수록 내부 구조가 복잡해짐에 따라 재난 상황에 대한 실시간 정보가 부족하여 상황에 대한 효과적인 대응이 어려우므로, 비상 상황 시 안전을 보장할 수 있는 지능적 안내 시스템의 필요성이 증가하고 있다. 따라서 분산적으로 배치된 센서들로부터 수집된 상황 데이터 정보에 기반하여 중앙서버에서 지능적으로 경로를 탐색하고 재난상황에서의 탈출을 유도하는 알고리즘이 제안되었다. 그러나 대피자의 효과적인 대피와 함께 중요한 부분이 구조자의 효율적인 구조활동이다. 현재까지 대피자의 대피 경로 유도에 대한 연구는 다양하게 이루어져왔으나, 구조자의 효율적 진입 경로 탐색에 대한 연구는 기본적인 방안의 설계에 그치고 있다. 따라서 본 논문에서는 센서 네트워크 환경에서 유전 알고리즘을 적용한 구조자 진입 경로 탐색 방안과 구조자원 투입량의 최적화 방안에 대해 제안하였다. 제안된 방식의 실효성을 검증하기 위해 컴퓨터 시뮬레이션을 통해 제안된 방식의 성능을 검증하였다.
Abstract
In current evacuation methods, a crew member describes the physical location of a possible accident and guides the evacuation using alarms and emergency guide lights. However, in case of an accident in a large and complex building, a more intelligent and effective emergency evacuation system is required to ensure the safety of the evacuees. This is because the current schemes are unsuitable for dynamically changing emergencies due to the deficiency of real-time status information. Therefore, several studies have been conducted on intelligent path finding and emergency evacuation algorithms. In these studies, guidance methods are operated on a central control server based on real-time sensing data received from distributed sensor nodes. Another important aspect of evacuation is having effective rescue guidance in an emergency. However, there have been only a few studies for efficient rescue guidance schemes due to the high-level design of their framework. Therefore, this paper proposes a genetic algorithm-based emergency rescue guidance method using distributed wireless sensor networks that optimizes the path based on the received rescue resources. The performance evaluation through a computer simulation showed that the proposed scheme guarantees efficient path finding.
Keywords:
Rescue, Genetic algorithm, Emergency situation키워드:
구조, 유전 알고리즘, 재난상황1. 서 론
선박 재난 사고는 꾸준히 발생하고 있으며, 1911년 타이타닉호 침몰사고를 비롯하여 최근 우리나라에서도 2014년 세월호 침몰 사고가 있었다. 그 이후에도 2015년 나일강에서는 여객선 침몰로 20명 이상이 익사하는 사고가 발생하였다. 최근 들어 선박의 규모가 커지고 구조가 복잡해짐에 따라 많은 인원과 화물이 선박 내 제한된 공간에 탑승 및 적재되어, 사고 발생 시 상당한 인명 및 재산 피해가 발생할 수 있다.
국제 해사 기구(International Maritime Organization; IMO)에서는 이러한 선박 재난 사고에 대비하기 위해, 여객선 설계 시 비상 상황에서의 승객 탈출에 대한 규정인 Maritime Safety Committee / Circulation 1238 (IMO MSC / Circ. 1238)을 마련하고 있으며, IMO에서는 여객선 승객의 안전을 위해 이 규정을 만족할 것을 요구하고 있다[1]. 현재까지 이러한 IMO 규정을 만족하기 위한 많은 국내외 연구개발이 진행되어 왔으며, 선박 재난상황뿐만 아니라 일반적인 육상 재난상황에 대응하기 위한 다양한 기술들이 개발되어왔다.
재난상황에서의 적절한 대응을 위해, 경로탐색 및 최적화 알고리즘을 활용한 다양한 대피경로 탐색 및 유도 방안이 연구되었다. 이러한 대피경로 탐색 방안은 선박 및 건물 등 구조물 내부의 전체적인 상황 정보를 수집·활용하여 최적의 대피경로를 탐색하는 중앙집중적 방식과[2], 재난상황으로 인해 특정 지역이 고립될 경우에 대비하여 효과적인 대피경로를 제시하기 위한 분산적 대피경로 결정 방안이 제안되었다[3]. 하지만 지금까지 대피경로 탐색을 위한 많은 연구가 있어왔지만, 대피자들에 대한 효과적인 구조방안에 대한 최적화 연구는 거의 이루어지지 않아서, 주어진 시간 내에 최대한의 생존자 구조를 위한 구조자원의 효율적인 투입이나 구조자의 안전을 확보할 수 있는 방안이 제시되지 못하였다.
최근 본 연구진에서는 유전 알고리즘을 적용한 구조경로 탐색 방안에 대한 기초연구[4]를 수행하였으며, 이를 통해 유전 알고리즘 기반으로 구조경로를 효과적으로 최적화할 수 있음을 확인하였다. 하지만 선박 내 재난상황을 가정한 컴퓨터 시뮬레이션에서 구조경로가 최적화되지 못하는 예외상황이 관찰되어 이에 대한 보완이 필요하다. 아울러 구조경로의 최적화뿐만 아니라 구조자 인원수와 같은 구조자원 투입량의 최적화를 위한 방안이 보완되어야 실제 재난상황에 대한 적용이 가능할 것이다.
따라서 본 논문에서는 선박 내 재난상황을 가정한 상태에서 최적의 구조경로를 탐색하고 구조자원 투입량을 최적화할 수 있는 방안을 제안한다.
본 논문의 2장에서는 제안한 방식의 근간이 되는 유전 알고리즘에 대해 간단히 살펴본 후, 3장에서는 본 논문에서 제안하는 유전 알고리즘 기반의 구조 경로 탐색 및 구조자원투입 최적화 방안을 기술한다. 이후 4장에서 제안된 시스템에 대한 컴퓨터 시뮬레이션을 통한 성능 평가 결과를 살펴보고, 이후 5장에서 본 논문의 결론을 맺는다.
2. 유전 알고리즘
유전 알고리즘(Genetic Algorithm)은 생물의 진화과정, 즉 자연선택(natural selection)과 유전법칙을 모방한 확률적 탐색 기법으로, 생물의 진화과정을 추상화하여 인공시스템을 설계하고자 하는 알고리즘이다[5]. 문자열의 형태로 정의된 개체, 즉 해(solution)와 그 해들의 전체 집합에 해당하는 해집단에서의 교차(crossover) 및 돌연변이(mutation)와 같은 유전연산의 과정을 적용하고 적합도 평가를 통해 다음 세대에 생존할 개체를 선별하는 과정을 반복하여 최적의 해를 찾아가는 추상화된 방식으로 그 개념과 적용이 단순하고, 해의 탐색성능이 우수하여 다양한 분야의 최적화 또는 의사결정문제에 적용이 가능하다. 초기 모집단에 대한 적합도 평가에서부터 전체적인 유전 알고리즘의 흐름을 Figure 1에 도시하였다.
Procedure of genetic algorithm
특히 유전 알고리즘의 다양한 적용 분야 중, 조립 라인 밸런싱(Assembly Line Balancing: ALB) 문제는 조립 라인에 존재하는 작업장에서 이루어질 작업들을 부과된 제약조건을 준수하며 목적함수로 주어진 요구사항을 최적화하기 위하여 작업장에 할당하는 문제와 관련된다[5]. ALB 문제에서 주로 다루는 문제는, (1) 사이클 타임이 주어지고 작업장 수를 최소화하는 문제, (2) 작업장 수가 주어지고 사이클 타임을 최소화하는 문제, (3) 작업장 간 작업부하의 균등화 문제, (4) 작업 관련성의 최대화 문제이다[6]. 즉 문제 (1)과 (4)는 조립 라인에서 이루어질 작업들에 대한 작업 허용시간이 고정된 문제이고, 문제 (2)와 (3)은 조립 라인 내 작업장의 수가 고정된 문제이다. 본 논문에서 고려하는 선박 내 재난상황은 대피자가 분포한 공간, 즉 구조가 필요한 공간까지의 경로를 작업장으로 두고 사이클 타임 즉 구조 소요시간을 최소화하는 문제로 적용될 수 있으므로, 유전 알고리즘 기반 ALB 문제 해결의 과정으로 변환하여 진행한다. 물론 재난상황에서 선박 내 존재하는 잔여 산소량, 선박 침몰까지 예상시간 등 구조작업 완료시간에 대한 제약이 명확히 제시될 경우에는 문제 (1), (4)의 관점에서 최적화가 가능할 것이다.
3. 제안하는 방식
유전 알고리즘의 조립 라인 밸런싱 문제에 재난상황에서의 구조경로 최적화 문제를 대입하여 구조자 진입 및 구조경로의 최적화를 실시한 기존 연구결과[4]는 선박 내 재난상황을 가정한 컴퓨터 시뮬레이션에서 구조경로가 최적화되지 못하는 예외상황이 관찰되어 이에 대한 보완이 필요하다.
이 문제를 해결하기 위해 본 논문에서는 개체표현 관점에서의 보완을 통해 개체해석 과정에서의 문제를 해결하여 발견된 예외상황을 해결하였으며, 아울러 구조경로의 최적화뿐만 아니라 구조자 인원수와 같은 구조자원 투입량의 최적화를 위한 방안을 마련하여 실제 재난상황에서의 구조작업에 적용될 수 있도록 한다.
조립 라인 밸런싱 문제의 4 유형 중 문제 (2)의 관점에서 외곽 출입구 중심으로 구성된 구조경로를 작업장에 대입하고 사이클 타임, 즉 총 구조작업시간을 최소화하는 문제로 변환하여 Figure 2와 같이 유전 알고리즘을 적용한다.
Proposed procedure
3.1 개체표현
유전 알고리즘의 분할문제는 개체표현에 있어 순열표현 방식과 그룹번호표현 방식이 사용된다. 순열표현에서는 작업들이 할당되는 순서에 따라 개체를 나열하고, 그룹번호표현에서는 개체의 순서, 즉 위치는 각 작업번호를 나타내고 각 개체의 값은 작업장 번호를 나타낸다. 예를 들어, 각 개체의 배열을 프로그래밍 언어의 배열(a[i])로 표현할 경우, 순열표현에서는 a[i]가 각 작업, 즉 대피자가 위치한 공간을 의미하고, 그룹번호표현에서는 a[i]가 작업장, 즉 특정 탈출구를 중심으로 한 구조경로를 의미하고, (i+1)은 작업번호가 1부터 시작할 경우 각 작업을 의미한다.
순열표현 방식으로 구현된 방안[4]에서는 작업장에 할당되는 순서에 따라 작업을 나열하고, 개체해석[5]에 의해 나열된 작업들을 순서대로 각 작업장에 할당하였다. 이 때 개체해석에서는 총 작업량을 기준으로 균등하게 작업을 분할하는 경향을 띠므로, 본 논문에서 가정하는 재난상황을 적용할 경우 마지막 두 작업장에 할당된 작업이 합리적이지 못한 상황이 발생한다. 따라서 본 논문에서는 구조경로 최적화 방안에 대해 재난상황을 적용한 실용 설계를 위해 기존 적용된 순열표현 대신 그룹번호표현을 적용하고 이를 통해 기존 연구결과의 예외상황을 해결하고 아울러 표현된 개체를 작업장에 분할하는 개체해석 과정을 생략할 수 있도록 한다.
그리고 구조경로 최적화와 더불어 구조자원 투입량 최적화의 근거 마련을 위해 각 노드별 구조순서를 결정해야 한다. 따라서 그룹번호표현에서 배열의 인덱스(i+1)를 작업번호와 일치시키지 않고 배열의 인덱스와 작업번호를 랜덤하게 매핑한다.
3.2 개체선별(selection)
적응도 평가를 총 작업량, 즉 총 구조소요시간을 기준으로 실시하며, 그 결과를 근거로 개체선별을 실시하여 다음 세대에 생존할 개체를 선택한다. 조립 라인 밸런싱 문제와 같은 최소화 문제에서는 평가값의 척도를 재구성할 필요가 없으므로 토너먼트 크기 2의 토너먼트 선별 방식을 통해 개체선별을 진행한다.
개체표현과 마찬가지로 구조자원 투입 최적화를 위해 개체선별에 있어서도 별도의 고려가 필요하다. 이 경우 총 작업량이 차이나지 않는 경우가 발생할 수 있으므로, 총 작업량을 기준으로 적응도 평가를 실시하고, 그 결과들이 차이가 나지 않을 경우 작업량이 균등하게 할당되었는지를 기준으로 작업 할당의 우선순위를 둔다.
4. 성능 평가
4.1 시뮬레이션 환경 및 조건
컴퓨터 시뮬레이션을 통한 성능 평가를 위해 Table 1과 같은 파라미터를 사용한다. 대피자의 이동 평균 속도는 3 m/s, 인접한 결정 노드 간 거리는 2 m로 가정하고, 20명의 대피자는 가정한 시뮬레이션 공간의 각 노드 위치에 균일분포(uniform distribution)에 따라 존재하는 것으로 가정한다.
Parameters for computer simulation
시뮬레이션을 위한 환경 구성은 Figure 3과 같이 한국해양대학교 실습선 한바다호의 일부를 단순화하여 모델링하였고, 선박 내 각 센서노드는 재난상황에 대한 충분한 인지가 가능한 분포로 이동경로 상에 배치되었음을 가정한다. 일반적으로 재난상황에 대비한 센서노드는 이동경로의 갈림길과 선실 혹은 격실과 같은 대피자 주요 분포공간 그리고 이동경로 상에 등간격으로 분포하며[3], 본 논문에서는 이동경로에 등간격으로 배치함을 가정하였다. 그리고 ‘x’로 표시한 상하의 4개의 종단노드는 출구를 의미하여, 4개의 출구노드를 중심으로 구조경로, 즉 조립 라인 밸런싱 문제의 작업장이 구성된다.
Simulation environment
4.2 시뮬레이션 결과 및 성능 분석
100개의 크기를 갖는 초기 모집단을 구성하고 적응도평가와 유전연산을 통해 구조경로 최적화를 실시하였고, 적응도 개선이 없이 진행된 세대수를 기준으로 종료조건을 적용하여 Figure 4와 같은 상황(Case I-1)에서의 컴퓨터 시뮬레이션을 수행하였다.
Computer simulation results (Case I-1)
참고문헌 [4]와 같은 순열표현을 통한 재난상황에서의 시뮬레이션 결과 Figure 4 (a)와 같이 좌측 하단 출구에서의 비정상적 경로 선택이 발견되었고, 이러한 문제를 해결하기 위해 앞서 설명한 바와 같이 그룹번호표현을 적용하여 Figure 4 (b)와 같은 정상적인 구조경로 선택을 확인하였다.
총 작업량을 기준으로 Figure 4의 상황에 대한 적응도 평가를 실시한 결과를 Figure 5에 도시하였다. 알고리즘 동작에 의해 최소 적응도 52를 갖는 Figure 4 (b)와 같은 구조경로를 탐색하였고 그 결과 모든 작업장, 즉 구조경로에 고르게 구조지점이 분포함을 확인하였다.
Fitness evaluation results (Case I-1)
다른 지점에서 발생한 재난상황(Case II)을 가정하여 시뮬레이션한 결과 Figure 6과 같은 구조경로를 확인하였으며, 이 상황에 대한 적응도 평가를 실시한 결과를 Figure 7에 도시하였다. 알고리즘 동작에 의해 최소 적응도 56으로 Case I-1과 달라진 재난위치에 의해 다소 증가된 적응도가 관찰되었고, 작업장 즉 구조지점별 구조경로의 배정에 있어서도 재난상황을 고려하여 구조경로가 할당됨을 확인하였다.
Computer simulation results (Case II)
Fitness evaluation results (Case II)
구조자원 투입의 최적화를 위해 각 구조지점별로 구조대원이 투입되어 거쳐 가는 경로에 대한 최적화를 실시하였다. Figure 4와 같은 재난상황에서 컴퓨터 시뮬레이션을 수행한 결과는 Figure 8, Figure 9와 같다.
Computer simulation results (Case I-2)
Fitness evaluation results (Case I-2)
시뮬레이션 결과에서 나타난 것처럼, 제안된 알고리즘을 통해 실질적인 구조자원이 이동하는 경로를 탐색할 수 있으며, 각 구조지점별 구조대상 인원이나 현장의 상황이 사전 파악된다면 이동경로별 투입인원을 결정하고 최적화할 수 있다.
5. 결 론
본 논문에서는 재난상황에서 구조경로 최적화와 구조자원 투입 방안의 최적화를 위해 유전 알고리즘의 조립 라인 밸런싱 문제를 적용하는 방안을 제안하였다. 기존 연구 결과를 재난 상황에 적용한 결과 발생한 예외상황을 해결하기 위해 유전 알고리즘의 개체표현 방식을 변경하고, 구조자원 투입 방식의 최적화 관점에서의 검증을 수행하였다. 선내 재난상황을 단순화하여 모델링하고 이를 적용한 환경에서 컴퓨터 시뮬레이션을 실시하여 제안한 방식의 성능을 검증하였으며, 그 결과 구조경로 및 구조자원 투입의 최적화를 위해 적용할 수 있음을 확인하였다. 향후 본 기반연구를 토대로 상세한 재난상황의 모델링을 통해 구조경로 최적화 알고리즘을 구체화하고, 실제 선박환경에서의 실험을 통해 실효성을 보완할 것이다.
Acknowledgments
이 논문은 2016년도 정부(교육부)의 재원으로 한국연구재단의 지원을 받아 수행된 기초연구사업(No.2016R1D1A3B03934492)이며, (사)한국마린엔지니어링학회 2019년도 전기학술대회 포스터발표내용을 확장한 것입니다.
Author Contributions
The research presented in this paper was wholly contributed by the author.
References
- International Maritime Organization, Guide lines for evacuation analysis for new and existing passenger ship, IMO MSC/Circ1238, 2007.
- S. H. Ok, J. H. Ahn, S. H. Kang, and B. I. Moon, “A combined heuristic algorithm for preference-based shortest path search,” Journal of The Institute of Electronics Engineers of Korea, vol. 47, no. 8, pp. 74-84, 2010 (in Korean).
-
M. B. Kang, G. Park, S. H. Yim, and Y. I. Joo, “Design of optimal evacuation route guidance system for accidents on board the ship,” Proceedings of the 40th Korean Society of Marine Engineering Spring Conference, p. 158, 2016 (in Korean).
[https://doi.org/10.5916/jkosme.2016.40.9.824]
- Y. I. Joo, “Emergency rescue guidance scheme using wireless sensor networks,” Journal of the Korea Institute of Information and Communication Engineering, vol. 23, no. 10, 2019 (in Korean).
- Y. K. Kim, B. S. Yun, and S. B. Lee, Meta-Heuristic, YoungJi, 1997 (in Korean).
-
S. Ghosh and R. J. Gagnon, “A comprehensive literature reivew and anlysis of the design, balancing and scheduling of assembly systems,” International Journal of Production Research, vol. 27, no. 4, pp. 637-670, 1989.
[https://doi.org/10.1080/00207548908942574]
- D. E. Goldberg and R. Lingle, “Alleles, Loci, and the TSP,” Proceedings of the 1st International Conference on Genetic Altorithms, Lawrence Erlbaum Associates, Hillsdale, NJ, pp. 154-159, 1985.
- M. Herdy, “Application of the evolution strategy to discrete optimization problems,” Proceedings of the 1st International Conference on Parallel Problem Solving from Nature, Springer-Verlag, Lecture Notes in Computer Science 496, pp. 188-192, 1991.
- K. B. Kim, “Combining A* and genetic algorithm for efficient path search,” Journal of the Korea Institute of Information and Communication Engineering, vol. 22, no. 7, pp. 943-948, 2018 (in Korean).