El mundo de los bloques es uno de los dominios de planificación más famosos de la inteligencia artificial . El algoritmo es similar a un conjunto de bloques de madera de varias formas y colores colocados sobre una mesa. El objetivo es construir una o más pilas verticales de bloques. Solo se puede mover un bloque a la vez: se puede colocar sobre la mesa o encima de otro bloque. Debido a esto, cualquier bloque que esté, en un momento dado, debajo de otro bloque no se puede mover. Además, algunos tipos de bloques no pueden tener otros bloques apilados encima.
La simplicidad de este mundo de juguetes se presta fácilmente a los enfoques clásicos de inteligencia artificial simbólica , en los que el mundo se modela como un conjunto de símbolos abstractos sobre los que se puede razonar.
Motivación
La inteligencia artificial se puede investigar en teoría y con aplicaciones prácticas. El problema con la mayoría de las aplicaciones prácticas es que los ingenieros no saben cómo programar un sistema de IA. En lugar de rechazar el desafío en absoluto, la idea es inventar un dominio fácil de resolver que se llama problema de juguete . Los problemas de juguetes se inventaron con el objetivo de programar una IA que pueda resolverlos. El dominio del mundo de los bloques es un ejemplo de un problema de juguetes. Su principal ventaja sobre las aplicaciones de IA más realistas es que hay muchos algoritmos y programas de software disponibles que pueden manejar la situación. [1] Esto permite comparar diferentes teorías entre sí.
En su forma básica, el problema del mundo de los bloques consiste en cubos del mismo tamaño que tienen todo el color negro. Un brazo de robot mecánico tiene que recoger y colocar los cubos. [2] Derivados más complicados del problema consisten en cubos de diferentes tamaños, formas y colores. [3] Desde la perspectiva de un algoritmo, el mundo de bloques es un problema de planificación y búsqueda np-difícil . La tarea consiste en llevar el sistema de un estado inicial a un estado objetivo.
Los problemas de planificación y programación automatizados generalmente se describen en la notación PDDL , que es un lenguaje de planificación de IA para tareas de manipulación simbólica. Si algo se formuló en la notación PDDL, se denomina dominio. Por lo tanto, la tarea de grapar bloques es un dominio mundial de bloques [4] que se mantiene en contraste con otros problemas de planificación como el dominio del robot trabajador portuario y el problema del mono y el plátano.
Configuración de ejemplo en el mundo de los bloques
Tesis / proyectos que tuvieron lugar en un mundo de bloques
- Terry Winograd 's SHRDLU
- Aprendiz del concepto estructural de Patrick Winston
- Gerald Jay Sussman 's Sussman anomalía
Problema de decisión (Gupta y Nau, 1992): Dado un mundo de bloques inicial, un mundo de bloques final y un número entero L> 0, ¿hay alguna manera de mover los bloques para cambiar la posición inicial a la posición final con L o menos pasos? ?
Este problema de decisión es NP-difícil . [5]
Ver también
Referencias
- ^ John Slaney y Sylvie Thiebaux (2001). "Blocks World revisited". Inteligencia artificial . Elsevier BV. 125 (1–2): 119-153. doi : 10.1016 / s0004-3702 (00) 00079-5 .
- ^ Chenoweth, Stephen V (1991). Sobre el mundo NP-Dureza de los bloques . AAAI Actas de la novena conferencia nacional sobre Inteligencia Artificial. págs.623--628.
- ^ SA Cook (2003). "Una completa axiomatización para el mundo de los bloques". Revista de Lógica y Computación . Prensa de la Universidad de Oxford (OUP). 13 (4): 581--594. doi : 10.1093 / logcom / 13.4.581 .
- ^ Zilles, Sandra y Holte, Robert C (2009). Ruta descendente que conserva las abstracciones del espacio de estado . Octavo Simposio de Abstracción, Reformulación y Aproximación.CS1 maint: varios nombres: lista de autores ( enlace )
- ^ Gupta, N .; Nau, D. (1992). "Sobre la complejidad de la planificación mundial de bloques" (PDF) . Inteligencia artificial . 56 (2-3): 223-254. CiteSeerX 10.1.1.30.1793 . doi : 10.1016 / 0004-3702 (92) 90028-v .