liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Optimal placement of UV-based communications relay nodes
Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.ORCID iD: 0000-0003-1836-4200
Linköping University, Department of Computer and Information Science, KPLAB - Knowledge Processing Lab. Linköping University, The Institute of Technology.
Linköping University, Department of Mathematics, Optimization . Linköping University, The Institute of Technology.ORCID iD: 0000-0001-5907-0087
Linköping University, Department of Computer and Information Science, KPLAB - Knowledge Processing Lab. Linköping University, The Institute of Technology.
2010 (English)In: Journal of Global Optimization, ISSN 0925-5001, E-ISSN 1573-2916, Vol. 48, no 4, p. 511-531Article in journal (Refereed) Published
Abstract [en]

We consider a constrained optimization problem with mixed integer and real variables. It models optimal placement of communications relay nodes in the presence of obstacles. This problem is widely encountered, for instance, in robotics, where it is required to survey some target located in one point and convey the gathered information back to a base station located in another point. One or more unmanned aerial or ground vehicles (UAVs or UGVs) can be used for this purpose as communications relays. The decision variables are the number of unmanned vehicles (UVs) and the UV positions. The objective function is assumed to access the placement quality. We suggest one instance of such a function which is more suitable for accessing UAV placement. The constraints are determined by, firstly, a free line of sight requirement for every consecutive pair in the chain and, secondly, a limited communication range. Because of these requirements, our constrained optimization problem is a difficult multi-extremal problem for any fixed number of UVs. Moreover, the feasible set of real variables is typically disjoint. We present an approach that allows us to efficiently find a practically acceptable approximation to a global minimum in the problem of optimal placement of communications relay nodes. It is based on a spatial discretization with a subsequent reduction to a shortest path problem. The case of a restricted number of available UVs is also considered here. We introduce two label correcting algorithms which are able to take advantage of using some peculiarities of the resulting restricted shortest path problem. The algorithms produce a Pareto solution to the two-objective problem of minimizing the path cost and the number of hops. We justify their correctness. The presented results of numerical 3D experiments show that our algorithms are superior to the conventional Bellman-Ford algorithm tailored to solving this problem.

Place, publisher, year, edition, pages
Springer , 2010. Vol. 48, no 4, p. 511-531
Keywords [en]
Unmanned vehicles, Global optimization, Hop-restricted shortest paths, Pareto solution, Label correcting algorithms
National Category
Mathematics
Identifiers
URN: urn:nbn:se:liu:diva-60067DOI: 10.1007/s10898-010-9526-8ISI: 000283223700001OAI: oai:DiVA.org:liu-60067DiVA, id: diva2:354877
Note
The original publication is available at www.springerlink.com: Oleg Burdakov, Patrick Doherty, Kaj Holmberg and Per-Magnus Olsson, Optimal placement of UV-based communications relay nodes, 2010, Journal of Global Optimization, (48), 4, 511-531. http://dx.doi.org/10.1007/s10898-010-9526-8 Copyright: Springer Science Business Media http://www.springerlink.com/ Available from: 2010-10-05 Created: 2010-10-05 Last updated: 2017-12-12

Open Access in DiVA

fulltext(459 kB)1432 downloads
File information
File name FULLTEXT01.pdfFile size 459 kBChecksum SHA-512
a402ac5abedcf2e9a26c8612b4924d64dc64162c84b0c930e39205926f83b1d393b652a5707ea87149f23de1dea4d3e672dece483ed398cccc7c6da022e4ff41
Type fulltextMimetype application/pdf

Other links

Publisher's full text

Authority records

Burdakov, OlegDoherty, PatrickHolmberg, KajOlsson, Per-Magnus

Search in DiVA

By author/editor
Burdakov, OlegDoherty, PatrickHolmberg, KajOlsson, Per-Magnus
By organisation
Optimization The Institute of TechnologyKPLAB - Knowledge Processing Lab
In the same journal
Journal of Global Optimization
Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 1432 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 629 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf