1st Reading

September 17, 2008 16:46 00409

Fractals, Vol. 16, No. 4 (2008) 1–16c© World Scientific Publishing Company

FRACTAL, A MICROSCOPIC CROWD MODEL

SETYAWAN WIDYARTODepartment of Computer and Information Management

State Polytechnics of LampungJalan Soekarno-Hatta No. 10 RajabasaBandar Lampung, 3514 2 Indonesia

Faculty of Industrial Information TechnologyBestari Jaya Campus, Jln Timur Tambahan

45600 Berjuntai BestariSelangor, Darul Ehsan, Malaysia

swidyarto@gmail.com

M. S. ABD. LATIFFDepartment of Computer System and CommunicationFaculty of Computer Science and Information System

Universiti Teknologi Malaysia81310 UTM Skudai, Johor, Malaysia

Received November 13, 2007Accepted June 6, 2008

AbstractThe core of this research is related to the human crowd problem. Some major problems arecongestion, emergency evacuation, and fatal catastrophe. In fact, it has been realized that manycrowd related problems can be resolved by influencing (controlling) human flow with providingvarious control measures. Thus, the problem itself becomes the motivation for this research andthe solution is approached through model and simulation within the virtual environment.The relationship between fractal pattern and crowd behavior is produced with respect to thecrowd behavior model. It exposes a comparison between the crowd paths resulting from themodel developed and the fractal formation created to imitate the crowd paths. A new approachfor crowd behavior modeling is proposed based on fractal features and, thus, gives new under-standing about a relationship between fractal pattern and crowd behavior. Several innovationsof fractal patterns that can be used in crowd behavior model applications adds to the novelty ofthe research contribution. Ultimately, the new method of modeling the crowd can be obtained

1

1st Reading

September 17, 2008 16:46 00409

2 S. Widyarto & M. S. Abd. Latiff

and at the same time the new direction of crowd modeling research can be directed. A newapproach for crowd behavior modeling is proposed based on fractal features and, thus, givesnew understanding about a relationship between fractal pattern and crowd behavior. Severalinnovations of fractal patterns that can be used in crowd behavior model applications adds tothe novelty of the research contribution. Ultimately, the new method of modeling the crowdcan be obtained and at the same time the new direction of crowd modeling research can bedirected.

Keywords :

1. INTRODUCTION

The focus of this research is the crowd microscopicmodel simulation for large agents by consideringthe interaction forces among the crowd membersbut the research is extended to fractal investiga-tion. The investigation also compares the charac-teristics of fractal formation and agent paths. Theagent paths are used to analyze crowd behavior.The crowd behavior is approached with fractal pat-terns. The crowd behavior is a collective behaviorfrom many agents. In the literatures, the collectivebehavior is a typical feature of living systems con-sisting of many similar units and it is suggestedthat the pattern would be fractal.However, fractaldetermination is a conjecture that needs convincingcriteria.

The overall of this research is in exposing discus-sion of the relationship between the crowd micro-scopic model and fractal. Some simulation resultsof fractal patterns are also supplied to support theconjecture relationship. Thus, the research objectiveis to study the relationship between fractal patternand crowd behavior with respect to producing thecrowd behavior model. The crowd behavior modelis constructed with forces inclusion (crowd dynam-ics). One of the research novelties is some findings offractal patterns that can be used in crowd behaviormodel applications.

2. A MICROSCOPIC SWARMMODEL SIMULATION

This research differentiates between crowd andswarm on the reason behind the usage. When crowdis used it has danger behind but when swarm is usedit is just a moving large number of agents and doesnot highlight any danger. This section uses bothcrowd and swarm. However swarm is used to refer tomulti-agent simulation in neutral observation with-out any prejudice of potential fatal catastrophe.

The microscopic model simulation of agents isa computer simulation model of agent movementwhere every agent member in the model is treatedas an individual agent. The microscopic model isalso known as a particle-based model. An exampleof such a microscopic model is reported in robotics.1

The microscopic model is used to study collectivebehavior of a swarm of robots engaged in objectaggregation and collaborative pulling. The stick-pulling experiment was carried out to the studydynamics of collaboration of robots. Venutia et al.2

suggested that further research should be addressedto the determination of the values of the parametersinvolved by means of ad hoc experimental tests andmicroscopic models of the human agent flow couldbe included in the framework of crowd-structureinteraction. However, this microscopic model andsimulation in this research is somewhat particlesystem- or physical force-based, but in this researchit is termed as “agent-based”.

The model is termed as agent-based because thismodel is based on identifying each member of thecrowd as an object or an agent. Moreover, it is asimulation of each agent motion with respect toall other agents and the environment in which itmoves. This style of model depends on simulatingthe behavior of an object or agents individuallywhere every agent member in the model is treated asan individual agent. The model has three variablesof force types. The forces will be further explainedin Sec. 2.1.

Customization of physical-based variables asinputs of the model is designed to get autonomousagents. The autonomous agents’ paths will be dif-ferent in every repeating simulation. It means thesimulation will be given predefined inputs and theagent motion is free from a user.

Agents in the microscopic simulation model aremodeled as non-player agents (NPAs). NPAs arethe autonomous agents that are free from the user’s

1st Reading

September 17, 2008 16:46 00409

Fractal, A Microscopic Crowd Model 3

control but initial conditions are keyed by the users.NPAs are seen from above the facilities (top view).An agent is modeled as a circle with a certainradius. Each agent’s initial conditions includes ini-tial location, initial time, initial velocity, and pre-determined target location (opposite to the initiallocation). These inputs can be determined by theuser as a design experiment and can be specifiedrandomly.

