Blokuje svět - Blocks world - Wikipedia

Tento článek pojednává o obecném pojetí ve výzkumu počítačových věd. Informace o videohře na pískovišti naleznete v části Blocksworld.

The blokuje svět je jedním z nejznámějších plánování domén v umělá inteligence. Algoritmus je podobný sadě dřevěných bloků různých tvarů a barev, které sedí na stole. Cílem je vybudovat jeden nebo více vertikálních hromádek bloků. Najednou lze přesunout pouze jeden blok: může být umístěn na stůl nebo umístěn na jiný blok. Z tohoto důvodu nelze přesunout žádné bloky, které jsou v daném čase pod jiným blokem. Některé druhy bloků navíc nemohou mít na sobě naskládané další bloky.

Jednoduchost tohoto světa hraček se snadno hodí ke klasice symbolická umělá inteligence přístupy, ve kterých je svět modelován jako soubor abstraktních symbolů, o nichž lze uvažovat.

Motivace

Umělou inteligenci lze zkoumat teoreticky a s praktickými aplikacemi. Problém většiny praktických aplikací spočívá v tom, že inženýři neví, jak naprogramovat systém AI. Místo toho, abychom výzvu vůbec odmítli, je myšlenka vymyslet snadno řešitelnou doménu, která se nazývá a problém s hračkou. Problémy s hračkami byly vynalezeny s cílem naprogramovat AI, která to dokáže vyřešit. Bloková světová doména je příkladem problému s hračkami. Jeho hlavní výhodou oproti realističtějším aplikacím AI je, že je k dispozici mnoho algoritmů a softwarových programů, které situaci zvládnou.[1] To umožňuje porovnávat různé teorie proti sobě.

Ve své základní formě se problém světových bloků skládá z kostek stejné velikosti, které mají všechny černé barvy. Mechanické robotické rameno musí vybrat a umístit kostky.[2] Složitější derivace problému se skládají z kostek v různých velikostech, tvarech a barvách.[3] Z pohledu algoritmu je svět bloků np-těžké Vyhledávání a problém plánování. Úkolem je uvést systém z počátečního stavu do stavu cíle.

Automatické plánování a plánování problém je obvykle popsán v PDDL zápis, který je plánovacím jazykem AI pro symbolické manipulační úkoly. Pokud bylo něco formulováno v zápisu PDDL, nazývá se to doména. Proto je úkolem sešívání bloků světová doména bloků [4] který zůstává v kontrastu s jinými plánovacími problémy jako dokovací robot robot problém s doménou a opicemi a banány.

Příklad nastavení ve světě bloků

Krok 1 Sussman anomálie

Práce / projekty, které proběhly v blokovém světě

Rozhodovací problém (Gupta a Nau, 1992): Vzhledem k počátečnímu světu bloků, koncovému světu bloků a celému číslu L> 0 existuje způsob, jak přesunout bloky a změnit výchozí pozici do koncové polohy s L nebo méně kroky?

Tento problém s rozhodnutím je NP-tvrdé.[5]

Viz také

Reference

  1. ^ John Slaney a Sylvie Thiebaux (2001). "Blocks World revisited". Umělá inteligence. Elsevier BV. 125 (1–2): 119--153. doi:10.1016 / s0004-3702 (00) 00079-5.
  2. ^ Chenoweth, Stephen V (1991). Na NP-tvrdost světa bloků. Sborník AAAI z deváté národní konference o umělé inteligenci. 623--628.
  3. ^ S. A. Cook (2003). "Kompletní axiomatizace pro svět bloků". Journal of Logic and Computation. Oxford University Press (OUP). 13 (4): 581--594. doi:10.1093 / logcom / 13.4.581.
  4. ^ Zilles, Sandra a Holte, Robert C (2009). Cesta dolů zachovávající abstrakce stavového prostoru. Osmé sympozium o abstrakci, reformulaci a aproximaci.CS1 maint: více jmen: seznam autorů (odkaz)
  5. ^ Gupta, N .; Nau, D. (1992). „O složitosti bloků - plánování světa“ (PDF). Umělá inteligence. 56 (2–3): 223–254. CiteSeerX  10.1.1.30.1793. doi:10.1016 / 0004-3702 (92) 90028-v.