Portal de Periódicos da CAPES

Generalized Shape Expansion-Based Motion Planning in Three-Dimensional Obstacle-Cluttered Environment

2020; American Institute of Aeronautics and Astronautics; Volume: 43; Issue: 9 Linguagem: Inglês

10.2514/1.g004756

1533-3884

Vrushabh Zinage, Satadal Ghosh,

Distributed Control Multi-Agent Systems

No AccessEngineering NotesGeneralized Shape Expansion-Based Motion Planning in Three-Dimensional Obstacle-Cluttered EnvironmentVrushabh Vijaykumar Zinage and Satadal GhoshVrushabh Vijaykumar ZinageIndian Institute of Technology, Chennai 600 036, India and Satadal GhoshIndian Institute of Technology, Chennai 600 036, IndiaPublished Online:22 Jul 2020https://doi.org/10.2514/1.G004756SectionsRead Now ToolsAdd to favoritesDownload citationTrack citations ShareShare onFacebookTwitterLinked InRedditEmail About References [1] Beard R., Kingston D., Quigley M., Snyder D., Christiansen R., Johnson W., McLain T. and Goodrich M., "Autonomous Vehicle Technologies for Small Fixed Wing UAVs," Journal of Aerospace Computing, Information, and Communication, Vol. 2, No. 1, 2005, pp. 92–108. https://doi.org/10.2514/1.8371 LinkGoogle Scholar[2] Winnefeld J. and Kendall F., "Unmanned Systems Integrated Roadmap: FY2011-2036," U.S. Dept. of Defense TR –11-S-3613, 2011. Google Scholar[3] Khatib O., "Real-Time Obstacle Avoidance for Manipulators and Mobile Robots," Proceedings of 1985 IEEE International Conference on Robotics and Automation, Vol. 2, IEEE Publ., Piscataway, NJ, 1985, pp. 500–505. https://doi.org/10.1109/ROBOT.1985.1087247 Google Scholar[4] Koren Y. and Borenstein J., "Potential Field Methods and Their Inherent Limitations for Mobile Robot Navigation," IEEE Conference on Robotics and Automation, IEEE Publ., Piscataway, NJ, 1991, pp. 1398–1404. https://doi.org/10.1109/ROBOT.1991.131810 Google Scholar[5] Chakravarthy A. and Ghose D., "Obstacle Avoidance in a Dynamic Environment: A Collision Cone Approach," IEEE Transactions on Systems, Man, and Cybernetics—Part A: Systems and Humans, Vol. 28, No. 5, 1998, pp. 562–574. https://doi.org/10.1109/3468.709600 CrossrefGoogle Scholar[6] Chakravarthy A. and Ghose D., "Collision Cones for Quadric Surfaces," IEEE Transactions on Robotics, Vol. 27, No. 6, 2011, pp. 1159–1166. https://doi.org/10.1109/TRO.2011.2159413 CrossrefGoogle Scholar[7] Chakravarthy A. and Ghose D., "Generalization of the Collision Cone Approach for Motion Safety in 3-D Environments," Autonomous Robots, Vol. 32, No. 3, 2012, pp. 243–266. https://doi.org/10.1007/s10514-011-9270-z CrossrefGoogle Scholar[8] Sunkara V., Chakravarthy A. and Ghose D., "Collision Avoidance of Arbitrarily Shaped Deforming Objects Using Collision Cones," IEEE Robotics and Automation Letters, Vol. 4, No. 2, 2019, pp. 2156–2163. https://doi.org/10.1109/LRA.2019.2900535 CrossrefGoogle Scholar[9] Manathara J. and Ghose D., "Reactive Collision Avoidance of Multiple Realistic UAVs," Aircraft Engineering and Aerospace Technology, Vol. 83, No. 6, 2011, pp. 388–396. https://doi.org/10.1108/00022661111173261 CrossrefGoogle Scholar[10] Tony L., Ghose D. and Chakravarthy A., "Precision UAV Collision Avoidance Using Computationally Efficient Avoidance Maps," AIAA Guidance, Navigation, and Control Conference, AIAA SciTech Forum, AIAA Paper 2018-0875, 2018. https://doi.org/10.2514/6.2018-0875 Google Scholar[11] Wilhelm J., Clem G. and Casbeer D., "Circumnavigation and Obstacle Avoidance Guidance for UAVs Using Gradient Vector Fields," AIAA Scitech 2019 Forum, AIAA Paper 2019-1791, 2019. https://doi.org/10.2514/6.2019-1791 LinkGoogle Scholar[12] Wilhelm J. P. and Clem G., "Vector Field UAV Guidance for Path Following and Obstacle Avoidance with Minimal Deviation," Journal of Guidance, Control, and Dynamics, Vol. 42, No. 8, 2019, pp. 1848–1856. https://doi.org/10.2514/1.G004053 LinkGoogle Scholar[13] Gong Q., Lewis L. R. and Ross I. M., "Pseudospectral Motion Planning for Autonomous Vehicles," Journal of Guidance, Control, and Dynamics, Vol. 32, No. 3, 2009, pp. 1039–1045. https://doi.org/10.2514/1.39697 LinkGoogle Scholar[14] Upadhyay S. and Ratnoo A., "Smooth Path Planning for Unmanned Aerial Vehicles with Airspace Restrictions," Journal of Guidance, Control, and Dynamics, Vol. 40, No. 7, 2017, pp. 1596–1612. https://doi.org/10.2514/1.G002400 LinkGoogle Scholar[15] Ghosh S., Davis D. and Chung T., "A Guidance Law for Avoiding Specific Approach Angles Against Maneuvering Targets," IEEE 55th Conference on Decision and Control, IEEE Publ., Piscataway, NJ, Dec. 2018, pp. 4142–4147. https://doi.org/10.1109/CDC.2016.7798897 Google Scholar[16] Ghosh S., Yakimenko O. A., Davis D. T. and Chung T. H., "Unmanned Aerial Vehicle Guidance for an All-Aspect Approach to a Stationary Point," Journal of Guidance, Control, and Dynamics, Vol. 40, No. 11, 2017, pp. 2871–2888. https://doi.org/10.2514/1.G002614 LinkGoogle Scholar[17] Singh S. and Sujit P. B., "Landmarks Based Path Planning for UAVs in GPS-Denied Areas," IFAC-PapersOnLine, Vol. 49, No. 1, 2016, pp. 396–400. https://doi.org/10.1016/j.ifacol.2016.03.086 CrossrefGoogle Scholar[18] Kabamba P. T., Meerkov S. M. and Zeitz F. H., "Optimal Path Planning for Unmanned Combat Aerial Vehicles to Defeat Radar Tracking," Journal of Guidance, Control, and Dynamics, Vol. 29, No. 2, 2006, pp. 279–288. https://doi.org/10.2514/1.14303 LinkGoogle Scholar[19] Lu P. and Liu X., "Autonomous Trajectory Planning for Rendezvous and Proximity Operations by Conic Optimization," Journal of Guidance, Control, and Dynamics, Vol. 36, No. 2, 2013, pp. 375–389. https://doi.org/10.2514/1.58436 LinkGoogle Scholar[20] Sujit P. B., Saripalli S. and Sousa J. B., "Unmanned Aerial Vehicle Path Following: A Survey and Analysis of Algorithms for Fixed-Wing Unmanned Aerial Vehicles," IEEE Control Systems Magazine, Vol. 34, No. 1, 2014, pp. 42–59. https://doi.org/10.1109/MCS.2013.2287568 CrossrefGoogle Scholar[21] Canny J., "A Voronoi Method for the Piano-Movers Problem," Proceedings of the 1985 IEEE International Conference on Robotics and Automation, Vol. 2, IEEE Publ., Piscataway, NJ, 1985, pp. 530–535. https://doi.org/10.1109/ROBOT.1985.1087297 Google Scholar[22] Takahashi O. and Schilling R. J., "Motion Planning in a Plane Using Generalized Voronoi Diagrams," IEEE Transactions on Robotics and Automation, Vol. 5, No. 2, 1989, pp. 143–150. https://doi.org/10.1109/70.88035 CrossrefGoogle Scholar[23] Dai R. and Cochran J., "Path Planning and State Estimation for Unmanned Aerial Vehicles in Hostile Environments," Journal of Guidance, Control, and Dynamics, Vol. 33, No. 2, 2010, pp. 595–601. https://doi.org/10.2514/1.46323 LinkGoogle Scholar[24] Asano T., Asano T., Guibas L., Hershberger J. and Imai H., "Visibility-Polygon Search and Euclidean Shortest Paths," 26th Annual Symposium on Foundations of Computer Science (sfcs 1985), IEEE Publ., Piscataway, NJ, 1985, pp. 155–164. https://doi.org/10.1109/SFCS.1985.65 Google Scholar[25] Alexopoulos C. and Griffin P. M., "Path Planning for a Mobile Robot," IEEE Transactions on Systems, Man, and Cybernetics, Vol. 22, No. 2, 1992, pp. 318–322. https://doi.org/10.1109/21.148404 CrossrefGoogle Scholar[26] Maekawa T., Noda T., Tamura S., Ozaki T. and Machida K.-I., "Curvature Continuous Path Generation for Autonomous Vehicle Using B-Spline Curves," Computer-Aided Design, Vol. 42, No. 4, 2010, pp. 350–359. https://doi.org/10.1016/j.cad.2009.12.007 CrossrefGoogle Scholar[27] Maini P. and Sujit P. B., "Path Planning for a UAV with Kinematic Constraints in the Presence of Polygonal Obstacles," 2016 International Conference on Unmanned Aircraft Systems (ICUAS), IEEE Publ., Piscataway, NJ, 2016, pp. 62–67. https://doi.org/10.1109/ICUAS.2016.7502625 Google Scholar[28] Brooks R. A. and Lozano-Perez T., "A Subdivision Algorithm in Configuration Space for Findpath with Rotation," IEEE Transactions on Systems, Man, and Cybernetics, Vol. SMC-15, No. 2, 1985, pp. 224–233. https://doi.org/10.1109/TSMC.1985.6313352 CrossrefGoogle Scholar[29] Dijkstra E. W., "A Note on Two Problems in Connexion with Graphs," Numerische Mathematik, Vol. 1, No. 1, 1959, pp. 269–271. https://doi.org/10.1007/BF01386390 CrossrefGoogle Scholar[30] Hart P. E., Nilsson N. J. and Raphael B., "A Formal Basis for the Heuristic Determination of Minimum Cost Paths," IEEE Transactions on Systems Science and Cybernetics, Vol. 4, No. 2, 1968, pp. 100–107. https://doi.org/10.1109/TSSC.1968.300136 CrossrefGoogle Scholar[31] Howard T. M., Green C. J. and Kelly A., "State Space Sampling of Feasible Motions for High Performance Mobile Robot Navigation in Highly Constrained Environments," Field and Service Robotics, Springer, Berlin, 2008, pp. 585–593. https://doi.org/10.1007/978-3-540-75404-6_56 CrossrefGoogle Scholar[32] Yang H. and Zhao Y., "Trajectory Planning for Autonomous Aerospace Vehicles Amid Known Obstacles and Conflicts," Journal of Guidance, Control, and Dynamics, Vol. 27, No. 6, 2004, pp. 997–1008. https://doi.org/10.2514/1.12514 LinkGoogle Scholar[33] Mattei M. and Blasi L., "Smooth Flight Trajectory Planning in the Presence of No-Fly Zones and Obstacles," Journal of Guidance, Control, and Dynamics, Vol. 33, No. 2, 2010, pp. 454–462. https://doi.org/10.2514/1.45161 LinkGoogle Scholar[34] Kavraki L. E., Svestka P., Latombe J.-C. and Overmars M. H., "Probabilistic Roadmaps for Path Planning in High-Dimensional Configuration Spaces," IEEE Transactions on Robotics and Automation, Vol. 12, No. 4, 1996, pp. 566–580. https://doi.org/10.1109/70.508439 CrossrefGoogle Scholar[35] Karaman S. and Frazzoli E., "Sampling-Based Algorithms for Optimal Motion Planning," International Journal of Robotics Research, Vol. 30, No. 7, 2011, pp. 846–894. https://doi.org/10.1177/0278364911406761 CrossrefGoogle Scholar[36] LaValle S. M. and Kuffner J. J., "Randomized Kinodynamic Planning," International Journal of Robotics Research, Vol. 20, No. 5, 2001, pp. 378–400. https://doi.org/10.1177/02783640122067453 CrossrefGoogle Scholar[37] Janson L., Schmerling E., Clark A. and Pavone M., "Fast Marching Tree: A Fast Marching Sampling-Based Method for Optimal Motion Planning in Many Dimensions," International Journal of Robotics Research, Vol. 34, No. 7, 2015, pp. 883–921. https://doi.org/10.1177/0278364915577958 CrossrefGoogle Scholar[38] Frazzoli E., Dahleh M. A. and Feron E., "Real-Time Motion Planning for Agile Autonomous Vehicles," Journal of Guidance, Control, and Dynamics, Vol. 25, No. 1, 2002, pp. 116–129. https://doi.org/10.2514/2.4856 LinkGoogle Scholar[39] Bhatia A. and Frazzoli E., "Incremental Search Methods for Reachability Analysis of Continuous and Hybrid Systems," International Workshop on Hybrid Systems: Computation and Control, Springer, Berlin, 2004, pp. 142–156. https://doi.org/10.1007/978-3-540-24743-2_10 Google Scholar[40] Cortés J., Jaillet L. and Siméon T., "Molecular Disassembly with RRT-Like Algorithms," IEEE International Conference on Robotics and Automation, IEEE Publ., Piscataway, NJ, 2007, pp. 3301–3306. https://doi.org/10.1109/ROBOT.2007.363982 Google Scholar[41] Zucker M., Kuffner J. and Branicky M., "Multipartite RRTs for Rapid Replanning in Dynamic Environments," IEEE Conference on Robotics and Automation, IEEE Publ., Piscataway, NJ, 2007, pp. 1063–1069. https://doi.org/10.1109/ROBOT.2007.363553 Google Scholar[42] Sun C., Liu Y.-C., Dai R. and Grymin D., "Two Approaches for Path Planning of Unmanned Aerial Vehicles with Avoidance Zones," Journal of Guidance, Control, and Dynamics, Vol. 40, No. 8, 2017, pp. 2076–2083. https://doi.org/10.2514/1.G002314 LinkGoogle Scholar[43] Baldini F., Bandyopadhyay S., Foust R., Chung S. J., Rahmani A., Croix J. P., Bacula A., Chilan C. M. and Hadaegh F. Y., "Fast Motion Planning for Agile Space Systems with Multiple Obstacles," AIAA/AAS Astrodynamics Specialist Conference, AIAA Paper 2016-5683, 2016, pp. 1–14. https://doi.org/10.2514/6.2016-5683 Google Scholar[44] Zinage V. and Ghosh S., "An Efficient Motion Planning Algorithm for UAVs in Obstacle-Cluttered Environment," Proceedings of American Control Conference, IEEE Publ., Piscataway, NJ, July 2019, pp. 2271–2276. Google Scholar[45] Wang P., Man Z., Cao Z., Zheng J. and Zhao Y., "Dynamics Modelling and Linear Control of Quadcopter," 2016 International Conference on Advanced Mechatronic Systems (ICAMechS), IEEE Publ., Piscataway, NJ, 2016, pp. 498–503. https://doi.org/10.1109/ICAMechS.2016.7813499 Google Scholar Previous article FiguresReferencesRelatedDetailsCited byA Guidance for Simultaneous Formation about a Stationary PointVivek A and Satadal Ghosh19 January 2023Right-of-Way-based Probabilistic Acceleration Velocity ObstacleFast and Efficient Motion Planning using Directional Sampling-based Generalized Shape ExpansionVrushabh V. Zinage and Satadal Ghosh4 January 2021On Probabilistic Completeness of the Generalized Shape Expansion-Based Motion Planning Algorithm What's Popular Volume 43, Number 9September 2020 CrossmarkInformationCopyright © 2020 by Vrushabh Vijaykumar Zinage and Satadal Ghosh. Published by the American Institute of Aeronautics and Astronautics, Inc., with permission. All requests for copying and permission to reprint should be submitted to CCC at www.copyright.com; employ the eISSN 1533-3884 to initiate your request. See also AIAA Rights and Permissions www.aiaa.org/randp. TopicsAircraft Operations and TechnologyAircraftsAlgorithms and Data StructuresAviation CommunicationCommunication SystemComputer Programming and LanguageComputing and InformaticsComputing, Information, and CommunicationData ScienceRADARRobot KinematicsRoboticsRobotsSearch AlgorithmUnmanned Aerial Vehicle KeywordsMotion PlanningUnmanned SystemSix Degree of FreedomTrajectory OptimizationShortest Path AlgorithmsSearch AlgorithmHistogramsMathematical OptimizationUnmanned Aerial SystemsProportional NavigationPDF Received7 August 2019Accepted18 June 2020Published online22 July 2020