# Assembling Ellipsoidal Particles at Fluid Interfaces using Switchable
Dipolar Capillary Interactions

Gary B. Davies<EMAIL_ADDRESS>Centre for Computational Science,
University College London, 20 Gordon Street, London WC1H 0AJ, United Kingdom.
Timm Krüger<EMAIL_ADDRESS>Institute for Materials and Processes,
Department of Engineering, University of Edinburgh, Mayfield Road, Edinburgh
EH9 3JL, Scotland, United Kingdom  Centre for Computational Science,
University College London, 20 Gordon Street, London WC1H 0AJ, United Kingdom.
Peter Coveney<EMAIL_ADDRESS>Centre for Computational Science,
University College London, 20 Gordon Street, London WC1H 0AJ, United Kingdom.
Jens Harting<EMAIL_ADDRESS>Department of Applied Physics, Eindhoven
University of Technology, P.O. Box 513, 5600 MB Eindhoven, The Netherlands.
Faculty of Science and Technology, Mesa+ Institute, University of Twente, 7500
AE Enschede, The Netherlands.  Fernando Bresme<EMAIL_ADDRESS>Department of Chemistry, Imperial College London, London, SW7 2AZ, United
Kingdom.  Department of Chemistry, Norwegian University of Science and
Technology, Trondheim, Norway.

The fabrication of novel soft materials is an important scientific and
technological challenge. We investigate the response of ellipsoidal particles
adsorbed at fluid-fluid interfaces to external magnetic fields. By exploiting
previously discovered first-order orientation phase transitions, we show how
to switch on and off dipolar capillary interactions between particles, leading
to the formation of distinctive self-assembled structures and allowing
dynamical control of the bottom-up fabrication of novel-structured materials.
Particles adsorb strongly at fluid-fluid interfaces: detachment energies of
spherical particles can be orders of magnitude greater than the thermal
energy, $k_{B}T$. binks_particles_2002; bresme_nanoparticles_2007 Once
particles are adsorbed at an interface, competing hydrodynamic,
electromagnetic and capillary interactions can lead to particles self-
assembling into two dimensional materials with specific mechanical, optical,
or magnetic properties. ozin2009nanochemistry
Capillary interactions botto_capillary_2012 have attracted interest for their
role in assembling mosquito eggs adsorbed at air-water interfaces,
loudet_how_2011 suppressing the coffee ring effect, yunker_suppression_2011
and aggregating Cheerios. vella_cheerios_2005 Capillary interactions occur
because of the creation of menisci around the particles, and these particle-
induced interface deformations, called capillary charges, interact with one
another analogously to electric charges. kralchevsky_capillary_1994;
kralchevsky_capillary_2000 The interface deformation, $h$, due to the presence
of a particle obeys Young’s equation, $\nabla^{2}h=0$, which can be solved
using a multipole expansion. botto_capillary_2012; lehle_ellipsoidal_2008;
oettel_colloidal_2008.

Heavy particles deform the interface symmetrically in a monopolar fashion
leading to $\log r$ interaction potentials between particles.
vella_cheerios_2005; botto_capillary_2012 However, for micron-sized particles,
gravitational forces are usually small compared to surface-tension forces.
botto_capillary_2012

Non neutrally-wetting ellipsoidal particles adsorbed at fluid-fluid interfaces
contort the interface around them in a quadrupolar fashion purely because of
their shape: loudet_capillary_2005; botto_capillary_2012 the interface is
depressed more at the tips than it is elevated at the sides, leading to
orientation-dependent interaction potentials between particles.
lehle_ellipsoidal_2008; botto_capillary_2012; loudet_capillary_2005;
oettel_colloidal_2008 The resulting capillary interaction energies can be
several orders of magnitude larger than the thermal energy, $E\sim
10^{5}k_{B}T$, providing a strong driving force for self-assembly.
loudet_capillary_2005; botto_capillary_2012 However, neither the monopolar nor
the quadrupolar interactions are dynamically tunable.

imgs/single_particle

Figure 1: Anti-symmetric meniscus formation (solid red lines) for a single
magnetic ellipsoidal particle with dipole moment $\bm{\mu}$ under the
influence of an applied magnetic field, $\mathbf{H}$, directed normal to the
interface.

Before First-Order Transition $H$ After First-Order Transition

(a) $B=0$, $t=0$

(b) $B=\frac{1}{2}B_{c}$, $t\rightarrow\infty$

(c) $B>B_{c}$, $t=0$

(d) $B\geq B_{c}$, $t\rightarrow\infty$

Figure 2: (a) The particles are distributed randomly in their equilibrium
orientations with surface fraction $\phi=0.38$. (b) Applying a magnetic field
causes them to self-assemble due to dipolar capillary interactions. (c) Once
the critical field strength is reached, particles transition to the vertical
state, halting dipolar capillary interactions. (d) Capillary interactions have
been turned off, the particles may order randomly if dipole-dipole and van der
Waals interactions are weak compared to thermal fluctuations.

Dipolar capillary charges are created by anisotropic particles influenced by
torques. External torques can be caused by particles with uneven mass
distributions interacting with gravity, complex surface chemistries (e.g.
Janus particles) interacting with fluids, li_size-controlled_2013;
guell_magnetically_2011; liu_self_2012 or - the focus of this communication -
embedded dipoles interacting with external magnetic fields, opening up new
routes for the manipulation of particle monolayers.

Materials science advances snoeks_colloidal_2000 have enabled the production
of anisotropic particles with embedded ferromagnetic dipoles, for use as e.g.
magnetic resonance imaging agents, zabow_ellipsoidal_2014 or
(super)-paramagnetic dipoles hyeon_chemical_2003; li_colloidal_2011 so that
particles can interact with external magnetic fields.

Bresme et al. bresme_orientational_2007 investigated the behaviour of magnetic
ellipsoidal particles adsorbed at fluid-fluid interfaces under the action of a
magnetic field, predicting that particles undergo a discontinuous, first-order
phase transition from a tilted state to a vertical state if a critical dipole-
field strength is reached. bresme_computer_2008 Davies et al.
davies_effect_2014 provided further evidence that the transition exists and
also showed that particle-induced interface deformations significantly affect
the transition when fluid solvent particles are much smaller than the adsorbed
particle.

|  0.0$B_{c}$ |  0.2$B_{c}$ |  0.5$B_{c}$ |  0.8$B_{c}$ |  1.2$B_{c}$
---|---|---|---|---|---
$\phi=0.38$ |  (e) |  (f) |  (g) |  (h) |  (i)
$\phi=0.53$ |  (j) |  (k) |  (l) |  (m) |  (n)
$\phi=0.60$ |  (o) |  (p) |  (q) |  (r) |  (s)
Figure 3: Snapshots of self-assembled structures as the external field, $B$,
and surface fraction of particles, $\phi$, is varied, showing a strong
dependence on both parameters. At small applied fields, $B=0.2B_{c}$, we see
some particle ordering where particles prefer to be in a side-by-side or tip-
to-tip state (b), (g), (l). For $B=0.5B_{c}$ we observed the formation of
curved “capillary caterpillars”, in which the particles are oriented side-by-
side and separate caterpillars prefer to face each other tip-to-tip (c), (h),
(m). As the field strength is increased to $0.8B_{c}$, the caterpillars begin
to prefer sharper, $90^{\circ}$ corners instead curved chains (d), (i), (n).
We see a further increase in corner sharpness for field strengths of
$B=1.2B_{c}$, and we observed small numbers of flipped particles in the
vertical state for $\phi=0.38$ (e). As the surface fraction is increased to
$\phi=0.53$ (j) and $\phi=0.60$ (o), fewer flipped particles are observed.

imgs/sideview

Figure 4: (a) The particles are randomly distributed on the interface, with
$B=0$ (Fig 2(a)). (b) Due to capillary charges - like menisci attract, unlike
menisci repel - the particles arrange into pairs because of the anti-symmetric
nature of the meniscus formation (Fig 2(b)). (c) Once the critical field is
reached, they discontinuously jump into the vertical configuration, aligning
with the external field, and the capillary interactions are turned off (Fig
2(c)).

When a magnetic ellipsoidal particle with dipole moment, $\bm{\mu}$, is
adsorbed at a fluid-fluid interface and subjected to an external magnetic
field, $\mathbf{H}$, it experiences a torque
$\bm{\mathrm{T}}=\bm{\mu}\times\mathbf{H}$, which attempts to align the
particle with the external field. Surface-tension forces oppose the magnetic
torque, and so for a given dipole-field strength,
$B=\lvert\bm{\mu}\rvert\lvert\mathbf{H}\rvert$, the particle is tilted with
respect to the external field, rather than aligned with it. When the particle
is tilted with respect to the interface, the constant contact-angle condition
stipulated by Young’s equation means that the particle deforms the interface:
davies_effect_2014 the interface is depressed on one side and elevated on the
other, as shown in Fig. 1.

When a critical dipole-field strength, $B_{c}$, is reached, however, the
magnetic torque overcomes surface-tension forces and the particle undergoes a
first-order phase transition and flips from a tilted orientation to a vertical
orientation, with respect to the interface. In the vertical orientation,
interface deformations, are absent.

The interface deformations that occur before the particle transitions to the
vertical state are important because they are analogous to electrostatic
charges, with a twist; Depressions attract depressions, elevations attract
elevations, and depressions repel elevations: opposites repel, rather than
attract. Therefore, if more than one particle is adsorbed at a fluid-fluid
interface and under the influence of an external magnetic field such that the
dipole-field strength is less than critical dipole-field strength, $B<B_{c}$,
we expect these capillary charges to interact with each other.

Due to the anti-symmetric, dipolar nature of the interface deformations, these
interactions are orientation dependent and will give rise to torques
orthogonal to the interface causing in-plane rotation and ordering. Further,
since the magnitude of the interface deformations depend on the dipole-field
strength, it is possible to tune the strength of these dipolar capillary
interactions by changing the strength of the external field, particle dipole
moment, or both.

