Optimal algorithm to find exit of a maze with no information
<p>I have to determine a way for a robot to get out of a maze. The thing is that the layout of the maze is unknown, and the position of the exit is unknown too. The robot also start at an unknown position in the maze.
I found 3 solutions but I have a hard time knowing which one should I use, because in the end it seems that the solutions will purely be random anyway. 
I have those 3 solutions :<br>
1) The basic "human" strategy(?), where you put your hand on a wall and go through all the maze if necessary. I also keep a variable "turn counter" to avoid situation where the robot loop.<br>
2) Depth first search<br>
3) Making the robot choose direction randomly  </p>

<p>The random one seems the worse, because he could take forever to find the exit (but on the other hand he could be the fastest too...). I'm not sure about the other two though.<br>
Also, is there a way to have some kind of heuristic? Again the lack of information makes me think that it's impossible, but maybe I'm missing something.  </p>

<p>Last thing : When the robot find the exit, he will have to go back to his start position using A*. This means that during the first part, where he looks for the exit, he will have draw a map of the maze that he will use for the 2nd part. Maybe this can help too chose the best algorithm for the first part, but yeah I don't see why one would be better.</p>

<p>Could someone help me please? Thanks (Also, sorry for my english).</p>