栅格编码新方法在机器人路径规划中的应用

Application of path encoding novel mechanism based on grids in path planning for mobile robot

基于遗传算法的移动机器人路径规划技术,提出了一种新的定长十进制路径编码机制.在对移动机器人的环境进行有效栅格剖分后,将障碍物表示为以栅格为基础的多边形,每个障碍物多边形的顶点对应于栅格线交点的惟一编号;随后将移动机器人的路径编码成以栅格地图上所有多边形有效顶点数之和为定长的十进制编码串,串中非零位上的十进制值对应着规划路径中途经障碍物多边形的顶点,各顶点在串中的顺序对应着其在规划路径中的顺序.所提出的编码方式拥有定长十进制编码机制通用性好的优点,并且基于此编码的遗传算法很容易克服路径规划算法中的障碍陷阱,使得路径规划算法更加简单有效,加快了遗传算法的收敛速度.

For genetic algorithm based on the technology of path planning of mobile robot, a novel fixed-length decimal encoding mechanism is proposed. Robot＇s motion environment was divided by effective grids. Then the obstacles can be described as polygons based on the grids. The only vertexes of every polygon have the corresponding decimal by the cross of the grids. After that, the paths are encoded into decimal data, which equal to the amount of all vertexes of polygons in grids. In the chromosome, each nonzero bit is the code of a vertex about corresponding obstacle for the path planning. The order of vertexes in a chromosome is that in a path. Such an encoding mechanism has excellent suitability of the fixed-length decimal encoding; it also easily overcomes the trap of the obstacles in path planning. The algorithm makes the path planning more simple and effective.