×

Optimal path finding with space- and time-variant metric weights via multi-layer CNN. (English) Zbl 1003.68137

Summary: Analogic CNN-based optimal path-finding algorithm is proposed to solve the problem with space and time-variant metric weights. The algorithm is based on the analog version of modified dynamic programming which is associated with nonlinear templates and multi-layer CNN employing the Distance Computing (DC), the Intermediate (I), and the Path-Finding (PF) layers. The cell outputs of I layer are jointly utilized among the cells on the DC layer and the PF layers, which allows the network structure to be compact. The arbitrary levels of metric weights can be provided externally and the real-time processing of the optimal path finding is achieved on the space with the time-variant metric weight. Parallel-processing capability for the multiple optimal path finding is the additional property of the proposed algorithm. The proposed multi-layer CNN structure and its nonlinear templates are introduced. The proper operation of the proposed structure is verified through theoretical analysis and simulations.

MSC:

68T05 Learning and adaptive systems in artificial intelligence
90C39 Dynamic programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Dynamic Programming. Princeton, NJ, Princeton University Press: 1957. · Zbl 0077.13605
[2] Singh, ASME Journal of Dynamic Systems, Measurement, and Control 109 pp 88– (1987) · Zbl 0621.93047 · doi:10.1115/1.3143842
[3] Nishimura, Proceedings of IEEE/RSJ International Conference on Intelligence Robots and Systems 1 pp 329– (1999)
[4] Hou, Proceedings of IEEE INFOCOM 1 pp 320– (1996) · doi:10.1109/INFCOM.1996.497909
[5] On the extended Bellman–Ford algorithm to solve two-constrained quality of service routing problems. Proceedings of IC3N 1999; 304–310.
[6] . Dynamic programming search for continuous speech recognition. IEEE Signal Processing Magazine 1999; 64–83.
[7] Itakura, IEEE Trans. on Acoustic, Speech and Signal Processing ASSP-23 pp 67– (1975) · doi:10.1109/TASSP.1975.1162641
[8] Ali, IEEE Transactions on Neural Networks 4 pp 931– (1993) · doi:10.1109/72.286889
[9] Chiu, IEEE Transactions on Neural Networks 2 pp 418– (1991) · doi:10.1109/72.88161
[10] Chua, IEEE Transactions on Circuits and Systems 35 pp 1257– (1988) · Zbl 0663.94022 · doi:10.1109/31.7600
[11] Roska, IEEE Transactions on Circuits Systems II: Analog Digital Signal Processing 40 pp 163– (1993) · Zbl 0800.68251 · doi:10.1109/82.222815
[12] Perez-Munuzur, IEEE Transactions on Circuits and Systems–I: Fundamental Theory and Applications 40 pp 174– (1993) · Zbl 0800.92038 · doi:10.1109/81.222798
[13] Rekeczky, Proceedings of International Symposium on Non-linear Theory and its Applications (NOLTA’99) 1 pp 423– (1999)
[14] , , , , Analog combinatorics and cellular automata-key algorithms and layout design. IEEE International Workshop on Cellular Neural Networks and their Applications (CNNA 1994); 249–254.
[15] Soumyanath, IEEE Transactions on Circuits and Systems–I: Fundamental Theory and Applications 46 pp 442– (1999) · Zbl 0953.65038 · doi:10.1109/81.754845
[16] Analogical and Neural Computing Lab. SimCNN-Multi-layer CNN Simulator for Visual Mouse Platform: Reference Manual Version 2.2, Computer and Automation Institute (MTA SzTAKI) of the Hungarian Academy of Sciences, 1998.
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.