DBPIA-NURIMEDIA

Size: px

Start display at page:

Download "DBPIA-NURIMEDIA"

현택 신
4 years ago
Views:

1 76 한국공간정보시스템학회논문지 : 제 12 권제 1 호 ( ) 개선된 Floor Field 기반보행시뮬레이션모델 (An Enhanced Floor Field based Pedestrian Simulation Model) 전철민 (Chulmin Jun) 요약실내공간과같이마이크로한스케일에서의분석을위해다양한보행시뮬레이션모델들이연구되어왔으며, 이중에는 social force 모델과 floor field 모델이주목을받는다. 이중연산이복잡한 social force 모델보다는 CA 기반의 floor field 모델이컴퓨터시뮬레이션에더적합한모델이라고할수있다. 그러나 Kirchner 등이제안한 floor field 모델에서는 dynamic field 의연산시자신의 dynamic 값에도영향을받을수밖에없는단점을가지고있으며, 본연구에서는이를개선한알고리즘을제안한다. 본연구에서는 dynamic field 의데이터구조를변경함으로써자신의 dynamic 값은배제한다른에이젼트의영향만을받도록하였으며, dynamic 값의초기값을할당하는문제도현실적으로변경하였다. 본연구에서제시된알고리즘을테스트하는데에는공간 DBMS 에저장된실제 3 차원건물모델을사용하여추후실내센서를이용한실시간대피시스템에적용할수있는기반이되도록하였다. 키워드 : 보행시뮬레이션, floor field 모델, CA, multi-agent 시뮬레이션, 실내공간모델 Abstract Many pedestrian simulation models for micro-scale spaces as building indoor areas have been proposed for the last decade and two models social force model and floor field model are getting attention. Among these, CA-based floor field model is viewed more favourable for computer simulations than computationally complex social force model. However, Kirchner s floor field model has limitations in capturing the differences in dynamic values of different agents and this study proposes an enhanced algorithm. This study improved the floor field model in order for an agent to be able to exclude the influences of its own dynamic values by changing the data structure, and, also modified the initial dynamic value problem in order to fit more realistic environment. In the simulations, real 3D building data stored in a spatial DBMS were used considering future integration with indoor localization sensors and real time applications. Keywords : Pedestrian simulation, Floor field model, CA, Multi-agent simulation, Indoor spatial model 1. 서론실내공간에서의화재대피나건축물안전진단과같은분석을위해다양한보행시뮬레이션모델들이연구되어왔다 [1]. Node-link 구조를이용한 way-finding 방식의매크로한스케이일의연구도있으나, 실내공간과같이마이크로한스케일에서의각에이전트들의동적인특성을모델링하는데에는 social force model[2, 3] 과 floor field model[4, 5] 이최근주목을받고있다. Helbing 등에의해제시된 social force 모델은엄격한수학적모델에근거하여공간내의개체들간의역학적인힘을표현하였으나연산과정이매우복잡하고보행자를동질화시킨다는단점을가지고있다 [6, 7]. 이에반해서 Kirchner 등에의해제시된 floor field 모델은 cellular 구조를이용하고인접셀들에대한작용만으로연산과정을단순화시켰음에도불구하고 social force 모델과유사한결과를보여서컴퓨터시뮬레이션에유리한모델로 주목받는다 [7, 8]. Floor field 모델은두개의 field(static field와 dynamic field) 를이용하여 social force 모델의역학적인특성을 cellular automata 기반의이동규칙으로변화시킨다. 이두개의 field 중 dynamic field는생물학의주화성 (chemotaxis) 과유사한특성을나타내며종종개미가짝짓기때분비하는페로몬 (pheromone) 에비유된다 [7, 10]. Kirchner 등이제시한연구에서는이값이다른에이젼트로향해서움직이는성향을나타내며, static field 값과의상대적인크기에따라그강도가달라지게된다 [7, 8, 10]. 본연구에서는이 dynamic field에주목한다. 에이젼트들이움직이면서자신들의주변에 dynamic field 값을남기게되고, 다른에이젼트들이이값을참조하여주변에이젼트들로의이끌림을형성하게된다. 그러나이전의연구에서는 dynamic field 값을셀에할당할때나이값을참조할때어떤에이젼트자신이남긴값과다른에 이논문은 2008 년도서울시립대학교교내학술연구비에의하여연구되었습니다. ** 서울시립대학교공간정보공학과교수, cmjun@uos.ac.kr( 교신저자 ) 논문접수 : 수정일 : 심사완료 :

