# 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 "heuristic search infinite state space" doesn't turn much up.

• Can the values really by arbitrary values in $\mathbb{R}$? Or did you mean $\mathbb{R^+}$? Commented May 4, 2021 at 21:37
• Technically they are positive but I'm trying a formulation where each edge has a cost (positive) and a resulting reward in the neighboring vertex (negative), so the sum of the cost and reward can be any real. Commented May 5, 2021 at 19:28