Ejercicio 2.5 Prolog. Pedro

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: Existe un mono en la puerta de un cuarto; enmedio del cuarto cuelga una banana del techo; el mono está hambriento y desea capturar la banana, pero no puede alcanzarla desde el piso. En la ventana del cuarto hay una caja que el mono puede usar.

El mono puede realizar solamente las siguientes acciones: caminar sobre el piso, subir a la caja, empujar la caja (si el mono está junto a la caja), y, 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.

Es conveniente combinar todas estas piezas de información en un solo

objeto estructurado. Escogeremos la palabra 'estado' como el functor que

retendrá los cuatro componentes anteriores :

 

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 :

(1). agarrar la banana.

(2). subir a la caja.

(3). empujar la caja.

(4). 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':

El movimiento 'agarrar' es una precondición necesaria antes de la meta final y lo podemos definir con la cláusula:

mover( estado( enmedio, sobrelacaja, enmedio, nolatiene),

agarrarlabanana,

estado( enmedio, sobrelacaja, enmedio, silatiene)).

Esta cláusula nos dice que después de ejecutarse, el mono tendrá la banana y permanece sobre la caja y enmedio del cuarto.

De una forma similar a la anterior 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:

% caminar de P1 a P2

mover( estado( P1, sobreelpiso, B, H),

caminar( P1, P2 ),

estado( P2, sobreelpiso, B, H)).

Esta cláusula nos dice entre otras cosas:

-El movimiento realizado fue: 'caminar de una posición P1 a otra P2'.

-El mono está sobre el piso antes y después del movimiento.

-La caja está en algún lugar B y permanece en el mismo lugar.

-El estado de tiene ó no tiene la banana permanece igual después del movimiento.

La cláusula especifica un conjunto de movimientos posibles porque es aplicable a cualquier situación que se apareje ('matching') al estado antes del movimiento.

Hasta aquí hemos definido los movimientos 'agarrar la banana' (1) y 'caminar de P1 a P2' (4). Los otros dos tipos de movimientos 'empujar la caja' (3) y 'subir a la caja' (2) se pueden definir de manera similar.

Finalmente, la pregunta que nuestro programa debe contestar es: ¿Puede el mono, desde algún estado inicial 'S', capturar la banana ?

Esta pregunta se puede formular con el predicado:

Puede tener(S)

Donde el argumento 'S' es un estado del mundo del mono. El programa para satisfacer el predicado 'puede tener' lo podemos basar en dos observaciones:

(1). Para cualquier estado 'S' en el cual el mono ya tiene la banana, el predicado 'puede tener' debe ser cierto:

puedetener( estado( _, _, _, sila tiene)) :- !.

(2). De otro modo, el mono puede tener la banana desde un estado S1 si existe algún movimiento M del estado S1 a otro estado S2, tal que el mono pueda tener la banana en el estado S2 :

Puede tener( S1) :-

mover( S1, M, S2),

puede tener(S2).