Siguiente: El mundo de los Un nivel arriba: Expresiones regulares y sistemas Anterior: Expresiones regulares y sistemas

Introducción

Los Sistemas de Planeación generan automáticamente procedimientos para resolver problemas bien planteados. En ellos , se describe al Universo del Problema, el cual consiste de sus objetos y de las relaciones entre ellos. Se describe también a las acciones legales, o movimientos. Cada una de ellas involucra a un conjunto de precondiciones que se deben de cumplir para aplicar la acción, y otro de postcondiciones que se cumplirán tras haber aplicado la acción. Una acción sólo se aplica a algunos estados, y al hacerlo, los transforma en otros nuevos. Si la acción a se puede aplicar al estado e escribiremos $a\downarrow e$ y denotaremos por a( e ) al estado que se obtiene de e al aplicar a. Una acción a₁ es sucesiva de otra a₀ respecto al estado e si se cumple que $a_1\downarrow a_0(e)$. Un plan, aplicado a un estado e, es una sucesión de acciones $a_0,\ldots,a_k$ tal que $a_0\downarrow e$, a₁ es sucesiva de a₀ respecto a e y además a_i+1 es sucesiva de a_i respecto a $a_{i-1}\circ a_{i-2}\circ \cdots\circ a_0( e )$, $i=2,\ldots,k-1$. El problema de cualquier Sistema de Planeación consiste en encontrar, para un estado inicial e y uno meta f dados, un plan $a_0,\ldots,a_k$ tal que $f = a_{k}\circ a_{k-1}\circ \cdots\circ a_0( e )$, siempre que exista un tal plan, o bien indicar que no existe, en otro caso. El Problema de los Bloques tiene como universo a un conjunto de n+1 objetos, de los cuales n son bloques y el último es el piso. Como relaciones sólo tiene a dos:

• $\mbox{\it sobre\/}( x , y )$ ``el bloque x está sobre el objeto y'', y
• $\mbox{\it libre\/}( x )$ ''el objeto x está libre para recibir un bloque encima de él''.

Las acciones legales son instancias de $\mbox{\it mueve\/}( x , y , z )$ ``mueve el bloque x del objeto y al objeto z'', con

• precondiciones:
  
  $$\mbox{\it libre\/}(x) \& \mbox{\it libre\/}(z) \& \mbox{\it sobre\/}(x,y)$$
  
  
  y
• postcondiciones:
  
  $$\mbox{\it libre\/}(x) \& \mbox{\it libre\/}(y) \& \mbox{\it sobre\/}(x,z).$$
  
  

Cada estado se especifica como una conjunción de enunciados atómicos, o átomos, los cuales son instancias de relaciones con objetos. Un primer criterio para generar planes de manera automática es poner a los átomos de una meta en una lista, considerarlos como ``submetas'', e ir lográndolos uno a uno. Es necesario preservar lo logrado al tratar de lograr un nuevo átomo. Si acaso no fuera posible, se permuta a la lista de átomos y se repite el proceso. A veces este criterio no logra estados metas, aún cuando efectivamente fueren alcanzables. La anomalía de Sussman es un ejemplo: Con tres bloques 1, 2 , 3, estado inicial

$$\mbox{\it sobre\/}(3,1) \& \mbox{\it sobre\/}(2,\mbox{\it piso\/})$$

y meta

$$\mbox{\it sobre\/}(1,2) \& \mbox{\it sobre\/}(2,3),$$

la estrategia anterior no logra encontrar un plan. En cualquiera de las dos permutaciones de la meta uno se ve obligado a deshacer logros ya obtenidos. El problema de planeación ha sido tratado con diversos enfoques, basados, en general, en deducción automática. Alternativamente, consideraremos aquí un enfoque de tipo combinatorio. Veremos que es posible calcular no sólo una solución, sino a todas las existentes. Primeramente, calcularemos el número de estados en el Problema de Bloques (PB). Presentamos luego una solución del correspondiente problema de planeación con técnicas de autómatas finitos. Finalmente observamos que, bien que el PB (de hecho cualquier otro problema para los Sistemas de Planeación), se resuelve por completo con estas técnicas, los algoritmos utilizados son tan complejos que aún queda lejos su implementación práctica.
Siguiente: El mundo de los Un nivel arriba: Expresiones regulares y sistemas Anterior: Expresiones regulares y sistemas