Во-первых, есть самый простой алгоритм — правило правой (левой) руки. Все время касаясь одной рукой одной стенки, двигаться вперед. Это означает, на каждом повороте сворачивать в одну сторону. У этого алгоритма есть куча недостатков: он исследует только ту связную компоненту лабиринта, к которой прислонили робота перед началом выполнения — но зато просто и методично. Если есть несколько связных компонент, то их можно выделить (на этом форуме уже обсуждалось, как именно) и к каждой в произвольной точке приставить по роботу, чтобы он ее обошел. При этом плюсом алгоритма является и то, что никакой памяти (отметок на стенах и т.д.) не нужно.

Во-вторых, есть универсальный алгоритм — "правила Тремо", по идее, описанные здесь. Читать сказки, к сожалению, времени нет, да и книжка, откуда я это почерпнул, уже тоже давно не под рукой, но суть где-то такая:

• перед входом в каждый коридор ставить отметку у входа, и после выхода из коридора в перекресток тоже ставить отметку у выхода.
  
• на перекрестке выбирать путь так: если перед каким-либо входом меньше двух отметок — идти туда. Если у каждого входа уже по две отметки — значит, обошли все.

А другие алгоритмы я забыл или не знаю