В 1957 году была начата разработка системы, получившей название "Универсальный решатель задач" (General Problem Solver — GPS). Эта система создавалась коллективом из трех исследователей: Аланом Ньюэлом, Дж. Шоу и Гербертом Саймоном. Первая публикация по результатам работы появилась лишь 1959 году [Newell et al., 1959]. Проект продолжался до 1969 года.
Название "Универсальный решатель задач" обусловлено тем фактом, что это была первая система для решения задач (problem-solving system), в которой общие методы решения были отделены от знаний, определяющих конкретную задачу. Часть программы, осуществлявшая поиск решения, не обладала информацией о конкретном виде задачи, с которой она работала. Специфичные для конкретной задачи знания организовывались в отдельные структуры: объекты и операторы для преобразования объектов. Задача для системы GPS ставилась в виде пары, состоящей из начального объекта и желаемого объекта, в который начальный объект должен быть преобразован.
Методология, использованная в GPS, отличается от стандартных методов поиска в пространстве состояний тем, что она выбирает путь, по которому продолжить поиск. Т.е. система пытается искать решение в первую очередь в "наиболее перспективных" ветвях поиска. Такая методология была названа "анализ средств и целей" (means-ends analysis). Ее суть заключалась в том, что сначала отыскивалось различие (difference) между текущим объектом и объектом, который мы хотим получить. Это различие относилось к одному из ряда классов различий. С каждым классом был сопоставлен набор действий, способных уменьшить различие между текущим и целевым объектами.
На каждом шаге поиска GPS искал различие объектов и выбирал один из релевантных операторов, который и пытался затем применить к текущему объекту. Поиск подходящей последовательности операторов выполнялся в глубину до тех пор, пока операторы оказывались применимы, а ветвь поиска "выглядела перспективной". Если ветвь поиска была бесперспективной, то выполнялся откат. Важной особенностью анализа средств и целей является то, что всегда выбирается "релевантный" оператор, уменьшающий различие объектов, даже если он и не применим к текущему объекту. Вместо того чтобы отказаться от неприменимого к текущему объекту оператора, GPS пытался преобразовать текущий объект в объект, пригодный для применения выбранного оператора. Применение такой стратегии привело к появлению рекурсивной, целеориентированной процедуры, которая фиксирует историю поиска в графе с частично-проработанными узлами.
Несмотря на то, что в качестве объекта могла выступать модель мира, а в качестве оператора — действие, задача планирования перед системой GPS не ставилась. Такой вариант использования GPS был осуществлен значительно позднее, когда была разработана система STRIPS.
Библиография
Трофимов И.В.
апрель 2005