Risolutore di problemi generali - General Problem Solver

Generale Problem Solver ( GPS ) è un programma per computer creato nel 1959 da Herbert A. Simon , JC Shaw , e Allen Newell ( RAND Corporation ) destinati al lavoro come un problema universale risolutore macchina. In contrasto con il precedente progetto Logic Theorist , il GPS funziona con l' analisi dei mezzi-fini .

Panoramica

Qualsiasi problema che può essere espresso come un insieme di formule ben formate (WFF) o clausole di Horn , e che costituiscono un grafo diretto con una o più sorgenti (cioè assiomi) e pozzi (cioè conclusioni desiderate), può essere risolto, in linea di principio, dal GPS. Le prove nella logica dei predicati e negli spazi problematici della geometria euclidea sono i primi esempi del dominio dell'applicabilità del GPS. Era basato sul lavoro teorico di Simon e Newell sulle macchine logiche . Il GPS è stato il primo programma per computer che ha separato la sua conoscenza dei problemi (regole rappresentate come dati di input) dalla sua strategia su come risolvere i problemi (un motore di risoluzione generico ). Il GPS è stato implementato nel linguaggio di programmazione del terzo ordine, IPL .

Mentre il GPS risolveva problemi semplici come le Torri di Hanoi che potevano essere sufficientemente formalizzate, non poteva risolvere alcun problema del mondo reale perché la ricerca si perdeva facilmente nell'esplosione combinatoria . In altre parole, il numero di "passeggiate" attraverso il digrafo inferenziale è diventato computazionalmente insostenibile. (In pratica, anche una semplice ricerca nello spazio degli stati come le Torri di Hanoi può diventare computazionalmente impraticabile, anche se potature giudiziose dello spazio degli stati possono essere ottenute con tecniche di IA elementari come A * e IDA * ).

L'utente oggetti e operazioni che potrebbero essere fatte sugli oggetti definiti, e GPS generato euristica di analisi mezzi-fini per risolvere i problemi. Si è concentrato sulle operazioni disponibili, trovando quali input erano accettabili e quali output sono stati generati. Ha quindi creato obiettivi secondari per avvicinarsi sempre di più all'obiettivo.

Il paradigma GPS alla fine si è evoluto nell'architettura Soar per l'intelligenza artificiale .

Guarda anche

• Teorico della logica

Riferimenti

• Newell, A .; Shaw, JC; Simon, HA (1959). Relazione su un programma generale di risoluzione dei problemi. Atti della Conferenza internazionale sull'elaborazione delle informazioni. pagg. 256–264.
• Newell, A. (1963). Una guida al programma per la risoluzione dei problemi generali GPS-2-2 . RAND Corporation , Santa Monica, California. Rapporto tecnico n. RM-3337-PR.
• Ernst, GW e Newell, A. (1969). GPS: un caso di studio in generale e risoluzione dei problemi. Stampa accademica. (Versione rivista della dissertazione di Ernst del 1966, Carnegie Institute of Technology .)
• Newell, A., and Simon, HA (1972) Human problem solving Englewood Cliffs, NJ: Prentice-Hall
• Noyes, James L. (1992). Intelligenza artificiale con Common Lisp . Lexington : DC Heath. pp. 343–371. ISBN   978-0-669-19473-9 .