Введение
Stanford Research Institute Problem Solver, известный под аббревиатурой STRIPS, — это автоматизированный планировщик, разработанный Ричардом Фиксом и Нильсом Нильссоном в 1971 году в SRI International. Позднее то же название стали использовать для обозначения формального языка, используемого для ввода данных в этот планировщик. Этот язык послужил основой для большинства современных языков, предназначенных для описания задач автоматизированного планирования; такие языки обычно называют языками действий. В данной статье описывается только язык, а не сам планировщик.
Расширения
Вышеописанный язык фактически является пропозициональной версией STRIPS; на практике условия часто относятся к объектам: например, положение робота может быть смоделировано предикатом , а означает, что робот находится в Комнате1. В этом случае действия могут иметь свободные переменные, которые неявно квантифицированы по существованию. Иными словами, действие представляет собой все возможные пропозициональные действия, которые можно получить, заменив каждую свободную переменную на конкретное значение. Начальное состояние считается полностью известным в описанном языке: условия, отсутствующие в , считаются ложными. Это часто является ограничивающим предположением, поскольку существуют естественные примеры задач планирования, в которых начальное состояние не полностью известно. Для работы с частично известными начальными состояниями были разработаны расширения STRIPS.
Сложность
Определение наличия плана для пропозициональной задачи STRIPS является PSPACE-полной задачей. Различные ограничения могут быть введены для определения наличия плана за полиномиальное время или, по крайней мере, для сведения задачи к классу NP-полных задач.
Оператор макросов
В задаче об обезьяне и банане робот-обезьяна должен выполнить последовательность действий, чтобы достать банан, висящий под потолком. Одно действие вносит небольшое изменение в состояние игры. Для упрощения процесса планирования целесообразно ввести абстрактное действие, которое отсутствует в стандартном описании правил. Супердействие состоит из действий низкого уровня и позволяет достигать целей высокого уровня. Преимущество заключается в снижении вычислительной сложности и возможности планирования более сложных задач решателем. Поиск новых макрооператоров для предметной области может быть реализован с помощью генетического программирования. Суть заключается не в планировании самой предметной области, а в создании на предварительном этапе эвристики, которая позволяет решать задачи в этой области значительно быстрее. В контексте обучения с подкреплением макрооператор называется опцией. Аналогично определению в планировании ИИ, идея состоит в обеспечении временной абстракции (охвата более длительного периода времени) и непосредственном изменении состояния игры на более высоком уровне.