基于滚动时域MILP的小型无人机航迹规划
|
摘要
本文研究了小型无人直升机的航迹规划，建立了基于滚动时域控制和混合整数线性规划（RHC-MILP）的航迹优化算法。这种算法特别适用于环境事先未知，需要在线逐渐探测的情形。本文利用数学规划建模语言AMPL以及采用高性能的商业优化求解软件CPLEX进行计算机仿真验证。仿真结果表明，对于一个复杂环境下的航迹规划问题，基于RHC-MILP的航迹优化算法能够实时求解出满足飞行器动态的最优航迹。本文从以下几个方面进行了研究。
首先，本文研究了飞行器在城市环境中飞行的航迹规划。讨论了三维建筑物作为障碍物的障碍物回避。建立了基于RHC-MILP的航迹规划算法。通过引入逻辑变量和连续变量的混合形式的线性约束来描述障碍物回避约束，对飞行器的动态特性进行线性近似，以最小时间和其它性能指标作为代价函数，建立混合整数线性规划，并采用滚动时域控制策略求解，仿真结果显示此算法能够实时规划最优航迹。
第二，本文研究了飞行器在山地环境中飞行的航迹规划。讨论了飞行器实现地形回避和地形跟随的方法。建立了基于RHC-MILP的航迹规划算法。本文提出一个新的方法—结合不规则三角网（TIN）和MILP描述地形回避。通过在代价函数中增加一项高度代价，选取适当的权因子，实现地形跟随。采用滚动时域控制策略，以及在地形回避约束中只考虑优化时间窗口范围内的局部地形，极大地减少求解时间。基于随机地形的仿真验证了算法的实时性和有效性。
第三，本文研究了直升机三维机动飞行的航迹规划。把飞行器在悬停，前飞等飞行模态之间的切换和各机动动作建模为混合自动机，把航迹最优化问题看作一个序列决策过程。用连续决策变量实现各飞行模态的连续优化，模态选择、模态切换和机动动作的触发通过逻辑决策变量来实现。此决策问题可以采用基于混合整数线性规划的优化算法解决。
最后本文研究了多飞行器的协调飞行航迹规划。建立了基于DRHC-MILP的航迹规划算法。采用分布式滚动时域控制策略，把多飞行器组成的飞行编队的航迹规划问题，分解成多个单一飞行器的航迹优化子问题。飞行编队中的每一个飞行器在线求解一个小规模的优化子问题而规划其自身的飞行轨迹，各单个飞行器作出的规划轨迹除了满足地形回避，还满足碰撞回避。各优化子问题通过分组可以并行计算。
This thesis studies the trajectory planning for the small-scale unmanned helicopters andpresents several trajectory optimization algorithms based on Receding Horizon Control andMixed Integer Linear Programming(RHC-MILP). The algorithms are specially suitable for thecase that environment is unknown ahead of time and needs to explore online. The algorithms aretested and demonstrated by computer simulation with the mathematical programming languageAMPL and the powerful commercial optimization solver CPLEX. The simulation results showthat, for the trajectory planning of the vehicles in complicated environment, the algorithms areapplicable of computing optimal trajectories in real-time. The research fields in this thesis areas follows.
Firstly, the thesis studies the trajectory planning for the vehicles ?ying in the city. Theobstacle-avoidance is discussed which the obstacles is 3-dimension buildings. The algorithmof trajectory planning based on RHC-MILP is presented. The obstacle-avoidance constraintscan be formulated as linear constraints by introducing logic variables combining continuousvariables. The dynamics of the vehicles is linearly approximated. The cost function is aboutminimal time or/and other performance index. Then trajectory optimization problem can be for-mulated as MILP forms. By solving the MILP and using receding horizon strategy, an optimaltrajectory from start to goal is planned online. The simulation result shows that the algorithmcan produce optimal trajectory in real time.
Secondly, the thesis studies the trajectory planning for the vehicles ?ying in the moun-tainous region. The terrain-avoidance and terrain-following of vehicles are discussed. Thealgorithm of the trajectory planning based on RHC-MILP is presented. A novel method is usedthat combines triangulated irregular network(TIN) and MILP describing terrain-avoidance. Thecost function has an item about the altitude cost, a suitable weight could keep the trajectory ofthe vehicle follows the terrain. By taking receding horizon strategy, and only considering thelocal terrain within the planning horizon, the computing time is greatly reduced. The simulationbased on random terrain demonstrates the the real-timeness and validness of the algorithm.
Thirdly, the thesis studies the trajectory planning of agile vehicles. The transition amonghover, cruise and other ?ight modes as well as maneuvers are modeled as an automata. Tra-jectory planning is viewed as a sequential decision process. The continuous decision variablesare associated with the optimization of the ?ight modes, while logic decision variables are as-sociated with mode-choosing, mode-transition and maneuver execution. The guidance decisionproblem can be formulated as the MILP form.
Finally, this thesis studies the trajectory planning for multi-vehicle’s cooperative ?ights.The algorithm of the trajectory planning based on DRHC-MILP is presented. The distributedalgorithm of the trajectory optimization for multi-vehicle ?eet breaks the optimization intosmaller subproblems. Each vehicle in the ?eet plans its trajectory by solving a reduced sizeoptimization problem online. Each trajectory planed by the single vehicle satisfies all con-strains of collision avoidances as well as terrain avoidances. The optimization subproblems canbe solved within a group in parallel.
首先，本文研究了飞行器在城市环境中飞行的航迹规划。讨论了三维建筑物作为障碍物的障碍物回避。建立了基于RHC-MILP的航迹规划算法。通过引入逻辑变量和连续变量的混合形式的线性约束来描述障碍物回避约束，对飞行器的动态特性进行线性近似，以最小时间和其它性能指标作为代价函数，建立混合整数线性规划，并采用滚动时域控制策略求解，仿真结果显示此算法能够实时规划最优航迹。
第二，本文研究了飞行器在山地环境中飞行的航迹规划。讨论了飞行器实现地形回避和地形跟随的方法。建立了基于RHC-MILP的航迹规划算法。本文提出一个新的方法—结合不规则三角网（TIN）和MILP描述地形回避。通过在代价函数中增加一项高度代价，选取适当的权因子，实现地形跟随。采用滚动时域控制策略，以及在地形回避约束中只考虑优化时间窗口范围内的局部地形，极大地减少求解时间。基于随机地形的仿真验证了算法的实时性和有效性。
第三，本文研究了直升机三维机动飞行的航迹规划。把飞行器在悬停，前飞等飞行模态之间的切换和各机动动作建模为混合自动机，把航迹最优化问题看作一个序列决策过程。用连续决策变量实现各飞行模态的连续优化，模态选择、模态切换和机动动作的触发通过逻辑决策变量来实现。此决策问题可以采用基于混合整数线性规划的优化算法解决。
最后本文研究了多飞行器的协调飞行航迹规划。建立了基于DRHC-MILP的航迹规划算法。采用分布式滚动时域控制策略，把多飞行器组成的飞行编队的航迹规划问题，分解成多个单一飞行器的航迹优化子问题。飞行编队中的每一个飞行器在线求解一个小规模的优化子问题而规划其自身的飞行轨迹，各单个飞行器作出的规划轨迹除了满足地形回避，还满足碰撞回避。各优化子问题通过分组可以并行计算。
This thesis studies the trajectory planning for the small-scale unmanned helicopters andpresents several trajectory optimization algorithms based on Receding Horizon Control andMixed Integer Linear Programming(RHC-MILP). The algorithms are specially suitable for thecase that environment is unknown ahead of time and needs to explore online. The algorithms aretested and demonstrated by computer simulation with the mathematical programming languageAMPL and the powerful commercial optimization solver CPLEX. The simulation results showthat, for the trajectory planning of the vehicles in complicated environment, the algorithms areapplicable of computing optimal trajectories in real-time. The research fields in this thesis areas follows.
Firstly, the thesis studies the trajectory planning for the vehicles ?ying in the city. Theobstacle-avoidance is discussed which the obstacles is 3-dimension buildings. The algorithmof trajectory planning based on RHC-MILP is presented. The obstacle-avoidance constraintscan be formulated as linear constraints by introducing logic variables combining continuousvariables. The dynamics of the vehicles is linearly approximated. The cost function is aboutminimal time or/and other performance index. Then trajectory optimization problem can be for-mulated as MILP forms. By solving the MILP and using receding horizon strategy, an optimaltrajectory from start to goal is planned online. The simulation result shows that the algorithmcan produce optimal trajectory in real time.
Secondly, the thesis studies the trajectory planning for the vehicles ?ying in the moun-tainous region. The terrain-avoidance and terrain-following of vehicles are discussed. Thealgorithm of the trajectory planning based on RHC-MILP is presented. A novel method is usedthat combines triangulated irregular network(TIN) and MILP describing terrain-avoidance. Thecost function has an item about the altitude cost, a suitable weight could keep the trajectory ofthe vehicle follows the terrain. By taking receding horizon strategy, and only considering thelocal terrain within the planning horizon, the computing time is greatly reduced. The simulationbased on random terrain demonstrates the the real-timeness and validness of the algorithm.
Thirdly, the thesis studies the trajectory planning of agile vehicles. The transition amonghover, cruise and other ?ight modes as well as maneuvers are modeled as an automata. Tra-jectory planning is viewed as a sequential decision process. The continuous decision variablesare associated with the optimization of the ?ight modes, while logic decision variables are as-sociated with mode-choosing, mode-transition and maneuver execution. The guidance decisionproblem can be formulated as the MILP form.
Finally, this thesis studies the trajectory planning for multi-vehicle’s cooperative ?ights.The algorithm of the trajectory planning based on DRHC-MILP is presented. The distributedalgorithm of the trajectory optimization for multi-vehicle ?eet breaks the optimization intosmaller subproblems. Each vehicle in the ?eet plans its trajectory by solving a reduced sizeoptimization problem online. Each trajectory planed by the single vehicle satisfies all con-strains of collision avoidances as well as terrain avoidances. The optimization subproblems canbe solved within a group in parallel.
引文
[1] R.E.Zelenka. Result from the NASA automatic nap-of-the-earth program[J]. Journal ofthe American Helicopter Society, 1997, 18(2):107–115.
[2] J.Reif. Complexity of the Mover’s Problem and Generalization[M]. New Jersey: AblexPublishing Corporation, 1987.
[3] Y.Hwing, N.Ahujia. Gross motion planning–a survey[J]. ACM Computing Survey,1992, 24(3):219–291.
[4] J.C.Latombe. Robot Motion Planning[M]. Boston: Kluwer Academic Publishers, 1991.
[5]丁明跃,郑昌文,周成平等.无人飞行器航迹规划[M].北京:电子工业出版社，2009.
[6]郑昌文.飞行器航迹规划方法研究[D].武汉:华中科技大学, 2003.
[7]韩志刚.低空突防路径规划方法综述[J].飞行力学, 2002, 20(3):1–4.
[8]张颖.机器人路径规划方法综述[J].控制工程, 2003, 10(增):152–155.
[9]成伟明,唐振民,赵春霞,等.移动机器人路径规划中的图方法应用综述[J].工程图学学报, 2008, 4:6–14.
[10] T.Asano, L.Guibas, J.Hershberger, et al. Visibility-polygon search and Euclidean shortestpath[C]//In Proc. of the 26th Annual Symposium on the Foundations of ComputerScience. Portland: OR, 1985:155–164.
[11] F.Aurenhammer. Voronoi diagrams– a survey of fundamental geometric data structure[J]. ACM Computing Surveys, 1991, 23(3):345–405.
[12] D.Kirkpatrick. Efficient computation of continuous skeletons[C]//In The Proceedingsof the 20th Annual Symposium on Foundations of Computer Science. San Juan: PuertoRico, 1979:18–27.
[13] D.T.Lee, L.Robert, R.L.Drysdale. Generalization of Voronoi diagrams in the plane[J].SIAM Journal of Computing, 1981, 10(1):73–87.
[14] C.K.Yap. An O(nlogn)algorithm for the Voronoi diagram of a set of simple curve segments[R]. Technical Report. No.43: Courant Institute,Robotics Laboratory,New YorkUniversity,1985.
[15] J.F.Canny, B.R.Donald. Simplified Voronoi Diagram[C]//In The Proceedings of the3rd Annual ACM Symposium on Computational Geometry. New York: ACM press,1987:153 161.
[16] J.F.Canny. A new algebraic method for robot motion planning and real geometry[C]//InThe Proceedings of the 28th IEEE Symposium on Foundations of Computer Science.Los Angeles: , 1987:39–48.
[17] J.F.Canny, M.Lin. An opportunistic global path planner[J]. Algorithmica, 1993, 10(2-4):102 120.
[18] L.Kavraki, J-C.Latombe. Randomized preprocessing of configuration space for fast pathplanning[C]//In The Proceedings of the IEEE International Conference on Robotics andAutomation. San Diego: CA, 1994:2138–2139.
[19] M.Overmars, P.Svestka. A probabilistic learning approach to motion planning[R]. TechnicalReport. RUU-CS-94-03: Ultrecht University, 1994.
[20] L.Kavraki, P.Svestka, J-C.Latombe. Probabilistic roadmaps for path planning in highdimensional configuration spaces[J]. IEEE Transactions on Robotics and Automation,1996, 12(4):566–580.
[21] Hsu D, lun Cheng H, claude Latombe J. Multi-level free-space dilation for samplingnarrow passages in PRM planning[C]//In Proc. IEEE Int. Conf. on Robotics and Automation.. 2006:1255–1260.
[22] Saha M, claude Latombe J, chi Chang Y, et al. Finding narrow passages with probabilisticroadmaps: The small step retraction method[C]//in Proc. IEEE/RSJ Int. Conf. onIntelligent Robots and Systems. . 2005.
[23] Wilmarth S A, Amato N M, Stiller P F. MAPRM: A probabilistic roadmap planner withsampling on the medial axis of the free space[C]//In IEEE Int. Conf. Robot. and Autom.. 1999:1024–1031.
[24]阙嘉岚丁贵涛.基于启发式节点增强策略的PRM路径规划方法[J].机器人, 2003,25(6):544–547.
[25] D.Parsons, J.F.Canny. A motion planner for multiple mobile robots[C]//IEEE InternationalConference on Robotics and Automation. . 1990:8–13.
[26] S.K.Kambhampati, L.S.Davis. Multi-resolution path planning for mobile robots[J]. IEEEJournal of Robotics and Automation, 1986, 2(3):135–145.
[27] O.Khatib. Real time obstacle avoidance for manipulators and mobile robots[J]. InternationalJournal of Robotics Research, 1986, 5(1):90–99.
[28] P.Khosla, R.Volpe. Superquadric artificial potentials for obstacle avoidance and approach[C]//In The Proceedings of IEEE International Conference on Robotics and Automation.Philadelphia: Pennsylvania, 1988:1778–1784.
[29] R.Volpe, P.Khosla. Manipulator control with super-quadric artificial potential functions:Theory and experiments[J]. IEEE Transactions on Systems,Man,and Cybernetics,1990, 20(8):1423–1436.
[30] Papadatos. A. Research on motion planning of autonomous mobile robot[D]. MasterThesis: Naval Postgraduate School, 1996.
[31] Stentz A. The Focussed D* Algorithm for Real-Time Replanning[C]//In Proceedings ofthe International Joint Conference on Artificial Intelligence. . 1995:1652–1659.
[32] S.M.LaValle. Rapidly-exploring random trees: a new tool for path planning[R]. TechnicalReport. TR98-11: Computer Science Dept, Iowa State University, 1998.
[33] Surmann H, Huser J,Wehking J. Path planning for a fuzzy controlled autonomous mobilerobot[C]//Fifth IEEE International Conference on Fuzzy Systems. . 1996:1660–1665.
[34] Roth U, Walker M, Hilmann A, et al. Dynamic Path Planning with Spiking NeuralNetworks[J]. TU-Berlin, Institute fur Mikroelektronik, Jebensstr, 1:10623.
[35] Sugihara K, Smith J. Genetic algorithms for adaptive motion planning of an autonomousmobile robot[C]//In Proc. of the IEEE International Symposium on Computational Intelligencein Robotics and Automation. IEEE, 1997:138–143.
[36]吴晓涛,孙增圻.用遗传算法进行路径规划[J].清华大学学报(自然科学版), 1995,35(5):14–19.
[37]齐敏等.三维地形生成及实时显示技术研究进展[J].中国图像图形学报A辑,2000,05A(4):269-276.
[38] Garcia C, Prett D, Morar M. Model predictive control: Theory and practice–a survey[J].Automatic, 1989, 25(3):335–348.
[39] Morari M, Le J. Model predictive control: Past, present and future[J]. Computers andChemical Engineering,1999, 23(4):667–682.
[40] D.Q.Mayne. Control of constrained dynamic systems[J]. European Journal of Control,2001, 7(2-3):87–99.
[41] Mayne D, Rawlings J, Rao C, et al. predictive control: Stability and optimality[J]. Automatica,2000, 36(6):789–814.
[42] Rawling J. Tutorial overview of model predictive control[J]. IEEE Control SystemsMagazine, 2000, 20(3):38–52.
[43] Maciejowsk J. Predictive Control with Constraints[M]. Prentice Hall, 2002.
[44] Hauser J, Jadbabaie A. Aggressive maneuvering of a thrust vectored flying wing:areceding horizon approach[C]//In Proc. 39th IEEE Conference on Decision and Control.Sydney: 2000:3582–358.
[45] Jadbabaie A. Receding Horizon Control of Nonlinear Systems: A Control LyapunovFunction Approach[D]. PhD thesis. Pasadena, CA: California Institute of Technology,2000.
[46] Dunbar W B, Murray R M. Model predictive control of coordinated multi-vehicle formations[C]//In IEEE Conference on Decision and Control. . 2002:4631–4636.
[47] Schouwenaars T, Moor B D, Feron E, et al. Mixed integer programming for multi-vehiclepath planning[C]//In European Control Conference 2001. . 2001:2603–2608.
[48] C.A.Floudas. Nonlinear and Mixed-Integer Programming - Fundamentals and applications.[M]. Oxford, UK: Oxford University Press,, 1995.
[49] Inc I. ILOG CPLEX 11.0 User’s guide[M]. CA: Mountain View, 2006.
[50] Hiriart-Urruty J B, Lemaréchal C. Fundamentals of Convex Analysis[M]. 1. Springer,2001.
[51] H.A.Tah. Operations Research, An Introduction[M]. 4. New Yor: Macmillan PublishingCompany, 1987.
[52] W.L.Winsto. Operations Research, Algorithms and Applications[M]. 3. Belmont, CA:Duxbury Press, 1994.
[53] D.Bertsimas, R.Weismantel. Optimization Over Integers[M]. Belmont,MA: DynamicIdeas, 2005.
[54] R.Fourer, D.M.Gay, W.Kernighan B. AMPL: A Modeling Language for MathematicalProgramming[M]. 2. Duxbury Press, 2002.
[55] J. E. Hopcroft J T S, Sharir M. On the Complexity of Motion Planning for MultipleIndependent Objects; PSPACE- Hardness of the”Warehouseman’s Problem[J]. TheInternational Journal of Robotics Research, 1984, 3(4):76–88.
[56] R.Bellman. Dynamic Programming[M]. Princeton, NJ: Princeton University Press, 1957.
[57] Bellingham J, Richards A, How J P. Receding Horizon Control of Autonomous AerialVehicles[C]//in Proceedings of the American Control Conference. .2002:3741–3746.
[58]邬伦,刘瑜.地理信息系统–原理、方法和应用[M].[北京]：科学出版社, 2005.
[59] T. Schouwenaars E F, B. Mettler, How J. Hybrid Model for Trajectory Planning of AgileAutonomous Aerial Vehicles[J]. Journal of Aerospace Computing, Information, andCommunication, Special Issue on Intelligent Systems, December,2004, 1:629–650.
[60] V G, B M, E R. Nonlinear Model for a Small-Size Acrobatic Helicopter[C]//Pro.AIAAGuidance, Navigation, and Control Conference. Montreal,Canada: 2001:No.AIAA2001–4333.
[61] Prajna S, Papachristodoulou A, Parrilo P A, et al. SOSTOOLS: Sum of Squares OptimizationToolbox for Matlab[CP].
[62] B.Faverjon, P.Tournassoud. A local based approach for path planning of manipulatorswith a high number of degrees of freedom[C]//In The Proceedings of IEEE InternationalConference on Robotics and Automation. New York: 1987:1152–1159.
[63] P.C.Chen, Y.K.Hwang. SANDROS:A motion planner with performance proportional totask difficulty[C]//In The Proceedings of the IEEE International Conference on Roboticsand Automation. Nice: France, 1992:2346–2353.
[64] J. Bellingham A R, How J. Receding Horizon Control of. Autonomous Aerial Vehicles[J]. Proceedings of the IEEE American Control Conference, 2005, 4:2684–2685.
[65] T.Schouwenaars, B.DeMoor, E.Feron,Mixed Integer Programming for Multi-VehiclePath Planning[C]//European Control Conference, Porto, Portugal,September,2001.
[66] T.Schouwenaars, E.Feron, J.How. Safe Receding Horizon Path Planning for AutonomousVehicles[C]//In Proc. of the 40th Annual Allerton Conference on Communication, Control,and Computin, October 2002
[67] A.G.Richards,J.P.How, Aircraft Trajectory Planning with Collision Avoidance usingMixed Integer Linear Programming[C]//In Proc. of American Control Conference,Austin,TX,August 2003.
[68] C.S.Ma and R.H.Miller, MILP Optimal Path Planning for Real-Time Applications[C]//InProc. of the 2006 American Control Conference, Minneapoiis, Minnesota, USA, June,2006.
[69] A.Khurana1, A.Sundaramoorthy,I.A. Karimi,Improving Mixed Integer Linear ProgrammingFormulations[C]//In Proc. of the AIChE Annual Meeting,2005.
[70] M.Zeiler, Modeling Our World[M], ESRI, 1999.
[71] V.Gavrilets. Autonomous Aerobatic Maneuvering of Miniature Helicopters[D]. PhD thesis,Massachusetts Institute of Technology, Cambridge, MA, 2003.
[72] A.Richards, J.How. Aircraft trajectory planning with collision avoidance using mixedinteger linear programming[C]//In Proc. 2002 American Control Conference, pages1936–1941, Anchorage, AK, 2002.
[73]陈述彭,鲁学军,周成虎.地理信息系统导论[M].北京：科学出版社，2000.
[74] P.J.Antsaklis. A Brief Introduction to the Theory and Applications of Hybrid Systems[C].In Proc. IEEE, Special Issue on Hybrid Systems: Theory and Applications, Vol.88, No.7,pp. 879-887, July 2000.
[75] R.C.Alur, T.A.Courcoubetis, P.H.Ho.Henzinger, Hybrid Automata: An Algorithmic Approachto the Specification and Verification of Hybrid Systems[M]. Hybrid Systems I,pages 209-229. Springer-Verlag, 1993.
[76] R. Alur, T.Dang, F.Ivancic. Progress on reachability analysis of hybrid systems usingpredicate abstraction[M]. Hybrid Systems: Computation and Control, pages 4-19.Springer-Verlag, 2003.
[77] A. Chutinan and B. H. Krogh. Computational techniques for hybrid system verification[J]. IEEE Trans. Automatic Control, 48(1):64-75, 2003.
[78] A. Kurzhanski and P. Varaiya. Ellipsoidal techniques for reachability analysis[M]. HybridSystems: Computation and Control, pages 203-213. Springer-Verlag, 2000.
[79] O. Botchkarev and S. Tripakis. Verification of hybrid systems with linear differential inclusionsusing ellipsoidal approximations[M]. Hybrid Systems: Computation and Control,pages 73-88. Springer-Verlag, 2000.
[80] C. J. Tomlin, I. Mitchell, A. M. Bayen, and M. Oishi. Computational techniques for theverification of hybrid systems[C]. In Proc. of the IEEE, 91(7):986-1001, 2003.
[81] S. Prajna and A. Jadbabaie, Safety verification of hybrid systems using barrier certificates[M]. Hybrid Systems: Computation and Control, pages 477-492, Springer-Verlag2004.
[82] C.W.Seibel, J.M.Farines and J.E.R Cury. Towards using hybrid automata for the missionplanning of unmanned aerial vehicles[M]. In Lecture Notes In Computer Science, HybridSystems V, Pages: 324-340, Springer-Verlag, 1999
[83] R. Alur, T. Dang, and F. Ivancic. Progress on reachability analysis of hybrid systemsusing predicate abstraction[M]. In Hybrid Systems: Computation and Control, pages 4-19, Springer-Verlag, 2003.
[84] A. Papachristodoulou, S. Prajna. A tutorial on Sum of Square Techniques for SystemsAnalysis[C]. In Proc. American Control Conference, 2005.
[85] L. Vandenberghe, S.Boyd. Semidefinite programming[J]. SIAM Review, 1996, 38(1):49-95.
[86] A. Papachristodoulou , S. Prajna. On the construction of Lyapunov functions using thesum of squares decomposition[C]. In Proceedings of the IEEE CDC, 2002.
[87]唐强,张翔伦,左玲.无人机航迹规划算法的初步研究[J].航空计算技术, 2003, 33(1) : 125-128.
[88]闵昌万,袁建平.军用飞行器航迹规划综述[J].飞行力学, 1998, 16 (4) : 14-19.
[89]高晖,陈欣,夏云程.无人机航路规划研究[J ].南京航空航天大学学报, 2001, 33 (2): 135-138.
[90] M.B.Pellazar, Vehicles Route Planning with Constraints Using Genetic Algorithms[C]//In Proceedings of the IEEE 1994 National Aerospace and Electronic Conference.1994.
[91] J.F.Glmore, J.A.C.Andrew, Neural Network Model for Route Planning Constraint Integration[C]//In Proceedings of the IEEE 1992 Neural Networks International Joint Conference.1992.
[92] K.Kastella, Aircraft Route Optimization Using Adaptive Simulated Annealing[R]. NAECON,1991.
[93] A. Richards and J. How. Model predictive control of vehicle maneuvers with guaranteedcompletion time and robust feasibility[C]// In Proc. 2003 American Control Conference,Denver, CO, June 2003.
[94] A. Richards, Y. Kuwata, J. How. Experimental demonstrations of real-time MILP control[C]//In Proc. AIAA Guidance, Navigation, and Control Conference, Austin, TX, August2003.
[95] A. Richards, T. Schouwenaars, J. How, and E. Feron. Spacecraft trajectory planningwith avoidance constraints using mixed-integer linear programming[J]. AIAA Journal ofGuidance, Control and Dynamics, 25(4):755–764, 2002.
[96] E. Roche. Parsing with finite-state transducers. In E. Roche and Y. Schabes, editors,Finite-State Language Processing[M]. MIT Press, Cambridge, MA, 1997.
[97] A.B. Roger and C.R. McInnes. Safety constrained free-?yer path planning at theinternational space station[J]. AIAA Journal of Guidance, Control, and Dynam-ics,23(6):971?979, 2000.
[98] J.A. Rossiter, B. Kouvaritakis, J.R. Gossner. Guaranteeing feasibility in con-strained stable generalized predictive control[C]//In Proc. Control Theory Applica-tions,143:463?469, 2001.
[99] D.P. Scharf, F.Y. Hadaegh, and S.R. Ploen. A survey of spacecraft formation ?yingguidance and control (Part I): Guidance[C]//In Proc. 2003 American Control Confer-ence,pages 1733?1739, June 2003.
[100] D.P.Scharf, F.Y. Hadaegh, and S.R. Ploen. A survey of spacecraft formation ?ying guid-ance and control (Part II): Control[C]//In Proc. 2004 American Control Conference,pages 2976?2985, June 2004.
[101] Steven Skiena. Implementing discrete mathematics: combinatorics and graph theory withMathematica.Addison-Wesley Longman Publishing Co., Inc. Boston, MA, USA,1991.
[102] E. Camponogara, D. Jia, B.H. Krogh, and S.N. Talukdar, Distributed model predictivecontrol[J] IEEE Control Systems Magazine 22(1) 44-52, February 2002.
[103] Yoshiaki Kuwata,Arthur Richards, Tom Schouwenaars,Jonathan P. How, Distributed Ro-bust Receding Horizon Control for Multivehicle Guidance[J] IEEE Transactions on Con-trol Systems Technology, VOL. 15, NO. 4, JULY 2007.
[2] J.Reif. Complexity of the Mover’s Problem and Generalization[M]. New Jersey: AblexPublishing Corporation, 1987.
[3] Y.Hwing, N.Ahujia. Gross motion planning–a survey[J]. ACM Computing Survey,1992, 24(3):219–291.
[4] J.C.Latombe. Robot Motion Planning[M]. Boston: Kluwer Academic Publishers, 1991.
[5]丁明跃,郑昌文,周成平等.无人飞行器航迹规划[M].北京:电子工业出版社，2009.
[6]郑昌文.飞行器航迹规划方法研究[D].武汉:华中科技大学, 2003.
[7]韩志刚.低空突防路径规划方法综述[J].飞行力学, 2002, 20(3):1–4.
[8]张颖.机器人路径规划方法综述[J].控制工程, 2003, 10(增):152–155.
[9]成伟明,唐振民,赵春霞,等.移动机器人路径规划中的图方法应用综述[J].工程图学学报, 2008, 4:6–14.
[10] T.Asano, L.Guibas, J.Hershberger, et al. Visibility-polygon search and Euclidean shortestpath[C]//In Proc. of the 26th Annual Symposium on the Foundations of ComputerScience. Portland: OR, 1985:155–164.
[11] F.Aurenhammer. Voronoi diagrams– a survey of fundamental geometric data structure[J]. ACM Computing Surveys, 1991, 23(3):345–405.
[12] D.Kirkpatrick. Efficient computation of continuous skeletons[C]//In The Proceedingsof the 20th Annual Symposium on Foundations of Computer Science. San Juan: PuertoRico, 1979:18–27.
[13] D.T.Lee, L.Robert, R.L.Drysdale. Generalization of Voronoi diagrams in the plane[J].SIAM Journal of Computing, 1981, 10(1):73–87.
[14] C.K.Yap. An O(nlogn)algorithm for the Voronoi diagram of a set of simple curve segments[R]. Technical Report. No.43: Courant Institute,Robotics Laboratory,New YorkUniversity,1985.
[15] J.F.Canny, B.R.Donald. Simplified Voronoi Diagram[C]//In The Proceedings of the3rd Annual ACM Symposium on Computational Geometry. New York: ACM press,1987:153 161.
[16] J.F.Canny. A new algebraic method for robot motion planning and real geometry[C]//InThe Proceedings of the 28th IEEE Symposium on Foundations of Computer Science.Los Angeles: , 1987:39–48.
[17] J.F.Canny, M.Lin. An opportunistic global path planner[J]. Algorithmica, 1993, 10(2-4):102 120.
[18] L.Kavraki, J-C.Latombe. Randomized preprocessing of configuration space for fast pathplanning[C]//In The Proceedings of the IEEE International Conference on Robotics andAutomation. San Diego: CA, 1994:2138–2139.
[19] M.Overmars, P.Svestka. A probabilistic learning approach to motion planning[R]. TechnicalReport. RUU-CS-94-03: Ultrecht University, 1994.
[20] L.Kavraki, P.Svestka, J-C.Latombe. Probabilistic roadmaps for path planning in highdimensional configuration spaces[J]. IEEE Transactions on Robotics and Automation,1996, 12(4):566–580.
[21] Hsu D, lun Cheng H, claude Latombe J. Multi-level free-space dilation for samplingnarrow passages in PRM planning[C]//In Proc. IEEE Int. Conf. on Robotics and Automation.. 2006:1255–1260.
[22] Saha M, claude Latombe J, chi Chang Y, et al. Finding narrow passages with probabilisticroadmaps: The small step retraction method[C]//in Proc. IEEE/RSJ Int. Conf. onIntelligent Robots and Systems. . 2005.
[23] Wilmarth S A, Amato N M, Stiller P F. MAPRM: A probabilistic roadmap planner withsampling on the medial axis of the free space[C]//In IEEE Int. Conf. Robot. and Autom.. 1999:1024–1031.
[24]阙嘉岚丁贵涛.基于启发式节点增强策略的PRM路径规划方法[J].机器人, 2003,25(6):544–547.
[25] D.Parsons, J.F.Canny. A motion planner for multiple mobile robots[C]//IEEE InternationalConference on Robotics and Automation. . 1990:8–13.
[26] S.K.Kambhampati, L.S.Davis. Multi-resolution path planning for mobile robots[J]. IEEEJournal of Robotics and Automation, 1986, 2(3):135–145.
[27] O.Khatib. Real time obstacle avoidance for manipulators and mobile robots[J]. InternationalJournal of Robotics Research, 1986, 5(1):90–99.
[28] P.Khosla, R.Volpe. Superquadric artificial potentials for obstacle avoidance and approach[C]//In The Proceedings of IEEE International Conference on Robotics and Automation.Philadelphia: Pennsylvania, 1988:1778–1784.
[29] R.Volpe, P.Khosla. Manipulator control with super-quadric artificial potential functions:Theory and experiments[J]. IEEE Transactions on Systems,Man,and Cybernetics,1990, 20(8):1423–1436.
[30] Papadatos. A. Research on motion planning of autonomous mobile robot[D]. MasterThesis: Naval Postgraduate School, 1996.
[31] Stentz A. The Focussed D* Algorithm for Real-Time Replanning[C]//In Proceedings ofthe International Joint Conference on Artificial Intelligence. . 1995:1652–1659.
[32] S.M.LaValle. Rapidly-exploring random trees: a new tool for path planning[R]. TechnicalReport. TR98-11: Computer Science Dept, Iowa State University, 1998.
[33] Surmann H, Huser J,Wehking J. Path planning for a fuzzy controlled autonomous mobilerobot[C]//Fifth IEEE International Conference on Fuzzy Systems. . 1996:1660–1665.
[34] Roth U, Walker M, Hilmann A, et al. Dynamic Path Planning with Spiking NeuralNetworks[J]. TU-Berlin, Institute fur Mikroelektronik, Jebensstr, 1:10623.
[35] Sugihara K, Smith J. Genetic algorithms for adaptive motion planning of an autonomousmobile robot[C]//In Proc. of the IEEE International Symposium on Computational Intelligencein Robotics and Automation. IEEE, 1997:138–143.
[36]吴晓涛,孙增圻.用遗传算法进行路径规划[J].清华大学学报(自然科学版), 1995,35(5):14–19.
[37]齐敏等.三维地形生成及实时显示技术研究进展[J].中国图像图形学报A辑,2000,05A(4):269-276.
[38] Garcia C, Prett D, Morar M. Model predictive control: Theory and practice–a survey[J].Automatic, 1989, 25(3):335–348.
[39] Morari M, Le J. Model predictive control: Past, present and future[J]. Computers andChemical Engineering,1999, 23(4):667–682.
[40] D.Q.Mayne. Control of constrained dynamic systems[J]. European Journal of Control,2001, 7(2-3):87–99.
[41] Mayne D, Rawlings J, Rao C, et al. predictive control: Stability and optimality[J]. Automatica,2000, 36(6):789–814.
[42] Rawling J. Tutorial overview of model predictive control[J]. IEEE Control SystemsMagazine, 2000, 20(3):38–52.
[43] Maciejowsk J. Predictive Control with Constraints[M]. Prentice Hall, 2002.
[44] Hauser J, Jadbabaie A. Aggressive maneuvering of a thrust vectored flying wing:areceding horizon approach[C]//In Proc. 39th IEEE Conference on Decision and Control.Sydney: 2000:3582–358.
[45] Jadbabaie A. Receding Horizon Control of Nonlinear Systems: A Control LyapunovFunction Approach[D]. PhD thesis. Pasadena, CA: California Institute of Technology,2000.
[46] Dunbar W B, Murray R M. Model predictive control of coordinated multi-vehicle formations[C]//In IEEE Conference on Decision and Control. . 2002:4631–4636.
[47] Schouwenaars T, Moor B D, Feron E, et al. Mixed integer programming for multi-vehiclepath planning[C]//In European Control Conference 2001. . 2001:2603–2608.
[48] C.A.Floudas. Nonlinear and Mixed-Integer Programming - Fundamentals and applications.[M]. Oxford, UK: Oxford University Press,, 1995.
[49] Inc I. ILOG CPLEX 11.0 User’s guide[M]. CA: Mountain View, 2006.
[50] Hiriart-Urruty J B, Lemaréchal C. Fundamentals of Convex Analysis[M]. 1. Springer,2001.
[51] H.A.Tah. Operations Research, An Introduction[M]. 4. New Yor: Macmillan PublishingCompany, 1987.
[52] W.L.Winsto. Operations Research, Algorithms and Applications[M]. 3. Belmont, CA:Duxbury Press, 1994.
[53] D.Bertsimas, R.Weismantel. Optimization Over Integers[M]. Belmont,MA: DynamicIdeas, 2005.
[54] R.Fourer, D.M.Gay, W.Kernighan B. AMPL: A Modeling Language for MathematicalProgramming[M]. 2. Duxbury Press, 2002.
[55] J. E. Hopcroft J T S, Sharir M. On the Complexity of Motion Planning for MultipleIndependent Objects; PSPACE- Hardness of the”Warehouseman’s Problem[J]. TheInternational Journal of Robotics Research, 1984, 3(4):76–88.
[56] R.Bellman. Dynamic Programming[M]. Princeton, NJ: Princeton University Press, 1957.
[57] Bellingham J, Richards A, How J P. Receding Horizon Control of Autonomous AerialVehicles[C]//in Proceedings of the American Control Conference. .2002:3741–3746.
[58]邬伦,刘瑜.地理信息系统–原理、方法和应用[M].[北京]：科学出版社, 2005.
[59] T. Schouwenaars E F, B. Mettler, How J. Hybrid Model for Trajectory Planning of AgileAutonomous Aerial Vehicles[J]. Journal of Aerospace Computing, Information, andCommunication, Special Issue on Intelligent Systems, December,2004, 1:629–650.
[60] V G, B M, E R. Nonlinear Model for a Small-Size Acrobatic Helicopter[C]//Pro.AIAAGuidance, Navigation, and Control Conference. Montreal,Canada: 2001:No.AIAA2001–4333.
[61] Prajna S, Papachristodoulou A, Parrilo P A, et al. SOSTOOLS: Sum of Squares OptimizationToolbox for Matlab[CP].
[62] B.Faverjon, P.Tournassoud. A local based approach for path planning of manipulatorswith a high number of degrees of freedom[C]//In The Proceedings of IEEE InternationalConference on Robotics and Automation. New York: 1987:1152–1159.
[63] P.C.Chen, Y.K.Hwang. SANDROS:A motion planner with performance proportional totask difficulty[C]//In The Proceedings of the IEEE International Conference on Roboticsand Automation. Nice: France, 1992:2346–2353.
[64] J. Bellingham A R, How J. Receding Horizon Control of. Autonomous Aerial Vehicles[J]. Proceedings of the IEEE American Control Conference, 2005, 4:2684–2685.
[65] T.Schouwenaars, B.DeMoor, E.Feron,Mixed Integer Programming for Multi-VehiclePath Planning[C]//European Control Conference, Porto, Portugal,September,2001.
[66] T.Schouwenaars, E.Feron, J.How. Safe Receding Horizon Path Planning for AutonomousVehicles[C]//In Proc. of the 40th Annual Allerton Conference on Communication, Control,and Computin, October 2002
[67] A.G.Richards,J.P.How, Aircraft Trajectory Planning with Collision Avoidance usingMixed Integer Linear Programming[C]//In Proc. of American Control Conference,Austin,TX,August 2003.
[68] C.S.Ma and R.H.Miller, MILP Optimal Path Planning for Real-Time Applications[C]//InProc. of the 2006 American Control Conference, Minneapoiis, Minnesota, USA, June,2006.
[69] A.Khurana1, A.Sundaramoorthy,I.A. Karimi,Improving Mixed Integer Linear ProgrammingFormulations[C]//In Proc. of the AIChE Annual Meeting,2005.
[70] M.Zeiler, Modeling Our World[M], ESRI, 1999.
[71] V.Gavrilets. Autonomous Aerobatic Maneuvering of Miniature Helicopters[D]. PhD thesis,Massachusetts Institute of Technology, Cambridge, MA, 2003.
[72] A.Richards, J.How. Aircraft trajectory planning with collision avoidance using mixedinteger linear programming[C]//In Proc. 2002 American Control Conference, pages1936–1941, Anchorage, AK, 2002.
[73]陈述彭,鲁学军,周成虎.地理信息系统导论[M].北京：科学出版社，2000.
[74] P.J.Antsaklis. A Brief Introduction to the Theory and Applications of Hybrid Systems[C].In Proc. IEEE, Special Issue on Hybrid Systems: Theory and Applications, Vol.88, No.7,pp. 879-887, July 2000.
[75] R.C.Alur, T.A.Courcoubetis, P.H.Ho.Henzinger, Hybrid Automata: An Algorithmic Approachto the Specification and Verification of Hybrid Systems[M]. Hybrid Systems I,pages 209-229. Springer-Verlag, 1993.
[76] R. Alur, T.Dang, F.Ivancic. Progress on reachability analysis of hybrid systems usingpredicate abstraction[M]. Hybrid Systems: Computation and Control, pages 4-19.Springer-Verlag, 2003.
[77] A. Chutinan and B. H. Krogh. Computational techniques for hybrid system verification[J]. IEEE Trans. Automatic Control, 48(1):64-75, 2003.
[78] A. Kurzhanski and P. Varaiya. Ellipsoidal techniques for reachability analysis[M]. HybridSystems: Computation and Control, pages 203-213. Springer-Verlag, 2000.
[79] O. Botchkarev and S. Tripakis. Verification of hybrid systems with linear differential inclusionsusing ellipsoidal approximations[M]. Hybrid Systems: Computation and Control,pages 73-88. Springer-Verlag, 2000.
[80] C. J. Tomlin, I. Mitchell, A. M. Bayen, and M. Oishi. Computational techniques for theverification of hybrid systems[C]. In Proc. of the IEEE, 91(7):986-1001, 2003.
[81] S. Prajna and A. Jadbabaie, Safety verification of hybrid systems using barrier certificates[M]. Hybrid Systems: Computation and Control, pages 477-492, Springer-Verlag2004.
[82] C.W.Seibel, J.M.Farines and J.E.R Cury. Towards using hybrid automata for the missionplanning of unmanned aerial vehicles[M]. In Lecture Notes In Computer Science, HybridSystems V, Pages: 324-340, Springer-Verlag, 1999
[83] R. Alur, T. Dang, and F. Ivancic. Progress on reachability analysis of hybrid systemsusing predicate abstraction[M]. In Hybrid Systems: Computation and Control, pages 4-19, Springer-Verlag, 2003.
[84] A. Papachristodoulou, S. Prajna. A tutorial on Sum of Square Techniques for SystemsAnalysis[C]. In Proc. American Control Conference, 2005.
[85] L. Vandenberghe, S.Boyd. Semidefinite programming[J]. SIAM Review, 1996, 38(1):49-95.
[86] A. Papachristodoulou , S. Prajna. On the construction of Lyapunov functions using thesum of squares decomposition[C]. In Proceedings of the IEEE CDC, 2002.
[87]唐强,张翔伦,左玲.无人机航迹规划算法的初步研究[J].航空计算技术, 2003, 33(1) : 125-128.
[88]闵昌万,袁建平.军用飞行器航迹规划综述[J].飞行力学, 1998, 16 (4) : 14-19.
[89]高晖,陈欣,夏云程.无人机航路规划研究[J ].南京航空航天大学学报, 2001, 33 (2): 135-138.
[90] M.B.Pellazar, Vehicles Route Planning with Constraints Using Genetic Algorithms[C]//In Proceedings of the IEEE 1994 National Aerospace and Electronic Conference.1994.
[91] J.F.Glmore, J.A.C.Andrew, Neural Network Model for Route Planning Constraint Integration[C]//In Proceedings of the IEEE 1992 Neural Networks International Joint Conference.1992.
[92] K.Kastella, Aircraft Route Optimization Using Adaptive Simulated Annealing[R]. NAECON,1991.
[93] A. Richards and J. How. Model predictive control of vehicle maneuvers with guaranteedcompletion time and robust feasibility[C]// In Proc. 2003 American Control Conference,Denver, CO, June 2003.
[94] A. Richards, Y. Kuwata, J. How. Experimental demonstrations of real-time MILP control[C]//In Proc. AIAA Guidance, Navigation, and Control Conference, Austin, TX, August2003.
[95] A. Richards, T. Schouwenaars, J. How, and E. Feron. Spacecraft trajectory planningwith avoidance constraints using mixed-integer linear programming[J]. AIAA Journal ofGuidance, Control and Dynamics, 25(4):755–764, 2002.
[96] E. Roche. Parsing with finite-state transducers. In E. Roche and Y. Schabes, editors,Finite-State Language Processing[M]. MIT Press, Cambridge, MA, 1997.
[97] A.B. Roger and C.R. McInnes. Safety constrained free-?yer path planning at theinternational space station[J]. AIAA Journal of Guidance, Control, and Dynam-ics,23(6):971?979, 2000.
[98] J.A. Rossiter, B. Kouvaritakis, J.R. Gossner. Guaranteeing feasibility in con-strained stable generalized predictive control[C]//In Proc. Control Theory Applica-tions,143:463?469, 2001.
[99] D.P. Scharf, F.Y. Hadaegh, and S.R. Ploen. A survey of spacecraft formation ?yingguidance and control (Part I): Guidance[C]//In Proc. 2003 American Control Confer-ence,pages 1733?1739, June 2003.
[100] D.P.Scharf, F.Y. Hadaegh, and S.R. Ploen. A survey of spacecraft formation ?ying guid-ance and control (Part II): Control[C]//In Proc. 2004 American Control Conference,pages 2976?2985, June 2004.
[101] Steven Skiena. Implementing discrete mathematics: combinatorics and graph theory withMathematica.Addison-Wesley Longman Publishing Co., Inc. Boston, MA, USA,1991.
[102] E. Camponogara, D. Jia, B.H. Krogh, and S.N. Talukdar, Distributed model predictivecontrol[J] IEEE Control Systems Magazine 22(1) 44-52, February 2002.
[103] Yoshiaki Kuwata,Arthur Richards, Tom Schouwenaars,Jonathan P. How, Distributed Ro-bust Receding Horizon Control for Multivehicle Guidance[J] IEEE Transactions on Con-trol Systems Technology, VOL. 15, NO. 4, JULY 2007.
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |