In this paper, Self-Organizing Map (SOM) for the Multiple Traveling Salesman Problem (MTSP) with minmax objective is applied to the robotic problem of multigoal path planning in the polygonal domain. The main difficulty of such SOM deployment is determination of collision-free paths among obstacles that is required to evaluate the neuron-city distances in the winner selection phase of unsupervised learning. Moreover, a collision-free path is also needed in the adaptation phase, where neurons are adapted towards the presented input signal (city) to the network. Simple approximations of the shortest path are utilized to address this issue and solve the robotic MTSP by SOM. Suitability of the proposed approximations is verified in the context of cooperative inspection, where cities represent sensing locations that guarantee to "see" the whole robots' workspace. The inspection task formulated as the MTSP-Minmax is solved by the proposed SOM approach and compared with the combinatorial heuristic GENIUS. The results indicate that the proposed approach provides competitive results to GENIUS and support applicability of SOM for robotic multigoal path planning with a group of cooperating mobile robots. The proposed combination of approximate shortest paths with unsupervised learning opens further applications of SOM in the field of robotic planning.

Department of Computer Science Faculty of Electrical Engineering Czech Technical University Prague Technická 2 166 27 Prague 6 Czech Republic

See more in PubMed

Kohonen T., Schroeder M. R., Huang T. S., editors. Self-Organizing Maps. 3rd. Berlin, Germany: Springer; 2001. DOI

Applegate D. L., Bixby R. E., Chvátal V., Cook W. J. The Traveling Salesman Problem: A Computational Study. Princeton, NJ, USA: Princeton University Press; 2006.

Lin S., Kernighan B. W. An effective heuristic algorithm for the traveling-salesman problem. Operations Research. 1973;21(2):498–516. doi: 10.1287/opre.21.2.498. DOI

Helsgaun K. An effective implementation of the Lin-Kernighan traveling salesman heuristic. European Journal of Operational Research. 2000;126(1):106–130. doi: 10.1016/S0377-2217(99)00284-2. DOI

Angéniol B., de La Croix Vaubois G., Le Texier J.-Y. Self-organizing feature maps and the travelling salesman problem. Neural Networks. 1988;1(4):289–293. doi: 10.1016/0893-6080(88)90002-0. DOI

Fort J.-C. Solving a combinatorial problem via self-organizing process: an application of the Kohonen algorithm to the traveling salesman problem. Biological Cybernetics. 1988;59(1):33–40. doi: 10.1007/BF00336888. PubMed DOI

Burke L. I. Neural methods for the traveling salesman problem: insights from operations research. Neural Networks. 1994;7(4):681–690. doi: 10.1016/0893-6080(94)90045-0. DOI

Somhom S., Modares A., Enkawa T. A self-organising model for the travelling salesman problem. Journal of the Operational Research Society. 1997;48(9):919–928. doi: 10.1057/palgrave.jors.2600439. DOI

Aras N., Oommen B. J., Altinel I. K. The Kohonen network incorporating explicit statistics and its application to the travelling salesman problem. Neural Networks. 1999;12(9):1273–1284. doi: 10.1016/S0893-6080(99)00063-5. PubMed DOI

Cochrane E. M., Beasley J. E. The co-adaptive neural network approach to the Euclidean travelling salesman problem. Neural Networks. 2003;16(10):1499–1525. doi: 10.1016/s0893-6080(03)00056-x. PubMed DOI

Créput J.-C., Koukam A. A memetic neural network for the Euclidean traveling salesman problem. Neurocomputing. 2009;72(4–6):1250–1264. doi: 10.1016/j.neucom.2008.01.023. DOI

Faigl J. On the performance of self-organizing maps for the non-Euclidean traveling salesman problem in the polygonal domain. Information Sciences. 2011;181(19):4214–4229. doi: 10.1016/j.ins.2011.05.019. DOI

Smith K., Palaniswami M., Krishnamoorthy M. Neural techniques for combinatorial optimization with applications. IEEE Transactions on Neural Networks. 1998;9(6):1301–1318. doi: 10.1109/72.728380. PubMed DOI