We employed lattice Boltzmann simulations chen_lattice_1998;
chen_recovery_1992; shan_lattice_1993; shan_simulation_1994;
ladd_numerical_1994; ladd_numerical_1994-1; ladd_lattice-boltzmann_2001;
bhatnagar_model_1954; orlandini_lattice_1995; swift_lattice_1996;
jansen_bijels_2011; frijters_effects_2012 to investigate magnetic prolate
spheroidal particles with aspect-ratio $\alpha=2$ adsorbed at a liquid-liquid
interface under the influence of a magnetic field applied parallel to the
interface normal. In our simulations, the dipole-field strength, $B$, is
dominated by a strong external magnetic field and weak dipole moment so that
dipole-dipole interactions can be neglected. This means that the structures we
observe are purely a result of dipolar capillary interactions between
particles.

In Fig. 2 we show the particles undergoing a first-order transition into the
vertical orientation by exceeding the critical dipole-field strength, $B_{c}$,
demonstrating the unique phenomenology of the dipolar capillary interaction
mode. The particles begin randomly oriented on the interface (Fig. 2(a)). An
external field is applied such that the dipole-field strength is $B=0.5B_{c}$,
creating capillary charges and causing the particles to interact with each
other (Fig. 2(b)). The particles assemble into “capillary caterpillars”, which
we analyse further in Fig. 3. Finally, the dipole-field strength is increased
beyond the critical dipole field, $B>B_{c}$, where the particles transition
into the vertical configuration (Fig. 2(c)) and capillary interactions are
spontaneously switched off.

After the particles have transitioned to the vertical orientation, they order
according to a complex balance of other forces, such as dipole-dipole
interactions, thermal fluctuations, and van-der-Waals forces, which depend
strongly on different combinations of external field strength, dipole moment,
particle size and shape, surface packing fraction and fluid properties, making
final structures in the absence of capillary interactions difficult to
predict. Fig 2(d) denotes a situation in which thermal fluctuations are
greater than dipole-dipole interactions, and the particles order randomly.

The above mentioned parameters can be varied to observe the transition
experimentally. For a typical system: a super-paramagnetic particle of long-
axis radius $R_{\|}\approx 1\mathrm{\mu m}$ with a saturated magnetic moment
$\mu\approx 80~{}\mathrm{Am^{2}kg^{-1}}$ and surface-tension $\gamma\approx
50\times 10^{-3}~{}\mathrm{Nm^{-1}}$, a magnetic field strength
$H<1\mathrm{T}$ should suffice to observe the first-order phase transition.
bresme_orientational_2007

In Fig. 3 we present investigations of the intermediate dipole-field strength
regime, $0<B<B_{c}$, where the particles are tilted with respect to the
interface, for several surface-fractions, $\phi=NA_{p}/A$, where $N$ is the
number of particles adsorbed at the interface, $A_{p}$ the interface cross
sectional area of a single particle, and $A$ the area of the interface.

We find that the self-assembled structures depend strongly on the dipole-field
strength. For weak dipole-field strengths, $B=0.2B_{c}$, particles show some
ordering, orienting in the side-by-side and tip-to-tip configuration. As the
dipole-field strength is increased to $B=0.5B_{c}$ the particles begin to form
long, curved ordered chains, or “capillary caterpillars”, where particles
strongly prefer to orient side-by-side. Different capillary caterpillars face
each other in a tip-tip configuration, as can be seen in the upper-right of
Fig. 3m. The particles in this region align in “capillary couples” (Fig. 4b).

For dipole-field strengths of $B=1.2B_{c}$, the particles should be flipped
into the vertical state having exceeded the critical dipole-field strength
(Figs. 4c and 2(c)). However, for low surface fractions $\phi=0.38$ only a
small number of particles are flipped, and the number of particles in the
flipped state decreases as the surface-fraction increases to $\phi=0.53$ and
$\phi=0.60$. This suggests that many-body effects inhibit the first order
discontinuous transition.

Additionally, for dipole-field strengths of $B=1.2B_{c}$ the capillary
caterpillars favour straight chains with sharp corners rather than curved
chains as seen for $B=0.5B_{c}$. This is because the particles would ideally
like to arrange as shown in Fig. 4: the right angled, sharp edges allow more
interface overlap between individual particles than the curved chains.
However, the particles must rotate in the interface plane and perform
rotational work. For smaller dipole-field strengths, $B=0.5B_{c}$, the
particles’ angle with respect to the interface is much smaller than for larger
applied fields, $B=1.2B_{c}$, requiring more rotational work due to an
increased rotation angle, which is the reason chains have sharper corners as
the dipole-field strength is increased.

In order to quantify the behaviour observed in Fig. 3, we analysed the
distributions of in-plane angles between a particle and its two nearest
neighbours as the dipole-field strength is varied for packing fraction
$\phi=0.60$, as shown in Fig. 5. We find that the median angle between nearest
neighbours decreases as the dipole-field strength is increased. We also see
that the 25th and 75th percentiles decrease, showing that the distributions
tightens, meaning that more particles are in the side-by-side configuration as
the dipole-field strength increases, confirming our findings from Fig. 3.

Figure 5: Nearest neighbour angle distribution for packing fraction
$\phi=0.60$. The median angle between particle nearest neighbour decreases as
the dipole-field strength $B$ is increased. The $25^{\mathrm{th}}$ and
$75^{\mathrm{th}}$ percentile also decrease as the dipole-field increases,
showing that the distribution of nearest neighbour angles tightens with
increasing dipole-field strength.

Compared with the self-assembled structures observed due to quadrupolar
capillary interactions, loudet_capillary_2005; loudet_self-assembled_2009;
loudet_how_2011; botto_capillary_2012 the dipolar capillary interactions
favour side-side orientations. This is because the magnitude of the interface
deformations are equal on both sides of the particle in the dipolar mode; in
contrast, non-neutrally wetting prolate spheroid particles depress the
interface more at the tips than the sides favouring tip-tip configurations and
the formation of capillary arrows loudet_capillary_2005; loudet_self-
assembled_2009; loudet_how_2011. In the dipolar mode presented here, tip-to-
tip formations occur between particles in different capillary caterpillars
rather than within an individual caterpillar.

By using magnetic anisotropic particles interacting with external magnetic
fields, we showed how to dynamically tune dipolar capillary interactions
between particles by varying the dipole-field strength, and how to switch
these dipolar capillary interactions on and off by making the particles
undergo a first-order orientation transition. Our simulations revealed novel
self-assembled structures that depend on the surface coverage of particles and
the dipole-field strength. We observed the formation of “capillary
caterpillars”, in which particles align in side-to-side configurations, and
“capillary couples” where particles align in short tip-to-tip chains, due to
the anti-symmetric menisci formation.

In addition to providing motivation for new experiments on the bottom-up
fabrication of new materials, the novel assembly behaviour reported here
should also be observable in colloid-liquid crystal mixtures
meeker_colloidliquid-crystal_2000; cleaver_network_2004, and have implications
for liquid crystals in general. Further, the discontinuous transition of the
prolate spheroidal particles and the on-off tunability of capillary
interactions could find applications in photonic systems that require dynamic
control of optical properties — e.g. e-readers kim_self-assembled_2011.
Finally, the sensitivity of the first order orientation transition, and hence
the assembly process, to the particle size and shape, external field strength
and interface surface tensions has potential applications in colloidal
metrology e.g. sensors that respond to small changes in interface properties.

###### Acknowledgements.

