Dynamic Path Planning Based On Ant Colony Algorithm And Its Simulation Application In Formation

With the development of the world economy,the human society including work,life and education will be going to step into the intelligent era gradually.As an important branch of "intelligent manufacture",the application and development related to intelligent algorithms become more and more popular.What is more,combined with intelligent algorithms and dynamical path programming methods,some new intelligent path programming algorithm designs with wide application prospect which are probably used to deal with some well known issues such as TSP,maritime navigation and unmanned aerial vehicle(uav)formation are also one of the most important developing direction in intelligent manufacture.As one of the important methods among intelligent algorithms,ant colony algorithm is widely used for its easy-to-understand idea and considerable robust performance.As a result,a new trend which combines the path planning with the ant colony algorithm gradually become one of the hot research areas.Considered the bad dynamic performance of the traditional ant colony algorithm when it was applied to dynamic path programming problems,several improved versions which own self-adaptive capacity for different traffic conditions were obtained through embedding some intelligent algorithm ideas such as greedy algorithm into the traditional one.Details of these research contents can be seen as follows:1)Local information dynamic path programming problems with a certain radius were discussed based on region segmentation model and time division model respectively.In the condition that the optimization environments changing as different sub-region or different time slot,two dynamic improved ant colony algorithms were designed where the robot with a fixed research radius was found the optimal feasible path by applying to real-time planning method.Finally,the effectiveness of the proposed algorithm was shown through comparing with the classic ant colony algorithm in the same example.2)Local information dynamic path programming problems with variable radius were discussed based on improved ant colony algorithm.As for the limitation that the local information dynamic path programming method with fixed radius can not self-adjust its research radius according to different environment during the process of path programming,an new local information dynamic path programming method with variable radius is proposed based on improved ant colony algorithm where robot can self-adjust its research radius as different environments.Moreover,comparisons between fixed radius algorithm and variable radius one were done when time division model was chosen.3)The dynamic path planning method based on ant colony algorithm is applied in the multi-agents formation.This dynamic path planning method based on improved ant colony algorithm proposed in this thesis was applied to the formation of multi-agent system.Several problems about path self-programming of multi-agent systems in unknown environment and cooperation among agents were also considered.Moreover,the feasibility and effectiveness of proposed algorithm were shown through simulation results.