Skip to main page content
U.S. flag

An official website of the United States government

Dot gov

The .gov means it’s official.
Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

Https

The site is secure.
The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

Access keys NCBI Homepage MyNCBI Homepage Main Content Main Navigation
. 2016:2016:2720630.
doi: 10.1155/2016/2720630. Epub 2016 Jun 2.

An Application of Self-Organizing Map for Multirobot Multigoal Path Planning with Minmax Objective

Jan Faigl  1
Affiliations

An Application of Self-Organizing Map for Multirobot Multigoal Path Planning with Minmax Objective

Jan Faigl. Comput Intell Neurosci. 2016.

Abstract

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.

PubMed Disclaimer

Figures

Figure 1
Figure 1
Schema of the SOM two-layered neural network for the TSP and associated geometric representation.
Figure 2
Figure 2
An example of SOM [16] evolution at the particular learning epochs in an instance of the MTSP-Minmax without obstacles.
Figure 3
Figure 3
An example of approximate shortest path and passed diagonals.
Figure 4
Figure 4
An example of the path approximation and its improvement during the adaptation: (a) node and city are not directly visible; (b) after the node movement towards the city, (c) the city becomes directly visible and the path refinement decreased the length about ten percent.
Figure 5
Figure 5
An example of SOM evolution in 𝒲; small standalone disks represent cities and connected disks represent nodes that form rings and finally the tours.
Figure 6
Figure 6
Examples of tour represented by the ring; the final solution is found in 72 learning epochs.
Figure 7
Figure 7
Examples of found solutions by the GENIUS-quality and SOM-based algorithm. L: length of the longest tour, CR: Cooperative Ratio, CE: Collaborative Effort. (a, d) potholes, four salesmen; (b, e) m3, four salesmen; (c, f) jh, three salesmen; (g, h) h2, five salesmen.
Figure 8
Figure 8
Required computation time.
Algorithm 1
Algorithm 1
SOM for the MTSP-Minmax.
See this image and copyright information in PMC

References

    1. Kohonen T., Schroeder M. R., Huang T. S., editors. Self-Organizing Maps. 3rd. Berlin, Germany: Springer; 2001. - DOI
    1. 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.
    1. 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
    1. 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
    1. 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

LinkOut - more resources