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.
Original language | English |
---|---|
Pages (from-to) | 1803-1815 |
Number of pages | 13 |
Journal | Nonlinear Dynamics |
Volume | 89 |
Issue number | 3 |
DOIs | |
Publication status | Published - 1 Aug 2017 |
Keywords
- Biased consensus neural network
- Linear program
- Nonlinear equation
- Path planning
- Shortest path
ASJC Scopus subject areas
- Control and Systems Engineering
- Aerospace Engineering
- Ocean Engineering
- Mechanical Engineering
- Applied Mathematics
- Electrical and Electronic Engineering