关键词: 路径规划, 遗传算法, 多机器人系统

Abstract:

A multiple robot system can be used to perform the tasks which are hard to be done or can not be done by a single robot. This paper, taking multiple mobile robots as researching objects, systematically studied the path planning method by means of GA(genetic algorithm), which is a probabilistic search algorithm based on the mechanics of natural selection and natural genetics. This paper has presented a new model of environment, which is called Multiple Path Nodes MAKLINK Graph (MAKing LINK Graph). In this model, the free space is decomposed by trapezoid and the multiple path nodes are set in each decomposing line, which makes it possible to generate a coordinated path where any robot can not interfere or collide with other robots. Based on this model, a new testing algorithm is also proposed for judging path interference, which can shorten the testing time. For multiple mobile robots, this paper has presented a new path planning method, which is called Centralized Coordinated Planning Method via GA. This method takes all robots as a whole and generates their moving paths simultaneously. In this method, a binary coded string is used to present a path, and a hybrid GA(which is a hybrid of SGA and FORD algorithms) is used to generate moving paths. Results of simulation show that this path planning method can be used to generate moving paths in the complex environment for multiple robots.

Key words: path planning, genetic algorithms, multiplerobots system