Não vi o vídeo (tô sem flash no Linux, preguiça), mas acho bastante plausível mesmo sem controle remoto
A solução do cubo de Rubik já é bastante conhecida... trata-se, então, de o robô reconhecer o estágio inicial do cubo, aplicar as transformações, e reconhecer quando o cubo está terminado. E talvez, possa fazer isso rápido. As transformações são bastante padrão, são só cinco ou seis, se não me engano.