Ghaziri H., Osman I. H. A neural network algorithm for the traveling salesman problem with backhauls. Computers and Industrial Engineering. 2003;44(2):267–281. doi: 10.1016/S0360-8352(02)00179-1. DOI

Modares A., Somhom S., Enkawa T. A self-organizing neural network approach for multiple traveling salesman and vehicle routing problems. International Transactions in Operational Research. 1999;6(6):591–606. doi: 10.1016/S0969-6016(99)00015-5. DOI

Somhom S., Modares A., Enkawa T. Competition-based neural network for the multiple travelling salesmen problem with minmax objective. Computers & Operations Research. 1999;26(4):395–407. doi: 10.1016/s0305-0548(98)00069-0. DOI

Alatartsev S., Stellmacher S., Ortmeier F. Robotic task sequencing problem: a survey. Journal of Intelligent and Robotic Systems: Theory and Applications. 2015;80(2):279–298. doi: 10.1007/s10846-015-0190-6. DOI

Faigl J., Kulich M., Vonásek V., Přeučil L. An application of the self-organizing map in the non-Euclidean Traveling Salesman Problem. Neurocomputing. 2011;74(5):671–679. doi: 10.1016/j.neucom.2010.08.026. DOI

Bektas T. The multiple traveling salesman problem: an overview of formulations and solution procedures. Omega. 2006;34(3):209–219. doi: 10.1016/j.omega.2004.10.004. DOI

Faigl J. Multi-goal path planning for cooperative sensing [Ph.D. thesis] Czech Technical University in Prague; 2010.

Faigl J. Approximate solution of the multiple watchman routes problem with restricted visibility range. IEEE Transactions on Neural Networks. 2010;21(10):1668–1679. doi: 10.1109/TNN.2010.2070518. PubMed DOI

França P. M., Gendreau M., Laporte G., Müller F. M. The m-traveling salesman problem with minmax objective. Transportation Science. 1995;29(3):267–275. doi: 10.1287/trsc.29.3.267. DOI

Saha M., Roughgarden T., Latombe J.-C., Sánchez-Ante G. Planning tours of robotic arms among partitioned goals. The International Journal of Robotics Research. 2006;25(3):207–223. doi: 10.1177/0278364906061705. DOI

Gueta L. B., Chiba R., Ota J., Ueyama T., Arai T. Coordinated motion control of a robot arm and a positioning table with arrangement of multiple goals. Proceedings of the IEEE International Conference on Robotics and Automation (ICRA '08); May 2008; Pasadena, Calif, USA. pp. 2252–2258. DOI

Reif J. H. Complexity of the mover's problem and generalizations. Proceedings of the 20th Annual Symposium on Foundations of ComputerScience (SFCS '79); October 1979; IEEE Computer Society; pp. 421–427.

