# Combining Optimal Path Search With Task-Dependent Learning in a Neural Network

arXiv: https://arxiv.org/abs/2201.11104 · HTML: https://mlsanity.com/paper/2201.11104/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 23 of its 64 references that are in the map.
- First posted on arXiv 26 Jan 2022.

## Builds on (most cited first, 23 of 23)

- [Modeling Relational Data with Graph Convolutional Networks](https://mlsanity.com/paper/1703.06103/) (2017)
- [Spatial Temporal Graph Convolutional Networks for Skeleton-Based Action Recognition](https://mlsanity.com/paper/1801.07455/) (2018)
- [Link Prediction Based on Graph Neural Networks](https://mlsanity.com/paper/1802.09691/) (2018)
- [Scene Graph Generation by Iterative Message Passing](https://mlsanity.com/paper/1701.02426/) (2017)
- [Neural Motifs: Scene Graph Parsing with Global Context](https://mlsanity.com/paper/1711.06640/) (2017)
- [Graph R-CNN for Scene Graph Generation](https://mlsanity.com/paper/1808.00191/) (2018)
- [Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Prediction](https://mlsanity.com/paper/2106.06935/) (2021)
- [Inductive Relation Prediction by Subgraph Reasoning](https://mlsanity.com/paper/1911.06962/) (2019)
- [A Comprehensive Survey of Scene Graphs: Generation and Application](https://mlsanity.com/paper/2104.01111/) (2021)
- [Neural Execution of Graph Algorithms](https://mlsanity.com/paper/1910.10593/) (2019)
- [Virtual-to-real Deep Reinforcement Learning: Continuous Control of Mobile Robots for Mapless Navigation](https://mlsanity.com/paper/1703.00420/) (2017)
- [AutoGAN: Neural Architecture Search for Generative Adversarial Networks](https://mlsanity.com/paper/1908.03835/) (2019)
- [Motion Planning Networks](https://mlsanity.com/paper/1806.05767/) (2018)
- [Factorizable Net: An Efficient Subgraph-based Framework for Scene Graph Generation](https://mlsanity.com/paper/1806.11538/) (2018)
- [Graph Neural Networks Inspired by Classical Iterative Algorithms](https://mlsanity.com/paper/2103.06064/) (2021)
- [LinkNet: Relational Embedding for Scene Graph](https://mlsanity.com/paper/1811.06410/) (2018)
- [Neural Path Planning: Fixed Time, Near-Optimal Path Generation via Oracle Imitation](https://mlsanity.com/paper/1904.11102/) (2019)
- [Learning Human-Aware Path Planning with Fully Convolutional Networks](https://mlsanity.com/paper/1803.00429/) (2018)
- [AGAN: Towards Automated Design of Generative Adversarial Networks](https://mlsanity.com/paper/1906.11080/) (2019)
- [Scene Graph Generation via Conditional Random Fields](https://mlsanity.com/paper/1811.08075/) (2018)
- [Fully Convolutional Search Heuristic Learning for Rapid Path Planners](https://mlsanity.com/paper/1908.03343/) (2019)
- [From Simplicity to Complexity Based on Consensus: A Case Study](https://mlsanity.com/paper/1610.09482/) (2016)
- [Generation of Paths in a Maze using a Deep Network without Learning](https://mlsanity.com/paper/2004.00540/) (2020)

## Abstract (arXiv)

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.