Decision making is an issue whose heyday has grown since the twentieth century with the beginning of the study of artificial intelligence. Among the topics of interest of the called decision making, we have the modeling of preferences, which is the main topic of this work. We give the basics of the Answer Set Programming theory (ASP), followed by a characterization of the ODLP programs and possible extensions of language, to end with a validation process that shows its usefulness to model problems where interfere options with some kind of preference on them. Resumen. La toma de decisiones es un tema cuyo auge ha crecido desde el siglo XX con el comienzo del estudio de la inteligencia artificial. Entre los temas de interés del llamado decision making, tenemos el modelado de preferencias, el cual es el tema principal de este trabajo. Se darán nociones básicas de la teoría de Answer Set Programming (ASP), seguido de una caracterización de los programas ODLP y sus posibles extensiones de lenguaje, para terminar con un proceso de validación que muestre su utilidad para modelar problemas donde interfieren opciones con algún tipo de preferencia sobre ellas.
En la vida diaria existen un gran número de situaciones donde es necesario elegir entre distintas opciones que se nos presentan. Por lo general, estas opciones vienen acompañadas con cierta jerarquía entre ellas que son resultado de las preferencias de cada persona. Tomemos como ejemplo el menú de un restaurante. Aquí existen varias opciones de platillos que serán elegidos de acuerdo a los gustos de cada persona. Así, supongamos que en el menú existen estos platillos de comida: {carne, pollo, pescado}; además, tiene estas dos opciones como bebida: {vino tinto, vino blanco}.
Si un cliente llega y nos dice que prefiere el pescado a la carne y la carne al pollo, añadido a que en caso de carne blanca entonces prefiere vino blanco y que prefiere vino tinto en caso de comer carne. La dificultad de estas preferencias se complica entre más alternativas se tenga en el menú. Si bien una persona realiza el proceso de elección sin razonarlo de esta forma, al momento de automatizarlo resultaría muy complejo sin el marco teórico que se presenta en este trabajo.
Aquí surgen varias preguntas al respecto. ¿Cómo podemos modelar este tipo de situación? ¿Qué pasaría si al llegar al restaurante nos dicen que se les acabo el pescado? ¿Cuál menú es el que mejor satisface las preferencias del cliente en esta situación? Aunque este ejemplo puede parecer sencillo de resolver, existen problemas de asignación de horarios en escuelas o de empresas que utilizan estas mismas ideas para resolverse y que requieren ser automatizados debido al número de reglas y variables que pueden llegar a tener.
Como veremos en este trabajo, el modelado en Answer Sets resulta útil para representar este tipo de problemas, con el empleo de proposiciones lógicas con disyunción ordenada, que serán definidos en las secciones siguientes.
Por otro lado, cabe mencionar que para el cálculo automático de los Answer Sets se ha utilizado un solver llamado DLV en línea, el cual está disponible en http://logic-lab.sourceforge.net/dlv.html. Además, todas las traducciones de los artículos de la lengua inglesa fueron realizadas por mi persona. 2
Es necesario caracterizar la forma de modelar problemas que ayuden a tomar
decisiones y encontrar la manera más adecuada para modelar estas situaciones. La
utilización de Answer Sets se ha incrementado en los últimos años con trabajos tan
importantes y demandados sobre teoría de juegos
El conocer mejor y el caracterizar el marco teórico nos brindará beneficios importantes no sólo en la lógica clásica per se, sino también repercute en las aplicaciones prácticas que se derivan. Tal es el caso de los agentes inteligentes, diagnósticos y teoría de juegos, por mencionar sólo algunos. 3
Caracterizar inferencia bajo sesgos y restricciones en Answer Sets Programming para determinar sus alcances y limitaciones.
En esta sección daremos una breve introducción sobre semántica de Answer Sets,
ya que es la herramienta que utilizaremos para el modelado de problemas con
preferencias. Para mayor detalle, puede consultar
Los programas lógicos tradicionales trabajan bajo el principio de “la suposición
del mundo cerrado”
Esta idea lleva a la necesidad de distinguir entre dos tipos de negaciones: la negación por falla (también llamada negación débil, denotada aquí por “¬”) que nos dice que no hay evidencia de que un átomo sea verdadero; y la negación clásica, o negación fuerte, que denotaremos aquí por “~”.
Definamos ahora el lenguaje de Answer Set Programming, ya que es el que nos permite trabajar en con los programas lógicos de nuestro interés.
Definición 1 (Lenguaje ASP para programas lógicos, ℒ ) En los siguiente, ℒ es un lenguaje de lógica proposicional con símbolos proposicionales: 0, 1, …; conectivos: “∧” (conjunción); disyunción, denotada por “∨”; “←” (derivación, también denotada como “→”); constantes proposicionales “⊤” (tautología); “⊥” (contradicción); “¬” (negación por falla o negación débil, también denotada por la palabra ; “~” (negación fuerte, equivalentemente denotada como “−”); símbolos auxiliares “(”, “)” (paréntesis). Los símbolos proposicionales son llamados átomos o proposiciones atómicas. Una literal es un átomo o un átomo negado fuertemente. Una regla es un par ordenado ( ) ← ( ).
Ahora podemos definir lo que es programa lógico extendido, que son los que nos permiten definir la semántica en Answer Sets para representar problemas donde se utilice la negación fuerte.
Definición 2 Un programa lógico extendido es un conjunto de reglas de la forma : 0 ← 1, … , , ¬ +1, … , ¬ , donde cada con 1 ≤ ≤ es una literal.
Para poder definir un Answer Set, necesitamos primero un par de conceptos. Llamamos un programa lógico básico a un programa extendido cuyas reglas no contienen negación por falla. Formalmente, decimos que un conjunto de literales de un programa básico Π es cerrado bajo Π si para cada ∈ Π, si se cumple que { 1, … , } ⊂ , entonces 0 ∈ . Al conjunto mínimo de átomos que es cerrado bajo Π lo denotaremos por (Π) y constituye el Answer Set de Π.
Para el caso general en donde Π es un programa extendido, definamos Π como el conjunto que se obtiene al eliminar: 1. cada regla que tenga una fórmula de la forma ¬L en Body(r) para alguna ∈ . 2. Todas las fórmulas de la forma ¬ de ( ) de las reglas restantes.
Como se puede observar, el programa Π que se obtiene es un programa básico, por lo que ya está definido su answer set. Por tanto, si ambos conjuntos coinciden, entonces decimos que es un answer set de Π. Es decir, el answer set de Π se caracteriza por
(Π ) = . Diremos que un answer set es consistente si no contiene un átomo y su negación fuerte a la vez.
En palabras informales, podemos decir que un answer set de Π es un conjunto de literales tales que todos sus elementos son verdaderos el programa Π. Es decir, son todas esas literales que son conclusiones del programa. Veamos el siguiente ejemplo ilustrativo:
Ejemplo 1 Sea Π1 el programa definido por las siguientes reglas:
← ← ¬
De acuerdo con la definición de Answer Set, concluimos que el único que existe para Π1 es {q}. 5
En
Con la introducción de este conectivo, se puede definir un nuevo tipo de
programa lógico, que es una generalización de un programa extendido. Las siguientes
ocho definiciones fueron obtenidas de
Definición 3 Un programa lógico con disyunción ordenada (ODLP por sus siglas en inglés) es un conjunto de reglas de la forma r:
C1 ⃗×⃗ … ⃗×⃗ Cn ← A1, … , Am, ¬B1, … , ¬Bk, donde cada Ci (1 ≤ i ≤ n), Aj (1 ≤ j ≤ m), Bl(1 ≤ l ≤ k), son literales. Note que un programa lógico extendido es un caso particular donde n = 1.
Ejemplo 2 Sea R el programa con disyunción ordenada que se compone de las siguientes reglas: r1: r2:
A ⃗×⃗ B ← ¬C.
B ⃗×⃗ C ← ¬D.
La definición de Answer Set para un ODLP es distinta a la ya definida para un programa extendido. Ésta se define por medio de programas separados.
Definición 4 Sea r: C
1 ⃗×⃗ … ⃗×⃗ Cn ← Body una regla. Para k ≤ n, definamos la késima opción de r como: rk: C
k ← Body ∪ {¬C1, … , ¬Ck−1}.
Definición 5 Sea P un ODLP. Decimos que P′ es un programa separado de P si se obtiene al remplazar cada regla de P por una de sus opciones.
Para ilustrar mejor estas dos definiciones, continuemos con nuestro Ejemplo 2. Como cada regla de R sólo tiene dos opciones, entonces se obtienen cuatro programas separados.
A ← ¬C
B ← ¬D B ← ¬C, ¬A
B ← ¬D
A ← ¬C C ← ¬D, ¬B B ← ¬C, ¬A C ← ¬D, ¬B
Como se puede observar, los programas separados no contienen disyunción ordenada, por tanto, para estos programas sin disyunción ya hemos definido sus answer sets. Esto nos lleva a la siguiente definición.
Definición 6 Sea P un ODLP. Un conjunto de literales X es un answer set de P si es un answer set consistente de un programa separado de P.
Nuevamente del Ejemplo 2, tenemos tres answer sets de P resultantes de los programas separados: {A, B}, {B}, {C}. La primera pregunta que nos podemos hacer es sobre cuál de estas tres opciones es preferible en el programa. Por lo tanto, es necesario definir un criterio para establecer qué answer set satisface mejor cada regla del programa.
Definición 7 Sea S un answer set de un ODLP P. Decimos que S satisface la regla r (denotado por degs(r)):
C1 ⃗×⃗ … ⃗×⃗ Cn ← A1, … , Am, ¬Bn, … , ¬Bk.
Con grado 1 si Aj ∉ S para algún j o Bi ∈ S para algún i.
Con grado j, 1 ≤ j ≤ n, si todos los Al ∈ S, ningún Bi ∈ S y j = min{r | Cr ∈ S}.
Con esta definición, podemos ver que si llamamos S1 = {A, B}, S2 = {B}, S3 = {C} a los answer set del Ejemplo 2, tenemos que: deg 1( 1) = 1 deg 1( 2) = 1 deg 2( 1) = 2 deg 2( 2) = 1 deg 3( 1) = 1 deg 3( 2) = 2
A partir de estos grados de satisfacción, se pueden definir ciertos criterios para
decidir cuál answer set es preferible sobre otro. En
Para las siguientes tres definiciones, consideremos P un ODLP y S1, S2 dos answer sets de P. Además, definamos Si(P) como el conjunto de reglas en P que se satisfacen por S con grado i. Así, continuando con el Ejemplo 2, tenemos que S11(R) = {r1, r2}, S12(R) = ∅, S21(R) = {r2}, S22(R) = {r1}, S31(R) = {r1}, S32(R) = {r2}.
Definición 8 Decimos que S1 es preferido por cardinal a S2 (denotado por S1 >c S2) si y sólo si existe un grado i tal que |S1i(P)| > |S2i(P)| y para toda j < i, |S1j(P)| = |S2j(P)|.
Es decir, este criterio compara la cantidad de reglas en los conjuntos de grados de satisfacción. Así, tenemos que en el Ejemplo 3, 1 > 2 y que 1 > 3 ya que el cardinal de 11( ) es mayor que el de cualquier otro conjunto de grado de satisfacción. Además, se cumple que 2 y 3 son igualmente preferidos por cardinal ya que | 2 ( )| = | 3 ( )| para ∈ {1,2}.
Definición 9 Decimos que 1 es inclusión-preferido a 2 (denotado por 1 > 2) si y sólo si existe una tal que 2 ( ) ⊂ 1 ( ) y para toda < se cumple que 1 ( ) = 2 ( ).
Este criterio no compara la cantidad de reglas de los conjuntos, sino compara la contención entre los conjuntos de grados de satisfacción. Nuevamente en el Ejemplo 3, tenemos que 21( ) ⊂ 11( ) y que 31( ) ⊂ 11( ) y por tanto 1 > 2 y 1 > 3. Tanto 2 como 3 son igualmente preferidos por inclusión ya que no es posible establecer la contención de conjuntos en esos casos.
Definición 10 Decimos que S1 es Pareto-preferido a S2 (denotado por S1 >p S2) si y sólo si existe r ∈ P tal que degS1(r) < degS2(r) y para ninguna r′ ∈ P, degS1(r′) > degS2(r′).
Este criterio utiliza los grados de satisfacción de las reglas para encontrar una regla cuyo grado de satisfacción sea menor en uno de los answer set, pero que para ninguna otra regla el grado sea mayor. Finalmente, en el Ejemplo 3 se cumple que S1 > p S2 y S1 >p S3 ya que el grado de satisfacción de ambas reglas es 1 para S1, mientras que en S2 y S3 alguna de las dos reglas tiene grado de satisfacción igual a 2.
La siguiente proposición nos habla sobre la relación que existe entre estos tres
distintos criterios. Puede encontrarse en
Proposición 1 Sean 1 y 2 answer sets de un ODLP . Entonces 1 > 2 implica 1 > 2 y además 1 > 2 implica 1 > 2.
Ejemplo 3 Supongamos que quiere adquirir un automóvil de agencia, el cual puede ser un carro, una camioneta o una pick-up. Además, supongamos que puede escoger entre transmisión automática y transmisión estándar. Aquí se presentan las preferencias entre las distintas opciones. 1: carro ⃗×⃗ camioneta ⃗×⃗ pick-up. 2: estándar ⃗×⃗ automático. 3: automático ← pick-up.
Donde la regla número tres nos dice que si nuestra elección es una pick-up, entonces la queremos automática.
Como r1 tiene tres opciones y r2 tiene dos, por tanto resultan seis programas separados. carro estándar automático ← pick-up carro automático ← ¬estandar automático ← pick-up camioneta ← ¬carro estándar automático ← pick-up camioneta ← ¬carro automático ← ¬estandar automático ← pick-up pick-up ← ¬carro, ¬camioneta estándar automático ← pick-up pick-up ← ¬carro, ¬camioneta automático ← ¬estandar automático ← pick-up
Utilizando un solver DLV, encontramos que existen seis distintos answer sets, que son los siguientes:
S1 = {carro, estándar}; S2 = {camioneta, estándar} S3 = {carro, automático}; S4 = {camioneta, automático} S5 = {pick-up, automático}; S6 = {pick-up, estándar, automático}
De acuerdo a la Definición 7, la siguiente tabla nos muestra el grado de satisfacción para cada regla según cada answer set.
1 2 3 rios, ninguno de los tres aplica para distinguir cuál de los dos es preferible. La pregunta aquí es ¿Qué otro criterio puede utilizarse para elegir entre estos dos answer sets? 6
Como se puede observar en el Ejemplo 3, los tres criterios que presentamos en este trabajo resultan útiles en unos casos, pero existen otros en donde nos son suficientes, como al agregar la restricción r4 al programa. Por tanto, es necesario buscar nuevos criterios que permitan aplicarse a situaciones donde intervienen preferencias y restricciones. A pesar de esto, hemos confirmado que la semántica en Answer Sets es una herramienta útil para modelar sesgos y restricciones. 7
La solución de los problemas donde intervienen preferencias puede resultar difícil de encontrar sin las herramientas adecuadas. Como acabamos de ilustrar en el Ejemplo 3, el modelado en Answer Sets resulta una opción viable para la resolución de este tipo de problemas. Además, con esta misma teoría pueden abordarse problemas más complejos donde intervengan un número significativamente mayor de reglas y de opciones. Otra ventaja es el uso de solver como DLV o PSmodels, que permitan automatizar los cálculos necesarios. Por otro lado, es importante continuar la investigación para resolver las cuestiones donde los criterios de elección del answer set preferente lleguen a fallar.