NPAs will interpret an action and this interpreta-tion process is important for the view in behavioralanimation. This will lead to further autonomousactions in the virtual environment as well as intelli-gent responses to the action being carried out. Thusmotion or path planning becomes much more com-plicated when an animation for large swarms mustbe made. The development in motion planning andin global techniques for improving the approach hasbeen discussed3 but it focused on the probabilisticroadmap (PRM). Furthermore, a model to simu-late the movement of virtual humans based on tra-jectories captured from filmed video sequences isinvestigated.4 It used a physically-based simulatorto animate virtual humans and to reproduce the tra-jectories. Whereas the improvement for path plan-ning techniques used for large swarms is very few.

Some available video materials have beenobserved (for example Thawaf), Fig. 1. The figureshows crowd movement circling (determined withblurred area) the Kaa’bah (black box in the mid-dle) and at the farther distance from the Kaa’bahcrowd keeps at their place.

Briefly, the summary of the characteristic fea-tures of bio-creatures crowd movement could beserved as follows: (1) Crowd flow is further slowedby fallen or injured or stopped agent acting as

Fig. 1 Pilgrim’s circumbulating around Kaa’bah.

“obstacles”. (2) The physical interactions in thejammed swarm add up. (3) People in special caseshow a tendency toward mass behavior, that is, todo what other people do.5 (4) Alternative exits areoften overlooked or not efficiently used in escapesituations.6

These observations have encouraged us to modelthe collective phenomenon of swarm flow in theframework of emerging swarm behavior, NPAs.The developed computer simulations of the swarmdynamics of agents are modeled as physical-basedwith explicit visual interaction. The explicit visualinteraction might represent a generalized forcemodel inside the collective behavior of the agents.The collective behavior in a crowd is dominantlyinfluenced by socio-psychological force.7

2.1. Modeling Agent Movements

KirchnerandSchadschneide8 andHeneinandWhite9

with their field-based model represent forces in sucha model that two individual factors — desire tomove toward an exit and desire to follow others —within a physical space laid out in a grid pattern.Force in models of crowds is a basic element thatmust be represented for three main reasons. First,force has a direct effect on movement. Second, forceis a perceptible input to the cognitive system anda major source of information in an information-starved situation. Third, force carries the conse-quences of dangerous crowd scenarios: injuries. Themodel developed applied those three reasons.

Modeling the agent crowd movement begins withan assumption that each agent is subjected to moti-vation to move ahead toward the target point ordestination. The motivation is an analogy of theforce that characterizes the internal driving force.Borrowing the general behavior rules in LiteratureReview from Thalmann et al.,10 the driving force isassumed proportional with the difference betweenthe intended velocities and the current velocity.

Briefly, Fig. 2 shows the method used in micro-scopic crowd modeling behavior. From Fig. 2, cal-ibration refers to real world features observation,whereas, verifying and validating mean comparingobservation with related existing works.

The microscopic swarm model is a mathemati-cal model that every agent has three variables offorces. The overall model is a mathematical modelthat is combination and extension of escape panicmodel,7,11,12, bird flocking behavioral model13 andpedestrian traffic model.14 The development of the

1st Reading

September 17, 2008 16:46 00409

4 S. Widyarto & M. S. Abd. Latiff

Fig. 2 The method used.

model and simulation is designed to capture theindividual swarm member and able to record thecharacteristics of its movements. The calibration ofthe simulation is concerned with the determinationof the numerical value of the parameters and theresults of the simulation. Whereas, validation andverification does not mean validating with real-lifemovement but it is rather an exposure to showthat the model does work. However, this researchextends the method with comparison between thecharacteristics of the microscopic model and fractalexperiment result.

The basic dynamical model will be

xt+1 = xt + vt (1)at = vt+1 − vt (2)

where xt, vt, at denotes the matrix or vector ofcurrent location, velocity and acceleration, respec-tively.

The force (f) is proportional with mass (m)and acceleration (a). The acceleration is a discrep-ancy between two velocities, and the model in thisresearch is the summation of desired velocities, v(t)and the actual current velocity, v(t). Thus, it is writ-ten as Eq. (2). Therefore, the force becomes Eq. (4).

f(t) = m.a (3)

mdv(t)dt

=∑

v(t) − v(t). (4)

The model developed comprises three variablesof force types, i.e. the force to move ahead (i.e. adesired velocity), the force to prevent collision (i.e.acceleration or deceleration) forward, and the forceto move away (i.e. change the direction) that is alsoto avoid collision. Each of the forces contains differ-ent parameters and is modeled obeying the Newtonlaw.

The developed model has four parameters. Theyare the mass, m, alpha, α, beta, β and chi, χ. Alphainfluences the force to move ahead, beta for colli-sion avoidance and chi for move away. The mass

is applied toward the three forces together (globalparameter) while the other three parameters areapplied only for the particular force. The threeforces are Eqs. (5)–(7).

maf =vf

α− α

αv (5)

maa =va

χ− χ

χv (6)

mar =vr

β− β

βv. (7)

Resultant of the three forces (addition of vectors)yields Eq. (8):

m (af + aa + ar)

=vf

α+

va

χ+

vr

β−(

α

α+

χ

χ+

β

β

)v. (8)

Say a = af +aa+ar and c = αα + χ

χ + ββ , then Eq. (8)

becomes Eq. (9)

ma + cv =vf

α+

va

χ+

vr

β. (9)

The first force is the main force and startingforce. It means the other two forces will not workif the main force does not exist. This force is theforward moving force and does move ahead. Theforward force will drive the agents from any initialor current positions into target positions or destina-tion. Generally, the movement of an agent is fromthe current location, p(t) toward the destinationpoint, e(t).

