Path Planning with Designated-Points Constraints for Unstructured Environment
DONG Dejin1，2， FAN Yunfeng3， CAI Yunze1，2
1. Department of Automation， Shanghai Jiao Tong University， Shanghai 200240，China；
2. Key Laboratory of System Control and Information Processing， Ministry of Education of China， Shanghai 200240，China；
3. Shanghai Electro-Mechanical Engineering Institute， Shanghai 201109，China
Abstract 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.
2024, Vol. 7 
