A comparative study of task assignment and path planning methods for multi-UGV missions
(2009) 8th International Conference on Cooperative Control and Optimization In Lecture Notes in Control and Information Sciences 381. p.167-180- Abstract
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... (More)
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.
(Less)
- author
- Thunberg, Johan LU ; Anisi, David A. and Ögren, Petter
- publishing date
- 2009
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- host publication
- Optimization and Cooperative Control Strategies : Proceedings of the 8th International Conference on Cooperative Control and Optimization - Proceedings of the 8th International Conference on Cooperative Control and Optimization
- series title
- Lecture Notes in Control and Information Sciences
- editor
- Hirsch, Michael ; Commander, Clayton ; Pardalos, Panos and Murphey, Robert
- volume
- 381
- pages
- 14 pages
- publisher
- Springer
- conference name
- 8th International Conference on Cooperative Control and Optimization
- conference location
- Gainsville, United States
- conference dates
- 2008-01-30 - 2008-02-01
- external identifiers
-
- scopus:54349103991
- ISSN
- 0170-8643
- ISBN
- 9783540880639
- 9783540880622
- DOI
- 10.1007/978-3-540-88063-9_10
- language
- English
- LU publication?
- no
- id
- 3ff2388d-d7aa-41a7-947f-e805cf8dabd3
- date added to LUP
- 2024-09-05 12:50:15
- date last changed
- 2024-10-03 16:35:40
@inproceedings{3ff2388d-d7aa-41a7-947f-e805cf8dabd3,
abstract = {{<p>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.</p>}},
author = {{Thunberg, Johan and Anisi, David A. and Ögren, Petter}},
booktitle = {{Optimization and Cooperative Control Strategies : Proceedings of the 8th International Conference on Cooperative Control and Optimization}},
editor = {{Hirsch, Michael and Commander, Clayton and Pardalos, Panos and Murphey, Robert}},
isbn = {{9783540880639}},
issn = {{0170-8643}},
language = {{eng}},
pages = {{167--180}},
publisher = {{Springer}},
series = {{Lecture Notes in Control and Information Sciences}},
title = {{A comparative study of task assignment and path planning methods for multi-UGV missions}},
url = {{http://dx.doi.org/10.1007/978-3-540-88063-9_10}},
doi = {{10.1007/978-3-540-88063-9_10}},
volume = {{381}},
year = {{2009}},
}