The magnitude of this force is intended to makethe speed of the agents (crowd members) within therange of the human agent walking speed, which isfrom zero to maximum of the walking speed, µmax

or at the mean human walking speed as shown inTable 1. This force will make an agent reach thedesired velocity. Let F , a force, is applied to moveahead that directs the agent to move. The F forcemakes the agent path almost in a straight line andits direction is from the current location toward thedestination. The gradient (direction) of the F isgiven by g(t),

g(t) =e(t) − p(t)

‖e(t) − p(t)‖ . (10)

If there is no obstruction, the agent’s intendedvelocity reaches the maximum walking speed, µmax

or smaller (0 ≤ v(t) ≤ µmax. The existence ofother agents or obstructions will reduce the walking

1st Reading

September 17, 2008 16:46 00409

Fractal, A Microscopic Crowd Model 5

Table 1 Observed Walking Speed in UncongestedCorridors.

Mean StandardSpeed Deviation

Ref. (m/s) (m/s) Location

15 1.4 Netherlands16 1.47 United Kingdom17 1.44 0.23 Australia18 1.45 Australia19 1.08 Saudi Arabia20 1.19 0.26 Hong Kong21 1.25 Sri Lanka

1.4 Canada22 1.32 1.0 United Kingdom23 1.46 0.63 India24 1.23 Singapore25 1.22 Thailand

Estimated 1.34 0.37overall average

speed. Thus, the intended velocity for the F forceis given by

vf (t) =µmax

Fg(t) =

µmax

F

e(t) − p(t)‖e(t) − p(t)‖ . (11)

The norm in the denominator of the equationabove represents the distance between the currentposition and the destination.

Generally, the movement of an agent is from thecurrent location, p(t) towards the destination point,e(t). Alpha force is applied as the force to moveahead that directs the agent to move. The alphaforce makes the agent path almost in a straight lineduring absence of the other two forces. On the otherhand, the absence of alpha force will make an agentimmobilized in sense of no destination. The direc-tion of the alpha force is from the current locationtowards the destination.

However, the detail of the model is somewhatcustomized with physical-based variables that canbe measured as inputs of the model. The modeldeveloped is different from the work by Helbinget al.11,26 where agents are influenced via veloc-ities adjustment by assuming the “psychological”repulsive force between people in a crowd is expo-nentially increasing with distance reaching the forceupon contact. The developed model eliminates theexponential increment and applies distance propor-tion to adjust the velocity because the model is notaimed for escape panic situation.

The second force is the force to prevent collisionbut it does not change the direction. It means an

agent will be patient by decreasing the speed withdeceleration or may quickly respond by increasingthe speed with acceleration. Thus, in both cases theagent keeps moving forward.

However, the developed model applies anotherrepulsive force of multi-agent reactions by assigningadditional radii to guarantee collision avoidance.Thus, the developed microscopic agent simulationmodel is made based on the existing models toimprove the deficiency of the existing models andkeeps their main advantages.

The model with the second force may avoid col-lision by keeping the safe distance between twoagents. When two agents nearly collide (Fig. 3) theyusually move away from each other within a cer-tain distance but do not change the path. In otherswords, an agent decreases the speed along (dottedline in the picture) the same axe, e.g. X. They maynot wait until their distance becomes too close tomove away unless there are no spaces surroundingthem. A similar behavior happens when an agent isfollowing another slower agent.

If d(t),y and r are, respectively, representing thedistance between the agents, interference of the clos-est agent in the area in front of the actor and theinfluence radius of agent, the intended velocity ofagent ith, vi

a(t) due to F force to move away, isgiven by

via(t) =

µmax(2r − y(t))Fd(t)

=µmax(2r − y(t))F‖pk(t) − pi(t)‖

.

(12)

Fig. 3 F Force to move away within sight distance in x-yplane.

1st Reading

September 17, 2008 16:46 00409

6 S. Widyarto & M. S. Abd. Latiff

The third force is is also to avoid collision but theforce will make the agents move away and changethe direction.

The expected velocity is a kind of predicted veloc-ity on which way the agent is going to move in thenext time ahead. The expected velocity directs theacceleration and the forward force toward the tar-get point. The direction of the expected velocitymust be the same as the force and the accel-eration. Based on the Newton law, the accelera-tion is proportional to the force with a constantproportion called mass, m. Since the accelerationhas the same direction as the force, it is also thedirection of the acceleration. When the expectedvelocity is equal to the current velocity, the force(and the acceleration) has zero value and theagent may be stopped or walking with a constantvelocity.

The model with the third force may avoid col-lision by changing the direction of the movement,thus the path will be curved. When two agentsnearly collide, they usually move (repulse) awayfrom each other by changing positions such thatdifferent force vectors occur (Fig. 4). They maynot wait until their distance becomes too closeto repulse away (three agents in the right in thepicture), unless there are no spaces surroundingthem. A similar behavior happens when an agentis following another slower agent (three agents onthe left of the picture). They have to adjust theirvelocity direction so that any proper alignmentcan be reached matching velocity with a nearbyagent. Align an actor’s velocity vector with thatof the local flock. This move (repulse) away direc-tion causes the path bend and the overall swarmpath may also create an emerging behavior of curvepath.

A repulsive force is generated if the influ-ence radius does overlap each other. The repul-sive force considers all agents surrounding and theforces are summed up linearly. The force dependson the distance between the agent and otheragents surrounding it. The repulsive force model is

Fig. 4 Repulse away.

given by

fi,r(t) =µmax

β

∑j

(2r − dij(t)

) (Xi(t) − Xj(t)

)dij(t)

− Vt.

(13)

The two forces are then totaled together witha weighing factor, the parameter m’ to define theacceleration.

at =1m′ (ff(t) + fi,r(t)). (14)

It is different from the two models, this researchmixes socio-psychological and physical force. Thepsychological force is an influencing force of thebehavior in a swarm and the force is a moving force.In other words, agents never move if no force movesahead (alpha = 0), even though other parametersare not zero. It is assumed that each agent is sub-ject to “mixed forces” that represent motivation tomove ahead toward the target location. The forcehere is the analogy of the force that characterizesthe internal driving force or motivation of the agent.

2.2. Collision-Free Multi-Agents(Swarm) Motion Planning

In practice, the repulse away force is not always suf-ficient to prevent a collision between swarm mem-bers and it is necessary to implement a skirtingrule. The repulse away rule is an extremely localversion of the separation rule. In other words, itonly reckons the nearest swarm member ignoringmulti-surrounding agents. To overcome this draw-back and to guarantee collision free, some collisionavoidance research can found from literatures andwill be revealed in the following paragraphs.

Provided with a situation that involves a largenumber of agents, for example an egress dur-ing an emergency, an agent is supposed to actand produce movement. Every single robot in aswarm is expected to move away from the threatbut there must not be any movement that causesjam, obstruction or other non-adaptive directions.Canter,27 and Still,28–30 modeled the problem byproducing movement in either predictable direc-tions: towards the threat or away from the threat orno movement. This problem was reduced to threevariables that interact — Objective, Motility andConstraint — and one parameter which representsthe reaction time; Assimilation. The Objective is toreach the expected point. The Motility is the speedof each agent. The Constraint is the geometric size

1st Reading

September 17, 2008 16:46 00409

Fractal, A Microscopic Crowd Model 7

of each agent. The interaction between these threevariables were plotted against each other and theresults are fractal in nature.28

Tzafestas et al.31 studied collision avoidance formotion planning and Bruzzone and Signorile32 usedrepulsion among the entities to avoid collision withother entities. Furthermore, Helbing et al.12 wasable to represent the collective phenomenon ofescape panic. Nevertheless, all the above researchhave successfully exposed the model and simula-tion of agent movement with each of their ownhighlighted objectives. This research developed theagents movement model that is different from theabove multi-agent models in respect of collisionavoidance method.

The collision method that is used in this researchhas characteristics that agents have sight distanceand influence diameter (Fig. 5). Snapshot of simu-lation agents with sight distance is the left picture,whilst the right picture is with the circle barrier.

If d(t), y and r are, respectively, representing thedistance between the agents, interference of the clos-est agent in the area in front of the actor and theinfluence radius of agent, the expected velocity ofagent ith, vi

a(t) due to chi force to move away, isgiven by Eq. (15).

via(t) =

µmax (2r − y(t))ξd(t)

=µmax (2r − y(t))ξ ‖pk(t) − pi(t)‖

.

(15)

By the alpha and chi forces, the agents can adjustthe distance between two agents and are able tomove away from each other. However, those twoforces may not be able to prevent a collision whenthere are many agents in the arena. To further pre-vent a collision, a force that considers all surround-ing agents is needed. For this purpose, it is assumedthat each agent has an influence radius that repre-sents his or her security awareness. By giving influ-enced radius they are able to keep a certain distanceaway from the nearest agent and to avoid collisions

Fig. 5 Collision avoidance characteristics.

with a nearby agent. The force must be generatedwhen at least two agents’ influencing radii partlycover each other as has been shown in Fig. 5.

No repulsive force is generated if the influenceradius does not overlap each other. Instead of con-sidering the closest agent as the first repulsive force,the second repulsive force considers all surroundingagents and the forces are summed up linearly. Sim-ilar to the first repulsive force, the second repul-sive force depends on the distance between theactor and other agents surrounding it. Since v(t) =dp(t)

dt and a(t) = dv(t)dt = d2p(t)

dt2, the formulation

can be put together in terms of the current posi-tion of agent i, p(t) as a second order differentialequation.

Equation (16) is a nonlinear second order dif-ferential equation of agent positions that dependon each agent’s positions, speeds and accelerations.The analytical solution of the differential equationis very difficult and not practical since it is alsodependent on the number of agents and the sightdistance. Numerical method through simulation ismore favorable and it has the benefit to visualize themovement of each agent in a plan as an animation.

md2pi(t)

dt2+

dpi(t)dt

= µmax

{e(t) − pi(t)

α‖e(t) − pi(t)‖+

2r − y(t)ξ‖pξ(t) − pi(t)‖

+∑

j

[2r

‖pi(t) − pi(t)‖− 1]

×[

pj(t) − pi(t)β‖pj(t) − pi(t)‖

]}. (16)

The differential Eq. (17)

vf (t) =µmax

αg(t) =

µmax

α

e(t) − p(t)‖e(t) − p(t)‖ (17)

is solved numerically by the divide and conqueralgorithm using Euler method, which provides ade-quate results while keeping the computational speedreasonable. Each equation is computed one by one,as each agent is assumed an autonomous agent.An agent has his own internal forces and influencesother agents only through his position. The agentmovement is based on the resultant forces that actupon him. Other numerical methods to solve thedifferential equation such as Runge Kutta may pro-duce a better approach to the differential equation

1st Reading

September 17, 2008 16:46 00409

8 S. Widyarto & M. S. Abd. Latiff

but it decreases the computational speed signifi-cantly if the number of agents is more than 100,thus, it is recommended for further study.

2.3. Modeling Fractal Patterns

Defining the fractal equation or pattern that mayhave potential sharing features to crowd featuresneeds many experiments. It is decided to find thepattern in the Holy Qur’an. Surah Yaasiin verses36 says “Glory to Allah, Who created in pairs allthings that the earth produces, as well as their own(human) kind and (other) things of which they haveno knowledge.” Based on the knowledge from theHoly Qur’an, a fractal pattern with a pair of armsis created.

A keyword from this verse is pair. Without try-ing to interpret it, a fractal pattern is able to createbased on pairing. It is like a tree with a certaingrowing pattern. It starts with the first branch andgrows up two branches and the pattern is iterated.The pattern is one branch generated toward leftand right, as shown in Fig. 6, and some exper-iments using this fractal pattern have been con-ducted. The fractal model, which is created, startswith two branches, i.e. one branch generated “sym-metrical”, toward left and right. Each branch hastwo variables, i.e. length and angle.

In order to make the experiments more practical,a simple interface is created. The interface can beused in constructing a variant form of the patternusing a different length and angle of arm. Figure 7shows the interface to make a series of experiments.By manipulating the branch length and angle, manyformations can be created.

Fig. 6 Simple fractal.

Fig. 7 Simple fractal toolbox.

3. SIMULATION RESULTS: THECROWD BEHAVIOR MODELAND FRACTAL STUDY

The simulation results are grouped into two subsec-tions. The path resulted from the model is servedbefore the path resulted from the fractal pattern.

3.1. Swarm Path Resulting from theModel

The path graphs served in this section are extractedfrom the system created. The input snapshots ofthe system are shown in Fig. 8 whereas the outputsnapshots are shown in Fig. 9.

In case of microscopic characteristics of agents’movements, the effects of forces applied areexplained from Fig. 10. It can be seen from Fig. 10

Fig. 8 Snapshot of inputs.

1st Reading

September 17, 2008 16:46 00409

Fractal, A Microscopic Crowd Model 9

Fig. 9 Snapshots of outputs.

Fig. 10 The effects of forward forces to agents’ paths.

that the forward force causes the paths to be a lin-ear line. The effects of forces to agents’ paths meansonly alpha force applied, Eq. (5). It is shown thepaths are linear, the agents may decelerate or accel-erate but they do not change direction or repulseaway.

If repulse away forces are also applied as an effortto avoid collision, the agents’ path direction willbe changed. Thus, repulse away forces direct theovertaking behavior, Fig. 11. The force Eqs. (5) and(6) were applied. It is clearly shown, some pathsin Fig. 11 on the low lines are still linear becausethe density is not high enough or distance amongstagents is not close enough to stimulate the repulseaway force.

However, if avoid obstruction or collision forceapplied instead of repulse away force the agents’path keeps linear, Fig. 12. It means the effects for-ward Eq. (5) and avoid collision forces [Eq. (7)] areapplied. It is also noted that the paths are moredistributed than the paths of forward forces appli-cation only, Fig. 10.

Fig. 11 The effects of forward, and move away forces toagents’ paths.

Fig. 12 Forward and avoid collision. The effects of forcesto agents’ paths.

Fig. 13 The effects of forward, repulse away and avoid col-lision forces to agents’ paths.

It could be predicted that the paths are curvingand the forces drive the overtaking behavior whenthe repulse away forces are applied again, Fig. 13. Itmeans all three forces are applied, [Eqs. (5) to (7)].

In all cases of the experiment results (Figs. 10to 13), it would be said that the paths have thesame pattern but they are not self-similar. However,each figure has the same rules for every member ofswarm, i.e. they move based on force(s) applied. Inother words it is up repetition of the rules but theyare not literally sequential. Therefore, the pathsformed do not construct a tree as a fractal does.

1st Reading

September 17, 2008 16:46 00409

10 S. Widyarto & M. S. Abd. Latiff

Fig. 14 The Sierpinski triangle, the game of chaos based on Barnsley.

Somewhat, the procedure of making a rule beapplied in itself innumerable times, which is calledrecursion or recursive process, is iterated indeed.That means, each time this rule is applied a newresult or a new path will be obtained. The differ-ence between the swarms model and fractal pathresults would happen because of random genera-tion inclusion. Further discussion of path resultedfrom fractal will be discussed in the followingsubsection.

3.2. Fractals Study andAgro-Biotechnology Results

Here, some of the significant results produced usingMatlab are presented. This is based on Michael F.Barnsley’s simulation of the game of chaos. Theresult is the Sierpinski triangle. The simulationsare shown with various STEPS. The STEPS is thenumber of iterations thus the number of points inthe image resulted. The following figures (Fig. 14)are simulation results with STEPS 100, 1000, and10,000, respectively.

Furthermore, the simulation of fractal applica-tion is applied in shaping both in 2D and 3Dusing Matlab and WRL software. Fractal 2D shapein Fig. 15 produces a remarkable shape of anybiological structure. Meanwhile, the fractal 3D

Fig. 15 Two-dimensional fractal shaping.

Fig. 16 Three-dimensional fractal shaping.

shape in Fig. 16 produces an attractive shape ofplantation.

IFS (iterated function system) shaping sim-ulation is exposed in another experimentation.The self-similarity dimension (also known as box-counting or Minkowski dimension, Fig. 17) providesa measure of the degree of space-filling exhibited bya particular fractal curve.33 This has been increas-ingly applied as a means of characterizing data tex-ture and shape in a large number of physical andbiological sciences.

On the other hand, Figs. 18 and 19 show thesimulation results of half-fern fractal. Two basicvariables are applied here, i.e. a number of pointsand a number of iterations. The result in Fig. 18uses iteration as a variable with a fixed number ofpoints. It is shown that the increased number of iter-ations does not significantly construct the desirable

1st Reading

September 17, 2008 16:46 00409

Fractal, A Microscopic Crowd Model 11

Fig. 17 The box-counting Minkowski dimension.

results. On the other hand, Fig. 19 gives a remark-able result by varying the number of points in frac-tal construction.

Marana et al.34 used density estimation based onMinkowski fractal dimension. Fractal dimension hasbeen widely used to characterize data texture inphysical and biological sciences. The results of theirexperiments show that fractal dimension can also be

Fig. 18 A hundred-points half-fern with various iterations.

Fig. 19 Fifty iterations half-fern with various points.

used to characterize levels of people congestion inimages of crowds.

Some experiments, which manipulates branchlengths and angle of the fractal pattern with onebranch generated symmetrical towards left andright (see Fig. 6), have been conducted. Figure 20shows some results with the variant of symmet-rical angle of branch but both asymmetrical andsymmetrical length of branches. Both figures inFig. 20 show that any curve path has not beenformed yet if the fractal has symmetric angle ofbranch. Analogically, any scalar parameters [e.g.mass] in a physical-based model may not signifi-cantly influence the path direction, but any vectorparameters [e.g. velocity] may cause bending of pathdirection.

Furthermore, Fig. 21 produces a very significantpattern of fractal that can contribute towards avery complicated structure of swarm research. Fig-ure 21, i.e. asymmetric angle of arm and the armlength both symmetric and asymmetric have sharedcharacteristics of curve emerging behavior with theagent microscopic model developed that appliedrepulse/move away forces (see Figs. 11 and 13).However, these shared characteristics have not beenmathematically proven except from the curve pathsseen.

1st Reading

September 17, 2008 16:46 00409

12 S. Widyarto & M. S. Abd. Latiff

Fig. 20 Left: Symmetric angle and symmetric length ofbranch. Right: Symmetric angle and asymmetric length ofbranch.

Fig. 21 Left: Asymmetric angle and asymmetric length ofbranch. Right: Asymmetric angle and symmetric length ofbranch.

The most important advantage of fractal usageto model swarm is that the whole members are rel-atively more uniformly distributed than any othermodels. Uniform distribution will achieve uniformswarm density. The occupied density is an influ-enced characteristic to control any swarm, crowd,flock or other large massive group of agents.

The same experiment with equal arm’s lengthand 60◦ equal arm’s angle resulted in an emerg-ing pattern of a beehive-like formation (Fig. 22).It is common knowledge that a bee is a groupingcreature. Are there any relationships between groupbehavior and fractal characteristics? This questionneeds further research.

Predictably, a straight line formation can bebuilt by equal arm’s length and 0◦ as shown inFig. 23. The straight line formation correspondsto the straight path of agents (in Fig. 10) whenonly a forward force is applied to the agents. Let

Fig. 22 Result with equal arm’s length and 60◦ equal arm’sangle.

Fig. 23 Result with equal arm’s length and 0◦.

straight lines represent swarm member lanes, ide-ally the more dense the members are the more lanesmust be formed. Consequently, swarm should becomposed of cooperative agents in such an adap-tive behavior that encodes a collective pattern. Thisadaptive pattern can be modeled from a fractal. Asthe research focuses on the formula with the basicshape and form of a fractal, the fractal images cre-ated were not further processed by transformationsthat transform and warp the shape of a fractal andcombine various transformations to create complexeffects. The research also does not involve coloringalgorithms to give beautiful and complex images.However, Fig. 21 produce a very significant patternof fractal that can contribute towards a very com-plicated structure of the crowd path.

4. PATH COMPARISON ANDVALIDATING OBSERVATION

This section compares the characteristics of themicroscopic model result and fractal. Some researchabout fractal and its application in topics of crowdalso motivate the project.

Paths resulting from experiment of crowd micro-scopic model with forward forces applied (Fig. 23)in a swarm has sharing characteristics with pathsresulting from the fractal experiment with equalarm’s length and a small degree e.g. 5◦) of arm’sangle (Fig. 24). In addition, the exit model couldbe counterparted with fern fractal using transfor-mation manipulation, Fig. 25. It is clearer than orig-inal when it is zoomed in, Fig. 26.