GBD & PVC are grateful to EPRSC and Fujitsu Laboratories Europe for funding
GBD’s PhD studentship. JH acknowledges financial support from NWO/STW (VIDI
grant 10787 of J. Harting). FB acknowledges EPSRC for the award of a
Leadership Fellowship. TK thanks the University of Edinburgh for the award of
a Chancellor’s Fellowship. Our work originally made use of HECToR and latterly
of ARCHER, the United Kingdom’s national high-performance computing service,
via CPU allocations provided through EPSRC grants “Large Scale Lattice
Boltzmann for Biocolloidal Systems” (EP/I034602/1), “2020 Science”
(http://www.2020science.net/; EP/I017909/1), and “UK Consortium on Mesoscale
Engineering Sciences” (EP/L00030X/1). This research was also partially
supported by the EU-FP7 CRESTA grant (http://www.cresta-project.eu/; Grant No.
287703).


# POSTER: Diagnosis of COVID-19 through Transfer Learning Techniques on CT
Scans: A Comparison of Deep Learning Models

Aeyan Ashraf  Department of Computer Engineering
Aligarh Muslim University
Aligarh, India
<EMAIL_ADDRESS>Asad Malik  Department of Computer Science
Aligarh Muslim University
Aligarh, India
<EMAIL_ADDRESS>Zahid Khan  College of Computer and Information
Sciences
Prince Sultan University
Riyadh, Saudi Arabia
<EMAIL_ADDRESS>
###### Abstract

The novel coronavirus disease (COVID-19) constitutes a public health emergency
globally. It is a deadly disease which has infected more than 230 million
people worldwide. Therefore, early and unswerving detection of COVID-19 is
necessary. Evidence of this virus is most commonly being tested by RT-PCR
test. This test is not 100% reliable as it is known to give false positives
and false negatives. Other methods like X-Ray images or CT scans show the
detailed imaging of lungs and have been proven more reliable. This paper
compares different deep learning models used to detect COVID-19 through
transfer learning technique on CT scan dataset. VGG-16 outperforms all the
other models achieving an accuracy of 85.33% on the dataset.

###### Index Terms:

Real-Time Polymerase Chain Reaction (RT-PCR), Computed Tomography (CT),
X-Radiation (X-Ray)

##  I Introduction

In 2020, Severe Acute Respiratory Syndrome Coronavirus 2 abbreviated as SARS-
CoV-2, an extremely dangerous and previously unknown virus, wreaked havoc
across the globe, killing more than 4.5 million people and leaving life long
complications among many. It was declared a pandemic by WHO on March 11,
2020[1]. COVID-19 is a disease caused by the SARS-CoV-2 virus. Coronavirus’s
first case was found in Wuhan, China, in December 2019. The RT-PCR (Real-Time
Polymerase Chain Reaction) test used to test the evidence for this virus is
not 100% reliable as it is known to give false-negative and false-positive
results. Furthermore, it takes at least 6-8 hours to give the results, which
is not helpful as this virus spreads rapidly through the air. In comparison to
RT-PCR, detection via CT scans is more reliable, useful, and quicker
technology for the classification of COVID-19. Recently, computer vision and
image processing has led to extraordinary developments with the advancement of
deep learning and especially the development of convolutional neural networks
(CNN). The AI-based computer-aided system can speed up the diagnostic process
and identify details imperceptible to the human eye. Several studies have been
done in this domain. Meng Li[2] reviewed the chest CT features of COVID-19
patients and analyzed the role of Chest CT. Dai et al.[3] explained the
findings from lung CT scans of some patients that were admitted in The Second
People’s Hospital of Shenzhen for treatment of COVID-19. Fang et al.[4] found
that the chest CT scans demonstrated a higher sensitivity of 97% and was
therefore a better way of screening and monitoring by radiologists. Ai et
al.[5] studied the correlation of Chest CT and RT-PCR Testing for Coronavirus
disease. Nuriel[6] also constructed a CNN model based on MobileNetV2 to
evaluate the ability of deep learning to detect COVID-19 from chest CT images.
Yu et al.[7] constructed a system based on UNet++ for identification of
COVID-19 from CT images. Chand et al.[8] compared AlexNet, Resnet, VGG for
classification of COVID-19. Similarly research has been carried out for
detecting COVID-19 from X-Ray images as well([9] and [10] are some examples).

##  II Methods and Materials

###  II-A Dataset used

This paper uses an open-sourced dataset COVID-CT[11], which contains 349
COVID-19 CT images from 216 patients and 463 non-COVID-19 CTs. The utility of
this dataset has been confirmed by a senior radiologist who was diagnosing and
treating COVID-19 patients since the outbreak of the pandemic.

###  II-B Data Preprocessing

Since the images were of different sizes, we resized them to $224\times 224$.
For this we used the Keras “preprocess_input” function. The dataset was not
very large so to address the problem of overfitting various data augmentation
techniques were applied to the training samples. “ImageDataGenerator” function
was used for this purpose. We set the rotation range to 20 degrees and used
Random Height, Random Width and Random Flip.

###  II-C Transfer learning

Transfer Learning is a method which helps us in building an accurate model
without starting the process from scratch. It saves us a lot of time and is
useful because we use pre-trained models which does not need a large dataset.
In this paper we have used VGG16 & VGG19[12], Resnet50[13], InceptionV3[14],
Xception[15] models. The input size for all the models is (224 $\times$ 224
$\times$ 3). The problem that we usually face in using a pre-trained model is
overfitting. In our case we used data Augmentation and Dropout to address this
issue. After the convolutional base the flatten layer is placed which
transforms the 2-D feature matrix into a vector. After that fully connected
layer with Rectified Linear Unit(ReLU) is used. The output is then fed to
Softmax activation Layer for final classification. Fig. 1 shows how a model is
constructed using transfer learning.

Figure 1: A basic work flow of transfer learning model by using augmentation
technique.

##  III Experiments and Results

For this experiment we have used the Google Colaboratory also known as Colab
with Intel(R) Xeon(R) CPU @2.30GHz, 30GB RAM and NVIDIA TESLA P100 GPU. The
performance evaluation used to see the performance of the model in this
research was calculated using AUC(area under the receiver operating
characteristic(ROC) curve), Accuracy, Precision, Recall, Specificity, $F_{1}$
score, Computation Time.

TABLE I: Model performance with different epochs.

2 Model | 50-epochs | 75-epochs | 100-epochs | best-ACC | best-F1 | best-AUC
---|---|---|---|---|---|---
2 VGG-16 | 85.33% | 82% | 81.33% | 85.33% | 85.51% | 0.858
VGG-19 | 82% | 84.66% | 81.33% | 84.66% | 83.68% | 0.846
ResNet-50 | 49.33% | 51.33% | 63.33% | 63.33% | 69.6% | 0.65
InceptionV3 | 76% | 76.66% | 76% | 76.66% | 76.62% | 0.765
Xception | 78.66% | 78.66% | 78.66% | 78.66% | 80% | 0.794
2 |  |  |  |  |  |

Figure 2: Confusion Matrices

Table I shows the accuracy, $F_{1}$ score and AUC for each model. Among all
the tested models, VGG16 and VGG19 produced the best classification accuracy
with 85.33% and 84.66% respectively, whereas ResNet50 produced the lowest with
63.33%. InceptionV3 and Xception showed considerable performance with 76.66%
and 78.66%. It can be observed that the highest $F_{1}$ score has been
attained by VGG16, which is 85.51% followed by VGG19 with 83.68%. The lowest
$F_{1}$ score was attained by ResNet50 with 64.47%, followed by InceptionV3
with 70.58% and Xception with 80%.

The confusion matrices(in their respective best cases) for the models are
shown in 2. If we take a look at the confusion matrices, VGG16 has the most
correct classifications followed by VGG19. Resnet50 classified the COVID
images very well but performed poorly on NonCOVID images. InceptionV3 performs
well on the NonCOVID images but can classify very few COVID images correctly.
Xception performs fairly. If Computation time is considered InceptionV3
performs the best with 306ms/step followed by VGG16(310ms/step),
VGG19(315ms/step), Xception(345ms/step) and lastly ResNet50(360ms/step). Since
InceptionV3 has inferior accuracy & is only faster by a very small
margin(5ms/step) therefore VGG16 and VGG19 prove to be the best models for
diagnosing COVID-19 from CT scans.

##  IV Conclusion

In this experiment we trained 5 different models with variations in epochs(50,
75 and 100). There are a lot of factors which influence the performance of the
models like image quantity, Model complexity, optimizer, epochs, loss
function. Our experiments and result obtained shows that VGG models perform
the best for classification on this particular dataset. ResNet50 has a simple,
single-scale processing unit with data pass-through connections due to which
it takes a toll on it’s performance. InceptionV3 divides processing by scale,
merges the results, and repeats leading to the gain in performance versus
Resnet. Xception and InceptionV3 are similar as Xception stands for extreme
Inception. It uses depthwise separable convolutions. From this we can conclude
that the very shallow and simple models like VGG perform well on our dataset.
Models with shortcut connection adding the input of the block to its output
like ResNet50 perform very poorly. Wider models like InceptionV3 and Xception
perform fairly good.

## References

  * [1] C. Wang, P. W. Horby, F. G. Hayden, and G. F. Gao, “A novel coronavirus outbreak of global health concern,” _The lancet_ , vol. 395, no. 10223, pp. 470–473, 2020.
  * [2] M. Li, “Chest ct features and their role in covid-19,” _Radiology of Infectious Diseases_ , vol. 7, no. 2, pp. 51–54, 2020.
  * [3] W.-c. Dai, H.-w. Zhang, J. Yu, H.-j. Xu, H. Chen, S.-p. Luo, H. Zhang, L.-h. Liang, X.-l. Wu, Y. Lei _et al._ , “Ct imaging and differential diagnosis of covid-19,” _Canadian Association of Radiologists Journal_ , vol. 71, no. 2, pp. 195–200, 2020.
  * [4] Y. Fang, H. Zhang, J. Xie, M. Lin, L. Ying, P. Pang, and W. Ji, “Sensitivity of chest ct for covid-19: comparison to rt-pcr,” _Radiology_ , vol. 296, no. 2, pp. E115–E117, 2020.
  * [5] T. Ai, Z. Yang, H. Hou, C. Zhan, C. Chen, W. Lv, Q. Tao, Z. Sun, and L. Xia, “Correlation of chest ct and rt-pcr testing for coronavirus disease 2019 (covid-19) in china: a report of 1014 cases,” _Radiology_ , vol. 296, no. 2, pp. E32–E40, 2020.
  * [6] N. S. Mor, “Corona virus disease (covid-19) screening with deep learning using ct images,” 2020.
  * [7] J. Chen, L. Wu, J. Zhang, L. Zhang, D. Gong, Y. Zhao, Q. Chen, S. Huang, M. Yang, X. Yang _et al._ , “Deep learning-based model for detecting 2019 novel coronavirus pneumonia on high-resolution computed tomography,” _Scientific reports_ , vol. 10, no. 1, pp. 1–11, 2020.
  * [8] A. Chand, K. Chandani, and M. Arora, “Transfer learning-based detection of covid-19 using chest ct scan images,” in _IoT and Analytics for Sensor Networks_ , P. Nayak, S. Pal, and S.-L. Peng, Eds. Singapore: Springer Singapore, 2022, pp. 393–402.
  * [9] M. Jawahar, L. J. Anbarasi, P. Jayachandran, M. Ramachandran, and F. Al-Turjman, “Utilization of transfer learning model in detecting covid-19 cases from chest x-ray images,” _International Journal of E-Health and Medical Communications (IJEHMC)_ , vol. 13, no. 2, pp. 1–11, 2021.
  * [10] S. Tammina, “Covidsort: Detection of novel covid-19 in chest x-ray images by leveraging deep transfer learning models,” in _ICDSMLA 2020_ , A. Kumar, S. Senatore, and V. K. Gunjan, Eds. Singapore: Springer Singapore, 2022, pp. 431–447.
  * [11] J. Zhao, Y. Zhang, X. He, and P. Xie, “Covid-ct-dataset: a ct scan dataset about covid-19,” _arXiv preprint arXiv:2003.13865_ , 2020.
  * [12] K. Simonyan and A. Zisserman, “Very deep convolutional networks for large-scale image recognition,” _arXiv preprint arXiv:1409.1556_ , 2014.
  * [13] K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2016, pp. 770–778.
  * [14] C. Szegedy, V. Vanhoucke, S. Ioffe, J. Shlens, and Z. Wojna, “Rethinking the inception architecture for computer vision,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2016, pp. 2818–2826.
  * [15] F. Chollet, “Xception: Deep learning with depthwise separable convolutions,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2017, pp. 1251–1258.


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

Tomas Kulvicius, Minija Tamosiunaite, and Florentin Wörgötter The research
leading to these results has received funding from the European Community’s
H2020 Programme (Future and Emerging Technologies, FET) under grant agreement
no. 899265 (ADOPD), and the German Science Foundation (DFG), under grant
agreement no. WO 388/16-1.T. Kulvicius, M. Tamosiunaite and F. Wörgötter are
with the Department for Computational Neuroscience, University of Göttingen,
37073 Göttingen, Germany.T. Kulvicius is also with University Medical Center
Göttingen, Systemic Ethology and Developmental Science, Child and Adolescent
Psychiatry and Psychotherapy, Göttingen, Germany.M. Tamosiunaite is also with
the Faculty of Computer Science, Vytautas Mangnus University, Kaunas,
Lithuania.

###### Abstract

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.

##  I Introduction

This study addresses the so-called single-source shortest path (SSSP) problem.
Possibly the most prominent goal for any path finding problem is to determine
a path between two vertices (usually called source and destination) in a graph
such that the total summed costs for traveling along this path is minimised.
Usually (numerical) costs are associated to the edges that connect the
vertices and costs are this way accumulated when traveling along a set of
them. In the SSSP problem, the aim is to find the shortest paths from one
vertex (source) to all other remaining vertices in the graph.

The SSSP problem has a wide range of applications, e.g., in computer networks
(shortest path between two computers), social networks (shortest path between
two persons or linking between two persons), trading and finance (e.g.,
currency exchange), multi-agent systems such as games, task and path planning
in robotics, etc., just to name a few.

The most general way to solve the SSSP problem is the Bellman-Ford (BF)
algorithm [1, 2, 3], which can also deal with graphs that have some negative
cost values. In this work, we present a neural implementation which is
mathematically equivalent to the BF algorithm with an algorithmic complexity
which is the same as for BF.

The neural implementation relies on the multiplication of activities (instead
of adding of costs). As a consequence, it is directly compatible with
(Hebbian) network learning, which is not the case for any additively operating
path planning algorithm. To demonstrate this, we are using Hebbian type
3-factor learning [4, 5, 6] to address SSSP tasks under some additional
constraints, solved by the 3-factor learning.

Our paper is structured as follows. First, we will provide an overview of the
state of the art methods and state our contribution with respect to that.
Next, we will describe details of the BF algorithm and the proposed neural
network (NN-BF). Afterwards, we will present the 3-factor learning scheme and
two learning scenarios: navigation learning and sequence learning. This will
be followed by a comparison between the BF algorithm and NN-BF and by examples
of combining NN-BF based planning with 3-factor learning. Finally, we will
conclude our study with a summary and provide an outlook for future work.

##  II Related Work

###  II-A State-of-the-art

There are mainly two types of approaches to solve the SSSP problem: classical
algorithms and approaches based on artificial neural networks. Classical
algorithms exist with different complexity and properties. The simplest and
fastest algorithm is ”breadth first search (BFS)” [7, 8]. However, it can only
solve the SSSP problem for graphs with uniform costs, i.e., all costs equal to
1. Dijkstra’s algorithm [9] as well as the Bellman-Ford (BF) algorithm [1, 2]
can deal with graphs that have arbitrary costs. From an algorithmic point of
view, Dijkstra’s algorithm is faster than the BF algorithm, however, Dijkstra
only works on graphs with positive costs, whereas the BF algorithm can also
solve graphs where some of the costs are negative. Furthermore, Dijkstra is a
greedy algorithm and requires a priority queue, which makes it not so well
suited for parallel implementation as compared to BF.

Some heuristic search algorithms such as A* [10] and its variants (see [11,
12, 13, 14]) exist, which are faster than Dijkstra or BF, but they can only
solve the single-source single-target shortest path problem.

The most general, but slowest, algorithm to solve the SSSP problem is the
Floyd-Warshall algorithm [15, 16], which finds all-pairs shortest paths
(APSP), i.e., all shortest paths from each vertex to all other vertices.
Another way to solve the APSP problem is by using Johnson’s algorithm [17],
which utilises Bellman-Ford and Dijkstra’s algorithms and is – under some
conditions – faster than the Floyd-Warshall algorithm (essentially this is the
case for sparse graphs).

Many different algorithms exist, which utilise artificial neural networks to
solve shortest path problems. Some early approaches, which were dealing with
relatively small graphs (below 100 nodes), were based on Hopfield networks
[18, 19, 20] or Potts neurons and a mean field approach [21]. These
approaches, however, may not always give optimal solutions or may fail to find
solutions at all, especially for larger graphs.

Some other bio-inspired neural networks were proposed [22, 23, 24, 25, 26, 27,
28] for solving path planning problems. These approaches work on grid
structures, where activity in the network is propagated from the source neuron
to the neighbouring neurons until activity propagation within the whole
network is finished. Shortest paths then can be reconstructed by following the
activity gradients. The drawback of these approaches is, however, that they
are specifically designed for grid structures and can not be applied at
general graphs with arbitrary costs.

Several deep learning approaches were proposed to solve shortest path
problems, for example using a deep multi-layer perceptron (DMLP, [29]), fully
convolutional networks [30, 31, 32], or a long short-term memory (LSTM)
network [33]. Some of these approaches had also employed deep reinforcement
learning [34, 35, 36]. These approaches are designed to solve path planning
problems in 2D or 3D spaces and cannot deal with graphs with arbitrary costs.

In addition to this, deep learning approaches based on graph neural networks
(GNNs) have been employed to solve path problems, too [37, 38, 39, 40, 41,
42], mostly in the context of relation and link predictions. While deep
learning approaches may lead to a better run-time performance as compared to
classical approaches due to fast inference, all deep learning based approaches
need to learn their (many) synaptic weights before they are functional. This
usually requires a large amount of training data. Another disadvantage of
these approaches is that optimal solution is not guaranteed since networks
intrinsically perform function approximation based on the training data.
Moreover, in some of the cases networks may even fail to find a solution at
all, especially, in cases where training data is quite different from new
cases (generalisation issue for out-of-distribution data).

###  II-B Contribution

Different from the discussed deep learning approaches, we present here a novel
neural network for solving the SSSP problem. To the best of our knowledge this
is the first neural implementation of the Bellman-Ford algorithm, which finds
optimal solutions for graphs with arbitrary positive and (some) negative
costs. The advantage of this is that, different from BF, we can also directly
apply neuronal learning rules that can dynamically change the activity in the
network and lead to re-routing of paths according to some requirements. We
show this by two cases where neuronal learning is used to structure the
routing of the paths in a graph in different ways.

##  III Methods

###  III-A Bellman-Ford algorithm

The Bellman-Ford (BF) algorithm finds shortest paths in a weighted graph from
a source node (vertex) to all other nodes [1, 2]. Shortest paths are defined
in terms of minimal distances from the source node to all other nodes.

Algorithm 1 Pseudo-code of the Bellman-Ford algorithm – version 1.

Input: list of graph edges $(u,v)$ with costs $(c_{u,v})$, source node $(s)$
Output: list of distances, list of predecessor nodes

for each node $v$ do

$distances[v]\leftarrow\infty$ $\triangleright$ Initialise all distances with
$\infty$

$predecessors[v]\leftarrow null$ $\triangleright$ Initialise all predecessors
with $null$

end for

$distances[s]\leftarrow 0$ $\triangleright$ Initialise distance of the source
node with $0$

for $k\leftarrow 1$ to $|V|-1$ do $\triangleright$ Repeat $|V|-1$ times ($|V|$
\- number of nodes)

for each edge $(u,v)$ with cost $c_{u,v}$ do $\triangleright$ For each edge
perform relaxation

$new\\_distance\leftarrow distances[u]+c_{u,v}$

if $new\\_distance<distances[v]$ then

$distances[v]\leftarrow new\\_distance$

$predecessors[v]\leftarrow u$

end if

end for

end for

return $distances$, $predecessors$ $\triangleright$ Return list of distances
and list of predecessors

Algorithm 2 Pseudo-code of Bellman-Ford algorithm – version 2.

Input: list of graph edges $(u,v)$ with costs $(c_{u,v})$, source node $(s)$
Output: list of distances, list of predecessor nodes

for each node $v$ do

$distances[v]\leftarrow\infty$ $\triangleright$ Initialise all distances with
$\infty$

$predecessors[v]\leftarrow null$ $\triangleright$ Initialise all predecessors
with $null$

end for

$distances[s]\leftarrow 0$ $\triangleright$ Initialise distance of the source
node with $0$

for $k\leftarrow 1$ to $|V|-1$ do $\triangleright$ Repeat $|V|-1$ times ($|V|$
\- number of nodes)

for each vertex $v\neq s$ do $\triangleright$ For each vertex perform
relaxation

for each edge $(u,v)$ of vertex $v$ with cost $c_{u,v}$ do

$new\\_distance\leftarrow distances[u]+c_{u,v}$

if $new\\_distance<distances[v]$ then

$distances[v]\leftarrow new\\_distance$

$predecessors[v]\leftarrow u$

end if

end for

end for

end for

return $distances$, $predecessors$ $\triangleright$ Return list of distances
and list of predecessors

There are two versions of the BF algorithm [3]. The pseudo-code of BF –
version 1 and BF – version 2 is presented in Algorithm 1 and Algorithm 2,
respectively. Both versions have the same basic algorithmic complexity (see
analysis below) but BF-Version 2 operates on graph nodes and not on graph
edges which allows implementing BF – version 2 in totally asynchronous way
(computations at each node are independent) [3]111In spite of this, BF –
version 2 is largely ignored in the literature and users will usually be
directed to BF – version 1 when doing a (web-)search..

We denote a weighted graph as $G(V,E,C)$ with vertices $V$, edges $E$ and
corresponding edge costs $C$. In the first version of the BF algorithm a so
called relaxation procedure (cost minimisation) is performed for all edges
whereas in the second version of the BF algorithm relaxation is performed for
all nodes. The relaxation procedure is performed for a number of iterations
until convergence, i.e., approximate distances are replaced with shorter
distances until all distances finally converge.

The BF algorithm is guaranteed to converge if relaxation of all edges is
performed $|V|-1$ times222Note that this corresponds to the worst case. See
also algorithmic complexity analysis below.. After convergence, shortest paths
(sequences of nodes) can be found from a list of predecessor nodes backwards
from target nodes to the source node.

###  III-B Neural implementation of the Bellman-Ford algorithm

In this section we will describe our neural implementation of Bellman-Ford
(BF) algorithm. Similar to BF, the proposed neural network finds shortest
paths in a weighted graph from a source node (vertex) to all other nodes,
however, shortest paths here are defined in terms of maximal activations from
the source neuron to all other neurons.

Algorithm 3 Pseudo-code of neural network algorithm.

Input: list of neuron connections $(i,j)$ with weights $(w_{i,j})$, source
neuron $(s)$
Output: list of neuron activations (outputs), list of input nodes with maximal
activity

for each neuron $i$ do

$activations[i]\leftarrow 0$ $\triangleright$ Initialise all neuron
activations with $0$

$max\\_inputs[i]\leftarrow null$ $\triangleright$ Initialise all maximal input
nodes with $null$

end for

$activations[s]\leftarrow 1$ $\triangleright$ Initialise activation of the
source neuron with $1$

for $k\leftarrow 1$ to $N-1$ do $\triangleright$ Repeat $N-1$ times ($N$ \-
number of neurons)

for each neuron $i$ do $\triangleright$ For each neuron compute its activation

for each input $j$ of neuron $i$ with weight $w_{i,j}$ do

$weighted\\_input\leftarrow activations[j]\times w_{i,j}$

if $weighted\\_input>activations[i]$ then

$activations[i]\leftarrow weighted\\_input$

$max\\_inputs[i]\leftarrow j$

end if

end for

end for

$activations[s]\leftarrow 1$ $\triangleright$ Set activation of the source
neuron to $1$

end for

return $activations$, $max\\_inputs$ $\triangleright$ Return list of
activations and list of max inputs

The neural network has $N$ neurons where $N$ corresponds to the number of
vertices $|V|$ in a graph, connections between neurons $i$ and $j$
($i,j=1\dots N$) correspond to the edges, and connection weights correspond to
the (inverse) costs of edges which are computed by

$w_{i,j}=1-\frac{c_{i,j}}{K},$ (1)

where $K>0$. We can prove that the solutions obtained with the neural network
are identical to the solutions obtained with BF under certain constraints (see
section IV-A1).

Figure 1: Example of solving a directed weighted graph with four vertices and
six edges using (a) BF and (b) NN-BF. Green circle denotes the source
vertex/neuron. Yellow numbers in (a) and (b) correspond to the edge and vertex
numbers respectively. Black numbers correspond to the edge/connection weights.
Red numbers correspond to costs/activations from the source vertex/neuron for
the respective edges/inputs. Numbers inside graph vertices/neurons correspond
to costs/activations from the source to the respective nodes/neurons. We used
$K=100$ to convert edge costs to connections weights, i.e.,
$w_{i}=1-c_{i}/100$ ($i=1\dots 6$). Green numbers in (a) correspond to the
numbers of edges and the order in which they were processed, whereas green
numbers in (b) correspond to numbers of neurons and their order in which their
were processed.

We present the pseudo-code of the neural network algorithm (NN-BF) in
Algorithm 3. Similar to BF – version 2 (Algorithm 2), we run NN-BF for a
number of iterations until convergence operating on the graph nodes (neurons).
In every iteration we update the activation (output) of each neuron by

$a_{i}=\max_{j}\\{a_{j}\,w_{i,j}\\},$ (2)

where $a_{j}$ correspond to the inputs of neuron $i$, and $w_{i,j}$ to the
connection weights between input neurons $j$ and output neuron $i$. To start
this process, we set the activation of the source neuron to $1$. Thus, this
way activity from the source neuron is propagated to all other neurons until
activation has converged everywhere. After convergence, shortest paths
(sequences of neurons) can be found from a list of maximal input activations
backwards from target neurons to the source neuron (similar to BF algorithm).

The NN-BF algorithm is guaranteed to converge if activity of the network is
updated $N-1$ ($N=|V|$) times. This can be shown by the the worst case
scenario where neurons would be connected in a sequence, i.e., $1\to 2\to
3\to\dots\to N$. Thus, to propagate activity from the $1st$ neuron to the last
neuron in the sequence one would need to perform $N-1$ updates.

A comparison of solving a simple graph using BF (version 1) and NN-BF is
presented in Fig. 1. Here we used a simple directed weighted graph with four
nodes and six edges with one negative cost and five positive costs. We show
the resulting distances in (a) and network activations in (b) after each
iteration (numbers inside the nodes/neurons of the graph/neural network). Red
edges/connections denote distance/activity propagation from the source
node/neuron to all other nodes/neurons. For more details please refer to the
figure caption. In this case, the algorithm converged after two iterations
when using BF and after one iteration when using NN-BF.

###  III-C Performance evaluation of the neural planner

We evaluated the performance of the neural network and compared it against
performance of the Bellman-Ford algorithm (version 1) with respect to 1)
solution equality, 2) algorithmic complexity and 3) number of iterations until
convergence.

