Reference : A comparative study of task assignment and path planning methods for multi-UGV missions
Parts of books : Contribution to collective works
Engineering, computing & technology : Multidisciplinary, general & others
http://hdl.handle.net/10993/20601
A comparative study of task assignment and path planning methods for multi-UGV missions
English
Thunberg, Johan mailto [University of Luxembourg > Luxembourg Centre for Systems Biomedicine (LCSB) > >]
Anisi, D. []
Ögren, P. mailto []
2009
Optimization and Cooperative Control Strategies
Springer
167-180
Yes
[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.
http://hdl.handle.net/10993/20601

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Limited access
A comparative study of task assignment and path planning methods for multi-UGV missions.pdfPublisher postprint349.43 kBRequest a copy

Bookmark and Share SFX Query

All documents in ORBilu are protected by a user license.