Path Finding

This is the official implementation for the paper Biologically Inspired Neural Path Finding. We propose a GNN framework to find the optimal low cost path between a source node and a destination node on a weighted graph.

Installation

Requirements: python=3.9, cuda=11.3

conda create -n ENVNAME python=3.9
conda activate ENVNAME
pip install -r requirements.txt
# install pytorch_geometric
pip install torch-scatter==2.0.9 torch-sparse==0.6.13 torch-cluster==1.6.0 torch-spline-conv==1.2.1 torch-geometric==2.0.4 -f https://data.pyg.org/whl/torch-1.11.0+cu113.html

Note: Installation of pytorch_geometric is sensitive to the cuda version. For different cuda versions (e.g., cuda-10.2) please refer to pytorch-geometric Installation to manually install pytorch_geometric.

Demo

You can find a demo script for inference on an example graph with a pre-trained GNN model under the folder ./demo/path-finding.py

Data Generation

The following script creates a dataset of simulated graphs and ground truth paths split into train/val/test sets.

python simulation.py --output_dir dataset/samples --num_graphs 10000

Train

To train our gnn model, run the following code. It saves the experiment result in the output directory defined in the config.

python train.py --data_root dataset/samples --output_dir output/gnn_samples --num_workers 8

Evaluation

Use the command to evaluate a trained model. You need to specify the experiment directory where the model is stored.

python test.py --exp_dir output/gnn_samples

Citation

If you find our work helpful in your research, please consider citing us

@InProceedings{10.1007/978-3-031-15037-1_27,
    author="Li, Hang
    and Khan, Qadeer
    and Tresp, Volker
    and Cremers, Daniel",
    title="Biologically Inspired Neural Path Finding",
    booktitle="Brain Informatics",
    year="2022",
    publisher="Springer International Publishing",
    pages="329--342",
    isbn="978-3-031-15037-1"
}