Regarding the validation and verification, crowdcompiler can be used to visually compare betweenthe real world (Fig. 27) and and simulation snap-shots.

Results are not validated with real data but withother models studied from literature. One validation

1st Reading

September 17, 2008 16:46 00409

Fractal, A Microscopic Crowd Model 13

Fig. 24 Result with equal arm’s length and 5◦ arm’s angle

Fig. 25 Fern fractal with manipulation.

is briefly evaluated with cellular automata (CA).CA are models that are discrete in space, timeand state variables. To describe the state of a laneusing a CA, the lane is first divided into cells ofagent length. This corresponds to the typical space(agent’s length + distance to the preceding agent)occupied by an agent in a dense jam. Each cell cannow either be empty or occupied by exactly oneagent. Each agent is characterized by its currentvelocity v which could take the values V = 0 toVmax. Here Vmax corresponds, e.g. to a speed limitand is therefore the same for all agents. An example

Fig. 26 Zoom in fern fractal with manipulation.

Fig. 27 Crowd compiler.

Fig. 28 CA configuration for validation.

of simple cases, a configuration of the lane is shownin Fig. 28.

Nagel and Schreckenberg35 have introduced arule set, which led to a realistic behavior. It consistsof four steps that have to be applied at the sametime to all of the agents (parallel or synchronousdynamics).

