{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,2]],"date-time":"2026-05-02T06:49:59Z","timestamp":1777704599738,"version":"3.51.4"},"reference-count":25,"publisher":"SAGE Publications","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IFS"],"published-print":{"date-parts":[[2020,12,4]]},"abstract":"<jats:p>In recent times, Unmanned Air Vehicles (UAVs) are being deployed for several tasks of terrain coverage such as surveillance, photogrammetry, smart irrigation, civil security, and disaster management. In these applications, one of the most vital issues to be addressed is, covering the area under observation with minimum traversal for the UAV. So, the problem addressed in this paper is as follows: For a given geographic area and the given parameters describing the UAV\u2019s coverage capacity, the problem is to find an optimal route that covers the given geographic area. In this paper, an optimal path planning algorithm for the area under observation, given as a closed curve, is proposed. The algorithm partitions the given area of interest into multiple non-uniform rectangles while considering other parameters such as the flying altitude of the UAV and obstacles that could be encountered during its flight. The problem is transformed into Traveling Salesman Problem by constructing a graph from the rectangular partitioning. Effective approximate solutions are provided to this problem, using the Minimum Spanning Tree (MST) approximation algorithm and Ant Colony Optimization (ACO). The experimental results show that ACO outperforms the MST based algorithm as it does not get stuck in local minima.<\/jats:p>","DOI":"10.3233\/jifs-189140","type":"journal-article","created":{"date-parts":[[2020,8,11]],"date-time":"2020-08-11T17:56:52Z","timestamp":1597168612000},"page":"8191-8203","source":"Crossref","is-referenced-by-count":28,"title":["Graph-based path planning for intelligent UAVs in area coverage applications"],"prefix":"10.1177","volume":"39","author":[{"given":"J.","family":"Akshya","sequence":"first","affiliation":[{"name":"School of Computing, SASTRA Deemed to be University, Thanjavur, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"P.L.K.","family":"Priyadarsini","sequence":"additional","affiliation":[{"name":"School of Computing, SASTRA Deemed to be University, Thanjavur, India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","reference":[{"key":"10.3233\/JIFS-189140_ref1","doi-asserted-by":"crossref","first-page":"101180","DOI":"10.1016\/j.techsoc.2019.101180","article-title":"Public acceptance of drones: Knowledge, attitudes, and practice","volume":"59","author":"Aydin","year":"2019","journal-title":"Technology in Society"},{"key":"10.3233\/JIFS-189140_ref2","doi-asserted-by":"crossref","first-page":"260","DOI":"10.1016\/j.engappai.2018.11.008","article-title":"TERRA: A path planning algorithm for cooperative UGV\u2013UAV exploration","volume":"78","author":"Ropero","year":"2019","journal-title":"Engineering Applications of Artificial Intelligence"},{"issue":"5","key":"10.3233\/JIFS-189140_ref5","doi-asserted-by":"crossref","first-page":"513","DOI":"10.1504\/IJCSM.2019.103679","article-title":"Robust and minimum spanning tree in fuzzy environment","volume":"10","author":"Dey","year":"2019","journal-title":"International Journal of Computing Science and Mathematics"},{"key":"10.3233\/JIFS-189140_ref6","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1016\/j.cie.2019.01.020","article-title":"Multiple traveling salesman problem with drones: Mathematical model and heuristic approach","volume":"129","author":"Kitjacharoenchai","year":"2019","journal-title":"Computers & Industrial Engineering"},{"issue":"4","key":"10.3233\/JIFS-189140_ref7","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1016\/j.plrev.2005.10.001","article-title":"Ant colony optimization: Introduction and recent trends","volume":"2","author":"Blum","year":"2005","journal-title":"Physics of Life reviews"},{"issue":"3","key":"10.3233\/JIFS-189140_ref8","doi-asserted-by":"crossref","first-page":"2075","DOI":"10.3233\/JIFS-169919","article-title":"A hybrid approach to generate visually seamless aerial mosaicks from unmanned aerial vehicles","volume":"36","author":"George","year":"2019","journal-title":"Journal of Intelligent & Fuzzy Systems"},{"issue":"2","key":"10.3233\/JIFS-189140_ref9","doi-asserted-by":"crossref","first-page":"967","DOI":"10.3233\/JIFS-169873","article-title":"A study on the UAV image-based efficiency improvement of bridge maintenance and inspection","volume":"36","author":"Lee","year":"2019","journal-title":"Journal of Intelligent & Fuzzy Systems"},{"issue":"4","key":"10.3233\/JIFS-189140_ref10","doi-asserted-by":"crossref","first-page":"4026","DOI":"10.3390\/rs70404026","article-title":"Evaluating multispectral images and vegetation indices for precision farming applications from UAV images","volume":"7","author":"Candiago","year":"2015","journal-title":"Remote Sensing"},{"issue":"3","key":"10.3233\/JIFS-189140_ref12","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1109\/MCOM.2017.1600238CM","article-title":"UAV-enabled intelligent transportation systems for the smart city: Applications and challenges","volume":"55","author":"Menouar","year":"2017","journal-title":"IEEE Communications Magazine"},{"issue":"2","key":"10.3233\/JIFS-189140_ref17","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1007\/s10732-019-09431-y","article-title":"A hybrid genetic algorithm for the traveling salesman problem with drone","volume":"26","author":"Ha","year":"2020","journal-title":"Journal of Heuristics"},{"key":"10.3233\/JIFS-189140_ref18","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1016\/j.knosys.2018.05.033","article-title":"Survey on computational-intelligence-based UAV path planning","volume":"158","author":"Zhao","year":"2018","journal-title":"Knowledge-Based Systems"},{"issue":"1","key":"10.3233\/JIFS-189140_ref19","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1007\/s10846-014-0077-y","article-title":"Path planning for multi-UAV for-mation","volume":"77","author":"Chen","year":"2015","journal-title":"Journal of Intelligent &Robotic Systems"},{"issue":"2","key":"10.3233\/JIFS-189140_ref20","doi-asserted-by":"crossref","first-page":"391","DOI":"10.1007\/s10846-013-9901-z","article-title":"Geometric reinforcement learning for path planning of UAVs","volume":"77","author":"Zhang","year":"2015","journal-title":"Journal of Intelligent & Robotic Systems"},{"issue":"11","key":"10.3233\/JIFS-189140_ref21","doi-asserted-by":"crossref","first-page":"3179","DOI":"10.1109\/TITS.2017.2673778","article-title":"Sampling-based path planning for UAV collision avoidance","volume":"18","author":"Lin","year":"2017","journal-title":"IEEE Transactions on Intelligent Transportation Systems"},{"issue":"6","key":"10.3233\/JIFS-189140_ref22","doi-asserted-by":"crossref","first-page":"1407","DOI":"10.1080\/00207721.2014.929191","article-title":"UAV path planning using artificial potential field method updated by optimal control theory","volume":"47","author":"Chen","year":"2016","journal-title":"International Journal of Systems Science"},{"key":"10.3233\/JIFS-189140_ref23","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1016\/j.ast.2016.04.002","article-title":"Cooperative path planning with applications to tar-get tracking and obstacle avoidance for multi-UAVs","volume":"54","author":"Yao","year":"2016","journal-title":"Aerospace Science and Technology"},{"issue":"2-4","key":"10.3233\/JIFS-189140_ref24","doi-asserted-by":"crossref","first-page":"751","DOI":"10.1007\/s10846-017-0559-9","article-title":"Area partition for coastal regions with multiple UAS","volume":"88","author":"Balampanis","year":"2017","journal-title":"Journal of Intelligent & Robotic Systems"},{"issue":"1-4","key":"10.3233\/JIFS-189140_ref25","doi-asserted-by":"crossref","first-page":"543","DOI":"10.1007\/s10846-015-0272-5","article-title":"A distributed algorithm for area partitioning in grid-shape and vector-shape configurations with multiple aerial robots","volume":"84","author":"Acevedo","year":"2016","journal-title":"Journal of Intelligent & Robotic Systems"},{"issue":"1","key":"10.3233\/JIFS-189140_ref26","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1007\/s11431-018-9449-9","article-title":"Formation control and collision avoidance for multi-UAV systems based on Voronoi partition","volume":"63","author":"Hu","year":"2020","journal-title":"Science China Technological Sciences"},{"issue":"3-4","key":"10.3233\/JIFS-189140_ref27","doi-asserted-by":"crossref","first-page":"663","DOI":"10.1007\/s10846-016-0461-x","article-title":"DARP: divide areas algorithm for optimal multi-robot coverage path planning","volume":"86","author":"Kapoutsis","year":"2017","journal-title":"Journal of Intelligent & Robotic Systems"},{"key":"10.3233\/JIFS-189140_ref28","doi-asserted-by":"crossref","first-page":"111","DOI":"10.5194\/isprsannals-III-7-111-2016","article-title":"A minimum spanning tree based method for UAV image segmentation","volume":"3","author":"Wang","year":"2016","journal-title":"ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences"},{"issue":"1","key":"10.3233\/JIFS-189140_ref29","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.ejor.2019.05.017","article-title":"The generalized minimum spanning tree problem: An overview of formulations, solution procedures and latest advances","volume":"283","author":"Pop","year":"2020","journal-title":"European Journal of Operational Research"},{"key":"10.3233\/JIFS-189140_ref31","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0304-3975(77)90012-3","article-title":"Euclidean traveling salesman problem is NP complete","volume":"4","author":"Papadimitriou","year":"1978","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"10.3233\/JIFS-189140_ref32","doi-asserted-by":"crossref","first-page":"3271","DOI":"10.1007\/s11277-017-3994-9","article-title":"Efficient nearest neighbor heuristic TSP algorithms for reducing data acquisition latency of UAV relay WSN","volume":"95","author":"Alemayehu","year":"2017","journal-title":"Wireless Personal Communications"},{"issue":"1","key":"10.3233\/JIFS-189140_ref33","doi-asserted-by":"crossref","first-page":"47","DOI":"10.3233\/JIFS-172127","article-title":"Multi-objective four dimensional imprecise TSP solved with a hybrid multi-objective ant colony optimization-genetic algorithm with diversity","volume":"36","author":"Khanra","year":"2019","journal-title":"Journal of Intelligent & Fuzzy Systems"}],"container-title":["Journal of Intelligent &amp; Fuzzy Systems"],"original-title":[],"link":[{"URL":"https:\/\/content.iospress.com\/download?id=10.3233\/JIFS-189140","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T09:41:34Z","timestamp":1777455694000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/full\/10.3233\/JIFS-189140"}},"subtitle":[],"editor":[{"given":"Vijayakumar","family":"Varadarajan","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]},{"given":"Piet","family":"Kommers","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]},{"given":"Vincenzo","family":"Piuri","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]},{"given":"V.","family":"Subramaniyaswamy","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[2020,12,4]]},"references-count":25,"journal-issue":{"issue":"6"},"URL":"https:\/\/doi.org\/10.3233\/jifs-189140","relation":{},"ISSN":["1064-1246","1875-8967"],"issn-type":[{"value":"1064-1246","type":"print"},{"value":"1875-8967","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,12,4]]}}}