본 논문에서는 실내 재난현장에서 다수의 요구조자를 구출하기 위한 경로계획 시스템을 고려한다. 화재현장에서 경로계획 문제는 일반적인 경로계획 문제와는 다른 요구조건들을 고려해야 한다. 빠른 구조 및 회피를 위해 경로 길이가 중요한 요소이며, 화재로 인해 건물 내부 환경이 빠르게 변화할 수 있다는 특성이 있다. 본 연구에서는 이러한 요소들을 고려한 경로계획 시스템을 개발하며, 지도생성, 지도전처리, 그래프 형성 및 축소, 방문순서 결정, 그리고 경로생성 및 후처리 단계가 포함된다. 지도생성 단계에서는 건물 내부를 격자 형태로 변환하고, 지도전처리 단계에서는 위험 영역을 제거한다. 그래프 형성 및 축소 단계에서는 격자에 나타난 정보를 가중치 그래프로 변환하며, 이 과정에서 두 지점을 잇는 경로의 길이로 가중치를 설정한다. 경로계획에는 A*, RRT, RRT*, PRM-A* 알고리즘을 고 려하였다. 방문순서 결정 단계에서는 모든 요구조자를 방문하고 회피하는 경로 길이가 최소가 되도록 방문순서를 결정한다. 끝으로 경로생성 및 후처리단계에서는 결정된 순서에 의해 지도에 경로를 생 성하며, 경로의 특성을 개선하는 후처리를 한다. 제안된 경로계획 시스템의 성능을 검증하기 위해 수치 시뮬레이션을 수행하였다.

Development of an Indoor Path Planning System for Search and Rescue Operations of the Firefighters

Heein Park, Jihoon Lee, Youdan Kim*, Chan Gook Park, Jae Hong Lee

An indoor path planning system for search and rescue operations of the firefighters is considered. Path planning inside a building where the fire occurred requires additional considerations compared to the general indoor path planning problem. For example, mission time performing search and rescue is the main factor to be considered, and the indoor spaces of the building might change rapidly due to the fire. The proposed indoor path planning system consists of five steps; i) map generation, ii) map processing, iii) graph generation and reduction, iv) order determination, and v) path generation and processing. In the map generation step, the map of the building is transformed into grids. In the map processing step, unreachable zones are excluded. In the graph generation and reduction step, the information given in grids is transformed into a weighted graph, where the weights of each edge are determined by the length of the path connecting the nodes. To generate the path, four algorithms are considered; A*, RRT, RRT*, and PRM-A*. In the order determination step, the order for rescue is determined by minimizing the length of the path. Finally, in the path generation and processing step, the actual path satisfying the order specified in the order determination step is generated, and the path is processed. Numerical simulation is performed to demonstrate the effectiveness of the proposed algorithm.

Keywords: path planning, optimization, indoor navigation

Speaker 박희인 서울대학교