Connectionist network for dynamic programming problems

摘要

Dynamic programming is well known as a powerful modelling technique for dealing with the issue of making optimal decisions sequentially. Many practical problems, such as finding shortest paths in route planning, and multi-stage optimal control, can be formulated as cases of the general sequential decision process. The paper proposes a connectionist network architecture, called the binary-relation inference network, which solves a special class of dynamic programming problems in the continuous time. They include the all-pair solutions for a family of closed semi-ring path problems, such as shortest paths, transitive closure, minimum spanning tree, and minimax path problems. The all-pair inference network specifies a basic and uniform computation of its individual units, which then collectively emerge towards a global optimal solution. The computational order in its discrete-time variants, either as synchronous or asynchronous networks, bears a close resemblance to the Floyd-Warshall algorithm and doubling algorithm. However, the continuous-time inference network offers a significant speed advantage if its non-sequential computation nature can be exploited. Simulation results of using analogue VLSI implementation of the inference network for solving shortest-path problems are promising.