제너럴 프라블럼 솔버

제너럴 프라블럼 솔버(General Problem Solver, GPS) 또는 일반 문제 풀이는 1957년에 허버트 A. 사이먼, J. C. 쇼 및 앨런 뉴얼(랜드 연구소)이 보편적인 문제 해결 기계로 작동하기 위해 만든 컴퓨터 프로그램이다. 이전 논리 이론가 프로젝트와 달리 GPS는 수단 목표 분석과 함께 작동한다.^[1]

개요

WFF(Well-Formed Formula) 또는 혼 절 세트로 표현될 수 있고 하나 이상의 소스(즉, 공리)와 싱크(sink, 즉, 원하는 결론)가 있는 유향 그래프를 구성하는 모든 문제는 원칙적으로 GPS를 통해 해결된다. 술어 논리와 유클리드 기하학 문제 공간의 증명은 GPS 적용 영역의 대표적인 예이다. 이는 논리 기계에 대한 사이먼과 뉴얼의 이론적 작업을 기반으로 했다. GPS는 문제에 대한 지식(입력 데이터로 표현되는 규칙)과 문제 해결 방법에 대한 전략(일반 해결 엔진)을 분리한 최초의 컴퓨터 프로그램이다. GPS는 3차 프로그래밍 언어인 IPL로 구현되었다.^[2]

GPS는 충분히 형식화될 수 있는 하노이의 탑과 같은 간단한 문제를 해결했지만, 조합 폭발로 인해 검색이 쉽게 손실되었기 때문에 실제 문제를 해결할 수 없었다. 다르게 말하면, 추론적 이중 그래프를 통한 "걷기" 횟수는 계산상 불가능해졌다. (실제로는 A* 및 IDA*와 같은 기본 AI 기술을 사용하여 상태 공간의 현명한 가지치기를 달성할 수 있지만 하노이 타워와 같은 간단한 상태 공간 검색도 계산적으로 실행 불가능해질 수 있다.)

사용자는 객체와 객체에 대해 수행할 수 있는 작업을 정의하고 GPS는 문제 해결을 위해 분석을 수단으로 휴리스틱을 생성했다. 사용 가능한 작업에 중점을 두고 어떤 입력이 수용 가능하고 어떤 출력이 생성되었는지 찾아냈다. 그런 다음 목표에 점점 더 가까워지기 위해 하위 목표를 만들었다.

GPS 패러다임은 결국 인공지능을 위한 소어(Soar) 아키텍처로 발전했다.

같이 보기

논리 이론가

각주

↑ Nils J. Nilsson (2009년 10월 30일). 《The Quest for Artificial Intelligence》. Cambridge University Press. 121–쪽. ISBN 978-1-139-64282-8.
↑ Norvig, Peter (1992). 《Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp》. San Francisco, California: Morgan Kaufmann. 109–149쪽. ISBN 978-1-55860-191-8.

출처

Newell, A.; Shaw, J.C.; Simon, H.A. (1959). Report on a general problem-solving program. Proceedings of the International Conference on Information Processing. pp. 256–264.
Newell, A. (1963). A Guide to the General Problem-Solver Program GPS-2-2. RAND Corporation, Santa Monica, California. Technical Report No. RM-3337-PR.
Ernst, G.W. and Newell, A. (1969). GPS: a case study in generality and problem solving. Academic Press. (Revised version of Ernst's 1966 dissertation, Carnegie Institute of Technology.)
Newell, A., and Simon, H. A. (1972) Human problem solving Englewood Cliffs, NJ: Prentice-Hall
Noyes, James L. (1992). 《Artificial Intelligence with Common Lisp》. Lexington: D. C. Heath. 343–371쪽. ISBN 978-0-669-19473-9.

[Nilsson2009-1] Nils J. Nilsson (2009년 10월 30일). 《The Quest for Artificial Intelligence》. Cambridge University Press. 121–쪽. ISBN 978-1-139-64282-8.

[Norvig1992-2] Norvig, Peter (1992). 《Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp》. San Francisco, California: Morgan Kaufmann. 109–149쪽. ISBN 978-1-55860-191-8.

[1]

[2]