양자 어닐링 기반 다중 밀집 사고 예방을 위한 보행자 네트워크 방향성 최적화

Quantum Guardian 팀
컴퓨터공학부

Abstract

군중 압착 사고는 좁은 도시 공간 내에서 서로 반대 방향으로 이동하는 조밀한 보행자 흐름이 한데 모일 때 발생하며, 이로 인해 개인의 이동성과 통제력이 상실될 수 있습니다. 본 연구는 보행자 네트워크를 위한 양자 어닐링(QA) 기반 방향성 최적화 프레임워크를 제안합니다. 보행자 네트워크는 가중치 그래프로 모델링되며, 최적화의 목적은 경로에 일방통행 방향을 할당하여 흐름 충돌을 줄이고 이동 효율성을 높이는 것입니다. 이를 위해 (i) 전역 연결성 유지를 위한 전처리, (ii) 이동 거리 단축을 위한 n-hop 기반 근사, (iii) 노드별 유량 보존 전략을 통합한 QUBO 모델을 정형화하였습니다. 실험 결과, 제안된 방법은 시뮬레이션 어닐링 대비 향상된 유량 안정성과 낮은 APSP 합계를 기록하였으며, 실제 양자 어닐러를 통한 검증 계획을 포함하고 있습니다.

1. 서론

이태원 참사와 같은 압사 사고는 좁은 공간 내에서 보행자 흐름의 '군중 유체화 현상'으로 인해 발생합니다. 특히 대향류(Opposing flows)의 충돌은 개인의 이동성을 상실시키고 정체를 유발하게 됩니다. 본 연구는 양방향 보행로를 최적의 단방향 네트워크로 전환하여 흐름의 충돌을 방지하고 전체 네트워크의 이동 효율성을 극대화하는 것을 목적으로 합니다.

2. 수학적 문제 정의

2.1 그래프 표현 및 결정 변수

보행자 네트워크를 무방향 그래프 $G = (V, E)$로 정의합니다. 각 간선의 방향을 결정하기 위해 $i < j$인 모든 간선 $(i, j) \in E$에 대해 이진 변수 $x_{ij} \in {0, 1}$를 정의합니다. $x_{ij}=0$은 $i \to j$, $x_{ij}=1$은 $j \to i$ 방향을 의미합니다.

특정 방향 흐름 $i \to j$의 존재 여부를 나타내는 지표 함수:

$$ I_{i \to j} = \begin{cases} 1 - x_{ij}, & i < j \newline x_{ji}, & i > j \end{cases} $$

3. 연결성 유지를 위한 전처리 (Preprocessing)

도로망 그래프의 연결성을 보장하기 위해 평면 임베딩과 face 구조를 활용합니다.

biconnected 구성
bridge / cut vertex 제거

교대 방향 배정(alternating orientation)을 통해 전역 연결성을 보장합니다.

이 조건은 dual graph가 bipartite일 때 성립합니다.

홀수 face 존재 시 최소 T-join 계산:

완전 매칭 문제로 환원
Blossom 알고리즘 사용[^1][^2]

4. QUBO 목적 함수 설계

$$ H_{total} = \alpha H_{flow} + \beta H_{dist} $$

4.1 유량 보존

$$ H_{flow} = \sum_{v \in V} \left( \sum_{u \in adj(v)} (2I_{v\to u}-1) \right)^2 $$

4.2 거리 항

n-hop 기반 근사 사용

Figures

음의 상관관계 기반 정의:

$$ H_{dist} = \sum_{\forall e_{ik}, e_{kj}}(I_{i\to k} I_{k\to j}) + \sum_{\forall e_{ij}, e_{jk}, e_{kl}}(I_{i\to j} I_{j\to k} I_{k\to l}) $$

5. 구현 및 실험

5.1 차수 감소

dimod.make_quadratic 사용
Rosenberg 방식 기반[^3]

5.2 성능 평가

Case 1

유형	최소 APSP	평균 APSP	평균 Σ(In-Out)^2	시간
MR2S	34	34.00	4.00	224.26
Raw	34	34.00	4.00	205.41
BF	34	34.00	4.00	103.12

Case 2

유형	최소 APSP	평균 APSP	평균 Σ(In-Out)^2	시간
MR2S	206	207.50	6.00	389.75
Raw	206	209.00	6.40	560.96

Case 3

유형	최소 APSP	평균 APSP	평균 Σ(In-Out)^2	시간
MR2S	1094	1094.00	8.00	421.91
Raw	1083	1100.20	9.20	1324.08

6. 결론

본 연구는 보행자 안전 문제를 QA로 정형화하여 동선 최적화 가능성을 제시합니다.

References

[^1]: Edmonds (1965) Paths, Trees, and Flowers
[^2]: Edmonds & Johnson (1973) Matching, Euler Tours
[^3]: Glover et al. (2018) QUBO tutorial
[^4]: Kadowaki & Nishimori (1998) Quantum Annealing