If you want AI that behaves in the way that a human might when exploring a completely new and unknown area, needing no prior knowledge of the map except for the coordinates of start and goal, then use D* Lite. This algorithm is both conceptually simpler and more efficient than the original D*, effectively obsoleting D*. It's been used in some of the Mars rovers. It eliminates the typical "omniscient" behaviour of AIs that move based on a single pre-emptive A* run on a known map.
D* Lite works on an ad hoc basis. It begins by calculating a fairly direct path between the designated goal and start points, working backward from goal to start, not yet knowing the occupancy status of those nodes along the path. It then begins to walk this path, like a pioneer.
This continues until it hits an obstacle on a node which it previously expected to walk through on its way to the goal. As a result of this mishap, it recalculates the remaining path (again backwards from goal to present position) based on the now known obstacle(s) and tries to continue stepping. Each time it find a new obstacle, it will recalculate as best it can based on local knowledge. If it follows a path to a dead-end, then, just like a human being, it will backtrack and seek new routes to the goal.
P.S. Just like A*, you can also accelerate D* Lite with Jump Point Search, also mentioned here.