机器人路径规划的栅格模型构建与蚁群算法求解

Grid Model and Ant Colony Algorithm for Robot Path Planning

针对二维平面上机器人路径规划问题,利用具有二元信息的栅格描述机器人移动环境,再以最短路径为目标,考虑移位约束、避碰约束、运动约束等约束条件,构建机器人路径规划的栅格模型。为降低模型计算复杂度,将其转化为混合整数线性规划模型,并用GAMS/Cplex找到小规模问题的全局最优解,验证模型有效性。为快速求解大规模问题的近优解,利用蚁群算法的进化机制,融合多路径选择和概率选择策略,寻找最短行走路径。实验结果表明,所提出的模型及算法能有效求解机器人路径规划问题。

For the two-dimensional plane robot path planning,the moving environment of the robot is described by the grid with binary information. The robot path planning raster model is built to obtain the shortest path considering shifting constraints,collision avoidance constraints,kinematic constraints and other constraints. The model is transformed into a mixed integer linear programming model so as to decrease the complexity. The globally optimal solution is obtained by GAMS/Cplex for the small scale of the problem. Multipath selection strategy and probability selection strategy are integrated into the evolutionary mechanism of the ant colony algorithm so as to solve large-scale problems quickly and find the shortest path.Experimental results show that the proposed model and algorithm can effectively solve the robot path planning.