ÍNDICE

TRANSPARENCIAS TEMA 1

Dirección del proceso de resolución de una meta

Construcción de Bases de Conocimientos en PROLOG

Máquina virtual Prolog toma como entrada à base de conocimientos (en forma clausal), y objetivo (también en forma clausal), generando una respuesta afirmativa en caso de que el objetivo se pueda demostrar aplicando conocimiento almacenado en base.

Uso de predicados recursivos: nuestro problema se expresa en términos de sí mismo aplicado sobre un conjunto de datos distintos que tiende a convertirse en el conjunto de datos que satisface el caso o casos triviales del proceso de recursión.

Consultas sobre la Base de Conocimientos

Cuando en la base de conocimientos sólo hay hechos

predicado1(arg1, ..., argN).

predicado2(arg1, ..., argN).

...

predicadoM(arg1, ..., argN).

Objetivo:

predicado2(arg1, ..., argN).

Cuando en la base de conocimientos hay hechos y reglas de inferencia no recursivas

pred1(arg1).

pred2(arg2).

pred3(arg1, arg2, arg3):-

pred1(arg1),

Aux is "operación sobre arg1",

pred2(aux),

arg3 is "operación entre arg1 y aux".

Objetivo:

"pred3(arg1, arg2, arg3)."

Cuando en la base de conocimientos hay hechos y reglas de inferencia recursivas

mcd(A,B,R):-A==B, R is A.

mcd(A,B,R):-A>B, Aux is A-B, mcd(Aux,B,R).

mcd(A,B,R):-A<B, Aux is B-A, mcd(A,Aux,R).

mcd(A,Aux,R):-mcd(B,A,R).

Objetivo:

"mcd(7, 5, R)."

EJEMPLO:

Construcción de una base de conocimientos para resolver objetivos o preguntas relacionadas con el código de la circulación de vehículos.

La aplicación va a permitir especificar un tipo de vehículo y las características de la vía por la que circula y nos informará sobre la velocidad máxima genérica que dicho vehículo puede alcanzar.

Características de la vía	Nombre de la vía
Vía interurbana señalizada con la señal S-1	Autopista
Vía interurbana señalizada con la señal S-1a	Autovía
Vía interurbana señalizada con la señal S-1b	Vía Rápida
Vía interurbana con dos o más carriles para cada sentido ó carril para facilitar el adelantamiento ó arcén pavimentado de, al menos, 1,5 metros de longitud	Carretera Convencional Buena
Vía interurbana que no cumple los requisitos de una carretera convencional buena.	Carretera Convencional Mala
Vía urbana	Vía Urbana
Vía interurbana que discurre por suelo urbano	Travesía

	Autopistas y Autovías	Vías Rápidas y Carreteras Convencionales Buenas	Carreteras Convencionales Malas	Vías Urbanas y Travesías
Turismos y Motocicletas	120	100	90	50
Autobuses y Vehículos Mixtos	100	90	80	50
Camiones y Vehículos Articulados	90	80	70	50
Automóviles con Remolque	80	80	70	50
Noveles	80	80	80	50

Experto de Autoescuela

predicates

maximo(string, string, integer)

via(integer, integer, string, string)

velocidad(string, integer, integer, string, integer)

nondeterm repeat

nondeterm pedirdatos

clauses

/* Definición de las velocidades genéricas de vehículos según la vía */

maximo("novel", "autopista", 80):-!.

maximo("novel", "autovia", 80):-!.

maximo("novel", "via_rapida", 80):-!.

maximo("novel", "ccb", 80):-!.

maximo("novel", "ccm", 80):-!.

maximo("turismo", "autopista", 120):-!.

maximo("motocicleta", "autopista", 120):-!.

maximo("vehiculomixto", "autopista", 100):-!.

maximo("autobus", "autopista", 100):-!.

maximo("camion", "autopista", 90):-!.

maximo("vehiculoarticulado", "autopista", 90):-!.

maximo("conjuntovehiculos", "autopista", 80):-!.

maximo(Veh, "autovia", R):-maximo(Veh, "autopista", R), !.

maximo("turismo", "ccb", 100):-!.

maximo("motocicleta", "ccb", 100):-!.

maximo("vehiculomixto", "ccb", 90):-!.

maximo("autobus", "ccb", 90):-!.

maximo("camion", "ccb", 80):-!.

maximo("vehiculoarticulado", "ccb", 80):-!.

maximo("conjuntovehiculos", "ccb", 80):-!.

maximo(Veh, "via_rapida", R):-maximo(Veh, "ccb", R),!.

maximo(Veh, "ccm", R):-maximo(Veh, "ccb", Auxi), R=Auxi-10, !.

maximo(Veh, "via_urbana", _):-