For the numerical evaluation we generated random directed weighted graphs of
different density, from sparse graphs (only few connections per node) to fully
connected graphs (every node connects to all other nodes). To generate graphs
of different density, we used the probability $p_{e}$ to define whether two
nodes will be connected or not. For example, a graph with 100 nodes and
$p_{e}=0.1$ will obtain a $10\%$ connectivity rate, and, thus, to $\approx 10$
edges per node and $\approx 1,000$ edges in total.

Costs for edges were assigned randomly from specific ranges (e.g., $[-10,-1]$
and $[1,100]$), where negative weights were assigned with probability $p_{n}$
(e.g., $p_{n}=0.1$) and positive weights with probability $1-p_{n}$. The
specific parameters for each evaluation case will be provided in the results
sections.

###  III-D Combining neural planning network with neural plasticity

The neural implementation of the Bellman-Ford algorithm allows us to use
neuronal learning rules in order to dynamically change connection weights
between neurons in the network and, thus, the outcome of the neural planner.
In this section we present a combination of the neural planner with Hebbian
type synaptic plasticity ([4, 43, 6]) where we first present a learning scheme
and rule, and then we present two learning scenarios, namely, navigation
learning and sequence learning.

####  III-D1 Learning scheme

As described above, the shortest path in the network between a source and a
target neuron is given by that specific sequence of connected neurons, which
leads to the largest activation at the target neuron. Hence, learning that
modifies connection weights (and, hence, the resulting activations) can alter
path-planning sequences.

