A comparative study of task assignment and path planning methods for multi-UGV missions. (English) Zbl 1195.93092
Hirsch, Michael J. (ed.) et al., Optimization and cooperative control strategies. Proceedings of the 8th international conference on cooperative control and optimization, Gainesville, FL, USA, January 30–February 1, 2008. Berlin: Springer (ISBN 978-3-540-88062-2/pbk; 978-3-540-88063-9/ebook). Lecture Notes in Control and Information Sciences 381, 167-180 (2009).
Summary: Many important problems involving a group of Unmanned Ground Vehicles (UGVs) are closely related to the Multi Traveling Salesman Problem (MTSP). This paper comprises a comparative study of a number of algorithms proposed in the literature to solve MTSPs occurring in robotics. The investigated algorithms 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 stochastic version of the Granular Tabu Search (GTS).
For the entire collection see [Zbl 1157.49002].
For the entire collection see [Zbl 1157.49002].
MSC:
| 93C85 | Automated systems (robots, etc.) in control theory |
| 90C27 | Combinatorial optimization |
| 90C11 | Mixed integer programming |
| 93A14 | Decentralized systems |
Keywords:
unmanned ground vehicles (UGVs); multi traveling salesman problem (M-TSP); mixed integer linear programming (MILP); Voronoi partition step (VP); granular tabu search (GTS)References:
| [1] | Alighanbari, M., Bertuccelli, L.F., How, J.P.: Filter-Embedded UAV Task Assignment Algorithms for Dyanamic Environments. In: AIAA Guidance, Navigation, and Control Conference and Exhibit, pp. 1-15 (2004) |
| [2] | Beard, R. W.; McLain, T. W.; Goodrich, M. A.; Anderson, E. P., Coordinated target assignment and intercept for unmanned air vehicles, IEEE Transactions on Robotics and Automation, 18, 6, 911-922 (2002) · doi:10.1109/TRA.2002.805653 |
| [3] | Bellmore, M.; Nemhauser, G. L., The traveling salesman problem: a survey, Operations Research, 16, 3, 538-558 (1968) · Zbl 0213.44604 · doi:10.1287/opre.16.3.538 |
| [4] | Bent, R.; van Hentenryck, P., A Two-Stage Hybrid Local Search for the Vehicle Routing Problem with Time Windows, Transportation Science, 38, 4, 515-530 (2004) · doi:10.1287/trsc.1030.0049 |
| [5] | Berhault, M., Huang, H., Keskinocak, P., Koenig, S., Elmaghraby, W., Griffin, P., Kleywegt, A.: Robot exploration with combinatorial auctions. In: Proceedings of 2003 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2003), vol. 2 (2003) |
| [6] | Bertuccelli, L.F., Alighanbari, M., How, J.P.: Robust planning for coupled cooperative UAV missions. In: Proc. of the 43rd IEEE Conference on Decision and Control, 2004, CDC, vol. 3 (2004) |
| [7] | Dechter, R.; Pearl, J., Generalized best-first search strategies and the optimality of A*, Journal of the ACM (JACM), 32, 3, 505-536 (1985) · Zbl 0631.68075 · doi:10.1145/3828.3830 |
| [8] | Frazzoli, E., Bullo, F.: Decentralized algorithms for vehicle routing in a stochastic time-varying environment. In: Proc. of the 43rd IEEE Conference on Decision and Control, CDC (2004) |
| [9] | Gambardella, L. M.; Taillard, É.; Agazzi, G., MACS-VRPTW: a multiple ant colony system for vehicle routing problems with time windows, 63-76 (1999), New York: McGraw-Hill, New York |
| [10] | Gendreau, M., Laporte, G., Potvin, J.Y.: Metaheuristics for the Capacitated VRP. In: The Vehicle Routing Problem, pp. 129-154 (2002) · Zbl 1076.90545 |
| [11] | Gerkey, B. P.; Mataric, M. J., A Formal Analysis and Taxonomy of Task Allocation in Multi-Robot Systems, The International Journal of Robotics Research, 23, 9, 939 (2004) · doi:10.1177/0278364904045564 |
| [12] | Guo, Y., Parker, L.E., Madhavan, R.: Towards collaborative robots for infrastructure security applications. In: Proceedings of International Symposium on Collaborative Technologies and Systems, pp. 235-240 (2004) |
| [13] | Jones, C., Shell, D., Mataric, M.J., Gerkey, B.: Principled Approaches to the Design of Multi-Robot Systems. In: Proc. of the Workshop on Networked Robotics, IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2004) (2004) |
| [14] | Kim, Y., Gu, D.W., Postlethwaite, I.: Real-time optimal mission scheduling and flight path selection. IEEE Transactions on Automatic Control (submitted) (accepted January 12, 2007) · Zbl 1366.90098 |
| [15] | Kim, Y., Gu, D.W., Postlethwaite, I.: A comprehensive study on flight path selection algorithms. In: The IEE Seminar on Target Tracking: Algorithms and Applications, pp. 77-90 (2006) |
| [16] | Lagoudakis, M.G., Markakis, E., Kempe, D., Keskinocak, P., Kleywegt, A., Koenig, S., Tovey, C., Meyerson, A., Jain, S.: Auction-based multi-robot routing. Robotics: Science and Systems (2005) |
| [17] | Laporte, G., Classical and Modern Heuristics for the Vehicle Routing Problem (1999), Malden: Blackwell Synergy, Malden |
| [18] | Le Bouthillier, A.; Crainic, T. G., A Cooperative Parllel Meta-Heuristic for the Vehicle Routing Problem with Time Windows, Computers & Operations Research, 32, 7, 1685-1708 (2005) · Zbl 1074.90006 · doi:10.1016/j.cor.2003.11.023 |
| [19] | Lindhe, M., Ögren, P., Johansson, K.H.: Flocking with Obstacle Avoidance: A New Distributed Coordination Algorithm Based on Voronoi Partitions. In: Proceedings of the 2005 IEEE International Conference on Robotics and Automation, 2005, pp. 1785-1790 (2005) |
| [20] | Overmars, M.H., Welzl, E.: New methods for computing visibility graphs. In: Proceedings of the fourth annual symposium on Computational geometry, pp. 164-171 (1988) |
| [21] | Panton, D. M.; Elbers, A. W., Mission planning for synthetic aperture radar surveillance, Interfaces, 29, 2, 73-88 (1999) · doi:10.1287/inte.29.2.73 |
| [22] | Pikovsky, A., Shabalin, P., Bichler, M.: Iterative Combinatorial Auctions with Linear Prices: Results of Numerical Experiments. In: E-Commerce Technology, 2006. The 8th IEEE International Conference on and Enterprise Computing, The 3rd IEEE International Conference on E-Commerce, and E-Services, p. 39 (2006) |
| [23] | Renaud, J.; Boctor, F. F., A sweep-based algorithm for the fleet size and mix vehicle routing problem, European Journal of Operational Research, 140, 3, 618-628 (2002) · Zbl 0998.90016 · doi:10.1016/S0377-2217(01)00237-5 |
| [24] | Thunberg, J.: Task assignment and path planning for systems of surveillance unmanned ground vehicles. Master’s thesis, The Royal Institute of Technology, KTH (2007) |
| [25] | Toth, P.; Vigo, D., The Granular Tabu Search and Its Application to the Vehicle-Routing Problem, INFORMS Journal on Computing, 15, 4, 333-346 (2003) · Zbl 1238.90141 · doi:10.1287/ijoc.15.4.333.24890 |
| [26] | Tovey, C., Lagoudakis, M.G., Jain, S., Koenig, S.: The generation of bidding rules for auction-based robot coordination. In: Proceedings of the 3rd International Multi-Robot Systems Workshop, pp. 14-16 (2005) |
| [27] | Zlot, R.; Stentz, A., Market-based Multirobot Coordination for Complex Tasks, The International Journal of Robotics Research, 25, 1, 73 (2006) · doi:10.1177/0278364906061160 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
