Dynamic pathfinding algorithms

Hi everybody,

I'm new here, and also quite new to most AI concepts. I need some help finding a good pathfinding algorithm. I've worked with A*, but it doesn't quite fit my needs, eventhough it is easy to understand and to implement. My problem is, what if my unit (e.g. a robot) is in an unknown territory, or a place of which he doesn't have a map, but can approximate where his goal is (direction and distance of the goal for example). The first approach would be to just move in that direction. But eventually the unit will encounter an obstacle with it's sensors. One that was not on the map and that is blocking the original path. It would seem inefficient to me to mark it on it's map (for example a grid map) and then run A* AGAIN. Imagine having to do this for every obstacle you encounter. I've heard of a D* algorithm but I'm not quite sure how it works. There is little documentation on this on the internet that is of use to me. I have the official paper, written by the man who worked out that solution, but I don't understand much of it, seeing as I have problems with my english when it comes to anything that has to do with maths etc. Anything that is out of the ordinary part of the english language that I learned in school (I'm German). I'm sure some of you have heard of this algorithm, and I would like to know if you guys could give me some basic tips on how it works, or perhaps, you have a better solution for my problem? Right now I'm just writing a simulator for this scenario, not building an actual robot.

Cheers,
Brick