• Step 1: Acceleration. All agents that have notalready reached the maximal velocity, vmax, accel-eration by one unit: v → v + 1.

• Step 2: Slowing (safety distance). If an agenthas d empty cells in front of it and has its velocityv (after step 1) larger then d, then it reduces thevelocity to d : v → min(d, v).

• Step 3: Congested (randomization). Withprobability p, the velocity is reduced by one unit(if v after step 2): v → v − 1.

1st Reading

September 17, 2008 16:46 00409

14 S. Widyarto & M. S. Abd. Latiff

Configuration at time t

(a) Acceleration (νmax = 2)

(b) Braking

(c) Randomization (p = 1/3)

(d) Driving (= configuration at time t + 1)

Fig. 29 CA configuration used for validation.

• Step 4: Moving ahead (driving). After steps1–3 the new velocity vn for each agent n has beendetermined forward by vn cells: xn → xn + vn.

Figure 29 shows a configuration at time t + 1which is updated step-by-step to obtain the newconfiguration at time t. Step 1 describes the desireof the agents to move ahead as fast as possible (orallowed). Step 2 encodes the interaction betweenthe agents. In this simple model, interactions onlyoccur to avoid accidents. Step 3, in a very simpleway, corresponds to many complex effects that playan important role in real crowd lane. Usually, asingle agent will not move with a constant speed,but there are always small fluctuations of the veloc-ity. An important point is overreactions at braking.An agent that had to decelerate (slowing) in step 2will, with some probability p, decelerate even fur-ther than necessary to avoid a collision. This kind ofimperfect movement can lead to a chain reaction, ifthe density of agents is large enough. In the end, itmight lead to the stopping of an agent which leadsto the creation of a jam. This jams occurs withoutobvious external reason and is therefore called “jamout of nowhere,” “phantom jam” or spontaneousjam. It shows the extreme importance of step 3,which reflects the imperfect behavior of the agents.

