Abstrakt

Improved Ant Colony Algorithms for Multi-agent Path Planning in Web3D Environment

Fengting Yan

The path planning in 3D large-scale scenes is a hard problem. Especially, there are many multi-agents searching their optimal paths in a complex and large-scale 3D scene. This paper improves two kinds of ant colony algorithms and a leader idea to solve the problem. Firstly, an improved 2D ant colony algorithm for flat path planning is proposed. It is a method based on direction to choice a point as the next step point to make path planning precision. Secondly, a classic 3D ant colony algorithm is improved for mountain terrain path planning. We put forward a concept of vertebral visual area, which accelerates the speed of path finding in looking for the next node locked area. At last, a leader idea was given for multi-agent path planning when soldiers are marching in a mountain. And in every improved method, an experiment was done which displayed that the convergence is fast, and the path planning results are efficient, real time and precise.