Change search
ReferencesLink to record
Permanent link

Direct link
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 (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.
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
URN: urn:nbn:se:kth:diva-10061DOI: 10.1007/978-3-540-88063-9_2ISI: 000265134800002ScopusID: 2-s2.0-54349098250ISBN: 978-3-540-88062-2OAI: diva2:202394
8th International Conference on Cooperative Control and Optimization, Gainesville, FL, JAN 30-FEB 01, 2008
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

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
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

Altmetric score

Total: 61 hits
ReferencesLink to record
Permanent link

Direct link