考虑运动学约束的不规则目标遗传避碰规划算法
收稿日期: 2014-05-08
修回日期: 2014-06-18
网络出版日期: 2014-07-09
基金资助
国家自然科学基金(61104037, 61304060);国家国际科技合作专项(2013DFR10030);中央高校基本科研业务费专项资金(HEUCFX41304)
Genetic collision avoidance planning algorithm for irregular shaped object with kinematics constraint
Received date: 2014-05-08
Revised date: 2014-06-18
Online published: 2014-07-09
Supported by
National Natural Science Foundation of China (61104037, 61304060); International S & T Cooperation Program of China (2013DFR10030); Fundamental Research Funds for the Central Universities (HEUCFX41304)
针对复杂环境下不规则目标的路径规划问题,提出了一种带有运动学约束的遗传避碰规划算法。以舰载机在航母甲板上的路径规划问题作为研究对象,并且该算法可推广至其他具有此类约束的路径规划问题中,它较好地解决了目标形状复杂、障碍环境复杂、目标运动时带有回转半径约束等特殊问题。在传统遗传路径规划算法的基础上,针对性地设计了三维位置和姿态混合编码、三段法路径解码、轨迹包围盒的碰撞检测及距离计算等方法,并在遗传操作中引入惩罚项和修补策略来辅助算法寻优。最后,为得出复杂环境下的最优路径,基于VC++平台对算法进行了仿真验证。结果表明,在复杂障碍环境下,本文提出的算法可求得最优避碰路径,并满足预先设定的目标回转半径约束,能够有效地解决此类目标的避碰路径规划问题。
张智 , 林圣琳 , 朱齐丹 , 王开宇 . 考虑运动学约束的不规则目标遗传避碰规划算法[J]. 航空学报, 2015 , 36(4) : 1348 -1358 . DOI: 10.7527/S1000-6893.2014.0130
To deal with the path planning problems of irregularly shaped objects in complex environment, a genetic collision avoidance algorithm with kinematics constraint is developed. This algorithm is then applied to the path planning operations on carrier-based aircraft scheduling on carrier flight deck. Moreover, it can be extended to solve other path planning cases under such constraints. For the problems resulting from these objects, which are characterized by complex shape and the bending radius constraint while moving in complicated obstacle situations, the technique proposed is proved to be effective. Based on the traditional genetic path planning algorithm, a three-dimensional position and orientation coding method, a three-stage path decoding method and an approach specific to the collision detection and distance calculation of a track bounding box are presented. Also, a penalty term and a gene repairing strategy are brought into the genetic process to seek the optimum. Finally, simulated verifications are conducted using VC++ platform to obtain the optimal paths. The results show that the optimal collision avoidance paths in complex obstacle environment are achieved utilizing the proposed algorithm, with the pre-set bending radius constraints satisfied. It is indicated that the design yields effective solutions to the collision avoidance path planning problems correlated with this kind of objects.
[1] Xing J J. Behavior dynamics based motion planning of mobile robots in uncertain dynamic environments[J]. Robotics and Autonomous Systems, 2005, 53(2): 99-123.
[2] Romero R A F, Prestes E, Idiart M A P. Locally oriented potential field for controlling multi- robots[J]. Communications in Nolinear Science Numerical Simulation, 2012, 17(12): 4664-4671.
[3] Zhu D Q, Yan M Z. Survey on technology of mobile robot path planning[J]. Control and Decision, 2010, 25(7): 961-967 (in Chinese). 朱大奇, 颜明重. 移动机器人路径规划技术综述[J]. 控制与决策, 2010, 25(7): 961-967.
[4] Tuncer A, Yildirim M. Dynamic path planning of mobile robots with improved genetic algorithm[J]. Computers and Electrical Engineering, 2012, 38(6): 1564-1572.
[5] Bingul Z, Karahan O. A fuzzy logic controller tuned with PSO for 2 DOF robot trajectory control[J]. Expert Systems with Applications, 2011, 38(1): 1017-1031.
[6] Joho D, Senk M, Burgard W. Learning search heuristics for finding objects in structured environments[J]. Robotics and Autonomous Systems, 2011, 59(5): 319-328.
[7] Zhang Y, Gong D W, Zhang J H. Robot path planning in uncertain environment using multi-objective particle swarm optimization[J]. Neuro Computing, 2013, 103(1): 172-185.
[8] Luo X, Fan X P, Yi S, et al. A novel genetic algorithm for robot path planning in environment containing large numbers of irregular obstacles[J]. Robot, 2004, 26(1): 11-16 (in Chinese). 罗熊, 樊晓平, 易晟, 等. 具有大量不规则障碍物的环境下机器人路径规划的一种新型遗传算法[J]. 机器人, 2004, 26(1): 11-16.
[9] Chen G, Shen L C. Genetic path planning algorithm for complex environment path planning[J]. Robot, 2001, 23(1): 40-44 (in Chinese). 陈刚, 沈林成. 复杂环境下路径规划问题的遗传路径规划算法[J]. 机器人, 2001, 23(1): 40-44.
[10] Cai Z X, Peng Z H. The application of a novel path encoding mechanism in path planning for a mobile robot[J]. Robot, 2001, 23(3): 230-233 (in Chinese). 蔡自兴, 彭志红. 一种新的路径编码机制在移动机器人路径规划中的应用[J]. 机器人, 2001, 23(3): 230-233.
[11] Vemuri B C. Efficient and accurate collision detection for granular flow simulation[J]. Graphical Models and Image Processing, 1998, 60(2): 403-422.
[12] Hubbard P M. Collision detection for intersection graphics application[J]. IEEE Transactions on Visualization and Computer Graphics, 1995, 1(3): 218-230.
[13] Toussaint G T. A simple linear algorithm for intersecting convex polygons[J]. The Visual Computer, 1985, 6(1): 118-123.
[14] Edelsbrunner H. Computing the extreme distances between two convex polygons[J]. Journal of Algorithms, 1985, 6(2): 213-224.
[15] Zhang Z, Lin S L, Xia G H, et al. Collision avoidance path planning for an aircraft in scheduling process on deck[J]. Journal of Harbin Engineering University, 2014, 35(1): 9-15 (in Chinese). 张智, 林圣琳, 夏桂华, 等. 舰载机甲板调运过程避碰路径规划研究[J]. 哈尔滨工程大学学报, 2014, 35(1): 9-15.
/
| 〈 |
|
〉 |
CJA