Finding optimal paths in connected graphs requires determining the smallest total cost for traveling along the graph's edges. This problem can be solved by several classical algorithms where, usually, costs are predefined for all edges. Conventional planning methods can, thus, normally not be used when wanting to change costs in an adaptive way following the requirements of some task. Here we show that one can define a neural network representation of path finding problems by transforming cost values into synaptic weights, which allows for online weight adaptation using network learning mechanisms. When starting with an initial activity value of one, activity propagation in this network will lead to solutions, which are identical to those found by the Bellman Ford algorithm. The neural network has the same algorithmic complexity as Bellman Ford and, in addition, we can show that network learning mechanisms (such as Hebbian learning) can adapt the weights in the network augmenting the resulting paths according to some task at hand. We demonstrate this by learning to navigate in an environment with obstacles as well as by learning to follow certain sequences of path nodes. Hence, the here-presented novel algorithm may open up a different regime of applications where path-augmentation (by learning) is directly coupled with path finding in a natural way.
翻译:在相连接的图形中找到最佳路径需要确定在图形边缘上旅行的最小总成本。 这个问题可以通过几种古典算法来解决, 通常情况下, 费用是为所有边缘预先确定的。 因此, 常规规划方法通常在想要按照某些任务的要求以适应的方式改变成本时不能使用。 这里我们显示, 可以通过将成本值转换成合成重量来定义路径发现问题的神经网络代表, 这样就可以使用网络学习机制进行在线体重调整。 从一个网络的初始活动值开始, 这个网络的活动传播将导致解决方案, 与贝尔曼福特算法发现的方法相同。 神经网络具有与贝尔曼福特( Bellman Ford) 相同的算法复杂性, 此外, 我们可以显示, 网络学习机制( 如 Hebbian 学习) 可以根据手头的任务来调整网络的重量, 增加由此导致路径的重量。 我们通过学习在有障碍的环境中航行, 以及学习遵循某些路径节点的顺序来证明这一点。 因此, 这里展示的新型算法可能打开一条不同的路径, 并直接找到一条自然路径。