Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • 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
Minimum time multi-UGV surveillance
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Optimization and Systems Theory.
2008 (English)In: OPTIMIZATION AND COOPERATIVE CONTROL STRATEGIES / [ed] Hirsch MJ; Commander CW; Pardalos PM; Murphey R, Berlin: Springer Verlag , 2008, 31-45 p.Conference paper, Published paper (Refereed)
Abstract [en]

This paper addresses the problem of concurrent task- and path planning for a number of  surveillance Unmanned Ground Vehicles (UGVs) such that a user defined area of interest is covered by the UGVs' sensors in minimum time. We first formulate the problem, and show that it is in fact  a generalization of the Multiple Traveling Salesmen Problem (MTSP), which is known to be NP-hard. We then propose a solution that decomposes the problem into three subproblems. The first is to find a maximal convex covering of the search area. Most results on static coverage  use disjoint partitions of the search area, e.g. triangulation, to convert the continuous sensor positioning problem into a  discrete one. However, by a simple example, we show that a highly overlapping set of maximal convex sets is better suited for  minimum time coverage. The second subproblem is a combinatorial assignment and ordering of the sets in the cover.  Since Tabu search algorithms are known to perform well on various routing problems,  we use it as a part of our proposed solution. Finally, the third subproblem utilizes a particular shortest path sub-routine in order to find the vehicle paths, and calculate the overall objective function used in the Tabu search. The proposed algorithm is illustrated by a number of simulation examples.

Place, publisher, year, edition, pages
Berlin: Springer Verlag , 2008. 31-45 p.
Series
LECTURE NOTES IN CONTROL AND INFORMATION SCIENCES, ISSN 0170-8643 ; 381
Keyword [en]
Boolean functions, Ground vehicles, Intelligent vehicle highway systems, Learning algorithms, Optimal control systems, Optimization, Routing algorithms, Sensor networks, Sensors, Set theory, Tabu search, Trees (mathematics), Unmanned vehicles, Area of interests, Combinatorial assignments, Concurrent tasks, Continuous, Convex sets, Discrete, Disjoint partitions, Minimum times, Objective functions, Path planning, Positioning, Routing problems, Search areas, Shortest paths, Simulation examples, Tabu search algorithms, Traveling salesman, Unmanned Ground Vehicles
National Category
Computational Mathematics
Identifiers
URN: urn:nbn:se:kth:diva-10061DOI: 10.1007/978-3-540-88063-9_2ISI: 000265134800002Scopus ID: 2-s2.0-54349098250ISBN: 978-3-540-88062-2 (print)OAI: oai:DiVA.org:kth-10061DiVA: diva2:202394
Conference
8th International Conference on Cooperative Control and Optimization, Gainesville, FL, JAN 30-FEB 01, 2008
Note
QC 20100622Available from: 2009-03-10 Created: 2009-03-10 Last updated: 2011-11-21Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Authority records BETA

Ögren, Petter

Search in DiVA

By author/editor
Anisi, David A.Ögren, Petter
By organisation
Optimization and Systems Theory
Computational Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

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

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • 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