Fig. 30 Toolbox crowd setting used for validation.

Fig. 31 CA-trajectories used for validation.

Finally, in step 4, all agents move according to theirnew velocity.

With the use of Visions Of Chaos,36 some simu-lations can be conducted within a toolbox, Fig. 30.Whereas the result is generally served as trajecto-ries graph, Fig. 31.

It is interesting to note that the gradient andthe intercept of the graph resulting from theexperiment are different from the traffic (Fig. 32).The developed model result is not consistently neg-ative gradient. First of all, the approach is not a

1st Reading

September 17, 2008 16:46 00409

Fractal, A Microscopic Crowd Model 15

Fig. 32 Speed and density comparison.

Fig. 33 Flow versus density in CA traffic flow model.

traffic approach with a fixed number of lanes, butit is an adaptive lane both in lane numbers anddirection. Second, the modeled agent characteristicsmay contribute to a difference result from the priorresults. Alternatively, the result may get similar ifthe influenced agent diameter and sight agent dis-tance are adjusted according to the speed applied.

However, a literature 37 also shows that a nega-tive gradient occurred in cellular automata for traf-fic flow model, Fig. 33.

The graph describes the connection between den-sity and flow rate on the lane. When the density islow, that is, agents are far from each other, the flowincreases linearly with increasing density. When thedensity reaches certain value, agents start to “inter-act” with each other, agents become cautious andlower their velocities to maintain a safe distance tothe agent ahead. The lowering of velocities causesthe flow to decrease. If the density still increases,agent velocities will be getting lower and finally theflow rate drops to zero when crowd is completely

