A Dual Ascent Method for the Hop-constrained Shortest Path with Application to Positioning of Unmanned Aerial Vehicles
Burdakov, Oleg Holmberg, Kaj Olsson, Per-Magnus
2008 (English)Report (Other academic)
We study the problem of positioning unmanned aerial vehicles (UAVs) to maintain an unobstructed flow of communication from a surveying UAV to some base station through the use of multiple relay UAVs. This problem can be modeled as a hopconstrained shortest path problem in a large visibility graph. We propose a dual ascent method for solving this problem, optionally within a branch-and-bound framework. Computational tests show that realistic problems can be solved in a reasonably short time, and that the proposed method is faster than the classical dynamic programming approach.
Place, publisher, year, pages
Linköping: Linköping University Electronic Press, 2008. , 30 p.
Report / Department of Mathematics, Universitetet i Linköping, Tekniska högskolan, ISSN 0348-2960 ; 2008:7
Hop-constrained, shortest path, dual ascent, visibility graph, UAV, relay
IdentifiersURN: urn:nbn:se:liu:diva-14997Local ID: LiTH-MAT-R-2008-07OAI: oai:DiVA.org:liu-14996DiVA: diva2:37550