A Progressive Motion-Planning Algorithm and Traffic Flow Analysis for High-Density 2D Traffic

References

• Abichandani P, Torabi S, Basu S, Benson H (2015) Mixed integer nonlinear programming framework for fixed path coordination of multiple underwater vehicles under acoustic communication constraints. IEEE J. Oceanic Engrg. 40(4):864–873.Google Scholar
• Amazon (2018) Amazon Prime Air. Accessed March 18, 2018, https://www.amazon.com/Amazon-Prime-Air/b?ie=UTF8\&node=8037720011.Google Scholar
• Anderson J (1978) Transit Systems Theory (Lexington Books, Lanham, MD).Google Scholar
• Barr A, Bensinger G (2014) Google is testing delivery drone system. Wall Street Journal (August 29), https://www.wsj.com/articles/google-reveals-delivery-drone-project-1409274480.Google Scholar
• Bayen AM, Raffard RL, Tomlin CJ (2006) Adjoint-based control of a new Eulerian network model of air traffic flow. IEEE Trans. Control Systems Tech. 14(5):804–818.Google Scholar
• Bergenhem C, Pettersson H, Coelingh E, Englund C, Shladover S, Tsugawa S, Trucks S (2012) Overview of platooning systems. Proc. 19th ITS World Congress, Vienna.Google Scholar
• Bertsimas D, Lulli G, Odoni A (2011) An integer optimization approach to large-scale air traffic flow management. Oper. Res. 59(1):211–227.Google Scholar
• Bilimoria KD, Lee HQ (2001) Properties of air traffic conflicts for free and structured routing. Proc. AIAA Guidance Navigation Control Conf. Exhibit (American Institute of Aeronautics and Astronautics, Reston, VA).Google Scholar
• Bureau of Transportation Statistics (2017) National transportation statistics 2017. Technical report, Bureau of Transportation Statistics, U.S. Department of Transportation, Washington, DC.Google Scholar
• Ceder A (2007) Public Transit Planning and Operation (Taylor & Francis, Abingdon, UK).Crossref, Google Scholar
• Cellier L, Cafieri S, Messine F (2013) A decomposition-based optimal control approach for aircraft conflict avoidance performed by velocity regulation. Proc. 3rd Internat. Conf. Application Theory Automation Command Control Systems (ACM, New York), 111–113.Crossref, Google Scholar
• Christodoulou M, Costoulakis C (2004) Nonlinear mixed integer programming for aircraft collision avoidance in free flight. Proc. 12th IEEE Mediterranean Electrotech. Conf., vol. 1 (IEEE, Piscataway, NJ), 327–330.Crossref, Google Scholar
• Cohen JD, Lin MC, Manocha D, Ponamgi M (1995) I-COLLIDE: An interactive and exact collision detection system for large-scale environments. Proc. Sympos. Interactive 3D Graphics (ACM, New York), 189–ff.Crossref, Google Scholar
• Crevier B, Cordeau JF, Laporte G (2007) The multi-depot vehicle routing problem with inter-depot routes. Eur. J. Oper. Res. 176(2):756–773.Crossref, Google Scholar
• Dell’Olmo P, Lulli G (2003) A new hierarchical architecture for Air Traffic Management: Optimisation of airway capacity in a free flight scenario. Eur. J. Oper. Res. 144(1):179–193.Crossref, Google Scholar
• Desaraju VR, How JP (2012) Decentralized path planning for multi-agent teams with complex constraints. Autonomous Robots 32(4):385–403.Google Scholar
• Donald B, Xavier P, Canny J, Reif J (1993) Kinodynamic motion planning. J. ACM 40(5):1048–1066.Google Scholar
• Drexl M (2012) Synchronization in vehicle routing—A survey of VRPs with multiple synchronization constraints. Transportation Sci. 46(3):297–316.Google Scholar
• Drud A (1985) CONOPT: A GRG code for large sparse dynamic nonlinear optimization problems. Math. Programming 31(2):153–191.Google Scholar
• Drud A (2018) CONOPT. GAMS, https://www.gams.com/latest/docs/S_CONOPT.html.Google Scholar
• Durand N, Alliot J, Chansou O (1995) An optimizing conflict solver for ATC. J. Air Traffic Control 3.Google Scholar
• Earl MG, D’Andrea R (2007) Multi-Vehicle Cooperative Control Using Mixed Integer Linear Programming (John Wiley & Sons, Hoboken, NJ), 231–259.Crossref, Google Scholar
• Eby MS, Kelly WE (1999) Free flight separation assurance using distributed algorithms. Proc. IEEE Aerospace Conf., vol. 2 (IEEE, Piscataway, NJ), 429–441.Google Scholar
• Eksioglu B, Vural AV, Reisman A (2009) The vehicle routing problem: A taxonomic review. Comput. Indust. Engrg. 57(4):1472–1483.Crossref, Google Scholar
• Federal Aviation Administration (2009) Traffic flow management in the National Airspace System. Technical report, Air Traffic Organization, Federal Aviation Administration, Washington, DC.Google Scholar
• Frazzoli E, Mao ZH, Oh JH, Feron E (2001) Resolution of conflicts involving many aircraft via semidefinite programming. J. Guidance Control Dynam. 24(1)79–86.Crossref, Google Scholar
• Gerlough DL, Huber MJ (1975) Traffic flow theory: a monograph. Technical report, Transportation Research Board, National Research Council, Washington, DC.Google Scholar
• Gharibi M, Boutaba R, Waslander SL (2016) Internet of drones. Technical report, Defense Systems Information Analysis Center, Belcamp, MD.Google Scholar
• Glaser A (2016) 7-Eleven beats Google and Amazon to the first regular commercial drone delivery service in the U.S. Recode (December 20), https://www.recode.net/2016/12/20/14026396/7-eleven-drone-delivery-flirtey-first-retail-us-reno-nevada.Google Scholar
• Hall RJ (2016) An internet of drones. IEEE Internet Comput. 20(3):68–73.Google Scholar
• Hetzner C (2018) Porsche joins Daimler, Geely, Italdesign in race for flying cars. Automotive News (March 11), http://www.autonews.com/article/20180311/COPY01/303119999/flying-cars-porsche-daimler-geely-italdesign.Google Scholar
• Hoekstra J, van Gent R, Hoekstra JM, Ruigrok R, Ruigrok RCJ (1998) Conceptual design of Free Flight with airborne separation assurance. Proc. AIAA Guidance Navigation Control Conf. Exhibit (American Institute of Aeronautics and Astronautics, Reston, VA).Google Scholar
• Hsu D, Kindel R, Latombe JC, Rock S (2002) Randomized kinodynamic motion planning with moving obstacles. Internat. J. Robotics Res. 21(3):233–255.Google Scholar
• Islami A, Chaimatanan S, Delahaye D (2016) Large scale 4D trajectory planning. Electronic Navigation Research Institute, ed. Air Traffic Management and Systems II, Lecture Notes in Electrical Engineering, vol. 420 (Springer Japan, Tokyo), 27–47.Google Scholar
• Jardin MR (2004) Air traffic conflict models. Proc. AIAA 4th Aviation Tech. Integration Oper. Forum (American Institute of Aeronautics and Astronautics, Reston, VA).Google Scholar
• Jenkins A (2017) The hyperloop just completed a major test. But the real challenges lie ahead. Fortune (July 15), http://fortune.com/2017/07/15/hyperloop-one-test-challenges/.Google Scholar
• Kuchar JK, Yang LC (2000) A review of conflict detection and resolution modeling methods. IEEE Trans. Intelligent Transportation Systems 1(4):179–189.Google Scholar
• Laumond JPP (1998) Robot Motion Planning and Control, Lecture Notes in Control and Information Sciences, vol. 229 (Springer-Verlag, Secaucus, NJ).Crossref, Google Scholar
• LaValle SM (2006) Planning Algorithms (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• LaValle SM, Kuffner JJ (2001) Randomized kinodynamic planning. Internat. J. Robotics Res. 20(5):378–400.Google Scholar
• Lehouillier T, Allignol C, Omer J, Soumis F (2014) Interactions between operations and planning in air traffic control. Proc. 6th Internat. Conf. Res. Air Transportation, Istanbul.Google Scholar
• Lehouillier T, Omer J, Soumis F, Desaulniers G (2017) Two decomposition algorithms for solving a minimum weight maximum clique model for the air conflict resolution problem. Eur. J. Oper. Res. 256(3):696–712.Crossref, Google Scholar
• Lieu H (1975) Revised monograph on traffic flow theory. Technical report, Federal Highway Administration, U.S. Department of Transportation, Washington, DC.Google Scholar
• Ma Z, Cui D, Cheng P (2004) Dynamic network flow model for short-term air traffic flow management. IEEE Trans. Systems Man Cybernetics A: Systems Humans 34(3):351–358.Google Scholar
• Mahjri I, Dhraief A, Belghith A (2015) A review on collision avoidance systems for unmanned aerial vehicles. Kassab M, Berbineau M, Vinel A, Jonsson M, Garcia F, Soler J, eds. Communication Technologies for Vehicles (Springer, Cham, Switzerland), 203–214.Crossref, Google Scholar
• Malcolm H, Weise E (2015) Walmart wants Amazon-like delivery drones. USA Today (October 26), https://www.usatoday.com/story/money/2015/10/26/walmart-wants-to-use-drones-to-deliver-packages/74646996/.Google Scholar
• McNally D, Gong C (2007) Concept and laboratory analysis of trajectory-based automation for separation assurance. Air Traffic Control Quart. 15(1):35–63.Crossref, Google Scholar
• Menon PK, Sweriduk GD, Bilimoria KD (2004) New approach for modeling, analysis, and control of air traffic flow. J. Guidance Control Dynam. 27(5):737–744.Google Scholar
• Menon PK, Sweriduk GD, Lam T, Diaz GM, Bilimoria KD (2006) Computer-aided Eulerian air traffic flow modeling and predictive control. J. Guidance Control Dynam. 29(1):12–19.Google Scholar
• Misener R, Floudas CA (2013) GloMIQO: Global mixed-integer quadratic optimizer. J. Global Optim. 57(1):3–50.Google Scholar
• Montgomery DC, Runger GC (2014) Applied Statistics and Probability for Engineering and Sciences, 6th ed. (Wiley, New York).Google Scholar
• Murray CC, Chu AG (2015) The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery. Transportation Res. Part C: Emerging Tech. 54:86–109.Crossref, Google Scholar
• Murray CC, Park W (2013) Incorporating human factor considerations in unmanned aerial vehicle routing. IEEE Trans. Systems Man Cybernetics A: Systems Humans 43(4):860–874.Google Scholar
• Musk E (2013) Hyperloop. Accessed March 18, 2018, https://www.tesla.com/blog/hyperloop.Google Scholar
• National Aeronautics and Space Administration (2015) First steps toward drone traffic management. Technical report, National Aeronautics and Space Administration, Washington, DC.Google Scholar
• Nocedal J, Wright S (2000) Numerical Optimization, Springer Series in Operations Research and Financial Engineering (Springer, New York).Google Scholar
• Ny JL, Pappas GJ (2010) Geometric programming and mechanism design for air traffic conflict resolution. Proc. Amer. Control Conf. (IEEE, Piscataway, NJ), 3069–3074.Google Scholar
• Pallottino L, Feron EM, Bicchi A (2002) Conflict resolution problems for air traffic management systems solved with mixed integer programming. IEEE Trans. Intelligent Transportation Systems 3(1):3–11.Google Scholar
• Parmar T (2016) This tech giant has kicked off drone delivery in rural China. Fortune (November 14), http://fortune.com/2016/11/14/jd-china-drone-delivery-singles-day/.Google Scholar
• Pechoucek M, Sislak D (2009) Agent-based approach to free-flight planning, control, and simulation. IEEE Intelligent Systems 24(1):14–17.Google Scholar
• Raghunathan AU, Gopal V, Subramanian D, Biegler LT, Samad T (2004) Dynamic optimization strategies for three-dimensional conflict resolution of multiple aircraft. J. Guidance Control Dynam. 27(4):586–594.Crossref, Google Scholar
• Richards A, How JP (2002) Aircraft trajectory planning with collision avoidance using mixed integer linear programming. Proc. Amer. Control Conf. (IEEE, Piscataway, NJ), 1936–1941.Google Scholar
• Šišlák D, Samek J, Pěchouček M (2008) Decentralized algorithms for collision avoidance in airspace. Proc. 7th Internat. Joint Conf. Autonomous Agents Multiagent Systems, vol. 2 (International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC), 543–550.Google Scholar
• Šišlák D, Volf P, Komenda A, Samek J, Pechoucek M (2007) Agent-based multi-layer collision avoidance to unmanned aerial vehicles. Proc. Internat. Conf. Integration Knowledge Intensive Multi-Agent Systems (IEEE, Piscataway, NJ), 365–370.Crossref, Google Scholar
• Sun D, Strub IS, Bayen AM (2007) Comparison of the performance of four Eulerian network flow models for strategic air traffic management. Networks Heterogeneous Media 2:569.Google Scholar
• Sunil E, Ellerbroek J, Hoekstra J, Maas J (2017) Modeling airspace stability and capacity for decentralized separation. Technical report, TU Delft Control & Simulation, Delft, Netherlands.Google Scholar
• Tawarmalani M, Sahinidis NV (2005) A polyhedral branch-and-cut approach to global optimization. Math. Programming 103(2):225–249.Crossref, Google Scholar
• Turri V, Besselink B, Johansson KH (2017) Cooperative look-ahead control for fuel-efficient and safe heavy-duty vehicle platooning. IEEE Trans. Control Systems Tech. 25(1):12–28.Crossref, Google Scholar
• Visintini AL, Glover W, Lygeros J, Maciejowski J (2006) Monte Carlo optimization for conflict resolution in air traffic control. IEEE Trans. Intelligent Transportation Systems 7(4):470–482.Google Scholar
• Vranas PB, Bertsimas DJ, Odoni AR (1994) The multi-airport ground-holding problem in air traffic control. Oper. Res. 42(2):249–261.Google Scholar
• Wardrop J (1952) Some theoretical aspects of road traffic research. Technical report, Institution of Civil Engineers, London.Google Scholar
• Wei P, Andrisani D, Sun D (2011) Routing flexible traffic into metroplex. Proc. AIAA Guidance Navigation Control Conf. (American Institute of Aeronautics and Astronautics, Reston, VA).Google Scholar
• Wei P, Spiers G, Sun D (2014) Algebraic connectivity maximization for air transportation networks. IEEE Trans. Intelligent Transportation Systems 15(2):685–698.Google Scholar
• Work DB, Bayen AM (2008) Convex formulations of air traffic flow optimization problems. Proc. IEEE 96(12):2096–2112.Google Scholar
• Wu T, Du W (2014) A distributed approach to aircraft conflict resolution based on satisficing game theory. Wen Z, Li T, eds. Foundations of Intelligent Systems (Springer, Berlin), 383–393.Crossref, Google Scholar
• Yang C, Mao J, Wei P (2016) Air traffic network optimization via Laplacian energy maximization. Aerospace Sci. Tech. 49:26–33.Crossref, Google Scholar