79233478

Date: 2024-11-28 10:37:33
Score: 1
Natty:
Report link

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]]
Reasons:
  • Blacklisted phrase (1): Is there a way
  • Long answer (-1):
  • Has code block (-0.5):
  • Starts with a question (0.5): Is there a
  • Low reputation (1):
Posted by: w9_