A Modified Heuristic Search Algorithm for Pedestrian Simulation

Abstract

A* algorithm is a typical heuristic search algorithm, which is widely used in Game Programming, Artificial Intelligence and robotics. However, AI programmers have found again and again that the standard A* algorithm can be woefully inadequate for achieving realistic movements. A modified A* algorithm is proposed in this paper to solve the pathfinding problem for an Agent-based pedestrian simulation system. First, several heuristic functions are introduced and compared. Second, a "Trimming Algorithm" has been developed to achieve smooth straight-line movements. Third, the problem of the output path "clinging to obstacle" of the standard A* algorithm has been solved by imposing a penalty on the nodes near obstacles in map preprocessing. With these modifications, we can get a more realistic path like a human trail, the feasibility and efficiency having been proved in the simulation tests.