Figure 2: Schematic diagram of the learning architecture. $I_{e}$ \- external
input; $R$ \- reward signal; $O_{pre}$ and $O_{post}$ \- output of pre-
synaptic and post-synaptic neuron, respectively; $w$ \- synaptic weight
between pre- and post-synaptic neuron.

A diagram of the learning scheme is presented in Fig. 2, where we show
components of the learning rule to change the synaptic weight between two
neurons in the planning network. The outputs of pre-synaptic and post-synaptic
neuron, $O_{pre}$ and $O_{post}$, are computed as described above using
Eq.(2). Note that here neurons will also receive additional external input
$I_{e}=1$ signaling occurrence of specific events, for instance, if an agent
is at the specific location in an environment (otherwise it will be set to
$I_{e}=0$). However, the network will only receive external inputs $I_{e}$
during learning but not during planning. The driving force of the learning
process is the reward signal $R$ which can be positive or negative and will
lead to weight increase (long-term potentiation [LTP]) or decrease (long-term
depression [LTD]), respectively. Thus, the synaptic weight $w$ between pre-
and post-synaptic neuron is changed according to

$\Delta w=\alpha\,O_{pre}\,O_{post}\,R,$ (3)

where $\alpha>0$ is the learning rate. This learning rule represents a three-
factor rule (see [5] for a discussion of three-factor learning), where here
the third-factor is the reward signal $R$. Note that in our learning scheme
weights were bounded between $0$ and $1$, i.e., $0\leq w<1$.

####  III-D2 Navigation learning

In the first learning scenario, we considered a navigation task in 2D space,
where an agent had to explore an unknown environment and plan the shortest
path from a source location to a destination.

We assume a rectangular arena, see Fig. 6(a,b), iteration 0, with some
locations (blue dots) and obstacles (grey boxes). The locations are
represented by neurons in the planning network, whereas connections between
neurons correspond to possible transitions from one location to other
neighbouring locations. Note that some transitions between neighboring
locations, and, thus, connections between neurons are not possible due to
obstacles. The positions of locations and possible transitions between them
were generated in the following way. The position of a location $k$ is defined
by

$(x_{k},y_{k})=(h\,i+\xi_{i},h\,j+\xi_{j}),$ (4)

