Аномалия Сассмана

Аномалия Сассмана — проблема искусственного интеллекта , впервые описанная Джеральдом Сассманом и иллюстрирующая слабость алгоритмов нечередующегося планирования , которые были популярны в начале 1970-х годов. Большинство современных систем планирования не ограничиваются нечередующимся планированием и, таким образом, могут справиться с этой аномалией. Хотя значимость/ценность проблемы теперь является исторической, она по-прежнему полезна для объяснения того, почему планирование нетривиально. В задаче три блока (обозначенные A, B и C) лежат на столе. Агент должен складывать блоки так, чтобы A находился над B, который, в свою очередь, находился над C. Однако за раз он может перемещать только один блок. Проблема начинается с того, что B на столе, C поверх A и A на столе:

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

1. поставить А поверх Б
2. поставить B поверх C

Предположим, что планировщик начинает с достижения цели 1. Простое решение состоит в том, чтобы убрать C с дороги, а затем переместить A поверх B. Но хотя эта последовательность позволяет достичь цели 1, агент теперь не может достичь цели 2, не отменяя цель 1, поскольку обе цели A и B необходимо переместить поверх C:

Если вместо этого планировщик начинает с цели 2, наиболее эффективным решением будет перейти к цели Б. Но опять же, планировщик не может достичь цели 1, не отменяя цель 2:

Проблема была впервые выявлена ​​Сассманом в рамках его докторского исследования. Сассман (и его руководитель Марвин Мински ) считали, что разведка требует списка исключений или уловок, и разработали модульную систему планирования для «отладки» планов.

См. также

• ПОЛОСКИ
• Автоматизированное планирование
• Жадный алгоритм

Источники

• Рассел, Стюарт Дж .; Норвиг, Питер (2003), Искусственный интеллект: современный подход (2-е изд.), Аппер-Сэддл-Ривер, Нью-Джерси: Прентис-Холл, стр. 414, ISBN  0-13-790395-2
• Г. Дж. Сассман (1975) Компьютерная модель приобретения навыков Elsevier Science Inc. Нью-Йорк, штат Нью-Йорк, США. Книжная версия его кандидатской диссертации.