Is there a way to convert graph to grid
No, you can't convert any graph to a grid. Simply because graph’s node can have an unlimited number of connections, whereas a grid's node typically has only 4 connections (or 8 if diagonal movements are allowed)
Can we use CBS on graph
Yes, CBS can be used on a graph. In fact, the original paper provides an algorithm that works with a graph.
If you need an example with a graph, there is a Python library that implements CBS and works with both graphs and grids. For example, we can reproduce the graph from the paper — the one with mice and cheese:
from w9_pathfinding import Graph, CBS
S1, S2, A1, A2, A3, B1, B2, B3, C, G1, G2 = range(11)
graph = Graph(
num_vertices=11,
edges=[
(S1, A1), (S1, A2), (S1, A3),
(S2, B1), (S2, B2), (S2, B3),
(A1, C), (A2, C), (A3, C),
(B1, C), (B2, C), (B3, C),
(C, G1), (C, G2),
]
)
starts = (S1, S2)
gaols = (G1, G2)
paths = CBS(graph).mapf(starts, gaols)
print(paths) # [[S1, A3, C, G1], [S2, B3, B3, C, G2]]