Spitz S. N., Requicha A. A. G. Multiple-goals path planning for coordinate measuring machines. Proceedings of the IEEE International Conference on Robotics and Automation (ICRA '00); April 2000; San Francisco, Calif, USA. pp. 2322–2327. DOI

Danner T., Kavraki L. E. Randomized planning for short inspection paths. Proceedings of the IEEE International Conference on Robotics and Automation (ICRA '00); April 2000; San Francisco, Calif, USA. pp. 971–976. DOI

González-Baños H., Hsu D., Latombe J.-C. Motion planning: recent developments. In: Ge S., Lewis F., editors. Autonomous Mobile Robots: Sensing, Control, Decision-Making and Applications. chapter 10. New York, NY, USA: CRC Press; 2006.

González-Baños H. A randomized art-gallery algorithm for sensor placement. Proceedings of the 17th Annual Symposium on Computational Geometry (SCG '01); June 2001; New York, NY, USA. pp. 232–240. DOI

Kazazakis G. D., Argyros A. A. Fast positioning of limited-visibility guards for the inspection of 2D workspaces. Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS '02); September 2002; Lausanne, Switzerland. pp. 2843–2848. DOI

Faigl J., Kulich M. Sensing locations positioning for multi-robot inspection planning. IEEE Workshop on Distributed Intelligent Systems—Collective Intelligence and Its Applications (DIS '06); June 2006; Prague, Czech Republic. pp. 79–84. DOI

Faigl J., Kulich M., Přeučil L. A sensor placement algorithm for a mobile robot inspection planning. Journal of Intelligent & Robotic Systems. 2011;62(3):329–353. doi: 10.1007/s10846-010-9449-0. DOI

Lagoudakis M. G., Markakis E., Kempe D., et al. Auction-based multi-robot routing. In: Thrun S., Sukhatme G. S., Schaal S., editors. Robotics: Science and Systems. The MIT Press; 2005. pp. 343–350.

Kalina P., Vokřínek J., Mařík V. Agents toward vehicle routing problem with time windows. Journal of Intelligent Transportation Systems: Technology, Planning, and Operations. 2015;19(1):3–17. doi: 10.1080/15472450.2014.889953. DOI

Yuan S., Skinner B., Huang S., Liu D. A new crossover approach for solving the multiple travelling salesmen problem using genetic algorithms. European Journal of Operational Research. 2013;228(1):72–82. doi: 10.1016/j.ejor.2013.01.043. DOI

Bellmore M., Hong S. Transformation of multisalesmen problem to the standard traveling salesman problem. Journal of the Association for Computing Machinery. 1974;21(3):500–504. doi: 10.1145/321832.321847. DOI

Bertazzi L., Golden B., Wang X. Min-max vs. min-sum vehicle routing: a worst-case analysis. European Journal of Operational Research. 2015;240(2):372–381. doi: 10.1016/j.ejor.2014.07.025. DOI

Vallivaara I. A Team ant colony optimization algorithm for the multiple travelling salesmen problem with MinMax objective. Proceedings of the 27th IASTED International Conference on Modelling, Identification, and Control; February 2008; ACTA Press; pp. 387–392.

Kubalík J., Faigl J. Iterative prototype optimization with evolved improvement steps. Proceedings of the 9th European Conference on Genetic Programming (EuroGP '06); April 2006; Budapest, Hungary. pp. 154–165.

Kubalík J., Kléma J., Kulich M. Application of soft computing techniques to rescue operation planning. Proceedings of the 7th International Conference on Artificial Intelligence and Soft Computing (ICAISC '04); June 2004; pp. 897–902.

Kulich M., Faigl J., Kléma J., Kubalík J. Rescue operation planning by soft computing techniques. Proceedings of the IEEE 4th International Conference on Intelligent Systems Design and Application; August 2004; Budapest, Hungary. IEEE; pp. 103–108.

Gendreau M., Hertz A., Laporte G. New insertion and postoptimization procedures for the traveling salesman problem. Operations Research. 1992;40(6):1086–1094. doi: 10.1287/opre.40.6.1086. DOI

Overmars M. H., Welzl E. New methods for computing visibility graphs (SCG '88). Proceedings of the 4th Annual Symposium On Computational Geometry; June 1988; Urbana-Champaign, Ill, USA. pp. 164–171. DOI

Edahiro M., Kokubo I., Asano T. A new pointlocation algorithm and its practical efficiency: comparison with existing algorithms. ACM Transactions on Graphics. 1984;3(2):86–109.

Kallmann M. Path planning in triangulations. Proceedings of the IJCAI Workshop on Reasoning, Representation, and Learning in Computer Games; 2005; Edinburgh, Scotland. pp. 49–54.

Devillers O., Pion S., Teillaud M. Walking in a triangulation. International Journal of Foundations of Computer Science. 2002;13(2):181–199. doi: 10.1142/S0129054102001047. DOI

Plebe A., Anile A. M. A neural-network-based approach to the double traveling salesman problem. Neural Computation. 2002;14(2):437–471. doi: 10.1162/08997660252741194. PubMed DOI