Download Ingenier´ıa Técnica en Informática de Gestión

Ingenierı́a Técnica en
Informática de Gestión
Inteligencia Artificial
Departamento de Informática
Universidad Carlos III de Madrid
Septiembre 2010
Normas generales del examen
•
•
•
•
El tiempo para realizar el examen es de 3 horas y 15 minutos
Sólo se responderán preguntas sobre el examen los primeros 30 minutos
Si se sale del aula, no se podrá volver a entrar durante el examen
No se puede presentar el examen escrito a lápiz
Problema 1. (3 puntos)
La planificación en Inteligencia Artificial trata de resolver problemas cuya solución es una secuencia de acciones
que permiten pasar de una situación o estado inicial dado a otro estado en que se cumplen una serie de metas.
La representación de los estados y de las acciones que se pueden ejecutar constituyen lo que se denomina un
dominio de planificación. Cada acción se define mediante unas precondiciones y unos efectos. Las precondiciones
representan las caracterı́sticas que se deben cumplir en el estado para que la acción se pueda ejecutar y los efectos
representan los cambios en el estado producidos tras la realización de la acción. Los dominios normalmente se
definen utilizando lógica de predicados. Uno de estos dominios es el denominado minas de oro que consiste en un
robot que se mueve por una mina de oro, y cuyo objetivo es recoger el oro situado en una celda conocida a priori.
La mina está organizada como un grid donde en las celdas puede haber rocas duras y blandas y debajo de una de
las rocas blandas está el oro. Para retirar las rocas el robot puede usar una bomba o un láser. Las bombas sólo
destruyen las rocas blandas mientras que el láser puede destruir los dos tipos de rocas. Sin embargo, si se usa el
láser en una celda donde hay oro se destruye el oro también, mientras que con una bomba sólo se destruye la roca
blanda y el oro queda intacto. El robot tiene un brazo con el que sólo puede sostener una cosa a la vez (el láser,
una bomba o el oro) y no tiene ningún almacén para guardar objetos. Tanto las bombas como el láser estarán
inicialmente situados en celdas del grid. Las acciones que puede realizar el robot son:
Moverse a una celda adyacente en la que no haya ninguna roca
Coger un láser: para ello tiene que estar en la misma celda del láser y tener el brazo libre
Coger una bomba: para ello tiene que estar en la misma celda de la bomba y tener el brazo libre
Coger el oro: para ello tiene que estar en la misma celda del oro y tener el brazo libre
Dejar el láser en la misma celda en la que está el robot
Explotar la bomba sujeta por el robot en una celda adyacente que contenga una roca blanda destruyéndola
Disparar el láser sujeto por el robot a una celda adyacente donde hay una roca destruyéndola. Si en la celda
disparada hubiese oro se destruirı́a
La Figura 1 muestra gráficamente un ejemplo de un posible problema en este dominio en el que hay un robot,
dos bombas, un láser, 3 rocas duras, 3 rocas blandas y el oro.
Utilizando lógica de predicados se pide:
1. (1 punto) Definir los predicados necesarios para poder representar el dominio anterior
2. (2 puntos) Definir las fórmulas bien formadas mı́nimas que representen todas las acciones del dominio
10BbaseT
10BbaseT
Roca dura
TRANSCEIVER
TRANSCEIVER
Roca blanda
Robot
Bomba
Laser
Oro
Figura 1: Ejemplo de problema en el dominio minas de oro.
Problema 2. (2 puntos)
Si se quiere modelar el mismo dominio del problema anterior utilizando sistemas de producción y marcos.
Se pide:
1. (1 punto) Definir una jerarquı́a de marcos utilizando sintaxis de CLIPS que permita minimizar el número
de reglas del sistema de producción
2. (1 punto) Definir, utilizando sintaxis de CLIPS y la jeraquı́a anterior, la/s regla/s mı́nimas para representan
las acciones de coger el láser, una bomba y el oro
Problema 3. (5 puntos)
Un conjunto de robots se encuentra en un tablero situado en el vacı́o. Pueden caminar en lı́nea recta por
el tablero, pero no saben cuándo parar. Cuando se mueven, sólo paran si encuentran otro robot en su camino,
quedándose en la posición inmediatamente anterior a la posición del robot con el que se encuentran; si no encuentran
a otro robot en la dirección que se están moviendo, caerı́an al vacı́o con lo cual ese movimiento no serı́a válido. Se
trata de conseguir que el robot rojo llegue hasta el cuadrado central y se detenga ahı́ (lo pare otro robot en esa
posición).
Las Figuras (a, b y c) muestran un ejemplo del problema en un tablero de tamaño 5 × 5 con 6 robots. En la
Figura (a) se muestra el estado inicial. La figura (b) muestra las cuatro posibles direcciones en las que se puede
mover cada robot: los cuatro puntos cardinales. La Figura (c) muestra un estado meta, en el que el robot rojo
está en la casilla meta tras ejecutar la acción de ir en dirección norte.
(a) (b) (d) (f) (g) (c) (e) (h) (i) En las Figuras (d y e) se muestra una situación en la que el robot rojo, desde el mismo estado inicial, no podrı́a
ejecutar la acción de moverse en dirección este, porque al no encontrar a otro robot en su camino que le pare, caerı́a
al vacı́o. En cualquier momento se puede mover a cualquier robot en cualquier dirección, a no ser que haya otro
robot en la posición contigua en la dirección elegida. En un único movimiento el robot se desplaza varias posiciones
hasta encontrar un robot que le pare. Además, al elegir una dirección se debe tener en cuenta que no se debe
permitir caer a ningún robot al vacı́o, como ocurre en la Figura (e). Las Figuras (f) a (i) muestran otro problema
resuelto de forma óptima en tres movimientos. La Figura (f) muestra el estado inicial. La Figura (g) muestra cómo
el robot situado en la zona superior se ha desplazado (dos posiciones en este caso) ejecutando la acción de moverse
en dirección este. En la Figura (h) el robot rojo también se ha desplazado en dirección este, llegando a la meta en
la Figura (i) tras desplazarse en dirección norte. Nótese que en las dos últimas figuras (h) e (i), da la casualidad
que el robot se desplaza sólo una casilla pero en general ésto no es ası́, en un mismo movimiento el robot se podrı́a
desplazar hasta 3 casillas de una vez en un tablero de 5 × 5. Por ejemplo, si el robot de la esquina superior izquierda
de la Figura (a) se moviera al este o al sur avanzarı́a 3 casillas en un sólo movimiento.
En este ejercicio se pide:
1. (1 punto) Describir formalmente cómo representar un estado para un tamaño de tablero y número de robots
dados por N × M y R. Representar el estado de la Figura (a).
2. (1,5 punto) ¿Cuántos operadores definirı́as en este dominio? Descrı́belos de manera informal. Según esta
definición de los operadores, ¿cuántos posibles sucesores tiene el estado de la Figura (a)?
3. (1 punto) ¿Cuál es el factor de ramificación mı́nimo que se puede dar en un nodo de un tablero de 5 × 5 y
6 robots? Dado que un robot puede llegar a moverse en 4 direcciones, ¿se podrı́a encontrar un nodo con un
factor de ramificación de 24?
4. (1,5 punto) Definir formalmente una heurı́stica admisible. ¿Cuál es el valor de la heurı́stica para los estados
mostrados en las figuras (d) y (g)? ¿Es esta heurı́stica muy informada?
Solución al problema 1
Para representar este dominio vamos a identificar cada celda por un sı́mbolo en vez de por sus coordenadas (x,y).
Para definir los predicados y las fórmulas pedidas, antes vamos a definir el dominio de las posibles variables a utilizar.
Para ello, definimos dos conjuntos: el conjunto de todas las celdas C y el conjunto B={nada,oro,laser,bomba} para
representar el contenido del brazo del robot.
1. Los predicados necesarios para definir el dominio son:
adyacente(c1,c2): Significa que la celda c1 es adyacente a la celda c2. c1, c2 ∈ C
robot(c,b): Significa que el robot está situado en la celda c sosteniendo en el brazo el objeto b. c ∈ C y
b∈B
oro(c): Significa que el oro está situado en la celda c. c ∈ C
laser(c): Significa que el láser está situado en la celda c. c ∈ C
bomba(c): Significa que hay una bomba en la celda c. c ∈ C
rocadura(c): Significa que en la celda c hay una roca dura. c ∈ C
rocablanda(c): Significa que en la celda c hay una roca blanda. c ∈ C
2. Las fórmulas bien formadas para representar las acciones del dominio son:
Acción de mover el robot:
∀c1, c2 ∈ C, b ∈ B, robot(c1, b) ∧ adyacente(c2, c1)∧ ∼ rocadura(c2)∧ ∼ rocablanda(c2) → robot(c2, b)
Acción de coger laser:
∀c ∈ C, robot(c, nada) ∧ laser(c) → robot(c, laser)∧ ∼ laser(c)
Acción de coger bomba:
∀c ∈ C, robot(c, nada) ∧ bomba(c) → robot(c, bomba)∧ ∼ bomba(c)
Acción de coger oro:
∀c ∈ C, robot(c, nada) ∧ oro(c) → robot(c, oro)∧ ∼ oro(c)
Acción de dejar laser:
∀c ∈ C, robot(c, laser) → robot(c, nada) ∧ laser(c)
Acción explotar bomba:
∀c1, c2 ∈ C, robot(c1, bomba) ∧ adyacente(c2, c1) ∧ rocablanda(c2) → robot(c1, nada)∧ ∼ rocablanda(c2)
Acción disparar laser roca :
∀c1, c2 ∈ C, robot(c1, laser) ∧ adyacente(c2, c1) ∧ (rocadura(c2) ∨ rocablanda(c2)) → robot(c1, nada)∧ ∼
rocadura(c2)∧ ∼ rocablanda(c2)∧ ∼ oro(c2)
Solución al problema 2
Para este caso se puede optar por seguir representando las celdas con un identificador y definir un marco o una
plantilla para representar las celdas que son adyacentes o bien representar las celdas por coordenadas (x,y) y verificar
en las reglas cuando dos celdas son adyacentes. De todas formas, en caso de elegir esta segunda representación es
necesario definir un marco o una plantilla que represente las coordenadas. En la solución propuesta definimos cada
celda por sus coordenadas (x,y) y definimos una plantilla que nos permita definir un hecho por cada celda.
1. La jerarquı́a de marcos del SP que minimiza el no de reglas es:
(defclass POSICIONABLE (is-a INITIAL-OBJECT)
(slot x (type INTEGER))
(slot y (type INTEGER)))
;;Marco para representar los objetos que puede coger el robot
;;Conviene poner el tipo de objeto que es para luego en la acción de coger
;;especificarlo por seguir las especificaciones del dominio de planificación. Aunque no es necesario
;;También se podrı́a poner un slot para representar si el objeto está sujeto por el robot. Pero si
;;en la acción de coger se borra la instancia no es necesario
(defclass OBJETO (is-a POSICIONABLE)
(slot id (type SYMBOL))
(slot tipo (type SYMBOL)
(allowed-values oro laser bomba)))
(defclass ORO
(is-a OBJETO))
(defclass LASER (is-a OBJETO))
(defclass BOMBA (is-a OBJETO))
(defclass ROCA (is-a POSICIONABLE))
(defclass ROCA-DURA (is-a ROCA))
(defclass ROCA-BLANDA (is-a ROCA))
(defclass ROBOT (is-a POSICIONABLE)
;;contiene el id del objeto sujeto por el robot o el sı́mbolo nada si está vacio
(slot brazo (type SYMBOL) (default nada))
)
2. Con la jerarquı́a anterior serı́a suficiente una regla para modelar las tres acciones de coger:
(defrule coger-objeto
?rob <- (object (is-a ROBOT) (x ?x) (y ?y) (brazo nada))
?obj <- (object (is-a OBJETO) (x ?x) (y ?y) (id ?id) (tipo ?t))
=>
(modify-instance ?rob (brazo ?id))
(unmake-instance ?obj)
(printout t "Coger " ?t " de la posición: (" ?x "," ?y ") " crlf))
Solución al problema 3
1. Una posible forma para representar los estados es utilizando marcos. Se podrı́a definir un marco abstracto
ROBOT con 3 atributos, el identificador, y las coordenada x e y que representan la posición del robot en el
tablero. Se definirı́an 2 marcos hijos de ROBOT para diferenciar entre el robot rojo y los azules. Formalmente
los marcos necesarios para representar los estados serı́an:
Atributo
x
y
id
ROBOT
es-un:
Posibles valores/Valor Valor omisión
entero 1..N
entero 1..M
sı́mbolo
Descripción
posición en X del robot
posición en Y del robot
identificador del robot
ROJO
es-un: ROBOT
AZUL
es-un: ROBOT
El estado de la Figura (a) se representarı́a definiendo 5 instancias de AZUL y una de ROJO. Si se elige como
origen de coordenadas el punto (1,1) en la esquina superior izquierda las instancias serı́an:
Atributo
x
y
id
Robot-rojo
instancia-de: ROJO
Posibles valores/Valor
3
4
rr
Cardinalidad
1..1
1..1
1..1
Atributo
x
y
id
Robot-1
instancia-de: AZUL
Posibles valores/Valor
1
1
r1
Cardinalidad
1..1
1..1
1..1
Atributo
x
y
id
Robot-2
instancia-de: AZUL
Posibles valores/Valor
5
1
r2
Cardinalidad
1..1
1..1
1..1
Atributo
x
y
id
Robot-3
instancia-de: AZUL
Posibles valores/Valor
3
2
r3
Cardinalidad
1..1
1..1
1..1
Atributo
x
y
id
Robot-4
instancia-de: AZUL
Posibles valores/Valor
1
5
r4
Cardinalidad
1..1
1..1
1..1
Atributo
x
y
id
Robot-5
instancia-de: AZUL
Posibles valores/Valor
5
5
r5
Cardinalidad
1..1
1..1
1..1
2. Existe un único operador, mover(r, d), que mueve el robot r en la dirección d, para r ∈ ROBOT y
d ∈ {E, O, N, S}, donde E, O, N, S representan cada uno de los puntos cardinales (Este, Oeste, Norte, Sur)
respectivamente. Para simplificar la representación, se puede desdoblar en cuatro operadores, moverEste,
moverOeste, moverN orte y moverSur. Conceptualmente, las precondiciones de los cuatro operadores y sus
efectos son los mismos, aunque formalmente se pueden describir de manera distinta. La primera precondición
es que en la posición contigua en la que se mueve el robot no haya otro robot, pero que sı́ lo haya en alguna
posición posterior. El efecto del operador es que el robot termina en la posición anterior al primer robot que
se encuentre en su camino. Por ejemplo, el operador moverEste se definirı́a:
MoverEste(r1):
SI ∃r1, r2 ∈ ROBOT, r2.y = r1.y, (r2.x − 1) > r1.x, (@r ∈ ROBOT, r.y = r1.y, r.x < r2.x)
ENTONCES r1.x = r2.x − 1
De esta forma, el estado de la Figura (a) tiene los sucesores resultantes de aplicar las siguientes instanciaciones
de operadores:
Mover el robot rojo al norte: mover(rr, n)
Mover el robot 1 en dirección sur o este: mover(r1, s), mover(r1, e).
Mover el robot 2 en dirección oeste o sur: mover(2, o), mover(2, s)
Mover el robot 3 en dirección sur: mover(3, s).
Mover el robot 4 en dirección norte o este: mover(4, n), mover(4, e).
Mover el robot 5 en dirección oeste o norte: mover(5, o), mover(5, n)
Por tanto, tendrı́amos un total de 10 posibles sucesores
3. El factor de ramificación mı́nimo se darı́a cuando ningún robot se pueda mover. Un estado que cumple esta
condición en un tablero de tamaño 7 × 7 con 7 robot es, por ejemplo, un estado solución del problema de
las 7 reinas. Pero hay muchas configuraciones del tablero que cumplen que ningún operador es instanciable
y que son més accesibles. El factor de ramificación méximo nunca puede llegar a 24, porque es fécil ver que
es imposible que todos los robots se puedan mover en cualquier dirección a la vez. Bésicamente, si un robot
se puede mover en una dirección, por ejemplo, este, es porque hay otro que lo para, es decir, hay otro més al
este. Pero siempre habré un robot que sea el que més al este esté, y ese no podré ejecutar esa acción.
4. Construiremos una heurı́stica por relajación del problema original. Para ello, supongamos que cuando un
robot se desplaza en una dirección, podemos pararlo en el momento que deseemos. Por tanto, si asumimos
que la posición meta es la posición (xg , yg ), entonces h(n) = entero(xg 6= x1 ) + entero(yg 6= y1 ). Esta
heurı́stica es muy poco informada, y de hecho sólo puede tomar 2 valores distintos: 1 ó 2, en función de si el
robot ya esté colocado en la misma columna y/o en la misma fila que la posición meta. Por ejemplo, para el
estado de la Figura (d), la heurı́stica toma el valor 1, mientras que para el estado de la Figura (g) toma el
valor 2. La heurı́stica es admisible puesto que la hemos construido mediante relajación de restricciones.
Otra posible heurı́stica admisible algo más informada podrı́a ser h(n) = f 1 + f 2 + f 3, donde f 1 es una
función que estima los movimientos de robot rojo para llegar a la meta, f 2 estima los movimientos de un
robot azul para bloquear al robot rojo cuando alcance la meta, y f 3 es otra función que vale 1 si algún robot
azul está posicionado en la meta y 0 en casa contrario. f 1 podrı́a tomar 3 valores: 0 si el robot rojo está en
la posición < xg , yg >, 1 si está en la misma fila o columna que la meta, y 2 en caso contrario. De la misma
forma f 2 serı́a el mı́nimo de calcualr para cada robot azul una función similar que toma valor 0 si el robot
está situado en alguna de las cuatro casillas adyacentes a la meta, 1 si está en la misma fila o columna, y 2 en
caso contrario. Nótese, que en este caso si un robot azul está en la posición de la meta su valor serı́a 0 pero
para alcanzar la solución al problema tendrı́a que utilizar al menos un movimiento para dejar esa posición
libre para que la pueda ocupar el robot rojo, de ahı́ la razón de añadir f 3 en h(n). Formalmente:
h(n) = f 1(n) + f 2(n) + f 3(n)
(1)
Definimos la función hcoor con dos entradas: las coordenadas de un robot (x, y) y un conjunto de coordenadas
C metas:
hcoor((x, y), C):
IF (x, y) ∈ C THEN return 0 /*misma posición*/
ELSE IF ∃c ∈ C, c.x = x ∨ c.y = y THEN return 1 /*misma fila o columna*/
ELSE return 2
f 1(n) = hcoor((rojo.x, rojo.y), (xg , yg ))
(2)
f 2(n) = ∀azul ∈ AZU L, mı́n(hcoor((azul.x, azul.y), ((xg , yg ), (xg , yg −1), (xg , yg +1), (xg −1, yg ), (xg +1, yg ))))
(3)
f 3(n) = IF ∃azul ∈ AZU L, azul.x = xg ∧ azul.y = yg THEN 1 ELSE 0