1965 veröffentlichte er mit „A machine-oriented logic based on the resolution principle“ wichtige Grundlagen zur automatisierbaren Resolution in der Logik. Auf ihn geht ein Algorithmus zur Unifikation von prädikatenlogischen Formeln zurück, der entscheidend beim Nachweis der Unerfüllbarkeit einer prädikatenlogischen Formel ist.
Seine Arbeiten sind maßgeblich in die Entwicklung der Logikprogrammiersprache Prolog eingeflossen. Von Stephen Muggleton, Donald Michie und Koichi Furukawa wurde Robinson deshalb in einem 1994 erschienenen Buch als der Begründer der modernen programmierbaren Logik bezeichnet.