Coordinated road-network search route planning by a team of UAVs

Hyondong Oh, Seungkeun Kim, Antonios Tsourdos and Brian A. White

International Journal of Systems Science, 2014, vol. 45, issue 5, 825-840

Abstract: This paper presents a road-network search route planning algorithm by which multiple autonomous vehicles are able to efficiently visit every road identified in the map in the context of the Chinese postman problem. Since the typical Chinese postman algorithm can be applied solely to a connected road-network in which ground vehicles are involved, it is modified to be used for a general type of road map including unconnected roads as well as the operational and physical constraints of unmanned aerial vehicles (UAVs). For this, a multi-choice multi-dimensional knapsack problem is formulated to find an optimal solution minimising flight time and then solved via mixed integer linear programming. To deal with the dynamic constraints of the UAVs, the Dubins theory is used for path generation. In particular, a circular–circular–circular type of the Dubins path is exploited based on a differential geometry to guarantee that the vehicles follow the road precisely in a densely distributed road environment. Moreover, to overcome the computational burden of the multi-choice multi-dimensional knapsack algorithm, a nearest insertion and auction-based approximation algorithm is newly introduced. The properties and performance of the proposed algorithm are evaluated via numerical simulations operating on a real village map and randomly generated maps with different parameters.

Date: 2014
References: View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://hdl.handle.net/10.1080/00207721.2012.737116 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:taf:tsysxx:v:45:y:2014:i:5:p:825-840

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/TSYS20

DOI: 10.1080/00207721.2012.737116

Access Statistics for this article

International Journal of Systems Science is currently edited by Visakan Kadirkamanathan

More articles in International Journal of Systems Science from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().