A path finding simulation model for human crowd using agent based ant colony optimization

• Main Author: Tin Htet Kyaw @ Jame Ng.
• Other Authors: School of Computer Engineering
• Format: Final Year Project
• Language: English
• Published: 2011
• Subjects: DRNTU::Engineering::Computer science and engineering::Computing methodologies::Simulation and modeling
• Online Access: http://hdl.handle.net/10356/44668
• Institution: Nanyang Technological University

Ant Colony Optimization (ACO) is a popular meta-heuristic used to solve NP problems such as TSP and is popular in areas such as Robotic. This paper will study the feasibility of using ACO to plan a path for human crowd simulation. The idea here is not to find only optimal paths, but to find suitable paths for human crowd which can be more than one and not necessarily optimal. As the traditional ACO uses Pheromone convergence to find optimal paths, this paper will look at a Hybrid ACO which incorporates shortest Euclidean distance with the traditional ACO to do path planning. This means that ant in the Hybrid model will move with some influence of choosing shortest Euclidean distance path and converge using the traditional Pheromone method. With the paths found, it can then be used to derive waypoints which can then be used for human agents in a crowd simulation. Experiments conducted compared the performance of the Hybrid ant model with the traditional Pheromone ant model and the extreme Euclidean Distance bias ant model. The performance measures will include the exploration, convergence, and number of ants that found food.