Generell problemløser - General Problem Solver

General Problem Solver ( GPS ) er et dataprogram opprettet i 1959 av Herbert A. Simon , JC Shaw og Allen Newell ( RAND Corporation ) ment å fungere som en universal problemløsermaskin . I motsetning til det tidligere Logic Theorist- prosjektet, fungerer GPS med middel-slutt-analyse .

Oversikt

Ethvert problem som kan uttrykkes som et sett med velformede formler (WFFs) eller Horn-ledd , og som utgjør en rettet graf med en eller flere kilder (det vil si aksiomer) og synker (det vil si ønskede konklusjoner), kan være løst, i prinsippet, med GPS. Bevis i predikatlogikken og problemområdene i euklidisk geometri er eksempler på domenets anvendbarhet av GPS. Den var basert på Simon og Newells teoretiske arbeid med logiske maskiner. GPS var det første dataprogram som skilte sin kunnskap om problemer (regler representert som inngangsdata) fra sin strategi på hvordan man skal løse problemer (en generisk løser motor ). GPS ble implementert i tredje ordens programmeringsspråk, IPL .

Mens GPS løste enkle problemer som Towers of Hanoi som kunne formaliseres tilstrekkelig, kunne den ikke løse noen virkelige problemer fordi søk lett gikk tapt i den kombinatoriske eksplosjonen . Sagt på en annen måte, antall "vandringer" gjennom den inferensielle grafen ble beregningsmessig uholdbar. (I praksis kan til og med en enkel statlig romsøk som Towers of Hanoi bli beregningsmessig umulig, om enn skjønn beskjæring av statsrommet kan oppnås ved slike elementære AI-teknikker som A * og IDA * ).

Brukeren definerte objekter og operasjoner som kunne utføres på objektene, og GPS genererte heuristikk ved hjelp-en-analyse for å løse problemer. Den fokuserte på tilgjengelige operasjoner, å finne hvilke innganger som var akseptable og hvilke utganger som ble generert. Det skapte deretter delmål for å komme nærmere og nærmere målet.

GPS-paradigmet utviklet seg til slutt til Soar- arkitekturen for kunstig intelligens .

Se også

• Logikk teoretiker

Referanser

• Newell, A .; Shaw, JC; Simon, HA (1959). Rapporter om et generelt problemløsingsprogram. Fremgangsmåten fra den internasjonale konferansen om informasjonsbehandling. s. 256–264.
• Newell, A. (1963). En guide til det generelle problemløsingsprogrammet GPS-2-2 . RAND Corporation , Santa Monica, California. Teknisk rapport nr. RM-3337-PR.
• Ernst, GW og Newell, A. (1969). GPS: en casestudie innen generalitet og problemløsning. Akademisk presse. (Revidert versjon av Ernsts avhandling fra 1966, Carnegie Institute of Technology .)
• Newell, A. og Simon, HA (1972) Menneskelig problemløsning Englewood Cliffs, NJ: Prentice-Hall
• Noyes, James L. (1992). Kunstig intelligens med vanlig lisp . Lexington : DC Heath. s. 343–371. ISBN   978-0-669-19473-9 .