[reitzensteinm]

But humans do quite intelligently pathfind around objects they're aware of, and update their mental models with new information. The front door is locked? I'll go around the back.

You can achieve exactly what you're describing by hiding information entities do not have from their pathfinding.

Graphs aren't the problem, and thinking along those lines won't get you where you're trying to go.