Iirc, the best approaches for this nowadays are machine learning based. Otherwise, you probably want to do an exploration step first, and bake in the environment.
GOFAI techniques are:
A) Usually unable to incorporate posteri knowledge of the environments they're working on.
And
B) Often entirely infeasible to adapt to take exploration costs into account.
I've heard of some GOFAI techniques for optimal unbiased pathfinding in unknown environments using optimal transport theory and the like. But unbiased methods are obviously going to lose out in real environments.