where $i,j=1,2,\dots m$, and $\xi$ is noise from a uniform distribution
$\mathcal{U}(a,b)$. In this study, we used $m=5$ ($k=m^{2}=25$), $h=0.2$,
$a=-0.05$, and $b=0.05$.

Possible transitions between neighbouring locations, and, thus, possible
connections between neurons were defined based on a distance threshold
$\theta_{d}$ between locations, i.e., connections were only possible if the
Euclidean distance between two locations
$d_{k,l}=||(x_{k},y_{k})-(x_{l},y_{l})||\leq\theta_{d}$. In one case (Fig.
6(a)) we used $\theta_{d}=0.25$ and in another case (Fig. 6(b)) we used
$\theta_{d}=0.35$.

Synaptic weights between neurons were updated after each transition (called
iteration) from the current location $k$ (pre-synaptic neuron) to the next
neighboring location $l$ (post-synaptic neuron) according to the learning rule
as described above, where pre- and post-synaptic neurons obtain an external
input $I_{e}=1$ during this transition (otherwise $I_{e}=0$). In the
navigation scenario the reward signal $R$ was inversely proportional to the
distance between neighbouring locations $d_{k,l}$, i.e., $R=1-\beta\,d_{k,l}$
(here we used $\beta=1$). Thus, smaller distances between locations lead to
larger reward values and larger weight updates, and vice versa. In the
navigation learning scenario, initially all weights were set to $0$, and the
learning rate was set to $\alpha=0.02$. The learning and planning processes
were repeated many times, where the learning process was performed for 100
iterations and then a path from the source (bottom-left corner) to the
destination location (top-right corner) was planned using current state of the
network.

We used two navigation learning cases. In the first case, a static environment
with multiple obstacles was used where obstacles were present during the whole
experiment (see Fig. 6(a)), whereas in the second case a dynamic environment
was simulated, where one big obstacle was used for some period of time and
then was removed some time later (see Fig. 6(b)).

####  III-D3 Sequence learning

In the second learning scenario, we were dealing with sequence learning, where
the task was to learn executing a predefined sequence of arbitrary events,
which in our study were denoted by letters. For instance, this could
correspond to learning to play a tune were letters correspond to sounds.

In this case, we used a fully connected network (without self-connections)
were neurons correspond to letters. In total we used six different events
(letters), i.e., $A$, $B$, $\dots$, $F$ (see Fig. 7(a)). Initially all weights
were set to random values from a uniform distribution $\mathcal{U}(0,0.5)$.
Here, the planning and learning procedure is performed in epochs, where we
execute the sequence based on the planner’s outcome always starting with
letter $A$ and ending with letter $F$, and perform weight updates for each
pair in the planned sequence. Suppose that at the beginning the planner
generates a sequence $A\,B\,F$, then there will be two learning iterations in
this epoch, i.e., weight update for the transition from $A$ to $B$ and from
$B$ to $F$. As in the navigation learning scenario, pre- and post-synaptic
neurons will receive external input $I_{e}=1$ whenever a certain transition
from one event to the next event happens, e.g., from $A$ (pre-synaptic neuron)
to $B$ (post-synaptic neuron).

Different from the navigation scenario, here we used positive and negative
rewards, i.e., $R=1$ if a sequence-pair is correct and $R=-1$ otherwise. In
case of our previous $A\,B\,F$ example, this would lead to an increase of the
synaptic weight between neurons $A$ and $B$ (correct), and to a decease of the
synaptic weight between neurons $B$ and $F$ (incorrect; after $B$ should be
$C$). The learning procedure is repeated for several learning epochs until
convergence. Here we used the relatively high learning rate $\alpha=0.9$,
which allows fast convergence to the correct sequence.

We performed two sequence learning cases where in the first case we were
learning a sequence consisting of all possible six events $A\,B\,C\,D\,E\,F$,
and in the second case a shorter sequence $A\,C\,D\,F$ had to be learnt.

##  IV Results

###  IV-A Comparison of BF and NN-BF

In the following we first provide a comparison between BF and NN-BF, and then
we will show results for NN-BF also on network learning.

####  IV-A1 Solution equality

To prove equivalence one can pairwise compare two paths A and B between some
source and a target, where A is the best path under the Bellman-Ford condition
and B is any another path. Path A is given by nodes $a_{i}$ and B by $b_{i}$.
As described above, for a Bellman-Ford cost of $a_{i}$ we define the weight of
the NN-BF connection as $w_{i}=1-\frac{a_{i}}{K}$ and likewise for $b_{i}$. We
need to show that:

$\textrm{if}~{}\sum_{i=1}^{n}a_{i}<\sum_{i=1}^{n+m}b_{i}~{}\textrm{then}~{}\prod_{i=1}^{n}(1-\frac{a_{i}}{K})>\prod_{i=1}^{n+m}(1-\frac{b_{i}}{K})$
(5)

Note, in general we can assume for both sides a path length of $n$, because –
if one path is shorter than the other – we can just extend this by some dummy
nodes with zero cost such that the Bellman-Ford costs still add up correctly
to the total.

First we analyse the simple case of $n=2$. The general proof, below, makes use
of the structural similarity to the simple case. Thus, we show:

$\displaystyle a_{1}+a_{2}$ $\displaystyle<$ $\displaystyle
b_{1}+b_{2}\Leftrightarrow$
$\displaystyle(1-\frac{a_{1}}{K})(1-\frac{a_{2}}{K})$ $\displaystyle>$
$\displaystyle(1-\frac{b_{1}}{K})(1-\frac{b_{2}}{K}),$ (6)

We start from the second line in Eq. 6 and rewrite it as:

${\frac{1}{K^{2}}}[K^{2}-K(a_{1}+a_{2})+a_{1}a_{2}]>{\frac{1}{K^{2}}}[K^{2}-K(b_{1}+b_{2})+b_{1}b_{2}]$
(7)

We simplify and divide by $K$, where $K>0$, to:

$-a_{1}-a_{2}+{\frac{a_{1}a_{2}}{K}}>-b_{1}-b_{2}+{\frac{b_{1}b_{2}}{K}}$ (8)

Now we let $K\rightarrow\infty$ and get:

$a_{1}+a_{2}<b_{1}+b_{2}$ (9)

which proves conjecture Eq. 6 for large enough $K$.

To generalize this we need to show that Eq. 5 holds. For this, we analyse the
second inequality given by:

$\prod_{i=1}^{n}(1-\frac{a_{i}}{K})>\prod_{i=1}^{n}(1-\frac{b_{i}}{K})$ (10)

From the structure of Eq. 7 we can deduce that:

$\displaystyle\prod_{i=1}^{n}(1-\frac{a_{i}}{K})={\frac{1}{K^{n}}}(K^{n}-K^{n-1}\sum_{i}a_{i}+$
$\displaystyle K^{n-2}\sum_{i\neq j}a_{i}a_{j}-K^{n-3}\sum_{i\neq j\neq
k}a_{i}a_{j}a_{k}\pm\dots)$ (11)

and likewise for $b_{i}$, which allows writing out both sides of inequality
Eq. 5. When doing this (not shown to save space), we see that the fore-factor
$\frac{1}{K^{n}}$ can be eliminated. Then the term $K^{n}$ also subtracts away
from both sides. After this we can divide the remaining inequality as in Eq. 8
above, here using $K^{n-1}$ as divisor. This renders:

$\displaystyle-\sum_{i}a_{i}+\frac{1}{K}\sum_{i\neq
j}a_{i}a_{j}-\frac{1}{K^{2}}\sum_{i\neq j\neq k}a_{i}a_{j}a_{k}\pm\dots>$
$\displaystyle-\sum_{i}b_{i}+\frac{1}{K}\sum_{i\neq
j}b_{i}b_{j}-\frac{1}{K^{2}}\sum_{i\neq j\neq
k}b_{i}b_{j}b_{k}\pm\dots\leftrightarrow$
$\displaystyle\sum_{i}a_{i}+D_{a}<\sum_{i}b_{i}+D_{b}$ (12)

using the correct individual signs for $D$. Now, for $K\rightarrow\infty$, the
disturbance terms $D$ vanish on both sides and we get:

$\sum_{i}a_{i}<\sum_{i}b_{i}$ (13)

as needed.

We conclude that for $K\rightarrow\infty$ the neural network is equivalent to
the Bellman-Ford algorithm.

In the following we will show by an extensive statistical evaluation that the
distribution of $K$ for different realistic graph configurations is well-
behaved and we never found any case where $K$ had to be larger than $10^{6}$.

Evidently $K$ can grow if $\sum_{i}a_{i}\approx\sum_{i}b_{i}$. This can be
seen easily as in this case we can express
$\sum_{i}b_{i}=\sum_{i}a_{i}+\epsilon$, with $\epsilon$ a small positive
number. When performing this setting we get from Eq. IV-A1 that
$\epsilon>D_{b}-D_{a}$, which can be fulfilled with large values for $K$.

We have set the word ”can” above in italics, because a broader analysis shows
that – even for similar sums – $K$ gets somewhat larger only for very few
cases only as can be seen from Fig. 3.

For this we performed the following experiment. We defined two paths A and B
with different lengths $L_{A}$ and $L_{B}$, where $L$ was taken from
$L\in\\{2,3,4,5,6,7,8,10,20,30,40,50,100,200\\}$ and all combinations of
$L_{A}$ and $L_{B}$ were used. We evaluated 60 instances for each path pair
(in total 11760 path pairs). To obtain those, we generated the cost for all
edges in both paths using Gaussian distributions, where mean $m$ and variance
$\sigma$ are chosen for each trial randomly and separately for A and B with
$1\leq m\leq 21$ and $0\leq\sigma\leq 5$.

