Блокирует мир - Blocks world

Эта статья посвящена общей концепции исследований в области информатики. Для видеоигры "песочница" см. Blocksworld.

В блокирует мир один из самых известных области планирования в искусственный интеллект. Алгоритм похож на набор деревянных блоков разной формы и цвета, сидящих на столе. Цель состоит в том, чтобы построить одну или несколько вертикальных стопок блоков. Одновременно можно перемещать только один блок: его можно либо положить на стол, либо положить на другой блок. Из-за этого любые блоки, которые в данный момент находятся под другим блоком, не могут быть перемещены. Более того, на некоторые типы блоков нельзя накладывать другие блоки поверх них.

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

Мотивация

Искусственный интеллект можно исследовать как в теории, так и на практике. Проблема с большинством практических приложений заключается в том, что инженеры не знают, как программировать систему ИИ. Вместо того, чтобы вообще отказываться от этой проблемы, идея состоит в том, чтобы изобрести легко решаемую область, которая называется проблема с игрушкой. Игрушечные задачи были изобретены с целью запрограммировать ИИ, который сможет их решить. Мир блоков - это пример игрушечной задачи. Его главное преимущество перед более реалистичными приложениями искусственного интеллекта состоит в том, что доступно множество алгоритмов и программ, которые могут справиться с ситуацией.[1] Это позволяет сравнивать разные теории друг с другом.

В своей основной форме мировая проблема блоков состоит из кубиков одинакового размера, которые имеют черный цвет. Механический робот-манипулятор должен собирать и складывать кубики.[2] Более сложные производные задачи состоят из кубиков разных размеров, форм и цветов.[3] С точки зрения алгоритма, мир блоков - это нп-жесткий поиск и проблема планирования. Задача - вывести систему из исходного состояния в целевое.

Автоматизированное планирование и составление графиков проблема обычно описывается в PDDL нотация, которая является языком планирования ИИ для задач символьной манипуляции. Если что-то было сформулировано в нотации PDDL, это называется доменом. Следовательно, задача скрепления блоков - это мировой домен блоков. [4] что контрастирует с другими проблемами планирования, такими как док рабочий робот домен и проблема обезьяны и банана.

Пример настройки в мире блоков

Шаг 1 Аномалия Сассмана

Тезисы / проекты, которые проходили в мире блоков

Проблема решения (Гупта и Нау, 1992): Учитывая начальный мир блоков, конечный мир блоков и целое число L> 0, есть ли способ переместить блоки, чтобы изменить начальную позицию на конечную с L или меньшим количеством шагов?

Эта проблема решения NP-жесткий.[5]

Смотрите также

Рекомендации

  1. ^ Джон Слейни и Сильви Тибо (2001). «Новый взгляд на мир блоков». Искусственный интеллект. Elsevier BV. 125 (1–2): 119--153. Дои:10.1016 / с0004-3702 (00) 00079-5.
  2. ^ Ченовет, Стивен V (1991). О NP-твердости мира блоков. AAAI Труды девятой национальной конференции по искусственному интеллекту. С. 623--628.
  3. ^ С. А. Кук (2003). «Полная аксиоматизация для мира блоков». Журнал логики и вычислений. Издательство Оксфордского университета (ОУП). 13 (4): 581--594. Дои:10.1093 / logcom / 13.4.581.
  4. ^ Зиллес, Сандра и Хольте, Роберт С. (2009). Нисходящий путь с сохранением абстракций пространства состояний. Восьмой симпозиум по абстракции, переформулировке и аппроксимации.CS1 maint: несколько имен: список авторов (связь)
  5. ^ Gupta, N .; Нау, Д. (1992). «О сложности блокового миропланирования» (PDF). Искусственный интеллект. 56 (2–3): 223–254. CiteSeerX  10.1.1.30.1793. Дои:10.1016 / 0004-3702 (92) 90028-в.