Blocks world

Wikipedia英語版の Blocks world のページの翻訳です。

 

 

Blocks world

The blocks world is one of the most famous planning domains in artificial intelligence. Imagine a set of wooden blocks of various shapes and colors sitting on a table. The goal is to build one or more vertical stacks of blocks. The catch is that only one block may be moved at a time: it may either be placed on the table or placed atop another block. Because of this, any blocks that are, at a given time, under another block cannot be moved. Moreover, some kinds of blocks cannot have other blocks stacked on top of them.

ブロック・ワールドは、人工知能における最も有名な計画領域での研究の1つです。テーブルの上に座っている様々な形や色の木製ブロックを想像してみてください。目標は、1つ以上のブロックの垂直スタックを構築することです。キャッチは、一度に1つのブロックしか移動できないということです。テーブルに置くか、別のブロックの上に置くことができます。このため、ある時点で他のブロックの下にあるブロックを移動することはできません。さらに、いくつかの種類のブロックには、他のブロックがその上に積み重ねられていてはいけません。

The simplicity of this toy world lends itself readily to symbolic or classical A.I. approaches, in which the world is modeled as a set of abstract symbols which may be reasoned about.

このおもちゃの世界の単純さは、世界が抽象的な記号の集合としてモデル化されている象徴的または古典的なAIアプローチに容易に役立ちます。

 

Thesis/projects which took place in a blocks world(ブロック・ワールドで行われた論文やプロジェクト)

Decision problem (Gupta and Nau, 1992): Given a starting Blocks World, an ending Blocks World, and an integer L > 0, is there a way to move the blocks to change the starting position to the ending position with L or less steps?

決定問題(Gupta and Nau、1992):開始Blocks World、終了Blocks World、整数L> 0が与えられた場合、L以下のステップで開始位置を終了位置に変更するためにブロックを移動する方法がある?

This decision problem is NP-hard.[1]

この決定の問題はNP困難です。

 

See also(関連情報)

 

References(参考文献)

  1. Gupta, N.; Nau, D. "On the Complexity of Blocks-World Planning" (PDF). Artificial Intelligence. 56: 223–254. doi:10.1016/0004-3702(92)90028-v.