基于遗传算法的多机器人系统集中协调式路径规划

 根据多机器人系统无碰撞运动的需要,对其工作空间进行了分解,确定了机器人运行路线上的各个可能路径点,从而得到了规划空间的多路径点链接图描述。基于这种对规划空间的链接图建模描述,开发了一种混合遗传算法用于寻找多个机器人的无碰撞协调运动路线。仿真结果表明,这种方法可有效地解决复杂规划空间下的多机器人路径规划问题。

A CENTRALIZED COORDINATED PATH PLANNING METHOD BASED ON GENETIC ALGORITHM FOR MULTIPLE MODILE ROBOTS

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.