50:. The algorithm is similar to 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. 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.
385:
27:
365:
70:. Toy problems were invented with the aim to program an AI which can solve it. The blocks world domain is an example for a toy problem. Its major advantage over more realistic AI applications is, that many algorithms and software programs are available which can handle the situation. This allows to compare different theories against each other.
73:
In its basic form, the blocks world problem consists of cubes in the same size which have all the color black. A mechanical robot arm has to pick and place the cubes. More complicated derivatives of the problem consist of cubes in different sizes, shapes and colors. From an algorithm perspective,
65:
Artificial
Intelligence can be researched in theory and with practical applications. The problem with most practical application is, that the engineers don't know how to program an AI system. Instead of rejecting the challenge at all the idea is to invent an easy to solve domain which is called a
91:) notation which is an AI planning language for symbolic manipulation tasks. If something was formulated in the PDDL notation, it is called a domain. Therefore, the task of stapling blocks is a blocks world domain which stays in contrast to other planning problems like the
137:
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?
369:
445:
426:
450:
348:
84:
43:
54:
34:, a problem in which an agent must recognise the blocks and arrange them into a stack with A at the top and C at the bottom
419:
392:
47:
412:
298:
16:
This article is about the general concept in computer science research. For the sandbox video game, see
92:
57:
approaches, in which the world is modeled as a set of abstract symbols which may be reasoned about.
303:
226:. AAAI Proceedings of the ninth national conference on Artificial Intelligence. pp. 623--628.
126:
186:
81:
and planning problem. The task is to bring the system from an initial state into a goal state.
344:
330:
396:
308:
283:
246:
202:
130:
113:
31:
121:
104:
78:
207:
190:
439:
312:
264:
334:
384:
153:
67:
26:
17:
250:
117:
364:
87:
problem are usually described in the
Planning Domain Definition Language (
140:
75:
108:
271:. Eighth Symposium on Abstraction, Reformulation, and Approximation.
53:
The simplicity of this toy world lends itself readily to classical
25:
237:
88:
343:(2nd ed.), Upper Saddle River, New Jersey: Prentice Hall,
338:
400:
99:Theses/projects which took place in a blocks world
269:Downward path preserving state space abstractions
23:Toy problem in artificial intelligence research
245:(4). Oxford University Press (OUP): 581--594.
118:Learning Structural Descriptions from Examples
420:
172:
8:
284:"On the Complexity of Blocks-World Planning"
427:
413:
340:Artificial Intelligence: A Modern Approach
95:domain and the monkey and banana problem.
302:
206:
135:Decision problem (Gupta and Nau, 1992):
370:Blocks worlds (artificial intelligence)
165:
7:
381:
379:
446:History of artificial intelligence
399:. You can help Knowledge (XXG) by
224:On the NP-Hardness of Blocks World
14:
85:Automated planning and scheduling
383:
363:
239:Journal of Logic and Computation
55:symbolic artificial intelligence
201:(1–2). Elsevier BV: 119--153.
1:
451:Artificial intelligence stubs
222:Chenoweth, Stephen V (1991).
208:10.1016/s0004-3702(00)00079-5
313:10.1016/0004-3702(92)90028-v
282:Gupta, N.; Nau, D. (1992).
467:
378:
267:; Holte, Robert C (2009).
15:
173:Russell & Norvig 2003
139:This decision problem is
191:"Blocks World revisited"
393:artificial intelligence
291:Artificial Intelligence
251:10.1093/logcom/13.4.581
195:Artificial Intelligence
48:artificial intelligence
395:-related article is a
35:
29:
372:at Wikimedia Commons
74:blocks world is an
331:Russell, Stuart J.
127:Gerald Jay Sussman
36:
408:
407:
368:Media related to
93:dock worker robot
458:
429:
422:
415:
387:
380:
367:
353:
317:
316:
306:
297:(2–3): 223–254.
288:
279:
273:
272:
261:
255:
254:
234:
228:
227:
219:
213:
212:
210:
185:John Slaney and
182:
176:
170:
466:
465:
461:
460:
459:
457:
456:
455:
436:
435:
434:
433:
376:
360:
351:
329:
326:
321:
320:
286:
281:
280:
276:
263:
262:
258:
236:
235:
231:
221:
220:
216:
187:Sylvie Thiébaux
184:
183:
179:
171:
167:
162:
150:
131:Sussman anomaly
114:Patrick Winston
101:
63:
44:planning domain
32:Sussman anomaly
24:
21:
12:
11:
5:
464:
462:
454:
453:
448:
438:
437:
432:
431:
424:
417:
409:
406:
405:
388:
374:
373:
359:
358:External links
356:
355:
354:
349:
325:
322:
319:
318:
304:10.1.1.30.1793
274:
265:Zilles, Sandra
256:
229:
214:
177:
164:
163:
161:
158:
157:
156:
149:
146:
145:
144:
133:
124:
111:
105:Terry Winograd
100:
97:
62:
59:
30:Step 1 of the
22:
13:
10:
9:
6:
4:
3:
2:
463:
452:
449:
447:
444:
443:
441:
430:
425:
423:
418:
416:
411:
410:
404:
402:
398:
394:
389:
386:
382:
377:
371:
366:
362:
361:
357:
352:
350:0-13-790395-2
346:
342:
341:
336:
335:Norvig, Peter
332:
328:
327:
323:
314:
310:
305:
300:
296:
292:
285:
278:
275:
270:
266:
260:
257:
252:
248:
244:
240:
233:
230:
225:
218:
215:
209:
204:
200:
196:
192:
188:
181:
178:
174:
169:
166:
159:
155:
152:
151:
147:
142:
138:
134:
132:
128:
125:
123:
119:
115:
112:
110:
106:
103:
102:
98:
96:
94:
90:
86:
82:
80:
77:
71:
69:
60:
58:
56:
51:
49:
45:
41:
33:
28:
19:
401:expanding it
390:
375:
339:
294:
290:
277:
268:
259:
242:
238:
232:
223:
217:
198:
194:
180:
168:
136:
83:
72:
64:
52:
40:blocks world
39:
37:
154:Toy problem
68:toy problem
18:Blocksworld
440:Categories
160:References
61:Motivation
299:CiteSeerX
122:Copy Demo
337:(2003),
189:(2001).
148:See also
324:Sources
141:NP-hard
76:np-hard
347:
301:
109:SHRDLU
79:search
391:This
287:(PDF)
42:is a
397:stub
345:ISBN
120:and
89:PDDL
38:The
309:doi
247:doi
203:doi
199:125
129:'s
116:'s
107:'s
46:in
442::
333:;
307:.
295:56
293:.
289:.
243:13
241:.
197:.
193:.
428:e
421:t
414:v
403:.
315:.
311::
253:.
249::
211:.
205::
175:.
143:.
20:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.