Мир блоков — это область планирования искусственного интеллекта . Алгоритм аналогичен набору деревянных брусков разной формы и цвета, лежащих на столе. Цель состоит в том, чтобы построить одну или несколько вертикальных стопок блоков. Одновременно можно перемещать только один блок: его можно либо положить на стол, либо положить поверх другого блока. По этой причине любые блоки, находящиеся в данный момент под другим блоком, не могут быть перемещены. Более того, некоторые типы блоков не могут располагаться поверх других блоков. [1]
Простота этого игрушечного мира легко поддается классическим символическим подходам искусственного интеллекта , в которых мир моделируется как набор абстрактных символов, о которых можно рассуждать.
Искусственный интеллект можно исследовать теоретически и с практическим применением. Проблема большинства практических приложений заключается в том, что инженеры не знают, как программировать систему искусственного интеллекта. Вместо того, чтобы вообще отвергать задачу, идея состоит в том, чтобы изобрести легко решаемую область, которая называется игрушечной задачей . Игрушечные задачи были изобретены с целью запрограммировать ИИ, который сможет их решить. Мировая область блоков является примером игрушечной задачи. Его главное преимущество перед более реалистичными приложениями ИИ заключается в том, что доступно множество алгоритмов и программ, которые могут справиться с ситуацией. [2] Это позволяет сравнивать различные теории друг с другом.
В своей базовой форме мировая задача блоков состоит из кубиков одинакового размера, все из которых окрашены в черный цвет. Механическая рука робота должна собирать и размещать кубики. [3] Более сложные производные задачи состоят из кубиков разных размеров, форм и цветов. [4] С точки зрения алгоритма, мир блоков представляет собой np-сложную задачу поиска и планирования. Задача — перевести систему из исходного состояния в целевое.
Проблемы автоматического планирования и составления графиков обычно описываются в нотации языка определения области планирования ( PDDL ), который является языком планирования ИИ для задач символического манипулирования. Если что-то было сформулировано в нотации PDDL, это называется доменом. Таким образом, задача сшивания блоков представляет собой область мира блоков [5] , которая контрастирует с другими проблемами планирования, такими как область роботов докеров и проблема обезьяны и банана.
Проблема принятия решения (Гупта и Нау, 1992): Учитывая начальный мир блоков, конечный мир блоков и целое число L > 0, существует ли способ переместить блоки, чтобы изменить начальное положение на конечное положение с помощью L или меньше шагов. ?
Эта проблема решения является NP-трудной . [6]