David A. Anisi |
Optimization and Systems Theory, Royal Institute of
Technology (KTH), Stockholm, Sweden
|
Johan Thunberg, Petter Ögren |
Dept. of Autonomous Systems, Swedish Defence Research Agency (FOI), Stockholm, Sweden |
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.