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

Path Planning with Designated-Points Constraints for Unstructured Environment

作　　者：董德金 范云锋 蔡云泽[1,2] DONG Dejin;FAN Yunfeng;CAI Yunze(Department of Automation,Shanghai Jiao Tong University,Shanghai 200240,China;Key Laboratory of System Control and Information Processing,Ministry of Education of China,Shanghai 200240,China;Shanghai Electro-Mechanical Engineering Institute,Shanghai 201109,China)

机构地区：[1]上海交通大学自动化系,上海200240 [2]系统控制与信息处理教育部重点实验室,上海200240 [3]上海机电工程研究所,上海201109

出　　处：《空天防御》2024年第1期71-80,共10页Air & Space Defense

基　　金：中国航天科技集团有限公司第八研究院产学研合作基金(USCAST2022-11)。

摘　　要：针对非结构化环境下具有必经点约束的路径规划问题,设计一种两阶段求解方法,并对每一阶段算法做出改进。第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.

关 键 词：路径规划 必经点 A-STAR算法 遗传粒子群算法 

分 类 号：TP242[自动化与计算机技术—检测技术与自动化装置]