When to terminate search for path in an infinite grid

Question

I'm learning shortest path algorithms like Dijkstra's, BFS, etc. I understand on a 2D finite grid there are boundary conditions (i.e. size of the grid) that help terminate the algorithm and keep it in a certain scope/range. However when expanding this to an infinite 2D grid, I don't understand when (say using BFS as an example) to conclude that a path simple doesn't exist without having the algorithm run infinitely since I can't use grid size as a boundary condition. Is there some kind of formula that can be used in these cases? Also, take into account that there could be obstacles along the path too so the path distance can vary from different origins to destinations.

I've considered trying to take the absolute value of the difference between the coordinate points and raising it to some power as a way of setting an upper limit of steps taken before considering that a path must not exist, but this approach is obviously lacking and incorrect to say it bluntly since it doesn't work for many cases.

I apologize if my question is confusing. I'll restate it here: basically, how do I know when to assume a path from an origin to a destination doesn't exist in an infinite 2D grid?

Answer 1

Unfortunately, the simple answer is, you can't.

All the standard search algorithms have a runtime that's polynomial in the size of the graph. If your graph is infinitely large, there's no guarantee that they'll ever terminate for arbitrary inputs: how can they ever know whether they should give up now, or whether they'd find the answer if they just expanded one more node?

Any approach that involves putting an upper limit on the number of steps, is doomed to failure. Even if the start and end points are right next to each other in the coordinate system, I could delete the edge between them, then make it so that the shortest path from one to the other takes one more step than you're allowing. And then your algorithm will say, incorrectly, that there's no solution.

However, if you have additional information about your graph (perhaps there's only a finite number of edges missing from the grid?), then you can potentially exploit this to find an answer. It's only impossible for arbitrary infinite graphs; there are many classes of infinite graphs for which it can be solved.