How do I solve a search problem on an infinite graph? I have a search problem that requires me to find a path from $v_s$ to $v_g$ in the graph $G = (V, E)$ where $v_s, v_g \in V$ are the start and goal vertices in a set of vertices and $E \subset V \times V$ is an undirected set of edges connecting vertices. Both $V$ and $E$ can be infinite. Each edge has an associated cost $c: E \rightarrow \mathbb{R}$ and the cost of a path (an ordered set of edges) between adjacent vertices that leads from the start to the goal is the sum of the cost of all of its edges. My goal is to find the path with minimal cost (assume it exists).
From my understanding, because this graph could possibly have an infinite branching factor, A* is not guaranteed to return a solution (or terminate). Are there any viable alternative algorithms that are designed for handling graphs with large or infinite state and action spaces? I'm not looking for guaranteed termination or optimality, just some names of algorithms that might be used in these sorts of problems as my search for &quot;heuristic search infinite state space&quot; doesn't turn much up.
I believe you can use any algorithm for heuristic search.  On infinite graphs, no algorithm is guaranteed to terminate, so I don't see a clear basis to reject A* or other standard algorithms for heuristic search.