STRIPS

STRIPS (Stanford Research Institute Problem Solver) — это автоматизированная система планирования, разработанная в Стэнфордском исследовательском институте (SRI International) в 1971 году под руководством Ричарда Фикса. STRIPS является одной из первых и наиболее влиятельных систем искусственного интеллекта, предназначенных для решения задач методом поиска в пространстве состояний. Она стала основой для формального языка описания задач планирования, который также называется STRIPS и широко используется в области искусственного интеллекта и робототехники.

История

Система STRIPS была создана в рамках проекта по разработке мобильного робота Shakey, который мог автономно перемещаться по комнате и выполнять простые команды, такие как перемещение объектов. Разработка велась в Стэнфордском исследовательском институте (SRI) в конце 1960-х — начале 1970-х годов. Основной задачей было создание программы, способной генерировать последовательность действий (план) для достижения заданной цели, исходя из описания текущего состояния мира и доступных операций.

Первая версия STRIPS была реализована на языке программирования Lisp. В 1971 году Ричард Фикс, Нилс Нильссон и другие исследователи опубликовали статью «STRIPS: A New Approach to the Application of Theorem Proving to Problem Solving», в которой описали архитектуру и принципы работы системы. STRIPS стала первым планировщиком, который использовал формальное представление состояний и действий, что позволило автоматизировать процесс решения задач в дискретных средах.

Впоследствии STRIPS оказала значительное влияние на развитие области автоматического планирования. Её подходы были расширены и модифицированы в таких системах, как ABSTRIPS (абстрактное планирование), NONLIN (планирование с частичным порядком) и Graphplan. Язык описания задач STRIPS стал стандартом де-факто для представления планировочных задач в исследованиях ИИ.

Основные принципы работы

STRIPS решает задачи, представляя их как поиск пути в пространстве состояний. Состояние мира описывается набором истинных логических предикатов (фактов). Действия (операторы) задаются в виде правил перехода между состояниями, которые включают три компонента:

• Предусловия (preconditions) — набор фактов, которые должны быть истинными в текущем состоянии, чтобы действие могло быть выполнено.
• Список удаления (delete list) — факты, которые перестают быть истинными после выполнения действия.
• Список добавления (add list) — факты, которые становятся истинными после выполнения действия.

Цель задачи задаётся как конъюнкция фактов, которые должны быть истинными в конечном состоянии. STRIPS пытается найти последовательность действий, которая преобразует начальное состояние в состояние, удовлетворяющее цели.

Алгоритм поиска

STRIPS использует метод поиска в глубину с возвратами (backtracking) и эвристики для уменьшения пространства поиска. Основной алгоритм включает следующие шаги:

1. Проверка цели: Если текущее состояние удовлетворяет цели, план считается найденным.
2. Выбор подцели: Если цель не достигнута, выбирается один из невыполненных фактов цели.
3. Поиск подходящего действия: Находится действие, которое добавляет выбранный факт в свой список добавления.
4. Рекурсивное планирование: Для выполнения выбранного действия сначала рекурсивно планируется достижение его предусловий (это может привести к вложенным подзадачам).
5. Выполнение действия: После достижения предусловий действие «выполняется», и состояние обновляется.
6. Повторение: Процесс повторяется для оставшихся невыполненных фактов цели.

Если на каком-то шаге не удаётся найти подходящее действие, система возвращается к предыдущему шагу (backtracking) и пробует альтернативные варианты.

Ограничения

• STRIPS работает только с дискретными состояниями и не поддерживает непрерывные параметры (например, время или координаты).
• Система предполагает, что мир полностью наблюдаем и детерминирован — все изменения происходят только в результате действий планировщика.
• Планирование в STRIPS является монотонным: факты могут только добавляться или удаляться, но не изменяться частично.
• Пространство поиска может быть экспоненциально большим, что делает систему непригодной для сложных задач без эвристик.

Формальный язык STRIPS

Язык STRIPS (часто называемый «STRIPS-формализмом») стал стандартом для описания задач планирования. Он включает три основных компонента:

• Состояние (state) — набор атомарных фактов (предикатов), которые истинны в данный момент.
• Действие (action) — оператор, задаваемый кортежем (название, предусловия, эффекты). Эффекты делятся на положительные (add-list) и отрицательные (delete-list).
• Задача (problem) — начальное состояние, целевое состояние (конъюнкция фактов) и набор доступных действий.

Пример описания задачи в стиле STRIPS (перемещение блоков):

• Начальное состояние: on(A, Table), on(B, Table), clear(A), clear(B).
• Цель: on(A, B).
• Действие move(x, y, z):
• Предусловия: on(x, y), clear(x), clear(z).
• Удаление: on(x, y), clear(z).
• Добавление: on(x, z), clear(y).

В современном виде язык STRIPS лёг в основу более формальных языков, таких как PDDL (Planning Domain Definition Language), который используется в международных соревнованиях по планированию (International Planning Competition).

Применение

Хотя оригинальная система STRIPS была разработана для робота Shakey, её формализм и алгоритмы нашли применение в различных областях:

• Робототехника: Планирование последовательности действий для манипуляторов и мобильных роботов.
• Логистика: Автоматическое планирование маршрутов и распределения ресурсов.
• Игры: Поиск решений в головоломках (например, «Ханойская башня», «Задача о волке, козе и капусте»).
• Управление производством: Планирование операций в сборочных линиях.
• Образование: Используется как учебный пример для изучения основ искусственного интеллекта.

Критика и развитие

STRIPS подвергалась критике за ограниченность выразительности и неэффективность при работе с большими пространствами состояний. Основные недостатки:

• Отсутствие поддержки иерархического планирования (позже решено в ABSTRIPS).
• Невозможность работы с частично наблюдаемыми средами.
• Жёсткая зависимость от точного описания начального состояния.

В ответ на эти ограничения были разработаны более мощные планировщики, такие как:

• Graphplan (1995) — использует графы планирования для параллельного поиска.
• SATPlan (1990-е) — сводит задачу планирования к выполнимости булевых формул (SAT).
• HTN-планировщики (Hierarchical Task Network) — позволяют работать с иерархическими задачами.

Тем не менее, STRIPS остаётся фундаментальной концепцией в области ИИ и продолжает использоваться в учебных целях и простых приложениях.

Интересные факты

• Название STRIPS происходит от Stanford Research Institute Problem Solver, хотя в некоторых источниках упоминается как «Stanford Research Institute Planning System».
• Робот Shakey, для которого была создана STRIPS, считается одним из первых мобильных роботов, способных к автономному планированию.
• В 1970-х годах STRIPS была реализована на компьютере PDP-10 с оперативной памятью около 256 КБ.
• Формализм STRIPS лёг в основу языка PDDL, который используется в соревнованиях по планированию с 1998 года.

Источники

• Fikes, R. E., & Nilsson, N. J. (1971). STRIPS: A new approach to the application of theorem proving to problem solving. Artificial Intelligence, 2(3-4), 189-208.
• Nilsson, N. J. (1980). Principles of Artificial Intelligence. Tioga Publishing Company.
• Russell, S., & Norvig, P. (2020). Artificial Intelligence: A Modern Approach (4th ed.). Pearson.
• Ghallab, M., Nau, D., & Traverso, P. (2004). Automated Planning: Theory and Practice. Morgan Kaufmann.