Solucionador de problemas gerais - General Problem Solver
General Problem Solver ( GPS ) é um programa de computador criado em 1959 por Herbert A. Simon , JC Shaw e Allen Newell ( RAND Corporation ) com o objetivo de funcionar como uma máquina universal de resolução de problemas . Em contraste com o antigo projeto do Logic Theorist , o GPS trabalha com análise de meios-fins .
Visão geral
Qualquer problema que pode ser expresso como um conjunto de fórmulas bem formadas (WFFs) ou cláusulas de Horn , e que constituem um gráfico direcionado com uma ou mais fontes (ou seja, axiomas) e sumidouros (ou seja, conclusões desejadas), pode ser resolvido, em princípio, por GPS. Provas na lógica de predicados e espaços de problemas de geometria euclidiana são exemplos primordiais do domínio da aplicabilidade do GPS. Foi baseado no trabalho teórico de Simon e Newell sobre máquinas lógicas . GPS foi o primeiro programa de computador que separou seu conhecimento de problemas (regras representadas como dados de entrada) de sua estratégia de como resolver problemas (um mecanismo solver genérico ). O GPS foi implementado na linguagem de programação de terceira ordem, IPL .
Embora o GPS resolvesse problemas simples, como as Torres de Hanói, que podiam ser suficientemente formalizados, ele não conseguia resolver nenhum problema do mundo real porque a busca era facilmente perdida na explosão combinatória . Dito de outra forma, o número de "caminhadas" pelo dígrafo inferencial tornou-se computacionalmente insustentável. (Na prática, mesmo uma busca direta no espaço de estado , como as Torres de Hanoi, pode se tornar computacionalmente inviável, embora podas judiciosas do espaço de estado possam ser alcançadas por técnicas elementares de IA como A * e IDA * ).
O usuário definiu objetos e operações que poderiam ser feitas nos objetos, e o GPS gerou heurísticas por meio de análises meios-fins para resolver problemas. Ele se concentrou nas operações disponíveis, encontrando quais entradas eram aceitáveis e quais saídas foram geradas. Em seguida, criou submetas para se aproximar cada vez mais da meta.
O paradigma GPS eventualmente evoluiu para a arquitetura Soar para inteligência artificial .
Veja também
Referências
- Newell, A .; Shaw, JC; Simon, HA (1959). Relatório sobre um programa geral de resolução de problemas. Proceedings of the International Conference on Information Processing. pp. 256–264.
- Newell, A. (1963). Um guia para o programa geral de solução de problemas GPS-2-2 . RAND Corporation , Santa Monica, Califórnia. Relatório Técnico nº RM-3337-PR.
- Ernst, GW e Newell, A. (1969). GPS: um estudo de caso em geral e resolução de problemas. Academic Press. (Versão revisada da dissertação de Ernst de 1966, Carnegie Institute of Technology .)
- Newell, A. e Simon, HA (1972) Human problem solving Englewood Cliffs, NJ: Prentice-Hall
- Noyes, James L. (1992). Inteligência Artificial com Common Lisp . Lexington : DC Heath. pp. 343–371. ISBN 978-0-669-19473-9 .