2 개선된 Floor Field 기반보행시뮬레이션모델 77 이젼트의값을구분하지않는다는점과, dynamic 값의초기화시 static 값과의균형을맞추지않는다는단점이있었다. 이때단일공간에서는큰문제가없으나실내공간이분할되어있고좁은입구를통과할때는경우에따라흐름이중단되어버리는문제가있다는것이발견되었다. 본연구에서는이러한 dynamic field의연산문제가해결된, 보다개선된 floor field 기반의보행시뮬레이션모델을제시한다. 본연구에서는 <key, value> 쌍의컬렉션 (C# 의 dictionary) 데이터구조를이용하여각에이젼트의 dynamic value를구분하여저장하였으며, dynamic value의초기값을할당하는문제에서도보다현실적으로개선하였다. 본연구에서제시된알고리즘을테스트하는데에는공간데이터베이스에저장된실제 3 차원건물모델을사용하여추후실내센서를이용한실시간대피시스템에적용할수있는기반이되도록하였다. 개체 ( 보행자및기타물리적환경 ) 와의다대다관계에대해모델을하고몇겹의편미분방정식을풀어야하며알고리즘복잡도로서는 O(n 2 ) 의복잡도를갖는다. 이는많은에이젼트를이용한컴퓨터시뮬레이션을매우불리하게만드는요소가된다 [6, 7, 8]. Helbing의 social force 모델에대한자세한이론은그의연구를참고하기바란다. 2. 관련연구대피관련모델은화재, 교통, 건축등다양한학문적영역에서연구되어왔으며서로다른문제영역과목적을위해연구되었다. 이들은대체로매크로와마이크로한모델로나누어볼수있다 [11]. 매크로모델들은보통 network flow나 traffic assignment 문제들에적용된연구들에서나타나며, 최적화접근방법을사용하고데이터구조로는 node-link 기반의 graph 구조를사용한다 [12, 13, 14, 15]. 그들은보행자들을 node나 link에할당할수있는동질한 (homogeneous) 그룹으로간주하며, 이동중개인간의상호작용은고려하지않는다. 그러나보행자들이자기자신들간또는물리적인환경과의작용 ( 예 : Jamming, lane formation, oscillation 등 ) 이보행흐름에영향을미치게되며실내공간과같은공간을분석하기위해서는매크로한접근방법은적절치않다. 마이크로모델들은개개보행자들의움직임과그들이다른보행자나물리적인환경 ( 벽이나장애물과같은 ) 과어떻게상호작용을하는지에중점을둔다. 이모델들은대체로시뮬레이션방법을사용하며시뮬레이션을위한기반데이터형식으로는대상공간을세분한그리드셀을사용한다. 이들모델들은건축디자인과같은영역에서화재와같은비상시건축구조가사람들의움직임에미치는영향을분석하는데흔히사용되어왔다. 지난수십년간다양한마이크로시뮬레이션모델들이연구되어왔는데 [16], 대체로두가지모델, 즉, social force model과 floor field model이주목을받는다 [5]. 전자는주로 Helbing과그의동료들에의해연구되었으며 [2, 3], 에이젼트가목적지 ( 예를들어출구 ) 를찾아가는과정을계산하는데매우엄격한수학적인모델을사용한다. Helbing의모델은각에이젼트가공간내의다른모든에이젼트들및물리적환경과의작용을고려한다. 즉, 인접한에이젼트뿐아니라원거리 (long-range) 의모든 그림 1. Helbing 의 social force model 개념최근에는마이크로보행시뮬레이션의기반으로서 cellular automata를이용하는경향이증가하고있다 [17, 18]. Kirchner와그의동료들은 CA 기반의 floor field 모델을제시하였다 [5]. 이모델은 Helbing 등의연구에서의에이젼트간의원거리상호작용 (long-range interaction) 을로컬상호작용으로해석하여변환하는데에 static field와 dynamic field라는두가지 field를사용한다. 이렇게로컬작용만을고려하는데도불구하고, 결과로나타나는 global한현상은 social force 모델에서보여주는특징들, 즉, lane formation, oscillations at bottlenecks, faster-is-slower effects 등을그대로보여준다. Floor field 모델은그리드셀을기반데이터구조로이용하며, Helbing 연구와같이모든에이젼트의다대다의계산이아닌, 에이젼트의인접한셀들중다음시간단계에서의에이젼트들의움직임만을계산하므로컴퓨터시뮬레이션에적용하는데에매우효과적이다. 본연구에서는 floor field 모델을기반모델로하여이모델에서사용하는 dynamic field의연산과정을개선한알고리즘을제시한다. 이에대해서는다음에소개된다. 3. Floor Field 모델과 Dynamic field 의개선 3.1 Floor Field 모델에서의두가지 field 본연구에서는새로운 CA기반모델을개발하는대신, 앞에서소개한 Kirchner 등이제시한 floor field 모델 [5, 10] 을기반으로하여이를개선하고자한다. 이들이제시한 floor field 모델은앞서소개한여러가지보행자들의특성을적절히반영한다는것으로보고되고있으며, 연산면에서도우수한것으로평가되고있다. 먼저 floor field 모델의기본적인이론을소개하고본연구에서개선한

3 78 한국공간정보시스템학회논문지 : 제 12 권제 1 호 ( ) 부분을제시하고자한다. Floor field model은기본적으로 multi-agent 기반의시뮬레이션모델이라고할수있다. 보행자하나하나는환경이나다른보행자와상호작용을하는에이젼트이다. 이렇게에이젼트들은다수가모여 multi-agentsystem (MAS) 을이룬다. Multi-agent 시스템에서의각에이젼트들은다음과같은특징이있다 [19]. Autonomy: 자율적이다. 스스로다른에이젼트나환경에대해인지하고반응 ( 움직이거나정지 ) 한다. Local view: 어떤에이젼트도전체시스템에대한 global한지식이없다. 즉, 각에이젼트가출구를향해어떻게움직일것인가에대한전역적인룰이있는것이아니라로컬한룰만으로움직인다. Decentralization: 모든에이젼트들이동등하며어느에이젼트도조정을하지않는다 [20]. MAS에서이러한에이젼트의특징은종종 cellular automata (CA) 기반의시뮬레이션모델을써서구현되며, Kirchner의모델도 CA 기반으로되어있다. CA에대해서는다수의문헌에소개되고있으므로여기에서는생략한다. Kirchner 모델의기본적인데이터구조는그리드셀이며, 각셀은에이젼트가움직이는위치이면서값 (value) 을저장하는데이터구조이다. 이값은두개의레이어로분류하는데, 하나는 static field이고다른하나는 dynamic field이다. Static field는출구로부터각 cell까지의최단거리를가지는 field이다. 각에이젼트는자기와인접된 cell의static field 값으로서출구로의최단방향을알게된다. Static field는출구로부터거리라는고정된 (static) 값을가지는반면, dynamic field는각에이젼트의움직임에따라달라지는값을나타낸다. Dynamic field는개미가짝짓기를할때분비하는페로몬 (pheromone) 과같이 [3] 각에이젼트가자신의영향권을확산 (diffuse) 하고소멸 (decay) 시키면서움직인다. 한에이젼트는근처의다른에이젼트의위치는모르면서도에이젼트가남긴 dynamic value를참고하여그방향으로따라가려는성향을갖게된다. 에이젼트의 static과 dynamic field에대한반응정도를변경함으로써다양한시뮬레이션이가능하게된다. 예를들어, dynamic field 에대한민감도를높임으로써공포 (panic) 상황에서다른사람을무조건따라가는행동을실험할수도있다. 3.2 Floor field 모델의 Update rule Floor field 모델에서각에이젼트는 cell에부여된점수 (score) 에따라동시에움직인다. Cell에부여된점수는곧그곳으로의유인력 (attraction) 또는이동가능성을나타내며, cell i의점수는다음과같이정의된다 [8]. Score(i) = exp(k dd i) exp(k ss i) ξ i η i (1) 여기에서, D i: 셀 i의 dynamic field 값 S i: 셀 i의 static field 값 k d,, k s: 에이젼트가 D i 또는 S i 값중어느쪽에더민감하게반응할지를조정하는조정계수 ξ i: 이동할인접셀의벽, 장애물과같은물리적요인을나타냄. 1인경우이동가능하며 0인경우이동불가함 η i: 인접셀의다른보행자의점유상태를나타냄. 1인경우이동가능하며 0인경우이동불가함 한에이전트의 cell-i에서인접된셀 (j) 로의움직임은다음과같은 p ij 확률값으로결정하며, 이는모든아홉개 cell에대한 Score(i) 의 normalized된값이다. 하지만 score(i) 나 p(i) 는인접한아홉 cell에대해서는항상서로비례하므로어떤것을사용하던동일한효과를보인다. P ij = Score(j)( a N(i)Score(a)) -1 (2) 출구로부터거리를기반으로한 static field가먼저결정된다. 이는 Dijkstra나 A* 알고리즘과같은최단거리알고리즘을사용하는것으로해결할수있다. 다음으로는모든에이젼트들이자신이움직여갈 cell을결정하게되며, 그후공간내의에이젼트들이동시에움직이게된다. 이과정은그림 2와같이수도코드 (pseudocode) 로나타낼수있다. O = Φ // Set the open list to empty set P(i) = null // Set the parent node of the beginning node to null s(i) = 0 // Set the score of the beginning node to 0 O = (b) // Add the beginning node to the open list d(b) = 0 // Set the dynamic value of i to 0 i = b // Set i to b While (i E) // Iterate while node-i is not the destination node // Choose the maximum score node among the open list. Let i O be a node for which p(i) = min s(i) : i O and s(i) > 0 // If the agent- i has moved to a node other than itself if( i P(i) ) // increase the dynamic value of the previous node by one d(p(i)) = d(p(i)) + 1 for each ( p(i), j ) A(p(i)) // j: Available adjacent nodes of p(i) // define the dynamic diffuse amount of j // as the α-portion of the dynamic value of the previous // node divided by the number of the adjacent nodes d diff = α*d(p(i))/n (A(p(i))) d(j) = d(j) + d diff // to decay, the previous node discards β portion // of the dynamic value d(p(i)) = d(p(i)) - β*d(p(i)) O = Φ // Reset the open list to empty set // For each of searchable adjacent nodes of i (i.e. including // i and excluding those obstacles as walls and furniture) // set parent, and add to the open list for each (i, j) A(i) // j: Adjacent nodes of i including i // If not in the open list, add j to it if j O then O = O (j) P(j) = i // Set the parent node of j to i 그림 2. Floor field 모델에서의에이젼트의움직임을나타내는 pseudocode

4 개선된 Floor Field 기반보행시뮬레이션모델 79 D i D i + 1 그림 3. Dynamic value 의 diffuse & decay 그림 2의 pseudocode와그림 3에나타낸바와같이에이젼트가어떤셀에서다른셀로움직인후에는원래의셀 i의 dynamic value를 1만큼증가시킨다 [4, 10]. 그다음에는그셀의 dynamic value를인접셀로일정부분 (α) 나누어서인접셀들의 dynamic 값들에더한다. 다음으로는 Di의값을일정부분 (β) 감소시키게된다. 이는마치개미가움직이면서자신의냄새를확산시킨후점차묽어져서사라질때까지흔적을길게남기는효과를준다. 에이젼트들은이와같은dynamic 값을 static값과더불어함께참조한다. 이두개의값중에더강한값에움직이는확률을높이기위해위에서언급한 scaling factor(k d 와 k s) 를사용한다. 이두 factor의비율, k d/k s 은공포감 (panic) 의강도로해석된다. 즉, 이비율이클수록한에이젼트가다른에이젼트로향하는정도가강하게된다. 4. Dynamic field의개선 4.1 Dynamic field 저장구조의개선 Kircher 등 [5] 의 floor field 모델에서의 dynamic field 는인접셀만이아닌 Helbing 모델에서의원거리 (longrange) 의에이젼트들에대한영향을포함시킬수있는효과적인수단이라고할수있다. 그러나위와같이 dynamic 값을정하게되면어떤셀의 dynamic 값은자신이남긴값과다른에이젼트들이남긴값들이섞여서더해지게되는문제가있다. 개미의페로몬 (pheromone) 과같이다른에이젼트들의영향에반응하여그쪽으로의인력을작용시키기위해서는자신의영향을배제해야하는것이당연하다. 왜냐하면자신의냄새에반응하지는않을것이기때문이다. 하지만 Kirchner의모델에서는자신과다른에이젼트의 dynamic 값을구분하지않고자신의 dynamic 값을다른에이젼트의값에누적해서더하는방식을쓰고있다. 이렇게되면, 어떤에이젼트가한방향으로만움직이게된다면문제가없지만, 그림 4와같이제자리로돌아오는등의움직임이발생했을때는결국자신이남긴 dynamic value의영향을받을수밖에없게된다. 이는셀별로에이젼트들의 dynamic 값을구분하지않아서생기는문제이다. 그림 5에서는이를간단한숫자를이용하여예시하였다. 여기에서는예시를단순화시키기위해 static 값은배제하였고, diffuse와 decay 계수를모두 0.1로하였다. 본연구에서는 dynamic field를자신의영향을제거한페로몬효과를부여할수있도록개선시켰다. 이를위해 그림 4. 자신의 dynamic value 에영향을받는문제 A 6 B (a) (b) (c) A:0.1 A:0.1 A: A:0.1 A:0.9 A: A:0.1 A:0.1 A: A:0.1 A:0.1 A: B:0.11 B: A: A B 0.99 B: A:0.1 A:0.1 A: B:0.11 B:0.11 (d) (e) (f) 그림 5. 자신의 dynamic value에영향을받는문제의예시 ((a) Agent A와 B가그림과같이이동. (b) 이동후 5위치에 D값이 1증가하고 α 만큼씩 diffuse( 이전 D값은없고 α= β=0.1이라고가정함 ) (c) 5셀의 D는 β만큼 decay (d) Agent B도동일하게 diffuse & decay함 (e) 움직임이끝난후최종 D값 (f) Agent B가 2셀을택했고, 또다른제3의 Agent가 8셀을택했을경우를가정하면, Agent A는 1 또는 2번셀을택할수밖에없음 ) 서는각셀에서에이젼트마다의 dynamic value를보관하는구조를가져야한다. 이때셀 k에서의에이젼트 p 의 dynamic value는 d(p, k) 라고하고이들값의집합을 D(k) 라고한다. D(k) = d(p, k) : p=1, 2,, n (3) 여기에서 n은셀 k에 dynamic이유지되고있는에이젼트의개수이다. 식 (3) 에서 D(k) 를유지하기위해모든셀이모든에이젼트에대해값을유지하는 O(n 2 ) 의복잡도를가진다고생각하기쉬우나, 실제로는움직임과정중셀 k에 dynamic 값의영향을준에이젼트들의리스트만유지하므로각셀은매우적은개수의값들만유지하게되어, 연산과정에도무리가없게된다. 실제로구현시에는.NET의 Dictionary 라는데이터구조를이용했는데, Dictionary는 (key, value) 쌍으로된리스트이다. 여기에서 key는에이젼트 p를의미하고 value는 dynamic value가된다. 이때, d(p, k) 는 p 에이젼트자신의 dynamic value 중항상최대값하나로만유지하도록한다. 개미주변에초기에가장강한 pheromone이발생한다고한다면, 위치

5 80 한국공간정보시스템학회논문지 : 제 12 권제 1 호 ( ) 를옮겨감에따라원래위치의 pheromone이약해져가다가도다시그위치로돌아올때강한 pheromone이다시발생하는것과같은원리라고할수있겠다. d(p, k) = maxd(p, k): p=1, 2,, m (4) 여기에서 m은에이젼트 p가 cell k에 dynamic 값을남긴회수이다. 실제로구현시에는자신의 m개의값을보관하는것이아니라항상최대값으로 update되도록한다. 또한 score(k) 를계산할때는 D(k) 중에이젼트 q 자신의값은제외한값중최대값을취해서자신의 dynamic 값에영향을받지않도록한다. D(k) q = maxd(p, k): p q (5) D(k) = d(p, k) : p=1, 2,, n i i-1 dmax dmax dmax dmax dmax dmax dmax dmax if d(p, k) D(k) then D(k) = D(k) d(p, k) where k is an adjacent cell of i, d(p, k) = dmax d(p,r) = d(p,r)? 1 where r is an adjacent cell of i-1 (a) (b) (c) 그림 6. Cell k 의 dynamic 값의리스트 (a), 에이젼트의움직임 (b), 움직임후의 dmax 값의할당 (diffusion) 및이전셀들의쇄퇴 (decay) 과정 (c) 4.2 Dynamic field 초기값연산의개선 본연구에서는에이젼트 p가움직였을때초기의 p의 dynamic value 값을정하는방법도 Kirchner의모델과는다른방법을사용했다. 그림 6-(c) 를보면, 에이젼트가움직였을때가장강한 dynamic value를인접셀에할당하고이전셀에서에이젼트 p가가지고있는 dynamic 값들을 1씩줄인다. 그림이다. 이때, 에이젼트 A와에이젼트 B가그림과같이위치해있다고가정한다. 셀에부여된숫자는주출입구로부터의거리, 즉, static field 값의예시를위해단순한값을사용해서나타낸것이다. 이때초기에부여되는 d max 값을정하는것이문제가된다. Kirchner 모델에서는 dynamic value가 static value에비해상대적으로지나치게커질수있다는점이발견되었다. 저자의실험에서는단일공간에서의시뮬레이션에서는큰문제가없었으나, 그림과같이내부공간이분할되어있고, 좁은출입구 ( 단일셀로되어있는 ) 가내부공간내에위치해있는세팅에서는문제가발생되었다. Static value는주출입구에서부터점진적으로역으로부여되기때문에건물의크기에따라서는내부에있는방들은상대적으로매우작은 static 값들을가질수있다. 예를들어, 주출입구에서멀리떨어져있는셀에서는, 에이젼트 A 주변의 static 값에비해, 에이젼트 B 주위의 static value는작은값을갖게된다. 단일공간이라면, dynamic 초기값을모든셀에일정하게할당하더라도점진적인 static value로인해서출구로의방향성을갖는다. 하지만, 이렇게분할된공간에서는일차적으로내부의방에서빠져나오는것이목적인데, 방출입구주변의 static 값이작기때문에, 이값보다 dynamic 값이지나치게커지게되면출입구를빠져나오지못하고 dynamic 값만을쫓는상황도발생하게된다. 그림 8은이렇게흐름이중단되어버리는문제를예시한것이다. Dynamic 값은 diffuse와 decay 계수, α, β를대체로 [0, 1] 범위에서부여한다. 매우작은값이라하더라도이값이누적이되어전방의 Static값과의합 (S+D) 보다후방의 (S+D) 값이커지게되면, 그림 8의 Agent A 는그림과같은상황에서전방으로빠져나가지못하고제자리에있던지후방셀과자신의자리를반복해서맴돌게된다. Hall Room A 그림 8. 좁은출입구 (1 개의셀로된 ) 를통과할때의흐름정지문제 Main Exit Agent A Agent B Room Door 그림 7. 분할된공간을가진건물평면에서의 Dynamic 초기값설정의문제 그림 7은건물의외부로나가는주출입문이있고, 그안에방과, 방을출입하는문이있는것을단순화시킨 본연구에서는이를개선하기위해서에이젼트가움직였을때갖는초기 dynamic 값을인접셀의 static value 중최대값을갖도록하였다. 이렇게함으로써공간의크기나분할공간유무에상관없이 dynamic value 는 static 값에대체로비례하는값을갖게된다. 개미의 pheromone에비유한것만고려한다면, 어떻게개미의냄

개선된 Floor Field 기반보행시뮬레이션모델 81 새가출구에가까워질수록비례해서강해질수있느냐는의문을가질수도있다. 그러나, 식 (1) 에서보면, 어차피 S와 D는서로다른단위의값을 exponential 함수의지수로사용한것을보면이해할수있다.

코드의주석은변경된부분에대해서만추가하였다. 초점을둔본연구에서는이와같은데이터구축과정과이론적배경에대해서는간단하게만언급하도록하겠다.

s(i) : i O and s(i) > 0 if( i P(i) ) // For each node in the open list, if the node contains // the agent p s dynamic value, decrease it by one for each k O if d(p, k) D(k) then d(p,k) = d(p,k) - 1

6 개선된 Floor Field 기반보행시뮬레이션모델 81 새가출구에가까워질수록비례해서강해질수있느냐는의문을가질수도있다. 그러나, 식 (1) 에서보면, 어차피 S와 D는서로다른단위의값을 exponential 함수의지수로사용한것을보면이해할수있다. 각에이젼트는 global한상황에대해서는모르는채, 로컬룰에따라서만움직이게되어있고, S와 D가현재로컬영역에서의에이젼트에대한 인력 이라고볼때, 서로비슷한값을사용하고, 이를 scaling parameter 로민감도를조절하는것이타당하다고할수있다. 그림 9는이렇게개선된 Dynamic 값의연산을포함하여수정한 pseudocode이다. 코드의주석은변경된부분에대해서만추가하였다. 초점을둔본연구에서는이와같은데이터구축과정과이론적배경에대해서는간단하게만언급하도록하겠다. (a) 각 3 차원공간의 floor surface 를이용하여 DB 에저장 O=Φ D(k)=Φ for k N // Set the Dynamic list for each node to empty set P(b) = null s(b) = 0 O = (b) i = b While (i E) Let i O be a node for which s(i) = max s(i) : i O and s(i) > 0 if( i P(i) ) // For each node in the open list, if the node contains // the agent p s dynamic value, decrease it by one for each k O if d(p, k) D(k) then d(p,k) = d(p,k) - 1 O=Φ for each ( i, j ) A(i) if j O then O = O (j) P(j) = i // Get the maximum static value of among those of // open list nodes d max = max t(k) : k O // For each node in the open list, if the dynamic list does // not contain the dynamic value of node k, add it to D(k) for each k O d(p, k) = d max if d(p, k) D(k) then D(k) = D(k) d(p, k) (b) 저장된데이터의추출과 grid cell 로의변환 그림 10. 공간 DBMS 를이용한 3 차원건물데이터저장 (a) 과시뮬레이션을위한 grid cell 로의변환 (b) 그림 10에나타난바와같이본연구에서는각공간의바닥면 (floor surface) 을공간 DBMS에저장하였으며 DBMS로는PostGIS를사용하였다. 보행자의이동은바닥면을통해서만이루어지므로바닥면만을이용하더라도시뮬레이션에는문제가없다. 또한이바닥면정보를이용하여공간간의토폴로지와 semantic 정보를저장할수있다. 계단부분은몇개의연속된폴리곤의집합으로정의하여저장하였다. 시뮬레이션실행시에는이저장된정보를쿼리로얻어온후그리드셀로변환한다. 본연구에서는실제사람의어깨폭을고려하여 40cm 40cm의셀들로이루어지도록하였다. 그림 9. 개선된 dynamic field 연산규칙을적용한 pseudocode 5. 적용테스트 5.1 DBMS 기반의 3차원모델적용본연구에서는시뮬레이션테스트를위해공간 DBMS 에저장된실제 3차원건물을사용하였다. 이는본연구가시뮬레이션차원에만머무는것이아니라추후에실내센서와연동이될경우실시간으로파악된실내거주보행자에따라시뮬레이션결과를이용하여구조나대피에활용할수있도록함이다. 이는기존의이론적인연구들에서보여지는단순한가상의사각형공간을이용한실험과는차별이되는부분이다. 그러나알고리즘의개선에 그림 11. 시뮬레이션에사용된건물데이터그림 11은본연구에서사용된 2층구조의캠퍼스건물이다. 그림에서와같이두개의주출입구와하나의계단으로구성되어있다. 본연구에서는시뮬레이션을위해 C# 언어와 OpenGL을이용하여간단한인터페이스를개발하였다. 시스템에서는먼저 PostGIS로부터데이터를읽어들여서그리드셀로변환하게된다. 이때 2차원및 3차원으로가시화가가능하며 k s, k d 와같은 scaling factor 및시간스텝, 반복회수, 에이젼트의개수및반복당증가수등의파라미터들을조정할수있다.

82 한국공간정보시스템학회논문지 : 제 12 권제 1 호 (2010. 3) 5.2 시뮬레이션시뮬레이션이시작되면우선두개의주출입구로부터각셀들까지의최단거리값에근거한 static field가계산된다. 본연구에서는 k s 와 k d 의비율을다르게하면서실험하였다. 그림 12는두가지의극단적인경우, 즉, k s=0 과 k d=0인경우를예시한다.

예를들어주출입구 (Exit 2) 의폭이부출입구 (Exit 1) 보다상당히클경우에는이와같이대피시간을줄이는효과는상대적으로떨어지게된다. 표 1. k d 의변화에따른 herding behavior 및 대피시간감축효과 k d=0 k d=0.05 k d=0.1 k d=0.25 k d=0.5 k d=1.

k d=0은에이젼트들자신들위치의 static 값에따라해당되는근접한출구로직접유도하게되며, k d>0은쫓는행태 (herding behavior) 를보이기시작한다. 그림 12-(b) 에서와같이주출입구를향해몰려있던에이젼트들중몇명이그룹을이탈하게되면, 이에이젼트들을쫓아서다른에이젼트들도그룹을이탈하는것이관찰되었다. 이들은왼쪽에보이는부출입구를통해건물을빠져나간다.

실험에서는 k d=0의경우시간당대피인원이거의비례하여증가하였으며, k d>0인값들에대해서는상호큰차이를보이지는않았다. 그러나결과에서보여주는바와같이 k d>0인값들은확실하게일부에이젼트들을대안출구로유도하게되어시간당대피인원을줄이는효과를가져오는것을알수있다. 그림 14. 몇가지다른 k d/k s 들을이용한시간당대피인원수 (a) (b) 그림 13.

7 82 한국공간정보시스템학회논문지 : 제 12 권제 1 호 ( ) 5.2 시뮬레이션시뮬레이션이시작되면우선두개의주출입구로부터각셀들까지의최단거리값에근거한 static field가계산된다. 본연구에서는 k s 와 k d 의비율을다르게하면서실험하였다. 그림 12는두가지의극단적인경우, 즉, k s=0 과 k d=0인경우를예시한다. 쉽게예상할수있듯이 k s=0 은출구로의방향성이전혀없이주변의에이젼트들만을쫓아서 (herding behavior) 공간을방황하는결과를낳는다. 한편, k d=0은다른에이젼트를쫓는효과는전혀없이곧장출구를향해움직여가는효과를가져온다. 가했으며, 두개의출입구를사용하는정도가증가한만큼전체대피시간도줄어드는것이관찰되었다. 그러나이는출구의폭이나공간구조와도상관이깊다. 예를들어주출입구 (Exit 2) 의폭이부출입구 (Exit 1) 보다상당히클경우에는이와같이대피시간을줄이는효과는상대적으로떨어지게된다. 표 1. k d 의변화에따른 herding behavior 및 대피시간감축효과 k d=0 k d=0.05 k d=0.1 k d=0.25 k d=0.5 k d=1.0 Exit Exit evactime (a) (b) 그림 12. 두가지극단적인경우에서의에이젼트들의움직임 k s = 0(a) and k d = 0(b) 그림 13은 k d 값을변화시키는데에따른효과를보여준다. k d=0은에이젼트들자신들위치의 static 값에따라해당되는근접한출구로직접유도하게되며, k d>0은쫓는행태 (herding behavior) 를보이기시작한다. 그림 12-(b) 에서와같이주출입구를향해몰려있던에이젼트들중몇명이그룹을이탈하게되면, 이에이젼트들을쫓아서다른에이젼트들도그룹을이탈하는것이관찰되었다. 이들은왼쪽에보이는부출입구를통해건물을빠져나간다. 또다른실험은에이젼트들을증가시키고, k d/k s 비율을증가시키면서실시하였다. 그림 14에서보여주는것과같이, 실험에서는여섯개의 (k d, k s) 쌍, (0, 0.3), (1, 0.1), (0.25, 0.5), (0.1, 0.1), (0.05, 0.1), (0.1, 1) 이이용되었다. 또한에이젼트들은 500~5000의범위에서증가시키면서실시하였다. 실험에서는 k d=0의경우시간당대피인원이거의비례하여증가하였으며, k d>0인값들에대해서는상호큰차이를보이지는않았다. 그러나결과에서보여주는바와같이 k d>0인값들은확실하게일부에이젼트들을대안출구로유도하게되어시간당대피인원을줄이는효과를가져오는것을알수있다. 그림 14. 몇가지다른 k d/k s 들을이용한시간당대피인원수 (a) (b) 그림 13. k d 값의변화에따른효과 k d = 0(a) 과 k d/k s = 0.5(b) 표 1은이렇게 k d 값의변화에따라그룹의 herding behavior 정도를측정한결과이다. 표에서는 k d 값의변화에따라왼쪽출입구 (Exit 1) 를사용한탈출인원수와공간내의전체에이젼트들이모두대피하는데에걸린시간을보여준다. 실험에는 2000명의에이젼트들이사용되었다. 예상대로 k d 값의증가에따라 Exit 1의사용이증 5. 결론본연구에서는 floor field를기반으로한 multi-agent 보행시뮬레이션모델을개선시키는데중점을두었다. Kirchner의모델은에이젼트를구분하지않고로컬룰에따라자율적으로움직인다는기본원칙에는충실하지만, 자신의 dynamic 값에도영향을받을수밖에없는단점을가지고있다. 본연구에서는 dynamic field의데이터구조를변경함으로써개미의 pheromone과같이자신의 dynamic 값은배제한다른에이젼트의영향만을받도록하였다. 또한

8 개선된 Floor Field 기반보행시뮬레이션모델 83 자신의 dynamic 값의최대값을 static 값에비례하게줌으로써, 공간의복잡도에상관없이두값의영향이항상유사하도록하고, scaling factor로조절이용이하도록하였다. 본연구는다양한에이젼트속도를다르게준다던지, 출구로의가시성 (visibility) 을포함시키는등모델의개선도지속적으로수행하고있다. 또한공간 DBMS를적용한실제데이터와의연동에도목적을두고있다. 여기에서는간단한 2층구조의DBMS를이용하여랜덤데이터를이용한시뮬레이션에초점을두었다. 그러나추후에는실내위치센서와의연동을통해건축공간에서실시간으로파악된사람들의분포를이용할수있다. 이렇게되면실시간으로수집된특정공간내의사람들이대피하는데에지나치게긴시간이예상된다면 ( 이는시뮬레이션결과, 즉, 시간당대피인원을이용한다 ) 대안대피로를안내하거나구조활동시우선적인구조장소와루트를안내하는데에이용될수있다. 참고문헌 [ 1 ] Schreckenberg, M and Sharma, S.D. (Eds.), Pedestrian and Evacuation Dynamics, Springer- Verlag, Berlin, [2] Helbing, D., and Molnár, P., Self-organization phenomena in pedestrian crowds, In F. Schweitzer (Ed.), Self-Organisation of Complex Structures: From Individual to Collective Dynamics, Gordon & Beach, London, UK, [3] Helbing, D., Farkas, I., Molnár, P., and Vicsek, T., Simulation of pedestrian crowds in normal and evacuation situations, In M. Schreckenberg and S. Sharma, (Eds.), Pedestrian and Evacuation Dynamics, Springer-Verlag, Berlin, 2001, pp [ 4 ] Burstedde, C., Klauck, K., Schadschneider, A., and Zittartz, J., Simulation of pedestrian dynamics using a two-dimensional cellular automaton, Physica A, Vol.295, 2001, pp [5] Kirchner, A., and Schadschneider, A., Simulation of evacuation processes using a bionics-inspired cellular automaton model for pedestrian dynamics, Physica A Vol.312, 2002, pp [6] Apel, M., Simulation of pedestrian flows based on the social force model using the Verlet Link Cell Algorithm, Master Thesis, Poznan University of Technology, Poland, [ 7 ] Henein, C. M., and White, T., Macroscopic effects of microscopic forces between agents in crowd models, Physica A, Vol.373, 2007, pp [ 8 ] Henein, C. M., and White, T., Agent-Based modelling of force in crowds, MABS 2004, LNAI, 3415, 2005, pp [ 9 ] Ben-Jacob. E., From snowflake formation to growth of bacterial colonies. II: Cooperative formation of complex colonial patterns, Contemporary physics, vol.38 no.3, 1997, pp [10] Nishinari, K., Kirchner, A., Namazi, A, and Schadschneider, A., Simulations of evacuation by an extended floor field CA model, In Traffic and Granular Flow 03, Spinger-Verlag, Berlin, 2005, pp [11] Hamacher, H. W., and Tjandra, S. A., Mathematical modelling of evacuation problems: a state of art, In M. Schreckenberg and S. Sharma, (Eds.), Pedestrian and Evacuation Dynamics, Springer-Verlag, Berlin, 2001, pp [12] 김종대, 원정임, 김상욱, " 도로네트워크에서이동객 체의과거궤적분석을통한미래경로예측," 한국공 간정보시스템학회 논문지, 제8권 제2호, 2006, pp [13] 김영진, 김영창, 장재우, 심춘보, " 공간네트워크상의 이동객체를위한시그니처기반의궤적색인구조," 한 국공간정보시스템학회논문지, 제10권제3호, 2008, pp [14] 김용기, 김아름, 장재우, " 공간네트워크데이터베이 스에서공간제약을고려한경로내최근접질의처리 알고리즘," 한국공간정보시스템학회논문지, 제10권 제3호, 2008, pp [15] 황정래, 강혜영, 이기준, " 도로네트워크상의이동 객체궤적의간략화," 한국공간정보시스템학회논문 지, 제9권제3호, 2007, pp [16] Schadschneider, A., Cellular automaton approach to pedestrian dynamics Theory, In M. Schreckenberg and S. Sharma, (Eds.), Pedestrian and Evacuation Dynamics, Springer-Verlag, Berlin, 2002, pp [17] Blue, V. J., and Adler, J. L., Using cellular automata microsimulation to model pedestrian movements, In A. Ceder (Ed.), Proceedings of the 14th International Symposium on Transportation and Traffic Theory, Jerusalem, Israel, 1999, pp [18] Klupfel, H., Konig, T., and Wahle, J., and Schreckenberg, M., Microscopic simulation of evacuation processes on passenger ships, In Proceedings of Fourth International Conference

84 한국공간정보시스템학회논문지 : 제 12 권제 1 호 (2010. 3) on Cellular Automata for Research and Industry, Oct. 4-6, Karlsruhe, Germany, 2002. [19] Wooldridge, M.

9 84 한국공간정보시스템학회논문지 : 제 12 권제 1 호 ( ) on Cellular Automata for Research and Industry, Oct. 4-6, Karlsruhe, Germany, [19] Wooldridge, M., An Introduction to Multi Agent Systems, John Wiley & Sons, [20] Panait, L. and Luke, S., Cooperative multi-agent learning: the state of the art, Autonomous Agents and Multi-Agent Systems, Vol.11 No.3, 2005, pp [21] Bonabeau, E., Dorigo, M., and Theraulaz, G., Swarm intelligence: From natural to artificial systems. Oxford University Press, New York, 전철민 1988년서울대학교도시공학과 ( 공학사 ) 1990년서울대학교도시공학과 ( 공학석사 ) 1997년 Texas A&M 대학교도시및지역계획학 ( 공학박사 ) 1997년~1999년 North Carolina RTI GIS 전문요원 1999년~ 현재서울시립대학교공간정보공학과교수 2008년~ 현재서울시립대학교공간정보연구센터센터장관심분야는 GIS, 공간데이터베이스, 3차원모델, network algorithm 등

<4D F736F F F696E74202D2038C2F7BFF6C5A998DEC0DAB7E128BCADBFEFBDC3B8B3B4EBC7D0B1B3295FBCF6C1A42DC0FCC3B6B9CE>

<4D F736F F F696E74202D2038C2F7BFF6C5A998DEC0DAB7E128BCADBFEFBDC3B8B3B4EBC7D0B1B3295FBCF6C1A42DC0FCC3B6B9CE> u-indoor Evacuation Planning System The 8 th ISA Workshop University of Seoul Feb. 6, 2009 Contents 연구개요 추진일정및진행사항 세부진행사항 활용방안 2 연구개요 필요성 실내공간데이터모델, 공간데이터베이스, 실내센서등 u-indoor 기반기술의활용사례로써 evacuation planning