Prolog Ejercicio 4: El Mono y la Banana (Solución de Problemas)

El problema del mono y la banana se utiliza como un ejemplo sencillo de solución de problemas. El siguiente programa en Prolog mostrará como se pueden utilizar los mecanismos de 'matching' y 'backtracking'.

Utilizaremos la siguiente versión del problema:

1. Existe un mono en la puerta de un cuarto.
2. Enmedio del cuarto cuelga una banana del techo.
3. El mono está hambriento y desea capturar la banana pero no puede alcanzarla desde el piso.
4. En la ventana del cuarto hay una caja que el mono puede usar.

El mono puede realizar solamente las siguientes acciones:

1. Caminar sobre el piso
2. Subir a la caja
3. Empujar la caja (Si el mono está junto a la caja)
4. Agarrar la banana (Si el mono está sobre la caja y bajo la banana).

¿Cómo puede el mono llegar a capturar la banana?

Análisis del problema.

Una tarea importante en programación es encontrar una representación del problema en términos del lenguaje de programación utilizado.
En este caso podemos pensar del 'mundo del mono' en términos de 'estados' que cambian con el tiempo. El estado actual se determina por la posición actual de los objetos.

Por ejemplo, el estado inicial del mundo está determinado por:

1). El mono está en la puerta.
2). El mono está sobre el piso.
3). La caja está en la ventana.
4). El mono no tiene la banana.

El estado final es una situación en que el mono tiene la banana, es decir, cualquier estado en cuyo componente último sea : estado( _, _, _, silatiene)

Las transiciones permitidas que cambian el mundo de un estado a otro son
las siguientes :
Agarrar la banana.
Subir a la caja.
Empujar la caja.
Caminar en el cuarto.

No todas las transiciones son posibles en cada estado posible del mundo del mono. Por ejemplo, la transición 'agarrar la banana' es solamente posible si el mono está sobre la caja y bajo la banana y si no tiene todavía la banana. Estas transiciones ó reglas se pueden formalizar en Prolog como una relación de tres componentes que llamaremos 'mover':

mover( Estado1, M, Estado2) 

Los tres argumentos de la relación especifican un movimiento tal que:
Estado1 ----- M -----> Estado2

'Estado1' es el estado antes del movimiento 'M'; 'M' es el movimiento realizado, y 'Estado2' es el estado del mundo del mono después de haberse realizado el movimiento 'M'.

Podemos expresar el hecho de que el mono estando sobre el piso puede caminar de la posición P1 a cualquier posición P2. El mono puede realizar esta acción sin importar la posición de la caja y si tiene ó no la banana:

          mover( estado( P1, sobreelpiso, B, H),
          caminar( P1, P2 ),
          estado( P2, sobreelpiso, B, H)).

El programa completo es el siguiente:

Consideremos la siguiente pregunta al programa anterior:
?- puedetener( estado( enlapuerta,sobreelpiso,enlaventana,nolatiene)).
Prolog contestará: 'yes'.

El proceso llevado a cabo por Prolog para alcanzar ésta respuesta involucra una serie de búsquedas de movimientos válidos entre una serie de movimientos alternativos posibles. En algún punto de la búsqueda existirá un movimiento equivocado y válido que conducirá a una hoja del árbol de búsquedas, en tal situación, un proceso de 'backtracking' (vuelta atrás) se llevará a cabo para continuar con el proceso.

Árbol de búsqueda para el problema del mono y la banana. El proceso de backtracking se realiza una sola vez. Las búsquedas se realizan de arriba a abajo y de izquierda a derecha.

Fuente: Prolog.pdf (By. Edgar Altamirano C.)