Figure 3: Statistics for $K$ computed from a large number of 2-path
combinations. Contrast
$C=(\sum_{i}a_{i}-\sum_{i}b_{i})/(\sum_{i}a_{i}+\sum_{i}b_{i})$. For
$K>K_{0}$, NN-BF renders identical results as BF.

In Fig. 3, we are plotting on the horizontal axis the ”contrast” between the
summed cost of path A and B given by
$C={\frac{\sum_{i}a_{i}-\sum_{i}b_{i}}{\sum_{i}a_{i}+\sum_{i}b_{i}}}$. This
allows comparing sums with quite different values. The vertical axis shows
$K_{0}$, where for $K>K_{0}$ the neural network renders identical results as
Bellman-Ford.

Note that we have truncated this plot vertically, but only $15$ values of
$K_{0}$ had to be left out, all with contrast values $C\simeq 0$, where the
largest was $K_{0}=812$ with a contrast of $C=5.3349\times 10^{-5}$. Hence,
only for small contrast a few larger values of $K_{0}$ are found. Note also
that the asymmetry with respect to positive versus negative contrast is
expected, because fewer negative costs exist in paths A and B due to our
choice of $1\leq m\leq 21$.

Figure 4: Analysis of $K_{0}$ values for graphs of different sizes (500,
1,000, and 2,000), different densities (5, 10, 50 and 100%) and different cost
ranges ([1, 10], [1, 100], and [1, 1000]). For cases $|V|=500$ with graph
densities 5 and 10% and cost range [1, 1000], and for $|V|=1,000$ with graph
density 5% and cost range [1, 1000], 10,000 random graphs were used, whereas
in all other cases 1,000 graphs were used.

Considering only pairwise paths is of limited practical use. From such a
perspective it is better to consider different graphs with certain cost ranges
and different connection densities where one should now ask how likely it
would be that results of BF and NN-BF are mismatched due to a possible
$K$-divergence. To assess this we had calculated the statistics for three
different graphs with sizes 500, 1,000, and 2,000 nodes and randomly created
costs taken from three different uniform cost distributions with intervals:
[1, 10], [1, 100], and [1, 1000]. We considered four different connectivity
densities for each graph with 5, 10, 50, and 100% connections each. Fig. 4
shows the maximal $K_{0}$ found was $10^{6}$, hence that in all cases $K\geq
10^{6}$ will suffice, where such a high value is only needed for sparse graphs
and large costs.

####  IV-A2 Algorithmic Complexity of the Algorithms

In the following we will show that all three algorithms have the same
algorithmic complexity.

Bellman-Ford (BF) – version 1 consists of two loops (see Algorithm 1), where
the outer loop runs in $\mathcal{O}(|V|)$ time and the inner loop runs in
$\mathcal{O}(|E|)$, where $|V|$ and $|E|$ define the number of graph vertices
(nodes) and edges (links), respectively. In the worst case, BF needs to be run
for $|V|-1$ iterations and in the best case only for one iteration. Thus, the
worst algorithmic complexity of BF is $\mathcal{O}(|V|\,|E|)$, whereas the
best is $\mathcal{O}(|E|)$.

The algorithmic structure of the second version of the BF algorithm (see
Algorithm 2) is the same as that of our NN-BF algorithm (Algorithm 3). Hence
their complexity is the same and we will provide analysis for the NN-BF
algorithm. NN-BF operates on neurons and their inputs and not on edges of the
graph as in BF – version 1. Hence NN-BF is similar to BF – version 2 that
operates on the nodes. The outer loop, as in BF – version 1, runs in
$\mathcal{O}(N)$ where $N$ is the number of neurons and corresponds to the
number of vertices $|V|$. The second loop iterates through all neurons and the
third loop iterates through all inputs of the respective neuron and runs in
$\mathcal{O}(N)$ and $\mathcal{O}(I_{j})$, respectively. Here $I_{j}$
corresponds to the number of inputs of a particular neuron $j$. Given the fact
that $N=|V|$ and $\sum_{j}{I_{j}}=|E|$ ($j=1\dots N$), we can show that the
worst and the best algorithmic complexity of the NN-BF algorithm is the same
as for BF – version 2, i.e., $\mathcal{O}(|V|\,|E|)$ and $\mathcal{O}(|E|)$,
respectively. Hence, this is the same complexity as for BF-version 1, too.

####  IV-A3 Convergence analysis

Figure 5: Results of convergence analysis. Maximal number of iterations until
convergence of Bellman-Ford – version 1 (BF) or NN-BF vs. number of edges
$|E|$. 500 randomly generated graphs with 5,000 nodes were analysed for each
case.

The worst case scenario would be to run the algorithms for $|V|-1$ iterations
where $|V|$ is the number of graph nodes. However, in practice this will be
not needed and significantly fewer iterations will usually suffice. Thus, we
tested how many iterations are needed until cost convergence of the Bellman-
Ford algorithm (version 1) as compared to activation convergence of the neural
network. In both cases we stopped the respective algorithm, as soon as its
node costs or neuron activations were not changing anymore.

For this analysis, we used 500 randomly generated graphs with 5,000 nodes with
positive costs ($p_{n}=0$) from the range $[1,10]$ and connectivity densities
corresponding to approximately $12.5\times 10^{3}$, $25\times 10^{3}$,
$250\times 10^{3}$, $2.5\times 10^{6}$, $12.5\times 10^{6}$, and to
$24.995\times 10^{6}$ edges.

The results are shown in Fig. 5 where we show the maximal number of iterations
obtained from 500 tested graphs until convergence. One can see that in case of
sparse graphs 16 for BF and 15 for NN-BF iterations suffice for convergence
and for denser graphs ($>10\%$ connectivity) only 3 iterations are needed. The
resulting run-time per one iteration on a sparse graph with 5,000 nodes and
12,500 edges is 21$\mu s$ and 59$\mu s$ for BF (version 1) and NN-BF,
respectively. Run-time on a fully connected graph with 24,995,000 edges is
26$ms$ and 14$ms$ for BF and NN-BF, respectively333C++ CPU implementation on
Intel Core i9-9900 CPU, 3.10GHz, 32.0GB RAM.. Thus, relatively large graphs
can be processed in less than $100~{}ms$.

###  IV-B Network learning and path planning

Note that the advantage of NN-BF is that it operates multiplicatively on
activations. Hence, learning and path finding can rely on the same numerical
representation. To achieve the same with BF (or any other additively operating
algorithm) one would have to transform costs (for path finding) to activations
(for network learning) back and forth. In the following we will show two
examples of network learning combined with path finding, which shall serve as
a proof of concept.

####  IV-B1 Navigation learning

Figure 6: Results of navigation learning: (a) static environment and (b)
dynamic environment. Blue dots correspond to locations represented by neurons,
and black lines correspond to connections between neurons (paths between
locations) where line thickness is proportional to the synaptic weight
strength. Grey blocks denote obstacles. Green and red dots correspond to the
start- and the end-point of the path marked by the red trajectory.

Results for navigation learning in a static environment are shown in Fig.
6(a), where we show the development of the network’s connectivity (black
lines; line thickness is proportional to the weight strength) and the planned
path (red trajectory) based on the network’s connectivity during the learning
process. After 100 learning iterations, the environment was only partially
explored. Therefore, the full path could not yet be planned. After 200
iterations, only a sub-optimal path was found, since the environment was still
not completely explored. As exploration and learning process proceeds,
connections between different locations get stronger (note thicker lines in
the second row), and eventually the planned path converges to the shortest
path (after 400 iterations).

In Fig. 6(b), we show results for navigation in a dynamic environment. Here,
we first run the learning process until the path has converged (see the top
row), and then remove the obstacle after 300 learning iterations. As expected,
after obstacle removal, the middle part of the environment is explored and new
connections between neurons are built. Eventually, as the learning proceeds,
the output of the planning network converges to the shortest path (after 1200
iterations).

Due to the learning rule used, in both cases, systems converge to the shortest
euclidean distance paths.

Figure 7: Results of sequence learning: (a) learning of sequence
$A\,B\,C\,D\,E\,F$, and (b) learning of sequence $A\,C\,D\,F$. Blue dots
correspond to letters represented by neurons, and black lines correspond to
connections between neurons where line thickness is proportional to the
synaptic weight strength. Green and red dots correspond to the start- and end-
point of the sequence marked by the red trajectory.

####  IV-B2 Sequence learning

Results for learning of the full sequence $A\,B\,C\,D\,E\,F$ and of the
partial sequence $A\,C\,D\,F$ are presented in Fig. 6(a) and Fig. 6(b),
respectively. As in the navigation learning example, we show the development
of the network’s connectivity during the learning process. In case (a), we can
see that before learning (epoch 0), due to random weight initialisation, the
generated sequence is $A\,B\,F$ which is neither correct nor complete.
However, after the first learning epoch we can see that the connection weight
between neurons $A$ and $B$ was increased (note thicker line between $A$ and
$B$ as compared to epoch 0), whereas the connection weight between neurons $B$
and $F$ was decreased, which then led to a different sequence $A\,B\,D\,F$.
After epoch 3, the connection weight between neurons $E$ and $F$ was increased
since in previously generated sequence $A\,E\,F$ (epoch 2) the transition from
$E$ to $F$ was correct. Finally, after learning epoch 7 the network generates
the correct sequence.

Similarly, in case of learning of the partial sequence $A\,C\,D\,F$ (see Fig.
6(b)), learning converges to the correct sequence already after epoch 5, since
the sequence is shorter.

##  V Conclusion

