General Problem Solver ( GPS ) - это компьютерная программа, созданная в 1959 году Гербертом А. Саймоном , Дж. К. Шоу и Алленом Ньюэллом ( RAND Corporation ), предназначенная для работы в качестве универсальной машины для решения проблем . В отличие от прежнего проекта Logic Theorist , GPS работает с анализом средств и целей . [1]
Обзор [ править ]
Любая проблема, которая может быть выражена в виде набора правильно сформированных формул (WFF) или предложений Хорна , и которая составляет ориентированный граф с одним или несколькими источниками (то есть аксиомами) и стоками (то есть желаемыми выводами), может быть решается в принципе по GPS. Доказательства в логике предикатов и проблемных пространствах евклидовой геометрии являются яркими примерами области применимости GPS. Он был основан на теоретической работе Саймона и Ньюэлла о логических машинах. GPS была первой компьютерной программой, которая отделила свои знания о проблемах (правила, представленные как входные данные) от своей стратегии решения проблем (общий механизм решения ). GPS был реализован на языке программирования третьего порядка,IPL . [2]
Хотя GPS решала простые проблемы, такие как Ханойские башни, которые можно было достаточно формализовать, она не могла решить никаких реальных проблем, потому что поиск легко терялся в комбинаторном взрыве . Другими словами, количество «прогулок» по логическому орграфу стало невыносимым с вычислительной точки зрения. (На практике даже простой поиск в пространстве состояний, такой как Ханойские башни, может стать вычислительно невыполнимым, хотя разумное сокращение пространства состояний может быть достигнуто с помощью таких элементарных методов ИИ, как A * и IDA * ).
Пользователь определяет объекты и операции, которые могут быть выполнены с объектами, а GPS генерирует эвристику с помощью анализа средств и результатов для решения проблем. Он сосредоточился на доступных операциях, обнаружив, какие входы были приемлемыми, а какие были получены. Затем он создал подцели, чтобы приближаться к цели.
Парадигма GPS в конечном итоге превратилась в архитектуру Soar для искусственного интеллекта .
См. Также [ править ]
Ссылки [ править ]
- ↑ Нильс Дж. Нильссон (30 октября 2009 г.). В поисках искусственного интеллекта . Издательство Кембриджского университета. стр. 121–. ISBN 978-1-139-64282-8.
- ^ Норвиг, Питер (1992). Парадигмы программирования с использованием искусственного интеллекта: примеры использования Common Lisp . Сан-Франциско , Калифорния : Морган Кауфманн. С. 109–149. ISBN 978-1-55860-191-8.
- Newell, A .; Шоу, JC; Саймон, HA (1959). Отчет по общей программе решения проблем. Материалы Международной конференции по обработке информации. С. 256–264.
- Ньюэлл, А. (1963). Руководство к программе решения общих проблем GPS-2-2 . RAND Corporation , Санта-Моника, Калифорния. Технический отчет № RM-3337-PR.
- Эрнст, Г. В. и Ньюэлл, А. (1969). GPS: тематическое исследование в целом и решение проблем. Академическая пресса. (Пересмотренная версия диссертации Эрнста 1966 года, Технологический институт Карнеги .)
- Ньюэлл, А., и Саймон, HA (1972) Решение человеческих проблем Энглвуд Клиффс, Нью-Джерси: Прентис-Холл
- Нойес, Джеймс Л. (1992). Искусственный интеллект с Common Lisp . Лексингтон : округ Колумбия Хит. С. 343–371. ISBN 978-0-669-19473-9.