  Numerous tasks in program analysis and synthesis reduce to deciding
reachability in possibly infinite graphs such as those induced by Petri nets.
However, the Petri net reachability problem has recently been shown to require
non-elementary time, which raises questions about the practical applicability
of Petri nets as target models. In this paper, we introduce a novel approach
for efficiently semi-deciding the reachability problem for Petri nets in
practice. Our key insight is that computationally lightweight
over-approximations of Petri nets can be used as distance oracles in classical
graph exploration algorithms such as A* and greedy best-first search. We
provide and evaluate a prototype implementation of our approach that
outperforms existing state-of-the-art tools, sometimes by orders of magnitude,
and which is also competitive with domain-specific tools on benchmarks coming
from program synthesis and concurrent program analysis.
