SS 研HPC フォーラム2017 「計算科学の新たな可能性」
パネルディスカッション「HPC の社会シミュレーションへの展開」
2017 年8 月30 日汐留シティセンター

マルチエージェントシステムを利用した
群集避難シミュレーション
堀 宗朗
東京大学地震研究所

群集避難の円滑化・効率化
対応手段が限られている津波災害
 避難経路の設定：出発地−目的地
 避難所の設定：津波シェルタ・垂直避難 避難経路の確保：揺れに備える耐震補強

円滑・効率化のための数値解析
 常時とは異なるかもしれない人の行動 徒歩の避難経路も含む精緻な避難経路

MASを利用した群集避難シミュレーション
 高度なエージェント
 精緻な避難経路ネットワーク

MUTL-AGENT SYSTEM (MAS) Agent
 Have functionalities to see, think and act
 Agents with different abilities, roles and information
residents, visitors, officials and cars

agent
see

GIS data

think

move

1x1m grid size

 Environment Hybrid model of grid and topological graph Grid is automatically generated from GIS data

grid modelNAVIGATION
Radar like scanning of the grid, to identify
the visual boundary and extract information• agents autonomously navigate• residents agent know the path to thedestination, defined with a few points ofthe graph• visitor agents either look for elevatedgrounds or follow group of agents

resident agent (pre-defined path)

50m

visitor agent (no pre-defined path)

NAVIAGATION

damaged environment

undamaged environment

ENVIRONMENTS
Dual Modeling of Road Network

2 lanesgraph (node and link)
for agent thinking

grid (physical space) for
agent movement

HPC RELATED ISSUES OF MAS
Improvement of Serial Algorithms
 Path findings with hierarchical graph Acceleration of visionImprovement of Parallel Algorithms
 Hybrid parallel algorithm of MPI & OpenMP Extension from homogeneous agents to heterogeneous agentsOptimization of Evacuation Route Planning Use of parallel GA

UTLIZATION OF MAS
recognition

extraction

1. set scenario
2. compute evacuation process
3. estimate congestion causes

1. change setting of possible cause
2. compare evacuation process
3. identify congestion cause

complete ratio

complete ratio

no interaction
interaction

congestion off
congestion peakafter

beforecongestion disappear

congestion on
time

time

PROBLEM SETTING
1
4

1
4

1

2
5

4

2 4
3 6 5

3

3
5

residence

vehicle

firm

hill

originpark

destination
Characteristics:• 5 kinds of evacuee• 5 areas & 1 firm of origin• 10 destinations

2

1

RESULTS

time [min]1

residence/walk63

2

residence/vehicle

127

3

vehicle/stop-by

127

4vehicle/passing

103

5group/firm/walk

42

walk
50
analysis
ideal
0

0

60
time [min]

120

100

complete ratio [%]typecomplete ratio [%]100

65 min50

vehicleanalysis

0

ideal
0

60
time [min]120

PATTERN

walk
vehiclecolor for origin

PATTERN

density

speed

RECOGNITION
complete rate [%]
100

1

1

50

0

A1

sparse
dense

A2

A3

fast
slow

A4

A5

O1

O4

O5

5

congestion

area Adensity

Congestion takes place in Area A, 20 min after earthquake
Cause of congestion: vehicle concentration

O5

EXTRACTION: CASE 1• Cause of congestion
vehicle concentration• Countermeasure
Change vehicle pathO5

original path100

complete rate [%]area A

congestion disappear
50

ideal
initial setting
improvement00

new path

60
time [min]120COMPARISON: CASE 1
area Ainitial setting

O5

new path

improved setting

PATH FINDINGS WITH HIERACHICAL GRAPH
Real-time path finding is a bottleneck in dynamically changing
environment.
Pathfinding with two level hierarchical graphs solves this bottleneck.
 Automatic generation of crude graph from fine graph Translation of path finding queries of crude graph to those of fine graphcrude graphfine graphComparison of run time for 1000 random paths# Nodes# Links

Run time

Embedded graph (fine)352,371484,81437.31 sTopological graph (crude)

