Блоки мира

Проблема игрушек в исследовании искусственного интеллекта

Шаг 1 аномалии Сассмана , задача, в которой агент должен распознать блоки и расположить их в стопке с A наверху и C внизу.

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

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

Мотивация

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

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

Автоматизированные задачи планирования и составления расписаний обычно описываются в нотации Planning Domain Definition Language ( PDDL ), которая является языком планирования ИИ для задач символической манипуляции. Если что-то сформулировано в нотации PDDL, это называется доменом. Таким образом, задача сшивания блоков является доменом мира блоков ^[5] , который отличается от других задач планирования, таких как домен робота-докера и задача об обезьяне и банане.

Диссертации/проекты, которые происходили в мире блоков

SHRDLU Терри Винограда
Патрик Уинстон «Изучение структурных описаний на основе примеров и демонстрационных копий»
Аномалия Сассмана Джеральда Джея Сассмана
Проблема принятия решения (Гупта и Нау, 1992): если задан начальный мир блоков, конечный мир блоков и целое число L > 0, есть ли способ переместить блоки, чтобы изменить начальное положение на конечное за L шагов или меньше? Эта проблема принятия решения является NP-трудной . ^[6]

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

Проблема с игрушками

Ссылки

^ Рассел и Норвиг 2003.
^ Джон Слэни и Сильви Тиебо (2001). «Blocks World revisited». Искусственный интеллект . 125 ( 1– 2). Elsevier BV: 119– 153. doi : 10.1016/s0004-3702(00)00079-5 .
^ Ченовет, Стивен В. (1991). О NP-трудности мира блоков . Труды AAAI девятой национальной конференции по искусственному интеллекту. С. 623–628 .
^ SA Cook (2003). «Полная аксиоматизация для мира блоков». Журнал логики и вычислений . 13 (4). Oxford University Press (OUP): 581– 594. doi :10.1093/logcom/13.4.581.
^ Зиллес, Сандра ; Холте, Роберт С. (2009). Сохранение абстракций пространства состояний по нисходящему пути . Восьмой симпозиум по абстракции, переформулированию и аппроксимации.
^ Гупта, Н.; Нау, Д. (1992). «О сложности планирования мира из блоков» (PDF) . Искусственный интеллект . 56 ( 2–3 ): 223–254 . CiteSeerX 10.1.1.30.1793 . doi :10.1016/0004-3702(92)90028-v. hdl :1903/5122.

Источники

Рассел, Стюарт Дж.; Норвиг , Питер (2003), Искусственный интеллект: Современный подход (2-е изд.), Аппер Сэдл Ривер, Нью-Джерси: Prentice Hall, ISBN 0-13-790395-2

Внешние ссылки

Медиа, связанные с мирами Blocks (искусственный интеллект) на Wikimedia Commons

Эта статья, связанная с искусственным интеллектом , является заглушкой . Вы можете помочь Википедии, расширив ее.

[FOOTNOTERussellNorvig2003-1] Рассел и Норвиг 2003.

[2] Джон Слэни и Сильви Тиебо (2001). «Blocks World revisited». Искусственный интеллект . 125 ( 1– 2). Elsevier BV: 119– 153. doi : 10.1016/s0004-3702(00)00079-5 .

[3] Ченовет, Стивен В. (1991). О NP-трудности мира блоков . Труды AAAI девятой национальной конференции по искусственному интеллекту. С. 623–628 .

[4] SA Cook (2003). «Полная аксиоматизация для мира блоков». Журнал логики и вычислений . 13 (4). Oxford University Press (OUP): 581– 594. doi :10.1093/logcom/13.4.581.

[5] Зиллес, Сандра ; Холте, Роберт С. (2009). Сохранение абстракций пространства состояний по нисходящему пути . Восьмой симпозиум по абстракции, переформулированию и аппроксимации.

[6] Гупта, Н.; Нау, Д. (1992). «О сложности планирования мира из блоков» (PDF) . Искусственный интеллект . 56 ( 2–3 ): 223–254 . CiteSeerX 10.1.1.30.1793 . doi :10.1016/0004-3702(92)90028-v. hdl :1903/5122.