带动态障碍区的自由区域路径实时优化问题的混合算法
|
摘要
自由区域路径优化问题可以在除障碍区之外的整个区域内自由规划路径,为了解决带动态障碍区的自由区域路径实时优化问题,提出了一种遗传算法(GA)加滑动地平线控制(RHC)的混合算法。首先,建立和讨论了带动态障碍区的自由区域路径实时优化问题的数学模型。然后,详细描述了提出的遗传算法加滑动地平线策略的混合算法,阐述了混合算法中滑动地平线控制与遗传算法结合的关键步骤之一:可变长度染色体的设计。全面探讨了混合算法中滑动地平线长度的选择对于混合算法的影响,说明了滑动地平线控制策略中不同终端加权设计的路径优化效果,并通过终端加权的设计,以保证路径规划的可行性和优化性能。仿真结果表明,遗传算法(GA)加滑动地平线控制(RHC)的混合算法非常有效,在确定性的环境条件下,获得与现有GA算法几乎相同的求解性能,而在动态和不确定的环境下,新算法则取得了更佳的求解效果。在这两种情况下,带RHC的混合算法的在线计算时间是单纯GA算法的一小部分。
The issue of path optimization of free area can be made freely in the entire area except the obstacle area. In order to solve the issue of real-time path optimization in free area with dynamic obstacles,a hybrid algorithm integrating Genetic Algorithm(GA) with Receding Horizon Control(RHC) is proposed. To begin with,a mathematical model for the issue of real-time path optimization in free area with dynamic obstacles is established and discussed. Furthermore,the details of the proposed hybrid algorithm based on GA with RHC is described. One of the key steps in the combination between RHC and GA in the hybrid algorithm is described: the design of variable length chromosomes. The influence of the selection of the receding horizon length on the hybrid algorithm is discussed comprehensively. Then,the path optimization effect of different terminal weighting designs in RHC strategy is illustrated,and the design of the terminal weighting is performed to ensure that the route planning is feasible and optimal. The simulation result illustrates that(1)the hybrid algorithm that combining GA and RHC is very efficient,it works better in a dynamic and uncertain environment than in the certain environment when achieving almost the same optimal solution as an existing GA algorithm. In both cases;(2) the online computing time of the hybrid algorithm with RHC is a small part of the pure GA algorithm.
The issue of path optimization of free area can be made freely in the entire area except the obstacle area. In order to solve the issue of real-time path optimization in free area with dynamic obstacles,a hybrid algorithm integrating Genetic Algorithm(GA) with Receding Horizon Control(RHC) is proposed. To begin with,a mathematical model for the issue of real-time path optimization in free area with dynamic obstacles is established and discussed. Furthermore,the details of the proposed hybrid algorithm based on GA with RHC is described. One of the key steps in the combination between RHC and GA in the hybrid algorithm is described: the design of variable length chromosomes. The influence of the selection of the receding horizon length on the hybrid algorithm is discussed comprehensively. Then,the path optimization effect of different terminal weighting designs in RHC strategy is illustrated,and the design of the terminal weighting is performed to ensure that the route planning is feasible and optimal. The simulation result illustrates that(1)the hybrid algorithm that combining GA and RHC is very efficient,it works better in a dynamic and uncertain environment than in the certain environment when achieving almost the same optimal solution as an existing GA algorithm. In both cases;(2) the online computing time of the hybrid algorithm with RHC is a small part of the pure GA algorithm.
引文
[1]CORMEN T H,LEISERSON C E,RIVEST R L,et al.Introduction to Algorithms[M].2nd ed.Cambridge:MIT Press and Mc Graw-Hill,2001.
[2]韩雪,刘英舜,郭唐仪.城市轨道交通网络中断下的有效路径搜索模型[J].公路交通科技,2015,32(10):97-101.HAN Xue,LIU Ying-shun,GUO Tang-yi.A Valid Path Searching Model for Interrupted Urban Rail Transit Network[J].Journal of Highway and Transportation Research and Development,2015,32(10):97-101.
[3]WICKENS C D,MAVOR AS,PARASURAMAN R,et al.Airspace System Integration:The Concept of Free Flight[M].Washington:National Academy Press,1998.
[4]KAHNE S.Research Issues in the Transition to Free Flight[J].Annual Reviews in Control,2000,24(1):21-29.
[5]MCLEAN D.Operational Requirements for Fully Automatic Flight[J].Aircraft Engineering and Aerospace Technology,2003,75(6):570-574.
[6]胡晓明,李万莉,朱为国,等.半挂液罐车的避障运动仿真分析[J].公路交通科技,2013,30(7):151-158.HU Xiao-ming,LI Wan-li,ZHU Wei-guo,et al.Simulation of Obstacle Avoidance Motion of Liquid Tank Semi-trailer[J].Journal of Highway and Transportation Research and Development,2013,30(7):151-158.
[7]GESER A,MUNOZ C.A Geometric Approach to Strategic Conflict Detection and Resolution[C]//AIAA/IEEE Digital Avionics for Commercial and Military SystemsProceedings.Irvine,US:Institute of Electrical and Electronics Engineers Inc,2002.
[8]PALLOTTINO L,BICCHI A,PANCANTI S.Safety of a Decentralized Scheme for Free-flight ATMS Using Mixed Integer Linear Programming[C]//Proceedings of the American Control Conference.Anchorage,US:Institute of Electrical and Electronics Engineers Inc,2002:742-747.
[9]GRANGER G,DURAND N,ALLIOT J M.Token Allocation Strategy for Free-flight Conflict Solving[C]//Proceedings of Innovative Applications of Artificial Intelligence.Seattle,US:American Association for Artificial Intelligence,2001:59-64.
[10]OH J H.SDP Relaxation Approach to Air Traffic Control Under Free Flight[C]//Proceedings of the 1999 IEEE International Conference on Control Applications.Kohala Coast,US:IEEE,1999:158-163.
[11]SHEWCHUN J M,OH J H,FERON E.Linear Matrix Inequalities for Free Flight Conflict Problems[C]//Proceedings of the 36th IEEE Conference on Decision and Control.San Diego,US:IEEE,1997:2417-2422.
[12]DURAND N,ALLIOT J M,CHANSOU O.Optimal Resolution of En Route Conflicts[J].Air Traffic Control Quarterly,2001,3(3):253-264.
[13]WARREN A.Methodology and Initial Results Specifying Requirements for Free Flight Transitions[C]//15th AIAA/IEEE Digital Avionics Systems Conference.Atlanta:IEEE,1996:87-93.
[14]PLAETTNER H,JOACHIM K,ZHAO Y Y J,et al.A Modularized Approach for Comprehensive Air Traffic System Simulation[C]//AIAA Guidance,Navigation,and Control Conference and Exhibit.Denver:American Institute of Aeronautics and Astronautics Inc,2000.
[15]MCDONALD J A,ZHAO Y.Time Benefits of Free-flight for a Commercial Aircraft[C]//AIAA Guidance,Navigation,and Control Conference and Exhibit.Devner:American Institute of Aeronautics and Astronautics Inc,2000.
[16]ANDREATTA G,BRUNETTA L,GUASTALLA G.From Ground Holding to Free Flight:An Exact Approach[J].Transportation Science,2000,34(4):394-401.
[17]HU X B,WU S F,JIANG J.On-line Free-flight Path Optimization Based on Improved Genetic Algorithms[J].Engineering Applications of Artificial Intelligence,2004,17(8):897-907.
[18]CLARKE D.Advances in Model-based Predictive Control[M].New York:Oxford University Press,1994.
[19]DE SCHUTTER B,VAN DEN BOOM T.Model Predictive Control for Max-plus-linear Discrete Event Systems[J].Automatica,2001,37(7):1049-1056.
[20]CHAND S,HSU V N,SETHI S.Forecast,Solution,and Rolling Horizons in Operations Management Problems:A Classified Bibliography[J].Manufacturing&Service Operations Management,2002,4(4):25-43.
[21]HU X B,CHEN W H.Receding Horizon Control for Aircraft Arrival Sequencing and Scheduling[J].IEEE Transaction on Intelligent Transportation System,2005,6(2):189-197.
[22]胡小兵,吴树范,江驹.民航飞机飞行航线动态实时优化仿真研究[J].计算机仿真,2001,18(3):80-83.HU Xiao-bing,WU Shu-fan,JIANG Ju.The Simulation Study On On-line Real-time Optimization of Commercial Aircraft's Flight Paths[J].Computer Simulation,2001,18(3):80-83.
[2]韩雪,刘英舜,郭唐仪.城市轨道交通网络中断下的有效路径搜索模型[J].公路交通科技,2015,32(10):97-101.HAN Xue,LIU Ying-shun,GUO Tang-yi.A Valid Path Searching Model for Interrupted Urban Rail Transit Network[J].Journal of Highway and Transportation Research and Development,2015,32(10):97-101.
[3]WICKENS C D,MAVOR AS,PARASURAMAN R,et al.Airspace System Integration:The Concept of Free Flight[M].Washington:National Academy Press,1998.
[4]KAHNE S.Research Issues in the Transition to Free Flight[J].Annual Reviews in Control,2000,24(1):21-29.
[5]MCLEAN D.Operational Requirements for Fully Automatic Flight[J].Aircraft Engineering and Aerospace Technology,2003,75(6):570-574.
[6]胡晓明,李万莉,朱为国,等.半挂液罐车的避障运动仿真分析[J].公路交通科技,2013,30(7):151-158.HU Xiao-ming,LI Wan-li,ZHU Wei-guo,et al.Simulation of Obstacle Avoidance Motion of Liquid Tank Semi-trailer[J].Journal of Highway and Transportation Research and Development,2013,30(7):151-158.
[7]GESER A,MUNOZ C.A Geometric Approach to Strategic Conflict Detection and Resolution[C]//AIAA/IEEE Digital Avionics for Commercial and Military SystemsProceedings.Irvine,US:Institute of Electrical and Electronics Engineers Inc,2002.
[8]PALLOTTINO L,BICCHI A,PANCANTI S.Safety of a Decentralized Scheme for Free-flight ATMS Using Mixed Integer Linear Programming[C]//Proceedings of the American Control Conference.Anchorage,US:Institute of Electrical and Electronics Engineers Inc,2002:742-747.
[9]GRANGER G,DURAND N,ALLIOT J M.Token Allocation Strategy for Free-flight Conflict Solving[C]//Proceedings of Innovative Applications of Artificial Intelligence.Seattle,US:American Association for Artificial Intelligence,2001:59-64.
[10]OH J H.SDP Relaxation Approach to Air Traffic Control Under Free Flight[C]//Proceedings of the 1999 IEEE International Conference on Control Applications.Kohala Coast,US:IEEE,1999:158-163.
[11]SHEWCHUN J M,OH J H,FERON E.Linear Matrix Inequalities for Free Flight Conflict Problems[C]//Proceedings of the 36th IEEE Conference on Decision and Control.San Diego,US:IEEE,1997:2417-2422.
[12]DURAND N,ALLIOT J M,CHANSOU O.Optimal Resolution of En Route Conflicts[J].Air Traffic Control Quarterly,2001,3(3):253-264.
[13]WARREN A.Methodology and Initial Results Specifying Requirements for Free Flight Transitions[C]//15th AIAA/IEEE Digital Avionics Systems Conference.Atlanta:IEEE,1996:87-93.
[14]PLAETTNER H,JOACHIM K,ZHAO Y Y J,et al.A Modularized Approach for Comprehensive Air Traffic System Simulation[C]//AIAA Guidance,Navigation,and Control Conference and Exhibit.Denver:American Institute of Aeronautics and Astronautics Inc,2000.
[15]MCDONALD J A,ZHAO Y.Time Benefits of Free-flight for a Commercial Aircraft[C]//AIAA Guidance,Navigation,and Control Conference and Exhibit.Devner:American Institute of Aeronautics and Astronautics Inc,2000.
[16]ANDREATTA G,BRUNETTA L,GUASTALLA G.From Ground Holding to Free Flight:An Exact Approach[J].Transportation Science,2000,34(4):394-401.
[17]HU X B,WU S F,JIANG J.On-line Free-flight Path Optimization Based on Improved Genetic Algorithms[J].Engineering Applications of Artificial Intelligence,2004,17(8):897-907.
[18]CLARKE D.Advances in Model-based Predictive Control[M].New York:Oxford University Press,1994.
[19]DE SCHUTTER B,VAN DEN BOOM T.Model Predictive Control for Max-plus-linear Discrete Event Systems[J].Automatica,2001,37(7):1049-1056.
[20]CHAND S,HSU V N,SETHI S.Forecast,Solution,and Rolling Horizons in Operations Management Problems:A Classified Bibliography[J].Manufacturing&Service Operations Management,2002,4(4):25-43.
[21]HU X B,CHEN W H.Receding Horizon Control for Aircraft Arrival Sequencing and Scheduling[J].IEEE Transaction on Intelligent Transportation System,2005,6(2):189-197.
[22]胡小兵,吴树范,江驹.民航飞机飞行航线动态实时优化仿真研究[J].计算机仿真,2001,18(3):80-83.HU Xiao-bing,WU Shu-fan,JIANG Ju.The Simulation Study On On-line Real-time Optimization of Commercial Aircraft's Flight Paths[J].Computer Simulation,2001,18(3):80-83.