jammed. The starting time for agents to interactcould heavily determine the shape of the graph.

5. CONCLUSIONS

The research revealed that the microscopic swarmmodel studies have been successfully applied toexplore the behavior of microscopic agents flow byshowing the three influenced forces representing for-ward velocity, repulsive away of single agent reac-tion, and repulsive away of multi-agents’ reactions.It is clearly shown that fractal could be used toapproach the emerging swarm behavior because theresearch has produced the result that has sharingcharacteristics with crowd microscopic model.

Fractal study presented in this research intro-duces a very significant result in producing a com-plicated pattern specifically for crowd behaviorresearch. The crowd behavior research has beenintroduced and has opened a lot of opportuni-ties for computer scientists to get involved. Theresult from the game of chaos suggests, the moreSTEPS results, the clearer the shape of the Sier-pinski triangle. Simulation results of fractal shap-ing application whether in 2D or 3D would suggestthat random choices will give a deterministic pic-ture. Fractal image compression is recognized as oneof the most effective image compressions.

The microscopic agent simulation model is devel-oped to determine the microscopic characteristics ofswarm. From the simulation results, there is relation-ship between density and agent speed. The relation-ship is influenced by maximum speed and velocitydistributions. The resulting agents paths are stud-ied and compared to paths that are created fromthe fractal. The research demonstrated that frac-tal could be used to approach the emerging swarmbehavior. Since the research has produced the resultthat has shared characteristics with crowd micro-scopic model, modeling swarm with fractal equationwould be potentially conducted in the future.

ACKNOWLEDGMENT

The authors would like to thank Kardi Teknomo,Tohoku University, Japan and the Research Man-agement Centre, Universiti Teknologi Malaysia.

REFERENCES

1. A. J. Ijspeert, A. Martinoli, A. Billard and L. M.Gambardella, Collaboration through the exploita-tion of local interactions in autonomous collective

1st Reading

September 17, 2008 16:46 00409

16 S. Widyarto & M. S. Abd. Latiff

robotics: the stick pulling experiment, Auton. Robots11(2) (2001) 149–171.

2. F. Venutia, L. Brunoa and N. Bellomob, Crowddynamics on a moving platform: mathematical mod-eling and application to lively footbridges, Math.Comput. Model. 45 (2007) 252–269.

