General Problem Solver

General Problem Solver (GPS) – wczesny program sztucznej inteligencji opracowany w połowie lat 50. Allena Newella i Herberta A. Simona. GPS miał na celu stworzenie uniwersalnego systemu rozwiązującego dowolny problem logiczny lub kombinatoryczny przy użyciu metod symulujących procesy myślenia człowieka.

Historia

Projekt rozpoczął się w 1955 roku w Instytucie Badawczym RAND Corporation. Pierwsza wersja została przedstawiona na konferencji AAAI w 1957 roku. Program został opracowany w języku LISP i testowany na maszynie IBM 704.

Architektura i zasada działania

GPS opiera się na trzech podstawowych elementach:

Reprezentacja problemu – opisowana przy pomocy logiki pierwszego rzędu i reguł transformacji.
Operatorzy – zestaw operacji (np. „przesuń”, „dodaj”) które mogą zmieniać stan problemu.
Strategia przeszukiwania – algorytm przeglądania w głąb i przeglądania wszerz, zwany „means‑ends analysis”, czyli analiza różnicy pomiędzy aktualnym a docelowym stanem.

System najpierw definiuje cele końcowe, potem generuje pośrednie podcele, a wreszcie aplikując operatorów stara się je osiągnąć, minimalizując różnicę pomiędzy stanem aktualnym a stanem docelowym.

Znaczenie i wpływ

GPS uznawany jest za kamień milowy w rozwoju sztucznej inteligencji oraz psychologii poznawczej. Wpłynął na powstanie kolejnych systemów, m.in. SOAR i ACT‑R. Jego koncepcje po raz pierwszy wprowadziły pojęcie heurystyki w rozwiązywaniu problemów.

Krytyka

Mimo innowacyjności GPS spotkał się z licznymi krytykami:

Ograniczona skalowalność – program radził sobie jedynie z małymi, sztucznie sprowadzonymi zadaniami.
Brak efektywności w porównaniu do specjalistycznych algorytmów, np. metod wyszukiwania w grafach.
Trudności w definiowaniu przestrzeni stanów dla problemów otwartych.

Dziedzictwo

Po zakończeniu prac nad GPS nowi badacze z MIT oraz Carnegie Mellon University rozwinęli jego idee, wprowadzając reprezentację wiedzy i bardziej zaawansowane techniki przeszukiwania. Współczesne systemy planowania, takie jak PDDL czy HTN Planning, wywodzą się wprost z koncepcji opracowanych w GPS.