Support for unstructured graphs about neural-astar HOT 2 CLOSED

Thank you @yonetaniryo for the quick reply, and for sharing the link to the DeepMind's paper.

It was an absolute blast to read, not only for potential applications in search-based planning, but also for tackling partially observable Markov decision processes in general.

I had something very similar in mind conceptually, albeit much simpler in implementation, trying to make use of graph convolution networks and some form of recurrent units to retain a graph embedding.

As a simple first iteration, I may just try to replace the convolutional encoder with a suitable graph counterpart and to force node expansion on adjacency matrices to use sparse convolution to save some memory.

I am closing this for now, but I will post back here if I happen to have some decent results.

from neural-astar.

Hi, thank you for your question!

Extending Neural A* to non-grid, general graphs is promising, and indeed technically possible. I am not currently planning to support it in this repository just because our team has other higher priority work. If someone can work on this that would be great and I'll be happy to help. Here are some thoughts:

• Replacing convolutional encoders to GCNs is relatively straightforward, just random sampling nodes from the valid space of environments and estimating a cost for each node.
• Extending differentiable A* to general graphs is possible as you recognized, but making it efficient for a large-scale training may be non-trivial. For now we are using 3x3 fixed convolution kernel to perform the node expansion (i.e., retrieving the neighboring nodes of selected nodes). This part will be replaced by the retrieval of neighboring nodes using adjacency matrices, which typically has the size of N^2 or Nxk (N is the number of nodes and k is the number of neighbors) for each map, which will be more memory-expensive. Enabling mini-batching will make this procedure further complex. Auto vectorizers such as torch.vmap would help, but I have never tried it in pytorch.
• I am not knowledgeable about heuristic functions for general graphs but recently I found one paper that is potentially relevant: https://www.deepmind.com/publications/learning-graph-search-heuristics.

from neural-astar.