Abstract
In this paper, a unified scheme is proposed for solving the classical shortest path problem and the generalized shortest path problem, which are highly nonlinear. Particularly, the generalized shortest path problem is more complex than the classical shortest path problem since it requires finding a shortest path among the paths from a vertex to all the feasible destination vertices. Different from existing results, inspired by the optimality principle of Bellman’s dynamic programming, we formulate the two types of shortest path problems as linear programs with the decision variables denoting the lengths of possible paths. Then, biased consensus neural networks are adopted to solve the corresponding linear programs in an efficient and distributed manner. Theoretical analysis guarantees the performance of the proposed scheme. In addition, two illustrative examples are presented to validate the efficacy of the proposed scheme and the theoretical results. Moreover, an application to mobile robot navigation in a maze further substantiates the efficacy of the proposed scheme.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Kim, S., Lewis, M.E., White, C.C.: State space reduction for nonstationary stochastic shortest path problems with real-time traffic information. IEEE Trans. Intell. Transp. Syst. 6, 273–284 (2005)
Cota-Ruiz, J., Rivas-Perea, P., Sifuentes, E., Gonzalez-Landaeta, R.: A recursive shortest path routing algorithm with application for wireless sensor network localization. IEEE Sens. J. 16, 4631–4637 (2016)
Junior, J.J., Cortex, P.C., Backes, A.R.: Color texture classification using shortest paths in graphs. IEEE Trans. Image Process. 23, 3751–3761 (2014)
Zhang, Y., Yan, X., Chen, D., Guo, D., Li, W.: QP-based refined manipulability-maximizing scheme for coordinated motion planning and control of physically constrained wheeled mobile redundant manipulators. Nonlinear Dyn. 85, 245–261 (2016)
Lawler, E.L.: Combinatorial Optimization: Networks and Matroids. Holt, Rinehart, and Winston, New York (1976)
Wang, J.: A recurrent neural network for solving the shortest path problem. IEEE Trans. Circuits Syst. I(43), 482–486 (1996)
Xia, Y., Wang, J.: A discrete-time recurrent neural network for shortest-path routing. IEEE Trans. Autom. Control 45(11), 2129–2134 (2000)
Sun, C.-C., Jan, G.E., Leu, S.-W., Yang, K.-C., Chen, Y.-C.: Near-shortest path planning on a quadratic surface with \(O(n \text{ log } n)\) time. IEEE Sens. J. 15, 6079–6080 (2015)
Jan, G.E., Sun, C.-C., Tsai, W.C., Lin, T.-H.: An \(O(n \text{ log }n)\) shortest path algorithm based on Delaunay triangulation. IEEE/ASME Trans. Mechatron. 19, 660–666 (2014)
Ma, S., Feng, K., Li, J., Wang, H., Cong, G., Huai, J.: Proxies for shortest path and distance queries. IEEE Trans. Knowl. Data Eng. 28(7), 1835–1849 (2016)
Lei, G., Dou, Y., Li, R., Xia, F.: An FPGA implementation for solving the large single-source-shortest-path problem. IEEE Trans. Circuits Syst. II(63), 473–477 (2016)
Li, X., Rakkiyappan, R., Velmurugan, G.: Dissipativity analysis of memristor-based complex-valued neural networks with time-varying delays. Inf. Sci. 294, 645–665 (2015)
Xiao, L., Lu, R.: Finite-time solution to nonlinear equation using recurrent neural dynamics with a specially-constructed activation function. Neurocomputing 151, 246–251 (2016)
Xiao, L., Zhang, Y.: A new performance index for the repetitive motion of mobile manipulators. IEEE Trans. Cybern. 44, 280–292 (2014)
Wang, Y., Cheng, L., Hou, Z.-G., Yu, J., Tan, M.: Optimal formation of multirobot systems based on a recurrent neural network. IEEE Trans. Neural Netw. Learn. Syst. 27, 322–333 (2016)
Liu, Q., Wang, J.: Finite-time convergent recurrent neural network with a hard-limiting activation function for constrained optimization with piecewise-linear objective functions. IEEE Trans. Neural Netw. 22, 601–613 (2011)
Xia, Y., Wang, J.: A bi-projection neural network for solving constrained quadratic optimization problems. IEEE Trans. Neural Netw. Learn. Syst. 27, 214–224 (2016)
Zhang, S., Xia, Y., Wang, J.: A complex-valued projection neural network for constrained optimization of real functions in complex variables. IEEE Trans. Neural Netw. Learn. Syst. 26, 3227–3238 (2015)
Li, X., Song, S.: Impulsive control for existence, uniqueness, and global stability of periodic solutions of recurrent neural networks with discrete and continuously distributed delays. IEEE Trans. Neural. Netw. Learn. Syst. 24, 868–877 (2013)
Hopfield, J.J., Tank, D.W.: “Neural” computation of decisions in optimization problems. Biol. Cybern. 52, 141–152 (1985)
Tank, D.W., Hopfield, J.J.: Simple “neural” optimization networks: an A/D converter, signal decision circuit, and a linear programming circuit. IEEE Trans. Circuits Syst. 33, 533–541 (1986)
Araújo, F., Ribeiro, B., Rodrigues, L.: A neural network for shortest path computation. IEEE Trans. Neural Netw. 12(5), 1067–1073 (2001)
Taccari, L.: Integer programming formulations for the elementary shortest path problem. Eur. J. Oper. Res. 252, 122–130 (2016)
Nazemi, A., Omidi, F.: An efficient dynamic model for solving the shortest path problem. Transport. Res. C Emerg. 26, 1–19 (2013)
Zhang, Y., Wu, L., Wei, G., Wang, S.: A novel algorithm for all pairs shortest path problem based on matrix multiplication and pulse coupled neural network. Digit. Signal Process. 21, 517–521 (2011)
Sang, Y., Lv, J., Qu, H., Yi, Z.: Shortest path computation using pulse-coupled neural networks with restricted autowave. Knowl. Based Syst. 114, 1–11 (2016)
Li, X., Ma, Y., Feng, X.: Self-adaptive autowave pulse-coupled neural network for shortest-path problem. Neurocomputing 115, 63–71 (2013)
Qu, H., Yi, Z., Yang, S.X.: Efficient shortest-path-tree computation in network routing based on pulse-coupled neural networks. IEEE Trans. Cybern. 43, 995–1010 (2013)
Bellman, R.: On a routing problem. Q. Appl. Math. 16(1), 87–90 (1958)
Li, H., Chen, G., Liao, X., Huang, T.: Leader-following consensus of discrete-time multiagent systems with encoding-decoding. IEEE Trans. Circuits Syst. II Express Briefs 63, 401–405 (2016)
Cheng, S., Yu, L., Zhang, D., Huo, L., Ji, J.: Consensus of second-order multi-agent systems using partial agents’ velocity measurements. Nonlinear Dyn. 86, 1927–1935 (2016)
Li, H., Chen, G., Huang, T., Dong, Z., Zhu, W., Gao, L.: Event-triggered distributed average consensus over directed digital networks with limited communication bandwidth. IEEE Trans. Cybern. 46, 3098–3110 (2016)
Wen, G.-X., Chen, C.L.P., Liu, Y.-J., Liu, Z.: Neural network-based adaptive leader-following consensus control for a class of nonlinear multiagent state-delay systems. IEEE Trans. Cybern. (2016). doi:10.1109/TCYB.2016.2608499
Li, H., Chen, G., Huang, T., Dong, Z.: High-performance consensus control in networked systems with limited bandwidth communication and time-varying directed topologies. IEEE Trans. Neural Netw. Learn. Syst. (2016). doi:10.1109/TNNLS.2016.2519894
Zhang, Y., Chen, D., Guo, D., Liao, B., Wang, Y.: On exponential convergence of nonlinear gradient dynamics system with application to square root finding. Nonlinear Dyn. 79, 983–1003 (2015)
Xiao, Y.: A nonlinearly activated neural dynamics and its finite-time solution to time-varying nonlinear equation. Neurocomputing 173, 1983–1988 (2016)
Ma, Z., Wang, Y., Li, X.: Cluster-delay consensus in first-order multi-agent systems with nonlinear dynamics. Nonlinear Dyn. 83(3), 1303–1310 (2016)
Chen, C.L.P., Wen, G.-X., Liu, Y.-J., Liu, Z.: Observer-based adaptive backstepping consensus tracking control for high-order nonlinear semi-strict-feedback multiagent systems. IEEE Trans. Cybern. 46, 1591–1601 (2016)
Zhou, B., Liao, X.: Leader-following second-order consensus in multi-agent systems with sampled data via pinning control. Nonlinear Dyn. 78, 555–569 (2014)
Khalil, H.K.: Nonlinear Systems. Prentice-Hall, Englewood Cliffs (2002)
Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge Univ. Press, Cambridge (2004)
Acknowledgements
This work is supported by the National Natural Science Foundation of China (with number 61401385), by Hong Kong Research Grants Council Early Career Scheme (with number 25214015) and also by Departmental General Research Fund of Hong Kong Polytechnic University (with number G.61.37.UA7L). Besides, the authors would like to thank the editors and anonymous reviewers for valuable comments and constructive suggestions.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Zhang, Y., Li, S. & Guo, H. A type of biased consensus-based distributed neural network for path planning. Nonlinear Dyn 89, 1803–1815 (2017). https://doi.org/10.1007/s11071-017-3553-7
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11071-017-3553-7