Автоматизированное планирование: что делает "blockworld" нетривиальной проблемой?

Question

Blocksworld , по-видимому, является эталонной областью в автоматизированном планировании.

This domain consists of a set of blocks, a table and a robot hand.
The blocks can be on top of other blocks or on the table;
a block that has nothing on it is clear;
and the robot hand can hold one block or be empty.
The goal is to find a plan to move from one configuration of blocks to another.

Может кто-нибудь объяснить, что делает эту проблему нетривиальной? Я не могу вспомнить случай, когда решение не является тривиальным (например, построить желаемые башни снизу вверх по одному блоку за раз).

Answer 1

Еще одна интересная статья о Blocksworld, которую я нахожу довольно интересной, - "Как Добро почти идеально?" (AAAI 2008) Хельмерта и Рёгера.

Он показал, что даже при использовании почти идеальной эвристики (эвристика, которая для каждого возможного состояния неверна только для константы), поиск * неизбежно приводит к экспоненциально большому пространству поиска. (Это показывает, что даже при почти идеальной информации о расстоянии до цели поиск все равно теряется в пространстве поиска в этом домене.)

Answer 2

Существует историческая и две практические причины, по которым Blocks World является эталоном интереса.

Исторически сложилось так, что Мир Блоков использовался для иллюстрации так называемой Аномалии Сусмана . Он больше не имеет научной значимости, но он использовался для иллюстрации ограничений и проблем алгоритмов планирования, которые подходят к проблеме планирования как к поиску в пространстве планов непосредственно . Ссылка указывает на главу следующей книги, которая является хорошим введением в автоматизированное планирование

Автоматизированное планирование и исполнение Малик Галлах, Дана Нау, Паоло Траверсо
Издательство Кембриджского университета

Раньше, особенно в середине 1990-х годов, когда SAT-решение действительно сработало, это был пример того, насколько ограниченным был уровень автоматизированного планирования в тот день.

Как вы пишете в своем вопросе, решить Blocks World очень просто: алгоритм, который вы набросали, хорошо известен и явно за полиномиальное время. Найти оптимальный план, однако, нелегко. Я отсылаю вас к этой превосходной книге

Понимание задач планирования: сложность домена и эвристическая декомпозиция
Мальте Хельмерт
Springer, 2006

или его более короткая классическая бумага

Результаты сложности для стандартных эталонных доменов при планировании Малте Хельмерт Искусственный интеллект, 2003

Вторая «практическая» причина актуальности Blocks World заключается в том, что, даже будучи «простой» проблемой, она может победить эвристику планирования и разработать алгоритмы или компиляции для других вычислительных сред, таких как SAT или SMT.

Например, лишь сравнительно недавно (2012 г.) Юсси Ринтанен показал хорошие результаты в этом "простом" тесте после значительного изменения стандартных решателей SAT

Планирование как удовлетворяемое: эвристика
Юсси Ринтанен
Искусственный интеллект, 2012

, скомпилировав в них эвристику как пункты, которые комбинация распространения единиц, обучения по пунктам и эвристики выбора переменных может использовать для быстрого получения дедуктивных нижних границ.

РЕДАКТИРОВАТЬ : Были запрошены дополнительные сведения о замечании выше оптимального планирования для непростых блоков. Из предоставленных ссылок, этот документ

О сложности блоков мирового планирования
Нареш Гупта и Дана С. Нау
Искусственный интеллект, 1992

имеет оригинальное доказательство, сводящее задачу вычисления оптимальных планов для Blocks World к HITTING-SET (одна из NP-сложных задач Карпа).

Более простой доступ к бумаге, которая достаточно глубоко подходит для планирования в домене Blocks World:

Blocks World вновь
Джон Слэйни, Сильви Тибо
Искусственный интеллект, 2001

Рисунок 1 в статье выше показывает пример экземпляра, который иллюстрирует интуицию, стоящую за Гуптой, и доказательство сложности Нау.