29,282

66,3402.24 s

94% reduction

ACCELERATION OF VISION 1/3
Agent’s location

6

8

7
×

1

×
×

2

9
×
×

3

10
×
×

4

11
×
×

5

Origins of 3x3 set of ray tracing templates

Vision is agent’s functionality of most time consuming process
Even with precomputed ray tracing, 80% of runtime is consumed by vision Excessive main memory access due to bloated C++ objects of sub grid and radar
templates Significant cache misses due to highly random memory accessACCELERATION OF VISION 2/3
6

7

8

9

10

0

1

2

3

4

D
C

11

B5
A

Implementation of new algorithm which reuses data of alreadyaccessed grid cells
 Use hash table to efficiently relate ray ID’s and cell indices Reduction of vision: 80% → 20% of total run timeRefactoring data structures so that absolutely minimum datarequired for vision can be isolated to a contiguous memory segment
 Improvement of cache friendliness of algorithm Reduction of vision: 20% → 10% of total run time

ACCELERATION OF VISION 3/3
cell access

Before path hashing
Instruction commit

L2 cache access

After path hashing
Other (No instruction commit)

Memory access

OLD
PATH HASHING
PH + SECTOR
PH + REFACTOR
0

0.5

1

1.5

2

2.5

3

3.5

8 core SPARC64 VIIIfx with 6MB shared L2 cache4

AGENT HETEROGENEITY
Agent Interaction
 Pedestrian-Pedestrian, Pedestrian-Car, Car-Car
 Agent-Environment (road side for narrow road)Agent heterogeneity increases complexity of interaction
inter-agent interaction:
P-P < {P-P, P-C, C-C}
agent-evnvironment interaction: P-E < {P-E, C-E}

Agent heterogeneity results in loss of numerical efficiency
 MAS tuned for homogeneous agent shows good scalability for setting of
homogeneous agents
 MAS tuned for homogeneous agent looses scalability for setting ofheterogeneous agents

HOMOGENEOUS AGENT
Problem setting
 Simple pedestrian agents with almost homogeneous actions
 Number of agents : 2,000,000
 Number of steps : 400 (80 seconds)

Excellent scalability with simple and homogeneous pedestrian agents

Strong scalability with flat MPI in K-computer
CPU cores (nodes)

runtimeStrong scalability

512 (64)

1814.318 s

1024 (128)965.242 s

94.0 %

2048 (256)495.2311 s

97.5 %

Strong scalability with OpenMP

HETEROGENEOUS AGENT
std::vector<pedestrian>+
5m overlapping

Interaction
p: pedestrianc: care: environment

std::vector<pedestrian>+
std::vector<car>+
30m overlapping

light p-p, p-a

re-partioning

heavy p-p, p-eheavy p-p, p-c, p-e, c-e

BREAK-DOWN
explicit synchronizations
migrations

MPI activities
1. At every 200 iterations, dynamic load balancing, which is heavy MPI work and is improved withMPI+MPI or MPI+OpenMP hybrid parallelism
2. At every 20 iterations, agent migration, which involves several complicated MPI operations
3. At each time step, transfer of agent states inside overlapping layer
Right after item #1, fluctuations are small. Each item#2 moves some agents, making MPI-ranks work
longer. Item #3 constantly needs communication within a shared memory node/core.

EVACUATION ROUTE PLANNING
original routedamaged: evacuation hinge

earthquake

Need for optimum route after earthquake damage

Use of GA
1. Mutations to GA individuals
are applied for fastest route
2. Populations of GA
individuals are spawned inparallel
3. Fitness of each individual isevaluatedshortest route
alternative route

Mitigation Search Results

Introspection Resultsroute unchangeroute change

おわりに津波避難の円滑・効率化のための数値解析
 MAS
相応に高度なエージェント
相応に精緻な避難経路ネットワーク

高性能計算の必要性
 エージェントの高度化
 多数ケース

津波避難は徒歩が原則の現在，自動車の利用を認めることができるか？
認めるとすれば，「誰がどのように使うのか」もしくは「使えないのは誰か」という問いにどう答えるか？