This paper focus on engineering and computer science aspects of development, applications, and resources related to increase the efficiency of crowd simulation using Particle Swarm Optimization. This paper presents the idea of crowd simulation and uniform conceptual model based on Particle Swarm Optimization paradigm to simulate crowd. Particle Swarm Optimization (PSO) is a technique used to explore the search space of a given problem to find the settings or parameters required to maximize a particular objective. This technique first described by James Kennedy and Russell Eberhart in 1995. Finally, resources related to PSO are listed, including books, websites, and software.
INTRODUCTION |
A. Crowd Simulation |
| It is the process of simulating the movement of a large number of objects or characters.Crowd simulation study has
been carried out from different aspects including psychological, sociological and physical aspects. A crowd is not
simply a collection of individuals. It describes the behaviour of an individual may be affected by others in the crowd,
which may depend on various physiological, psychological and social factors. Crowd simulations are highly dynamic
and agents interact with different agents and different regions of the environment. We can use collision avoidance in
crowd simulation with priority rules. For instance, collision avoidance among a large number of individuals in the same
area requires different resolving strategies in comparison with the methods used to avoid collisions between just two
individuals. |
B. Need of Crowd Simulation |
| Simulating crowds offer the advantages of being cost effective as well as allow for total control of each simulated agent
or character. Crowd simulation is a process of simulating the movement of a large number of animated characters,
agents in the virtual environment. Crowd simulation can also refer to simulations based on group behaviour and crowd
psychology, often in public safety planning. In this case, the focus is just the behaviour of the crowd, and not the visual
realism of the simulation. The basic need of crowd simulation is for safety purposes. |
C. Models of Crowd Simulation |
| There are two main types of model for simulating crowd movement. |
| • Macroscopic level: models focus on the model system as a whole and concern collective observable
behaviours which emerge from the crowd e.g., the behaviour of the crowd as a whole. |
| • Microscopic level: models focus on the individual level and concern the behaviour, actions and decisions of
individuals within the crowd and their interactions with others. |
D. Macroscopic Models include the following |
| • Regression Models: These predict pedestrian flow under specific circumstances, dependent on the
infrastructure. For e.g. simple spreadsheet models are an incredibly helpful means of measuring and predicting
flow variables such as ingress and egress rates, flow rate, speed of movement, and density. |
| • Route Choice Models: These describe pedestrian way-finding, based on the basis that pedestrians chose their
route in order to maximize utility, in terms of travel time, effort, comfort, etc. |
E. Microscopic Models includes |
| • Rule-Based Models: This likens crowd behaviours to the movement flocking birds, underpinned by rules of
separation, alignment, cohesion avoidance. |
| • Social Forces Models: Each individual is represented by a self-drive particle subject to social and physical
forces. Accordingly, individuals – each with a certain mass – like to move in a certain direction at a certain
speed, adapting their velocity within a certain time period, whilst keeping their distance from other individuals
and obstacles. |
| • Cellular Automata Models: These divide the environment into a uniform grid of discrete cells with agents
able to move between unoccupied neighbouring cells. |
| • Agent-Based Models: These are the most complex and realistic of the simulation models, wherein a system
(i.e., environment) is modelled as a collection of intelligent, autonomous, decision-making entities known as
„agents‟. |
PARTICLE SWARM OPTIMIZATION |
| The particle swarm optimization (PSO) technique appeared as a promising algorithm for handling the optimization
problems. PSO is a crowd-based optimization technique, inspired by social behaviour of bird flocking or fish
schooling.PSO indicates the no of agent or particle following a simple rule for movement within this search-space,
trying to better its fitness - i.e. the evaluation of a fitness function taking as argument the position of a particle. |
| Particle swarm optimization (PSO) is a newer evolutionary computational method than genetic algorithm and
evolutionary programming. PSO has some common properties of evolutionary computation like randomly searching,
iteration time and so on.PSO simulates the social behaviour of birds: Individual birds exchange information about their
position, velocity and fitness, and the behaviour of the flock is then influenced to increase the probability of migration
to regions of high fitness. Many optimization problems are very complex and hard to solve by conventional gradientbased
techniques, particularly the objective function and constraint are not in closed forms. Particle swarm optimization
(PSO) algorithm attracts many sights around the world due to its powerful searching ability and simplicity. PSO
simulates the swarm behaviour of birds flocking and fish schooling that swarms work in a collaborative manner to
search for foods as efficient and quick as possible. Similar to genetic algorithm or evolutionary algorithm, PSO is also a
population-based optimization technique. PSO searches for optimal solution via collaborating with individuals within a
swarm of population. Each individual, called particle, is made of two parts, the position and velocity, and proceeds
according to two major operations, velocity and position updating rules. Position and velocity represent the candidate
solution and step size, a particle will advance in the next iteration. The particle swarm can be understood as a number
of agents placed in a so called search space, with each agent or particle following a simple rule for movement within
this search-space, trying to better its fitness - i.e. the evaluation of a fitness function taking as argument the position of
a particle. The particles in the swarm exchange information regarding what points of the search space are promising,
thus enabling individual particles to learn from their neighbours as well as themselves. The initial placements and
velocities of the particles are initialized randomly. |
| At time step t the position and velocity of a particle are given by x(t) and v(t) respectively, the update formula for the
velocity being: |
 |