Veh<>"turismo",

Veh<>"motocicleta",

Veh<>"vehiculomixto",

Veh<>"autobus",

Veh<>"camion",

Veh<>"vehiculoarticulado",

Veh<>"conjuntovehiculos",

Veh<>"novel",

fail, !.

maximo(_, "via_urbana", 50):-!.

maximo(Veh, "travesia", R):-maximo(Veh, "via_urbana", R).

/* Definición de vía en función de sus características */

via(_, _, "autopista", "autopista"):-!.

via(_, _, Senal, Tipo):-Senal="autovia", Tipo="autovia", !.

via(_, _, Senal, Tipo):-Senal="viarapida", Tipo="via_rapida", !.

via(_, _, Senal, Tipo):-Senal="de_via_urbana", Tipo="via_urbana", !.

via(_, _, Senal, Tipo):-Senal="de_travesia", Tipo="travesia", !.

via(Arcen, _, "nohay", "ccb"):-Arcen >=150, !.

via(_, Carriles, "nohay", "ccb"):-Carriles>=2, !.

via(_, -1, "nohay", "ccb"):-!.

via(_, _, "nohay", "ccm").

/* Predicado de cálculo de velocidad en función del vehículo y las características

de la vía */

velocidad(Vehiculo, A, C, S , V):-via(A, C, S, Carretera),

maximo(Vehiculo, Carretera, V).

repeat.

repeat:-repeat.

pedirdatos:-repeat,

write("PETICIÓN DE DATOS (nohay=no hay dato concreto)"),

nl,

write("Especifica el tipo de vehículo, (turismo, motocicleta,

vehiculomixto, autobus, camion)"), nl,

write("(vehiculoarticulado, conjuntovehiculos, novel): "),

readln(V),

nl,

write("Especifica el tamaño del arcen: "), readint(A),

nl,

write("Especifica el número de carriles

(-1 para adelantamiento): "), readint(C),

nl,

write("Especifica señal (autopista, autovia, via_rapida): "),

readln(S),

velocidad(V, A, C, S , Velocidad), nl,

write("La velocidad máxima es: "), write(Velocidad), nl,

write("Continuar=Cualquier tecla, Salir=1"), nl,

readint(Tecla), nl, nl, nl,

Tecla=1.

goal

pedirdatos.

Definición y funcionamiento de la Máquina PROLOG

Intérprete Prolog es un demostrador de teoremas sobre Cláusulas de Horn que trabaja Top-Down, y que emplea Resolución Lineal con Función de Selección. La entrada al intérprete es un conjunto de cláusulas definidas C, junto con la especificación de la meta G0.

El proceso del intérprete consiste en una búsqueda incremental por backtracking en el espacio (organización en forma de árbol), de refutaciones posibles a G0 [Adarraga, 1994].

Unificación

La unificación se realiza, para cada predicado, de izquierda a derecha, y para cada conjunto de predicados, de arriba a abajo.

Se pueden unificar variables con constantes, siempre que la variable no esté instanciada. Si la variable está instanciada, el hecho de hacer unificación entre ambas se corresponde con la situación de unificación de dos constantes.

Para que dos constantes se puedan unificar ambas han de ser iguales.

Backtracking

El procedimiento de backtracking consiste en generar un árbol de búsqueda de todas las posibles resoluciones que puede tener la meta en función de la base de conocimientos.

El algoritmo itera hasta que encuentra una solución.

Cada vez que los predicados fallan y no son unificables se va generando una nueva rama hasta encontrar la solución deseada, de esta forma se va construyendo el árbol de búsqueda.

Puede ser que un problema se pueda resolver de varias formas. Es, por tanto, posible especificar que deseamos una nueva solución. El intérprete Prolog ignora la solución encontrada hasta ahora y construye el árbol de búsqueda hasta generar una nueva solución o encontrar que ésta no existe.

Cuando un predicado se demuestra en función de una llamada a sí mismo, la llamada se convierte en un subobjetivo casi idéntico al objetivo a cumplir, salvo por el conjunto de datos sobre el que se aplica. Cuando se consigue la demostración de los subobjetivos generados en el proceso de recursión, se produce lo que se denomina vuelta atrás de la recursión, que funciona igual que en cualquier lenguaje.

No hemos de confundir recursividad con backtracking.

Bibliografía

[Adarraga, 1994] Adarraga, Pablo. Zaccagnini José Luis. "Psicología e Inteligencia Artificial". Editorial Trotta. 1994.

[Giannesini, 1986] PROLOG. Addison-Wesley Iberoamericana, 1986.

[Russell, 1996] Russell, Stuart. Norvig, Peter. "Inteligencia Artificial. Un enfoque moderno". Editorial Prentice Hall. 1996.