{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,30]],"date-time":"2026-06-30T01:13:50Z","timestamp":1782782030129,"version":"3.54.5"},"reference-count":41,"publisher":"MDPI AG","issue":"7","license":[{"start":{"date-parts":[[2019,7,15]],"date-time":"2019-07-15T00:00:00Z","timestamp":1563148800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"National Key Research and Development Project","award":["2018YFB0505300"],"award-info":[{"award-number":["2018YFB0505300"]}]},{"name":"National Key Research and Development Project","award":["2017YFB0503703"],"award-info":[{"award-number":["2017YFB0503703"]}]},{"name":"Guangxi Science and Technology Major Project","award":["AA18118025"],"award-info":[{"award-number":["AA18118025"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IJGI"],"abstract":"<jats:p>The increasing number of unmanned aerial vehicles (UAVs) has led to challenges related to solving the collision problem to ensure air traffic safety. The traditional approaches employed for collision detection suffer from two main drawbacks: first, the computational burden of a pairwise calculation increases exponentially with an increasing number of spatial entities; second, existing grid-based approaches are unsuitable for complicated scenarios with a large number of objects moving at high speeds. In the proposed model, we first identified UAVs and other spatial objects with GeoSOT-3D grids. Second, the nonrelational spatial database was initialized with a multitable strategy, and spatiotemporal data were inserted with the GeoSOT-3D grid codes as the primary key. Third, the collision detection procedure was transformed from a pairwise calculation to a multilevel query. Four simulation experiments were conducted to verify the feasibility and efficiency of the proposed collision detection model for UAVs in different environments. The results also indicated that 64 m GeoSOT-3D grids are the most suitable basic grid size, and the reduction in the time consumption compared with traditional methods reached approximately 50\u201380% in different scenarios.<\/jats:p>","DOI":"10.3390\/ijgi8070299","type":"journal-article","created":{"date-parts":[[2019,7,16]],"date-time":"2019-07-16T02:23:16Z","timestamp":1563243796000},"page":"299","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":21,"title":["Collision Detection for UAVs Based on GeoSOT-3D Grids"],"prefix":"10.3390","volume":"8","author":[{"given":"Weixin","family":"Zhai","sequence":"first","affiliation":[{"name":"Academy for Advanced Interdisciplinary Studies, Peking University, Beijing 100871, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9754-1502","authenticated-orcid":false,"given":"Xiaochong","family":"Tong","sequence":"additional","affiliation":[{"name":"Zhengzhou Institute of Surveying and Mapping, Zhengzhou 450001, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5308-1551","authenticated-orcid":false,"given":"Shuangxi","family":"Miao","sequence":"additional","affiliation":[{"name":"College of Engineering, Peking University, Beijing 100871, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Chengqi","family":"Cheng","sequence":"additional","affiliation":[{"name":"College of Engineering, Peking University, Beijing 100871, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fuhu","family":"Ren","sequence":"additional","affiliation":[{"name":"Beijing Institute of Big Data Research, Beijing 100871, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2019,7,15]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"13","DOI":"10.3390\/machines2010013","article-title":"The multiple unmanned air vehicle persistent surveillance problem: A review","volume":"2","author":"Nigam","year":"2014","journal-title":"Machines"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1155\/2016\/7426913","article-title":"Survey of robot 3D path planning algorithms","volume":"2016","author":"Yang","year":"2016","journal-title":"J. Control Sci. Eng."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"1519","DOI":"10.3390\/rs4061519","article-title":"Development of a UAV-LiDAR system with application to forest inventory","volume":"4","author":"Wallace","year":"2012","journal-title":"Remote Sens."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1177\/0278364914558017","article-title":"Motion primitives and 3D path planning for fast flight through a forest","volume":"34","author":"Paranjape","year":"2015","journal-title":"Int. J. Robot. Res."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Zang, Y., Yang, B., Li, J., and Guan, H. (2019). An Accurate TLS and UAV Image Point Clouds Registration Method for Deformation Detection of Chaotic Hillside Areas. Remote Sens., 11.","DOI":"10.3390\/rs11060647"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1016\/j.eswa.2016.02.007","article-title":"Coverage path planning with unmanned aerial vehicles for 3D terrain reconstruction","volume":"55","author":"Torres","year":"2016","journal-title":"Expert Syst. Appl."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Ryan, A., Zennaro, M., Howell, A., Sengupta, R., and Hedrick, J.K. (2004, January 14\u201317). An overview of emerging results in cooperative UAV control. Proceedings of the 2004 43rd IEEE Conference on Decision and Control (CDC) (IEEE Cat. No. 04CH37601), Nassau, Bahamas.","DOI":"10.1109\/CDC.2004.1428700"},{"key":"ref_8","unstructured":"Achtelik, M., Bachrach, A., He, R., Prentice, S., and Roy, N. (2019, May 01). Autonomous Navigation and Exploration of a Quadrotor Helicopter in GPS-Denied Indoor Environments. Available online: http:\/\/citeseerx.ist.psu.edu\/viewdoc\/download?doi=10.1.1.330.2679&rep=rep1&type=pdf."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1177\/0278364908090949","article-title":"Flying fast and low among obstacles: Methodology and experiments","volume":"27","author":"Scherer","year":"2008","journal-title":"Int. J. Robot. Res."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1002\/rob.20178","article-title":"Building a Robust Implementation of Bearing-only Inertial SLAM for a UAV","volume":"24","author":"Bryson","year":"2007","journal-title":"J. Field Robot."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1109\/TRO.2011.2162999","article-title":"A fully autonomous indoor quadrotor","volume":"28","author":"Grzonka","year":"2012","journal-title":"IEEE Trans. Robot."},{"key":"ref_12","first-page":"718","article-title":"LIDAR obstacle warning and avoidance system for unmanned aircraft","volume":"8","author":"Sabatini","year":"2014","journal-title":"Int. J. Mech. Aerosp. Ind. Mechatron. Eng."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"294","DOI":"10.1590\/S1678-58782012000300010","article-title":"In-flight collision avoidance controller based only on OS4 embedded sensors","volume":"34","author":"Becker","year":"2012","journal-title":"J. Braz. Soc. Mech. Sci. Eng."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"150","DOI":"10.1109\/MCOM.2015.7060497","article-title":"WiFi-based indoor positioning","volume":"53","author":"Yang","year":"2015","journal-title":"IEEE Commun. Mag."},{"key":"ref_15","unstructured":"Bekkelien, A., Deriaz, M., and Marchand-Maillet, S. (2012). Bluetooth Indoor Positioning. [Master\u2019s Thesis, University of Geneva]."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"760","DOI":"10.1177\/027836499801700706","article-title":"Motion planning in dynamic environments using velocity obstacles","volume":"17","author":"Fiorini","year":"1998","journal-title":"Int. J. Robot. Res."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"1265","DOI":"10.1109\/TAES.2011.5751257","article-title":"Probabilistic noncooperative near mid-air collision avoidance","volume":"47","author":"Nordlund","year":"2011","journal-title":"IEEE Trans. Aerosp. Electron. Syst."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"2490","DOI":"10.1109\/TAES.2011.6034646","article-title":"Near-optimal terrain collision avoidance trajectories using elevation maps","volume":"47","author":"Malaek","year":"2011","journal-title":"IEEE Trans. Aerosp. Electron. Syst."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"79","DOI":"10.2514\/2.4678","article-title":"Resolution of conflicts involving many aircraft via semidefinite programming","volume":"24","author":"Frazzoli","year":"2001","journal-title":"J. Guid. Control. Dyn."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"2947","DOI":"10.1109\/TAES.2012.6324671","article-title":"Integration of a triaxial magnetometer into a helicopter UAV GPS-aided INS","volume":"48","author":"Barczyk","year":"2012","journal-title":"IEEE Trans. Aerosp. Electron. Syst."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"311","DOI":"10.2514\/atcq.9.4.311","article-title":"System performance characteristics of centralized and decentralized air traffic separation strategies","volume":"9","author":"Krozel","year":"2001","journal-title":"Air Traffic Control Q."},{"key":"ref_22","unstructured":"Jardin, M.R. (2003, January 23\u201327). Real-time conflict-free trajectory optimization. Proceedings of the fifth USA\/Europe Air Traffic Management R&D Seminar, Budapest, Hungary."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"1150","DOI":"10.2514\/1.12758","article-title":"Analytical relationships between conflict counts and air-traffic density","volume":"28","author":"Jardin","year":"2005","journal-title":"J. Guid. Control. Dyn."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Jardin, M.R. (2005, January 15\u201318). Grid-based strategic air traffic conflict detection. Proceedings of the AIAA Guidance, Navigation, and Control Conference and Exhibit, San Francisco, CA, USA.","DOI":"10.2514\/6.2005-5826"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Koeners, J., and de Vries, M. (2008, January 26\u201330). Conflict resolution support for air traffic control based on solution spaces: Design and implementation. Proceedings of the 2008 IEEE\/AIAA 27th Digital Avionics Systems Conference, St. Paul, MN, USA.","DOI":"10.1109\/DASC.2008.4702808"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1007\/s10514-013-9349-9","article-title":"Towards a swarm of agile micro quadrotors","volume":"35","author":"Kushleyev","year":"2013","journal-title":"Auton. Robot."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"025012","DOI":"10.1088\/1748-3182\/9\/2\/025012","article-title":"Flocking algorithm for autonomous flying robots","volume":"9","author":"Tarcai","year":"2014","journal-title":"Bioinspir. Biomim."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"V\u00e1s\u00e1rhelyi, G., Vir\u00e1gh, C., Somorjai, G., Tarcai, N., Sz\u00f6r\u00e9nyi, T., Nepusz, T., and Vicsek, T. (2014, January 14\u201318). Outdoor flocking and formation flight with autonomous aerial robots. Proceedings of the 2014 IEEE\/RSJ International Conference on Intelligent Robots and Systems, Chicago, IL, USA.","DOI":"10.1109\/IROS.2014.6943105"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1007\/s11277-016-3184-1","article-title":"Two tier search scheme using micro UAV swarm","volume":"93","author":"Choi","year":"2017","journal-title":"Wirel. Pers. Commun."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"320","DOI":"10.3390\/ijgi4010320","article-title":"Categorization and conversions for indexing methods of discrete global grid systems","volume":"4","author":"Amiri","year":"2015","journal-title":"ISPRS Int. J. Geo-Inf."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/j.cag.2015.08.005","article-title":"A survey of digital earth","volume":"53","author":"Alderson","year":"2015","journal-title":"Comput. Graph."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"898","DOI":"10.1080\/13658816.2012.725474","article-title":"Efficient encoding and spatial operation scheme for aperture 4 hexagonal discrete global grid system","volume":"27","author":"Tong","year":"2013","journal-title":"Int. J. Geogr. Inf. Sci."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1007\/s12145-018-0362-6","article-title":"Method for managing and querying geo-spatial data using a grid-code-array spatial index","volume":"12","author":"Li","year":"2019","journal-title":"Earth Sci. Inform."},{"key":"ref_34","first-page":"443","article-title":"Subdivision R-Tree Index Model of the Earth-based Three-dimensional Subdivision Grids","volume":"41","author":"Zhai","year":"2016","journal-title":"Geomat. Inf. Sci. Wuhan Univ."},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Hu, X., and Cheng, C. (2014, January 25\u201327). The three-dimensional data organization method based on GeoSOT-3D. Proceedings of the 2014 22nd International Conference on Geoinformatics, Kaohsiung, Taiwan.","DOI":"10.1109\/GEOINFORMATICS.2014.6950825"},{"key":"ref_36","doi-asserted-by":"crossref","unstructured":"Li, S., Cheng, C., and Pu, G. (2019). QRA-Grid: Quantitative Risk Analysis and Grid-based Pre-warning Model for Urban Natural Gas Pipeline. ISPRS Int. J. Geo-Inf., 8.","DOI":"10.3390\/ijgi8030122"},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Zhang, H., Cheng, C., and Miao, S. (2019). A Precise Urban Component Management Method Based on the GeoSOT Grid Code and BIM. ISPRS Int. J. Geo-Inf., 8.","DOI":"10.3390\/ijgi8030159"},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"034003","DOI":"10.1117\/1.JRS.10.034003","article-title":"Integration and management of massive remote-sensing data based on GeoSOT subdivision model","volume":"10","author":"Li","year":"2016","journal-title":"J. Appl. Remote Sens."},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Qi, K., Cheng, C., Hu, Y.n., Fang, H., Ji, Y., and Chen, B. (2017). An improved identification code for city components based on discrete global grid system. ISPRS Int. J. Geo-Inf., 6.","DOI":"10.3390\/ijgi6120381"},{"key":"ref_40","doi-asserted-by":"crossref","unstructured":"Cheng, C., Tong, X., Chen, B., and Zhai, W. (2016). A subdivision method to unify the existing latitude and longitude grids. ISPRS Int. J. Geo-Inf., 5.","DOI":"10.3390\/ijgi5090161"},{"key":"ref_41","unstructured":"Dempsey, M.E., and Rasmussen, S. (2010). Eyes of the Army\u2013US Army Roadmap for Unmanned Aircraft Systems 2010\u20132035, US Army UAS Center of Excellence."}],"container-title":["ISPRS International Journal of Geo-Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2220-9964\/8\/7\/299\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T13:05:41Z","timestamp":1760187941000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2220-9964\/8\/7\/299"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7,15]]},"references-count":41,"journal-issue":{"issue":"7","published-online":{"date-parts":[[2019,7]]}},"alternative-id":["ijgi8070299"],"URL":"https:\/\/doi.org\/10.3390\/ijgi8070299","relation":{},"ISSN":["2220-9964"],"issn-type":[{"value":"2220-9964","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,7,15]]}}}