| And then simply adding this to the old position gives the new position: |
 |
| The inertia weight w determines the influence of the previous velocity on the current velocity. First we have to update
the positions and velocities of the particles are initialized to random values within some boundaries. Then until some
criterion is met (e.g. number of iterations or stagnation of fitness) the following is looped: Evaluate fitness for the
particles, then update velocities and positions. |
| A. PSO Algorithm |
| • Initialize each particle with a random velocity and random position. |
| • Calculate the fitness function for each particle. If the current value is lower than the best value is called pBest. |
| • Choose the particle with the lowest value of all particles. The position of this particle is gBest. |
| • Calculate, for each particle, the new velocity and position according to the above equations. |
| • Repeat steps 2-4 until maximum iteration or minimum error criteria is not attained. |
| B. Shortcomings of PSO Algorithm |
| • The major shortcoming of the PSO is that some knowledge of the search space is required to efficiently guide
the swarm and adjust the balance of exploration vs. exploitation. |
| • In order to avoid premature convergence, but still ensuring convergence, the parameters must be selected
according to the problem at hand. While there is some flexibility, it is still highly undesirable in real-world
scenarios to rely on human interaction for the success of PSO. |
| C. Assumptions of PSO Algorithm |
| • Current position. |
| • Velocity (or in some models, probability) |
| • Location of individuals “best” success. |
| • Location of neighbours “best” successes. |
| Therefore, each individual in a population will gradually move towards the “better” areas of the problem space.
Hence, the overall population moves towards “better” areas of the problem space Path finding in crowd simulation is
also a problem to find a particular path to reach to their target. Path planning consists in finding an optimal path
(generally the shortest one) between a starting point and a destination point in a virtual environment, avoiding
obstacles.A crowd simulation model of a long-term phenomenon usually focuses on some intangible social and
psychological characteristics rather than the physical characteristics of the crowd. |
ADVANTAGES OF PSO |
| • PSO is based on the intelligence. It can be applied into both scientific research and engineering use. |
| • PSO have no overlapping and mutation calculation. The search can be carried out by the speed of the particle.
During the development of several generations, only the most optimist particle can transmit information onto the
other particles, and the speed of the researching is very fast. |
| • The calculation in PSO is very simple. Compared with the other developing calculations, it occupies the bigger
optimization ability and it can be completed easily. |
| • PSO adopts the real number code, and it is decided directly by the solution. The number of the dimension is equal
to the constant of the solution. |
DISADVANTAGES OF PSO |
| • The method easily suffers from the partial optimism, which causes the less exact at the regulation of its speed
and the direction. |
| • The method cannot work out the problems of scattering and optimization |
| • The method cannot work out the problems of non-coordinate system, such as the solution to the energy field
and the moving rules of the particles in the energy field. |
CONCLUSION |
| This paper presents the idea of crowd simulation to simulate the crowd movements. We considered that agents finding a
suitable path to reach at their destination by finding the best suitable path by PSO. By the PSO mechanism, each person
can search for a path automatically. However, particles controlled by the original PSO may penetrate obstacles. Hence,
we developed the collision avoidance mechanism in the form of local search to work with PSO. Finally, we have
described a method to add these attention behaviours in order for crowd characters to seem more individual. |
Figures at a glance |
 |
| Figure 1 |
|
References |
- Russell C. Eberhart, Yuhui Shi, “ Partical Swarm Optimization: Development, application and resources” ,2001.
- Ying Yin- Lin,”Crowd simulation with swarm inlelligence” june,2007.
- James Blondin, “Partical Swarm Optimization a tutorial“,2009.
- Leticia C. Cagnina and Susana C. Esquivel “Optimization Techniques in swarm intelligence”2009.
- Daniel Thalmann, Helena Grillon, Jonathan Maim, Barbara Yersin “Challenges in Crowd Simulation”2009.
- Xin Chen and Yangmin Li, “On Convergence and Parameter Selection of an Improved Particle Swarm Optimization”,2008.
- Yongwei Wang Et Al, “Cluster Based Partitioning For Agent-Based Crowd Simulations”,2009.
- Ying-ping Chen*, Ying-yin Lin,” Controlling the movement of crowds in computer graphics by using the mechanism of particle swarmoptimization”,2009.
|
Menu