一种具有必经点约束的非结构化环境路径规划方法

Path Planning with Designated-Points Constraints for Unstructured Environment

针对非结构化环境下具有必经点约束的路径规划问题,设计一种两阶段求解方法,并对每一阶段算法做出改进。第1阶段,对典型非结构化环境进行地图建模,针对A-Star算法存在的接触障碍物、路径曲折的问题,提出新的障碍物安全距离方法并设计折线优化策略平滑路径。第2阶段,详细阐述必经点问题的求解流程,建模为旅行商变体问题并将多种优化算法拓展至必经点场景。由于现有方法难以高效求解必经点问题,提出一种改进遗传粒子群(IGPSO)算法,包括分层随机初始化、改进交叉方式以及变异算子。最后进行对比实验验证,结果表明改进算法在最优解成功率、运行时间和迭代次数方面具备明显优势。

Focusing on path planning with designated point constraints in unstructured environments,this study has proposed a two-stage solution method which can improve the algorithm for each stage.In the first stage,map modelling was commissioned on typical unstructured environments.To solve the problems of contacting obstacles and winding paths in the A-Star algorithm,a new obstacle safety distance method was established and a line optimization strategy was developed to smooth the path.In the second stage,the processes of solving the designated-points problem were elaborated in detail,modelling a travel salesman variant problem and extending various optimization algorithms to this scenario.Due to the existing methods’difficulty in effectively solving designated-point problems,an improved Genetic Particle Swarm Optimization(IGPSO)algorithm was proposed,including a hierarchical random initialization,an improved crossover method,and a mutation operator.Finally,comparative experiments were conducted where the significant advantages of the improved algorithm in optimal solution success rate,running time,and number of iterations were verified.