3. M. H. Overmars, Recent developments in motionplanning, in Int. Conf. Comput. Sci. 2002, p. 3–13.

4. S. R. Musse, C. R. Jung, J. C. S. Jacques Jr. andA. Braun, Using computer vision to simulate themotion of virtual agents, Comput. Anim. VirtualWorlds 18(2) (2007) 83–93.

5. J. P. Keating, The myth of panic, Fire J. 147 (1982)57–61.

6. D. Elliott and D. Smith, Football stadia disasters inthe United Kingdom: learning from tragedy?, Ind.Environ. Crisis Q. 7(3) (1993) 205–229.

7. D. Helbing and P. Molnar, Social force model forpedestrian dynamics, Phys. Rev. E 51 (1995) 4282–4286.

8. A. Kirchner and A. Schadschneider, Simulation ofevacuation processes using a bionics-inspired cellularautomaton model for pedestrian dynamics, PhysicaA 312 (2002) 260–276.

9. C. M. Henein and T. White, Macroscopic effects ofmicroscopic forces between agents in crowd models,Physica A 373 (2007) 694–712.

10. D. Thalmann, S. R. Musse and M. Kallmann,From individual human agents to crowds, Inform./Inform.-Revue Organ. d’inform. 1(11) (2003) 6–11.

11. D. Helbing, I. Farkas and T. Vicsek, Simulatingdynamical features of escape panic, Nature 407(2000) 487–490.

12. D. Helbing, I. Farkas and T. Vicsek, Freezing byheating in a driven mesoscopic system, Phys. Rev.Lett. 84 (2000) 1240–1243.

13. C. Reynolds, Flocks, herds and schools: a distributedbehavioral model, in Proc. SIGGRAPH’87, Vol. 21,Computer Graphics, July 1987.

14. K. Teknomo, Microscopic pedestrian flow character-istics: development of an image processing data col-lection and simulation model, PhD thesis, TohokuUniversity, Tohoku. Japan (2002).

15. CROW, Asvv: Recommendations for Traffic Provi-sions in Built-Up Areas, Technical Report, Report15 (CROW, 1998).

16. P. N. Daly, F. McGrath and T. J. Annesley, Pedes-trian speed/flow relationships for underground sta-tions, Traffic–Eng. Control 32(2) (1991) 75–78.

17. L. F. Henderson, The statistics of crowd fluids,Nature 229 (1971) 381–383.

18. H. Knoflacher, Fugeher und Fahrradverkehr: Pla-nungsprinzipien, Boehlau Verlag, Vienna (in Ger-man) 1995.

19. P. M. Koushki, Walking characteristics in CentralRiyadh, Saudi Arabia, J. Transport. Eng. 114(6)(1988) 735–744.

20. H. K. Lam, J. F. Morrall and H. Ho, Pedestrian flowcharacteristics in Hong Kong, Transport. Res. Rec.1487 (1995) 56–62.

21. J. F. Morrall, L. L. Ratnayake and P. N. Senevi-ratne, Comparison of central business district pedes-trian characteristics in Canada and Sri Lanka,Transport. Res. Rec. 1294 (1991) 57–61.

22. C. A. O’Flaherty and M. H. Parkinson, Movementon a city centre footway, Traffic Eng. Control 13(1972) 434–438.

23. A. K. Sarkar and K. S. V. S. Janardhan, A study onpedestrian flow characteristics, in Proc. Transport.Res. Board, Washington (CD-R), (1971).

24. Y. Tanariboon, S. S. Hwa and C. H. Chor, Pedes-trian characteristics study in Singapore, J. Trans-port. Eng. ASCE 112(3) (1986) 229–235.

25. Y. Tanariboon and J. A. Guyano, Analysis of pedes-trian movements in bangkok, Transport. Res. Rec.1294 (1991) 52–56.

26. D. Helbing, P. Molnar, I. J. Farkas and K. Bolay,Self-organizing pedestrian movement environmentand planning b, Plann. Des. 28(3) (2001) 361–383.

27. D. Canter (ed.), Fires and Human Behavior (Foul-ton Publishers, London, 1990).

28. G. K. Still, New insights into crowd behavior — it’sfractal, Focus (November 1994).

29. G. K. Still, The secret life of crowds, Focus (June1996).

30. G. K. Still, New computer system can predict humanbehavior response to building fires, Fire 84 (1993)40–41.

31. S. G. Tzafestas, M. P. Tzamtzi and G. G. Rigatos,Robust motion planning and control of mobilerobots for collision avoidance in terrains with mov-ing objects, Math. Comput. Simul. 59(4) (2002)279–292.

32. A. G. Bruzzone and R. Signorile, Crowd controlsimulation in java based environment, in Proc.Int. Conf. Web-Based Model. Simul., San Francisco(CA), USA, 1999.

33. J. C. Russ, Fractal Surfaces (Plenum Press, 1994).34. A. N. Marana, L. F. Costa and R. A. Lotufo,

Estimating crowd density with Minkowski fractaldimension, in IEEE Int. Conf. Acoust. Speech Sig-nal Process., Vol. 6, Arizona, March 1999, pp. 3521–3524.

35. K. Nagel and M. Schreckenberg, A cellular automa-ton model for freeway traffic, J. Phys. I 2 (1992)2221–2228.

36. Internet softology, http://softology.com.au/index.htm, accessed on 23 September 2007.

37. R. Barlovic, L. Santen, A. Schadschneider andM. Schreckenberg, Metastable states in cellularautomata for traffic flow, Eur. Phys. J. B 5 (1998)793–800.