基于改进的A~*算法在三维路径规划中的仿真应用
|
摘要
针对无人机路径规划中全局静态路径优化和局部动态避障的需求,提出一种基于生物神经动力学模型的改进A~*算法实现全局冬天路径规划。建立生物神经动力学模型,并应用该模型实时获取环境中的动态障碍物信息,通过神经元的活性值来引导无人机的局部动态避障。设计了一种A~*算法的优化启发函数,有效地减少A~*算法在全局路径搜索过程中的节点数量,提高A~*算法的全局搜索效率。最后,将生物动力学模型中神经元的活性值融入到A~*算法的实际代价函数中,融合算法保证了A~*算法在全局路径优化的性能,又秉承了生物神经动力学模型的局部实时避障能力。静态路径和动态路径下仿真结果表明:与生物动力学模型相比,该融合算法考虑到实际代花费问题,能够在动态和静态环境下规划出一条低代价的全局路径;与A~*算法相比,该融合算法可提高全局搜索效率,且实现实时动态避障性能。
To meet the requirements of global static path optimization and local dynamic obstacle avoidance in UAV path planning, an improved A~* algorithm based on biological neural dynamics model is proposed to realize global dynamic path planning. First of all, a bio-neuro-dynamics model is established, and the model is used to obtain the dynamic obstacle information in the environment in real time, and the local dynamic obstacle avoidance of the UAV is guided by activity value of the neuron. Then, an A~* algorithm optimizes the heuristic function, effectively reduces the number of nodes in the A~* algorithm in the global path search and improves the global search efficiency of the A~* algorithm; finally, integrates the activity value of the neuron in the biokinetic model into the actual cost function of the A~* algorithm. The fusion algorithm guarantees the performance of the A~* algorithm in the global path optimization, and adheres to the local real-time obstacle avoidance capability of the biological neural dynamics model. The simulation results under static path and dynamic path show that compared with the biokinetic model, the fusion algorithm can take into account the actual cost of generation, and can be used to plan a low-cost global path under dynamic and static conditions. Compared with the A~* algorithm, the fusion algorithm can improve global search efficiency and achieve real-time dynamic obstacle avoidance performance.
To meet the requirements of global static path optimization and local dynamic obstacle avoidance in UAV path planning, an improved A~* algorithm based on biological neural dynamics model is proposed to realize global dynamic path planning. First of all, a bio-neuro-dynamics model is established, and the model is used to obtain the dynamic obstacle information in the environment in real time, and the local dynamic obstacle avoidance of the UAV is guided by activity value of the neuron. Then, an A~* algorithm optimizes the heuristic function, effectively reduces the number of nodes in the A~* algorithm in the global path search and improves the global search efficiency of the A~* algorithm; finally, integrates the activity value of the neuron in the biokinetic model into the actual cost function of the A~* algorithm. The fusion algorithm guarantees the performance of the A~* algorithm in the global path optimization, and adheres to the local real-time obstacle avoidance capability of the biological neural dynamics model. The simulation results under static path and dynamic path show that compared with the biokinetic model, the fusion algorithm can take into account the actual cost of generation, and can be used to plan a low-cost global path under dynamic and static conditions. Compared with the A~* algorithm, the fusion algorithm can improve global search efficiency and achieve real-time dynamic obstacle avoidance performance.
引文
[1]Wu Chaoshuai,Liu Guorong,Zhang Wenli,et al.A*algorithm used in three-dimensional environment for optimal path planning[C].Xiamen,China:International Conference on Automatic Control and Artificial Intelligence(ACAI 2012),2012:5-8.
[2]Ren Tianzhu,Zhou Rui,Xia Jie,et al.Three-dimensional path planning of UAV based on an improved A*algorithm[C].Nanjing,China:Proceedings of 2016 IEEE Chinese Guidance,Navigation and Control Conference(IEEE CGNCC2016),2016:141-146.
[3]李春华,郑昌文,周成平,等.一种三维航迹快速搜索方法[J].宇航学报,2002,23(3):13-17.
[4]史久根,李凯业.基于分层改进D*算法的室内路径规划[J].计算机应用研究,2015,32(12):3609-3612.
[5]Lei W.Multi-model machining path planning based on improved genetic algorithm[J].Journal of Mechanical Engineering,2014,50(11):153.
[6]Pan Jie,Wang Xuesong,Cheng Yuhu.Improved ant colony algorithm for mobile robot path planning[J].Journal of China University of Mining and Technology,2012,41(1):108-113.
[7]Glasius R,Komoda A,Gielen S C A M.Neural network dynamics for patch planning and obstacle avoidance[J].Neural Networks,1995,8(1):125-133.
[8]Zhu A,Yang S X.A neural network approach to dynamic task assignment of multirobots.[J].IEEE Transactions on Neural Networks,2006,17(5):1278-87.
[9]Humphrey L,Cohen K,Rasmussen S.Application of proper orthogonal decomposition and artificial neural networks to multiple UAV task assignment[C].Toronto,Canada:AIAAGuidance,Navigation,and Control Conference.2013:296-300.
[10]Montiel O,Sepúlveda R,Orozco-Rosas U.Optimal path planning generation for mobile robots using parallel evolutionary artificial potential field[J].Journal of Intelligent&Robotic Systems,2015,79(2):237-257.
[11]Seder M,Petrovic I.Dynamic window based approach to mobile robot motion control in the presence of moving obstacles[C].Roma,Italy:Proceedings 2007 IEEE International Conference on Robotics and Automation,2007:1986-1991.
[12]姚远,周兴社,张凯龙,等.基于稀疏A*搜索和改进人工势场的无人机动态航迹规划[J].控制理论与应用,2010,27(7):953-959.
[13]Li Shuai,Guo Yi.Neural-network based AUV path planning in estuary environments[C].Beijing,China:Proceedings of the10th World Congress on Intelligent Control and Automation,2012:3724-3730.
[2]Ren Tianzhu,Zhou Rui,Xia Jie,et al.Three-dimensional path planning of UAV based on an improved A*algorithm[C].Nanjing,China:Proceedings of 2016 IEEE Chinese Guidance,Navigation and Control Conference(IEEE CGNCC2016),2016:141-146.
[3]李春华,郑昌文,周成平,等.一种三维航迹快速搜索方法[J].宇航学报,2002,23(3):13-17.
[4]史久根,李凯业.基于分层改进D*算法的室内路径规划[J].计算机应用研究,2015,32(12):3609-3612.
[5]Lei W.Multi-model machining path planning based on improved genetic algorithm[J].Journal of Mechanical Engineering,2014,50(11):153.
[6]Pan Jie,Wang Xuesong,Cheng Yuhu.Improved ant colony algorithm for mobile robot path planning[J].Journal of China University of Mining and Technology,2012,41(1):108-113.
[7]Glasius R,Komoda A,Gielen S C A M.Neural network dynamics for patch planning and obstacle avoidance[J].Neural Networks,1995,8(1):125-133.
[8]Zhu A,Yang S X.A neural network approach to dynamic task assignment of multirobots.[J].IEEE Transactions on Neural Networks,2006,17(5):1278-87.
[9]Humphrey L,Cohen K,Rasmussen S.Application of proper orthogonal decomposition and artificial neural networks to multiple UAV task assignment[C].Toronto,Canada:AIAAGuidance,Navigation,and Control Conference.2013:296-300.
[10]Montiel O,Sepúlveda R,Orozco-Rosas U.Optimal path planning generation for mobile robots using parallel evolutionary artificial potential field[J].Journal of Intelligent&Robotic Systems,2015,79(2):237-257.
[11]Seder M,Petrovic I.Dynamic window based approach to mobile robot motion control in the presence of moving obstacles[C].Roma,Italy:Proceedings 2007 IEEE International Conference on Robotics and Automation,2007:1986-1991.
[12]姚远,周兴社,张凯龙,等.基于稀疏A*搜索和改进人工势场的无人机动态航迹规划[J].控制理论与应用,2010,27(7):953-959.
[13]Li Shuai,Guo Yi.Neural-network based AUV path planning in estuary environments[C].Beijing,China:Proceedings of the10th World Congress on Intelligent Control and Automation,2012:3724-3730.