Change search
ReferencesLink to record
Permanent link

Direct link
Algorithms for the connectivity constrained unmanned ground vehicle surveillance problem
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.). (Optimization and Systems Theory)
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.).
KTH, School of Computer Science and Communication (CSC), Computer Vision and Active Perception, CVAP.ORCID iD: 0000-0002-7714-928X
2009 (English)In: European Control Conference (ECC), Budapest, Hungary: EUCA , 2009Conference paper (Refereed)
Abstract [en]

The Connectivity Constrained UGV Surveillance Problem (CUSP) considered in this paper is the following. Given a set of surveillance UGVs and a user defined area to be covered, find waypoint-paths such that; 1) the area is completely surveyed, 2) the time for performing the search is minimized and 3) the induced information graph is kept recurrently connected. It has previously been shown that the CUSP is NP-hard. This paper presents four different heuristic algorithms for solving the CUSP, namely, the Token Station Algorithm, the Stacking Algorithm, the Visibility Graph Algorithm and the Connectivity Primitive Algorithm. These algorithms are then compared by means of Monte Carlo simulations. The conclusions drawn are that the Token Station Algorithm provides the most optimal solutions, the Stacking Algorithm has the lowest computational complexity, while the Connectivity Primitive Algorithm provides the best trade-off between optimality and computational complexity for larger problem instances.

Place, publisher, year, edition, pages
Budapest, Hungary: EUCA , 2009.
Keyword [en]
Cooperative control, Optimization algorithms, Autonomous systems
National Category
Natural Sciences
URN: urn:nbn:se:kth:diva-10058OAI: diva2:202383
European Control Conference 2009 - ECC’09. 23-26 August 2009, Budapest, Hungary
QC 20111010Available from: 2009-03-10 Created: 2009-03-10 Last updated: 2011-11-21Bibliographically approved

Open Access in DiVA

No full text

Search in DiVA

By author/editor
Anisi, David A.Lindskog, ThereseÖgren, Petter
By organisation
Mathematics (Dept.)Computer Vision and Active Perception, CVAP
Natural Sciences

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

Total: 90 hits
ReferencesLink to record
Permanent link

Direct link