Change search
ReferencesLink to record
Permanent link

Direct link
A comparative study of task assignment and path planning methods for multi-UGV missions
Department of Autonomous Systems, Swedish Defence Research Institute (FOI).
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Optimization and Systems Theory.
Department of Autonomous Systems, Swedish Defence Research Institute (FOI).ORCID iD: 0000-0002-7714-928X
2009 (English)In: OPTIMIZATION AND COOPERATIVE CONTROL STRATEGIES / [ed] Hirsch, MJ; Commander, CW; Pardalos, PM; Murphey, R, 2009, 167-180 p.Conference paper (Refereed)
Abstract [en]

Many important problems involving a group of unmanned ground vehicles (UGVs) are closely related to the multi traviling salesman problem (m-TSP). This paper comprises a comparative study of a number of algorithms proposed in the litterature to solve m-TSPs occuring in robotics. The investigated algoritms include two mixed integer linear programming (MILP) formulations, a market based approach (MA), a Voronoi partition step (VP) combined with the local search used in MA, and a deterministic and a stocastic version of the granular tabu search (GTS). To evaluate the algoritms, an m-TSP is derived from a planar environment with polygonal obstacles and uniformly distributed targets and vehicle positions. The results of the comparison indicate that out of the decentralized approaches, the MA yield good solutions but requires long computation times, while VP is fast but not as good. The two MILP approaches suffer from long computation times, and poor results due to the decomposition of the assignment and path planning steps. Finally, the two GTS algorithms yield good results in short times with inputs from MA as well as the much faster VP. Thus the best performing centralized approach is the GTS in combination with the VP. Funded by the Swedish defence materiel administration (FMV) and the Swedish armed forces through the Technologies for Autonomous and Intelligent Systems (TAIS) project. 297316-LB704859

Place, publisher, year, edition, pages
2009. 167-180 p.
, Lecture Notes in Control and Information Sciences, ISSN 0170-8643
Keyword [en]
National Category
Computer Vision and Robotics (Autonomous Systems)
URN: urn:nbn:se:kth:diva-57996ISI: 000265134800010ScopusID: 2-s2.0-54349103991ISBN: 978-3-540-88062-2OAI: diva2:472897
8th International Conference on Cooperative Control and Optimization. Gainesville, FL. JAN 30-FEB 01, 2008
QC 20120109Available from: 2012-01-04 Created: 2012-01-04 Last updated: 2012-01-09Bibliographically approved

Open Access in DiVA

No full text


Search in DiVA

By author/editor
Thunberg, JohanAnisi, DavidÖgren, Petter
By organisation
Optimization and Systems Theory
Computer Vision and Robotics (Autonomous Systems)

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: 13 hits
ReferencesLink to record
Permanent link

Direct link