Finding the optimal path in a connected graph is a classical problem and, as
discussed in the section on state of the art, many different algorithms exist
to address this. Here we proposed a neural implementation of the Bellman-Ford
algorithm. The main reason, as we would think, for translating Bellman-Ford
into a network algorithm is the now-arising possibility to directly use
network learning algorithm on a path finding problem. To do this with BF or
other cost-based algorithm, you would have to switch back and forth between a
cost- and a weight-based representation of the problem. This is not needed for
NN-BF. Given that BF and NN-BF have the same algorithmic complexity,
computational speed of the path-finding step is similar, too, where learning
epochs can be built into NN-BF as needed. The examples shown above rely on a
local learning rule that alters the weights only between directly connected
nodes. Globally acting rules could, however, also be used to address different
problems, too, and – as far as we see – there are no restrictions with respect
to possible network learning mechanisms, because BF-NN is a straight-forward
architecture for activity propagation without any special limitations.

Hence, network algorithm with NN-BF allows for new and different applications
where learned path-augmentation is directly coupled with path finding in a
natural way.

## References

  * [1] R. Bellman, “On a routing problem,” _Quarterly of applied mathematics_ , vol. 16, no. 1, pp. 87–90, 1958.
  * [2] L. R. Ford, “Network flow theory,” Rand Corp Santa Monica Ca, Tech. Rep., 1956\.
  * [3] J. S. Baras and G. Theodorakopoulos, “Path problems in networks,” _Synthesis Lectures on Communication Networks_ , vol. 3, no. 1, pp. 1–77, 2010.
  * [4] D. O. Hebb, _The organization of behavior_. New York: Wiley & Sons, 2005.
  * [5] L. Kuśmierz, T. Isomura, and T. Toyoizumi, “Learning with three factors: modulating hebbian plasticity with errors,” _Current opinion in neurobiology_ , vol. 46, pp. 170–177, 2017.
  * [6] B. Porr and F. Wörgötter, “Learning with “relevance”: using a third factor to stabilize hebbian learning,” _Neural computation_ , vol. 19, no. 10, pp. 2694–2719, 2007.
  * [7] E. F. Moore, “The shortest path through a maze,” in _International Symposium on the Theory of Switching_ , 1959, pp. 285–292.
  * [8] D. Merrill, M. Garland, and A. Grimshaw, “Scalable GPU graph traversal,” _Acm Sigplan Notices_ , vol. 47, no. 8, pp. 117–128, 2012.
  * [9] E. W. Dijkstra, “A note on two problems in connexion with graphs,” _Numerische Mathematik_ , vol. 1, no. 1, pp. 269–271, 1959.
  * [10] P. E. Hart, N. J. Nilsson, and B. Raphael, “A formal basis for the heuristic determination of minimum cost paths,” _IEEE Trans. Systems Science and Cybernetics_ , vol. 4, no. 2, pp. 100–107, 1968.
  * [11] R. E. Korf, “Depth-first iterative-deepening: An optimal admissible tree search,” _Artificial Intelligence_ , vol. 27, no. 1, pp. 97–109, 1985.
  * [12] S. Koenig, M. Likhachev, and D. Furcy, “Lifelong planning A*,” _Artificial Intelligence_ , vol. 155, no. 1-2, pp. 93–146, 2004.
  * [13] X. Sun, S. Koenig, and W. Yeoh, “Generalized adaptive A*,” in _Proc. of the 7th Int. J. Conf. on Autonomous Agents and Multiagent Systems - Volume 1_ , ser. AAMAS ’08, 2008, pp. 469–476.
  * [14] D. D. Harabor and A. Grastien, “Online graph pruning for path finding on grid maps.” in _AAAI_ , 2011, pp. 1114–1119.
  * [15] R. W. Floyd, “Algorithm 97: shortest path,” _Communications of the ACM_ , vol. 5, no. 6, p. 345, 1962.
  * [16] S. Warshall, “A theorem on Boolean matrices,” _Journal of the ACM (JACM)_ , vol. 9, no. 1, pp. 11–12, 1962.
  * [17] D. B. Johnson, “Efficient algorithms for shortest paths in sparse networks,” _Journal of the ACM (JACM)_ , vol. 24, no. 1, pp. 1–13, 1977.
  * [18] M. K. M. Ali and F. Kamoun, “Neural networks for shortest path computation and routing in computer networks,” _IEEE Transactions on Neural Networks_ , vol. 4, no. 6, pp. 941–954, 1993.
  * [19] D.-C. Park and S.-E. Choi, “A neural network based multi-destination routing algorithm for communication network,” in _1998 IEEE International Joint Conference on Neural Networks_ , vol. 2, 1998, pp. 1673–1678.
  * [20] F. Araujo, B. Ribeiro, and L. Rodrigues, “A neural network for shortest path computation,” _IEEE Transactions on Neural Networks_ , vol. 12, no. 5, pp. 1067–1073, 2001.
  * [21] J. Häkkinen, M. Lagerholm, C. Peterson, and B. Söderberg, “A Potts neuron approach to communication routing,” _Neural Computation_ , vol. 10, no. 6, pp. 1587–1599, 1998.
  * [22] R. Glasius, A. Komoda, and S. Gielen, “Neural network dynamics for path planning and obstacle avoidance,” _Neural Networks_ , vol. 8, no. 1, pp. 125–133, 1995.
  * [23] ——, “A biologically inspired neural net for trajectory formation and obstacle avoidance,” _Biological Cybernetics_ , vol. 74, no. 6, pp. 511–520, 1996.
  * [24] N. Bin, C. Xiong, Z. Liming, and X. Wendong, “Recurrent neural network for robot path planning,” in _Int. Conf. on Parallel and Distributed Computing: Applications and Technologies_ , 2004, pp. 188–191.
  * [25] S. X. Yang and M. Meng, “Neural network approaches to dynamic collision-free trajectory generation,” _IEEE Trans. on Systems, Man, and Cybernetics, Part B (Cybernetics)_ , vol. 31, no. 3, pp. 302–318, 2001.
  * [26] H. Qu, S. X. Yang, A. R. Willms, and Z. Yi, “Real-time robot path planning based on a modified pulse-coupled neural network model,” _IEEE Transactions on Neural Networks_ , vol. 20, no. 11, pp. 1724–1739, 2009.
  * [27] J. Ni, L. Wu, P. Shi, and S. X. Yang, “A dynamic bioinspired neural network based real-time path planning method for autonomous underwater vehicles,” _Computational intelligence and neuroscience_ , vol. 2017, 2017.
  * [28] T. Kulvicius, S. Herzog, M. Tamosiunaite, and F. Wörgötter, “Finding optimal paths using networks without learning–unifying classical approaches,” _IEEE Transactions on Neural Networks and Learning Systems_ , pp. 1–11, 2021.
  * [29] A. H. Qureshi, M. J. Bency, and M. C. Yip, “Motion planning networks,” _CoRR_ , vol. abs/1806.05767, 2018.
  * [30] N. Pérez-Higueras, F. Caballero, and L. Merino, “Learning human-aware path planning with fully convolutional networks,” in _2018 IEEE Int. Conf. on Robotics and Automation (ICRA)_ , 2018, pp. 1–6.
  * [31] Y. Ariki and T. Narihira, “Fully convolutional search heuristic learning for rapid path planners,” _arXiv:1908.03343_ , 2019.
  * [32] T. Kulvicius, S. Herzog, T. Lüddecke, M. Tamosiunaite, and F. Wörgötter, “One-shot multi-path planning using fully convolutional networks in a comparison to other algorithms,” _Frontiers in Neurorobotics_ , vol. 14, p. 115, 2021.
  * [33] M. J. Bency, A. H. Qureshi, and M. C. Yip, “Neural path planning: Fixed time, near-optimal path generation via oracle imitation,” _CoRR_ , vol. abs/1904.11102, 2019.
  * [34] L. Tai, G. Paolo, and M. Liu, “Virtual-to-real deep reinforcement learning: Continuous control of mobile robots for mapless navigation,” in _2017 IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS)_ , 2017, pp. 31–36.
  * [35] A. I. Panov, K. S. Yakovlev, and R. Suvorov, “Grid path planning with deep reinforcement learning: Preliminary results,” _Procedia computer science_ , vol. 123, pp. 347–353, 2018.
  * [36] A. Banino, C. Barry, B. Uria, C. Blundell, T. Lillicrap, P. Mirowski, A. Pritzel, M. J. Chadwick, T. Degris, J. Modayil _et al._ , “Vector-based navigation using grid-like representations in artificial agents,” _Nature_ , vol. 557, no. 7705, pp. 429–433, 2018.
  * [37] M. Schlichtkrull, T. N. Kipf, P. Bloem, R. Van Den Berg, I. Titov, and M. Welling, “Modeling relational data with graph convolutional networks,” in _European semantic web conference_ , 2018, pp. 593–607.
  * [38] M. Zhang and Y. Chen, “Link prediction based on graph neural networks,” _Advances in Neural Information Processing Systems_ , vol. 31, pp. 5165–5175, 2018.
  * [39] P. Velickovic, R. Ying, M. Padovano, R. Hadsell, and C. Blundell, “Neural execution of graph algorithms,” in _International Conference on Learning Representations_ , 2020, pp. 1–14.
  * [40] K. Teru, E. Denis, and W. Hamilton, “Inductive relation prediction by subgraph reasoning,” in _International Conference on Machine Learning_ , 2020, pp. 9448–9457.
  * [41] Z. Zhu, Z. Zhang, L.-P. Xhonneux, and J. Tang, “Neural bellman-ford networks: A general graph neural network framework for link prediction,” in _Neural Information Processing Systems_ , 2021, pp. 1–15.
  * [42] Y. Yang, T. Liu, Y. Wang, J. Zhou, Q. Gan, Z. Wei, Z. Zhang, Z. Huang, and D. Wipf, “Graph neural networks inspired by classical iterative algorithms,” in _International Conference on Machine Learning_ , 2021, pp. 1–11.
  * [43] B. Porr and F. Wörgötter, “Isotropic sequence order learning,” _Neural Computation_ , vol. 15, no. 4, pp. 831–864, 2003.