Not a solution but a starting point: http://en.wikipedia.org/wiki/D*

I used this for a similar problem in my computer science studies. We had a map with an unknown layout of fields, each with a different travel cost and had to drive a tour of multiple flags in the fastest way possible. It worked quite well.