Hierarchical Neural Path Search

Omar A. A. Al Tamimi

Why?

Current methods suffer from the following:

​

• High computational cost for large graphs

​

• Iterative, non-parallelizable algorithms are most used

​

• Current SOTA does not utilize encoded minimal representations of the graph for multiple queries

​

Why?

Current methods suffer from the following:

​

• High computational cost for large graphs

​

• Iterative, non-parallelizable algorithms are most used

​

• Current SOTA does not utilize encoded minimal representations of the graph for multiple queries

​

Tiled Motion Planning Dataset

Tiled Motion Planning Dataset is widely used as a benchmarking dataset for motion and path planning

​

​

The dataset is comprised of 4,000 Images of 64x64 size, however, we can tile the dataset to reach bigger and more complex maps and problems.

​

Neural Path Planning

Path Planning using Neural A* Search�Kanezaki et al. (2021)

TransPath: Learning Heuristics For Grid-Based Pathfinding via Transformers�Krililenko et al. (AAAI 2023)

Hierarchical Neural Path Search

Cluster Assignment & Aggregation

Inter-Cluster Pathfinding

Intra-Cluster Pathfinding

Map Problem

Cluster Assignment

Pathfinding map / graph

Communities

Louvain Method

Cluster Assignment

Node Features

Vision Transformer Model

Map + Community Indicators

(W, H, 5)

Feature Maps

(W, H, C)

Node Features

Community Aggregation

(W, H)

Feature Maps

(W, H, C)

Can be cached

Inter-Cluster Pathfinding

Problem Statement

Inter-Cluster Pathfinding

Graph Neural Network

Target Engineering

Target Engineering

We can see that the optimality measure is highest on the possible optimal paths.

Target Engineering

Target Engineering

Target Engineering

Inter-Cluster Pathfinding

Graph Neural Network

​

• Personally written using TensorFlow

​

• Dense computation for speed during deployment

​

• Caching added to layers

​

• Masked Batch Normalization (Allowing multiple graphs at once)

​

• Graph compilation compatible

​

Loss Function:

​

Graph Convolution Block

​

​

Chebyshev Convolution

K = 5, C = 64

Batch Normalization

Mish activation

Dropout

​

​

x9

Inter-Cluster Pathfinding

Shortest Path Search

Path Nodes

Intra-Cluster Pathfinding

Intra-Cluster Pathfinding

Start (C1) -> C1 Exit

C2 Entry -> C2 Exit

C3 Entry -> Goal (C3)

Graph Neural Network + Shortest Path Search

Results

Hierarchical Neural Path Search

​

• TransPath requires 9.5ms for 64 batch on A100 Tesla
• Our solution requires 4.23ms for 64 batch on RTX 3080, and 4.3ms as well on Tesla T4

​

​

• TransPath requires the full image to be processed for each query
• Our solution requires only the cached graph

​

​

Results on TMP [64x64] with A*

Results on TMP [64x64] non-A*

Results on TMP [512x512]

Thank you

Omar Tamimi