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