La programación de conjuntos de respuestas ( ASP ) es una forma de programación declarativa orientada a problemas de búsqueda difíciles (principalmente NP-hard ) . Se basa en la semántica de modelos estables (conjunto de respuestas) de la programación lógica . En ASP, los problemas de búsqueda se reducen al cálculo de modelos estables, y los solucionadores de conjuntos de respuestas (programas para generar modelos estables) se utilizan para realizar la búsqueda. El proceso computacional empleado en el diseño de muchos solucionadores de conjuntos de respuestas es una mejora del algoritmo DPLL y, en principio, siempre termina (a diferencia de la evaluación de consultas de Prolog , que puede conducir a un bucle infinito ).
En un sentido más general, ASP incluye todas las aplicaciones de conjuntos de respuestas a la representación y razonamiento del conocimiento [1] [2] y el uso de la evaluación de consultas estilo Prolog para resolver problemas que surgen en estas aplicaciones.
Un ejemplo temprano de programación de conjuntos de respuestas fue el método de planificación propuesto en 1997 por Dimopoulos, Nebel y Köhler. [3] [4] Su enfoque se basa en la relación entre planes y modelos estables. [5] En 1998 Soininen y Niemelä [6] aplicaron lo que ahora se conoce como programación de conjuntos de respuestas al problema de la configuración del producto . [4] En 1999, el término "programación de conjuntos de respuestas" apareció por primera vez en un libro The Logic Programming Paradigm como título de una colección de dos artículos. [4] El primero de estos artículos identificó el uso de solucionadores de conjuntos de respuestas para la búsqueda como un nuevo paradigma de programación . [7] Ese mismo año Niemelä también propuso "programas lógicos con semántica de modelo estable" como un nuevo paradigma. [8]
Lparse es el nombre del programa que se creó originalmente como una herramienta de base (front-end) para el solucionador de conjuntos de respuestas smodels. El lenguaje que acepta Lparse ahora se denomina comúnmente AnsProlog, [9] abreviatura de Answer Set Programming in Logic . [10] Ahora se utiliza de la misma manera en muchos otros solucionadores de conjuntos de respuestas, incluidos assat, clasp, cmodels, gNt, nomore++ y pbmodels. (dlv es una excepción; la sintaxis de los programas ASP escritos para dlv es algo diferente).
Un programa AnsProlog consta de reglas de la forma
< cabeza > :- < cuerpo > .El símbolo :-("si") se omite si <body>está vacío; dichas reglas se denominan hechos . El tipo más simple de reglas de Lparse son las reglas con restricciones .
Otro constructo útil incluido en este lenguaje es la elección . Por ejemplo, la regla de elección
{ p , q , r }.dice: elige arbitrariamente cuál de los átomos incluir en el modelo estable. El programa Lparse que contiene esta regla de elección y ninguna otra regla tiene 8 modelos estables: subconjuntos arbitrarios de . La definición de un modelo estable se generalizó a programas con reglas de elección. [11] Las reglas de elección también pueden tratarse como abreviaturas de fórmulas proposicionales bajo la semántica del modelo estable . [12] Por ejemplo, la regla de elección anterior puede verse como una abreviatura de la conjunción de tres fórmulas de " tercero excluido ":
El lenguaje de Lparse también nos permite escribir reglas de elección "restringidas", como
1 { p , q , r } 2.Esta regla dice: elige al menos 1 de los átomos , pero no más de 2. El significado de esta regla bajo la semántica del modelo estable está representado por la fórmula proposicional
Los límites de cardinalidad también se pueden utilizar en el cuerpo de una regla, por ejemplo:
:- 2 { p , q , r }.Al añadir esta restricción a un programa Lparse se eliminan los modelos estables que contienen al menos 2 de los átomos . El significado de esta regla se puede representar mediante la fórmula proposicional
Las variables (en mayúscula, como en Prolog ) se utilizan en Lparse para abreviar conjuntos de reglas que siguen el mismo patrón, y también para abreviar conjuntos de átomos dentro de la misma regla. Por ejemplo, el programa Lparse
p ( a ). p ( b ). p ( c ). q ( X ) :- p ( X ), X ! = a .tiene el mismo significado que
p ( a ). p ( b ). p ( c ). q ( b ). q ( c ).El programa
p ( a ). p ( b ). p ( c ). { q ( X ):- p ( X )} 2.es una abreviatura de
p ( a ). p ( b ). p ( c ). { q ( a ), q ( b ), q ( c )} 2.Un rango tiene la forma:
( inicio ... fin )donde inicio y fin son expresiones aritméticas de valor constante. Un rango es un atajo de notación que se utiliza principalmente para definir dominios numéricos de una manera compatible. Por ejemplo, el hecho
a ( 1..3 ).es un atajo para
a ( 1 ). a ( 2 ). a ( 3 ).Los rangos también se pueden utilizar en cuerpos de reglas con la misma semántica.
Un literal condicional tiene la forma:
p ( X ) : q ( X )Si la extensión de qes {q(a1), q(a2), ..., q(aN)}, la condición anterior es semánticamente equivalente a escribir {p(a1), p(a2), ..., p(aN)}en el lugar de la condición. Por ejemplo,
q ( 1..2 ). a :- 1 { p ( X ) : q ( X )}.es una abreviatura de
q ( 1 ). q ( 2 ). a :- 1 { p ( 1 ), p ( 2 )}.Para encontrar un modelo estable del programa Lparse almacenado en el archivo ${filename}usamos el comando
% lparse ${ nombre_archivo } | smodels La opción 0 indica a smodels que busque todos los modelos estables del programa. Por ejemplo, si el archivo testcontiene las reglas
1 { p , q , r } 2. s :- no p .entonces el comando produce la salida
% lparse test | smodels 0 Respuesta: 1 Modelo estable: qp Respuesta: 2 Modelo estable: p Respuesta: 3 Modelo estable: rp Respuesta: 4 Modelo estable: qs Respuesta: 5 Modelo estable: rs Respuesta: 6 Modelo estable: rqs Una coloración de un gráfico es una función tal que para cada par de vértices adyacentes . Nos gustaría utilizar ASP para encontrar una coloración de un gráfico dado (o determinar que no existe).
Esto se puede lograr utilizando el siguiente programa Lparse:
c ( 1. . n ). 1 { color ( X , I ) : c ( I )} 1 :- v ( X ). :- color ( X , I ), color ( Y , I ), e ( X , Y ), c ( I ).La línea 1 define los números como colores. De acuerdo con la regla de elección de la línea 2, se debe asignar un color único a cada vértice . La restricción de la línea 3 prohíbe asignar el mismo color a los vértices y si hay una arista que los conecta.
Si combinamos este archivo con una definición de , como por ejemplo
v ( 1..100 ). % 1,...,100 son vértices e ( 1 , 55 ). % hay una arista de 1 a 55 . . .y ejecute smodels en él, con el valor numérico de especificado en la línea de comando, entonces los átomos del formulario en la salida de smodels representarán una coloración de .
El programa de este ejemplo ilustra la organización de "generación y prueba" que se encuentra a menudo en programas ASP simples. La regla de elección describe un conjunto de "soluciones potenciales" (un superconjunto simple del conjunto de soluciones para el problema de búsqueda dado). Le sigue una restricción que elimina todas las soluciones potenciales que no son aceptables. Sin embargo, el proceso de búsqueda empleado por smodels y otros solucionadores de conjuntos de respuestas no se basa en prueba y error .
Una camarilla en un grafo es un conjunto de vértices adyacentes por pares. El siguiente programa Lparse encuentra una camarilla de tamaño en un grafo dirigido dado o determina que no existe:
n { en ( X ) : v ( X )}.:- en ( X ), en ( Y ), X ! = Y , no e ( X , Y ).Este es otro ejemplo de la organización de generación y prueba. La regla de elección en la línea 1 "genera" todos los conjuntos que constan de vértices. La restricción en la línea 2 "elimina" los conjuntos que no son grupos.
Un ciclo hamiltoniano en un grafo dirigido es un ciclo que pasa por cada vértice del grafo exactamente una vez. El siguiente programa Lparse se puede utilizar para encontrar un ciclo hamiltoniano en un grafo dirigido dado si existe; suponemos que 0 es uno de los vértices.
{ en ( X , Y )} :- e ( X , Y ). :- 2 { en ( X , Y ) : e ( X , Y )}, v ( X ).:- 2 { en ( X , Y ) : e ( X , Y )}, v ( Y ).r ( X ) :- en ( 0 , X ), v ( X ).r ( Y ) :- r ( X ), en ( X , Y ), e ( X , Y ).:- no r ( X ), v ( X ).La regla de elección de la línea 1 "genera" todos los subconjuntos del conjunto de aristas. Las tres restricciones "eliminan" los subconjuntos que no son ciclos hamiltonianos. La última de ellas utiliza el predicado auxiliar (" es alcanzable desde 0") para prohibir los vértices que no satisfacen esta condición. Este predicado se define recursivamente en las líneas 6 y 7.
Este programa es un ejemplo de la organización más general "generar, definir y probar": incluye la definición de un predicado auxiliar que nos ayuda a eliminar todas las posibles soluciones "malas".
En el procesamiento del lenguaje natural , el análisis basado en dependencias se puede formular como un problema ASP. [13] El siguiente código analiza la oración en latín "Puella pulchra in villa linguam latinam discit", "la linda chica está aprendiendo latín en la villa". El árbol sintáctico se expresa mediante los predicados de arco que representan las dependencias entre las palabras de la oración. La estructura calculada es un árbol con raíz ordenado linealmente.
% ********** frase de entrada ********** palabra ( 1 , puella ). palabra ( 2 , pulchra ). palabra ( 3 , en ). palabra ( 4 , villa ). palabra ( 5 , linguam ). palabra ( 6 , latinam ). palabra ( 7 , discit ). % ********** léxico ********** 1 { nodo ( X , attr ( pulcher , a , fem , nom , sg )); nodo ( X , atributo ( pulcher , a , fem , abl , sg )) } 1 :- palabra ( X , pulchra ). nodo ( X , atributo ( latinus , a , fem , acc , sg )) : - palabra ( X , latinam ). 1 { nodo ( X , attr ( puella , n , fem , nom , sg )); nodo ( X , attr ( puella , n , fem , abl , sg )) } 1 :- palabra ( X , puella ). 1 { nodo ( X , attr ( villa , n , fem , nom , sg )); nodo ( X , attr ( villa , n , fem , abl , sg )) } 1 :- palabra ( X, villa ). nodo ( X , attr ( linguam , n , fem , acc , sg )) :- palabra ( X , linguam ). nodo ( X , attr ( discere , v , pres , 3 , sg )) :- palabra ( X , discit ). nodo ( X , attr ( in , p )) :- palabra ( X , in ). % ********** reglas sintácticas ********** 0 { arc ( X , Y , subj ) } 1 :- nodo ( X , attr ( _ , v , _ , 3 , sg )), nodo ( Y , attr ( _ , n , _ , nom , sg )). 0 { arc ( X , Y , dobj ) } 1 :- nodo ( X , attr ( _ , v , _ , 3 , sg )), nodo ( Y , attr ( _ , n , _ , acc , sg )). 0 { arc ( X , Y , attr ) } 1 :- nodo ( X , attr ( _ , n , Género , Caso , Número )), nodo ( Y , attr ( _ , a , Género , Caso, Número )). 0 { arc ( X , Y , prep ) } 1 :- nodo ( X , attr ( _ , p )), nodo ( Y , attr ( _ , n , _ , abl , _ )), X < Y . 0 { arc ( X , Y , adv ) } 1 :- nodo ( X , attr ( _ , v , _ , _ , _ )), nodo ( Y , attr ( _ , p )), no hoja ( Y ). % ********** garantizando la arbolidad del grafo ********** 1 { raíz ( X ) : nodo ( X , _ ) } 1. :- arco ( X , Z , _ ), arco ( Y , Z , _ ), X ! = Y . :- arco ( X , Y , L1 ), arco ( X , Y , L2 ), L1 ! = L2 . ruta ( X , Y ) :- arco ( X , Y , _ ). ruta ( X , Z ) :- arco ( X , Y , _ ), ruta ( Y , Z ). :- ruta ( X , X ). :- raíz ( X ), nodo ( Y, _ ), X ! = Y , no camino ( X , Y ). hoja ( X ) :- nodo ( X , _ ), no arco ( X , _ , _ ).El grupo de trabajo de estandarización de ASP elaboró una especificación de lenguaje estándar, denominada ASP-Core-2, [14] hacia la cual convergen los sistemas ASP más recientes. ASP-Core-2 es el lenguaje de referencia para la Competencia de Programación de Conjuntos de Respuestas, en la que los solucionadores ASP se evalúan periódicamente en relación con una serie de problemas de referencia.
Los primeros sistemas, como smodels, utilizaban el método de retroceso para encontrar soluciones. A medida que la teoría y la práctica de los solucionadores SAT booleanos evolucionaron, se crearon varios solucionadores ASP sobre los solucionadores SAT, incluidos ASSAT y Cmodels. Estos convertían la fórmula ASP en proposiciones SAT, aplicaban el solucionador SAT y luego convertían las soluciones nuevamente a la forma ASP. Los sistemas más recientes, como Clasp, utilizan un enfoque híbrido, utilizando algoritmos impulsados por conflictos inspirados en SAT, sin convertir completamente a una forma de lógica booleana. Estos enfoques permiten mejoras significativas del rendimiento, a menudo de un orden de magnitud, en comparación con los algoritmos de retroceso anteriores.
El proyecto Potassco actúa como un paraguas para muchos de los sistemas a continuación, incluyendo clasp , sistemas de conexión a tierra ( gringo ), sistemas incrementales ( iclingo ), solucionadores de restricciones ( clingcon ), lenguaje de acción para compiladores ASP ( coala ), implementaciones distribuidas de interfaz de paso de mensajes ( claspar ) y muchos otros.
La mayoría de los sistemas admiten variables, pero sólo de manera indirecta, al forzar la conexión a tierra, mediante el uso de un sistema de conexión a tierra como Lparse o gringo como interfaz. La necesidad de conexión a tierra puede provocar una explosión combinatoria de cláusulas; por lo tanto, los sistemas que realizan la conexión a tierra sobre la marcha pueden tener una ventaja. [15]
Las implementaciones de programación de conjuntos de respuestas basadas en consultas, como el sistema Galliwasp [16] y s(CASP) [17] evitan la conexión a tierra por completo mediante el uso de una combinación de resolución y coinducción .