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 del modelo estable (conjunto de respuestas) de la programación lógica . En ASP, los problemas de búsqueda se reducen a calcular modelos estables y para realizar la búsqueda se utilizan solucionadores de conjuntos de respuestas (programas para generar modelos estables). 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 Prolog , que puede conducir a un bucle infinito ).
En un sentido más general, ASP incluye todas las aplicaciones de conjuntos de respuestas para la representación y el razonamiento del conocimiento [1] [2] y el uso de 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 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 nuevo paradigma. [8]
Lparse es el nombre del programa que se creó originalmente como una herramienta básica (front-end) para los modelos de resolución de conjuntos de respuestas. El lenguaje que acepta Lparse ahora se llama comúnmente AnsProlog, [9] abreviatura de Programación de conjuntos de respuestas en lógica . [10] Ahora se usa de la misma manera en muchos otros solucionadores de conjuntos de respuestas, incluidos assat, broche, 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 elimina si <body>está vacío; tales reglas se llaman hechos . El tipo más simple de reglas Lparse son 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: elija 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 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 según 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 " intermedios excluidos ":
El lenguaje de Lparse también nos permite escribir reglas de elección "restringidas", como
1 { p , q , r } 2.Esta regla dice: elija 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 }.Agregar esta restricción a un programa Lparse elimina 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 colecciones de reglas que siguen el mismo patrón, y también para abreviar colecciones de átomos dentro de la misma regla. Por ejemplo, el programa Lparse
pag ( una ). pag ( segundo ). pag ( c ). q ( X ) :- p ( X ), X ! = un .tiene el mismo significado que
pag ( una ). pag ( segundo ). pag ( c ). q ( segundo ). q ( c ).El programa
pag ( una ). pag ( segundo ). pag ( c ). { q ( X ): - p ( X )} 2.es una abreviatura de
pag ( una ). pag ( segundo ). pag ( c ). { q ( a ), q ( b ), q ( c )} 2.Un rango es de la forma:
( inicio fin )donde inicio y fin son expresiones aritméticas de valores constantes. Un rango es un atajo de notación que se utiliza principalmente para definir dominios numéricos de forma compatible. Por ejemplo, el hecho
un ( 1..3 ).es un atajo para
un ( 1 ). un ( 2 ). un ( 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 un archivo ${filename}usamos el comando
% lparse ${ nombre de archivo } | modelos 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
% prueba de dispersión | 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 determinado (o determinar que no existe).
Esto se puede lograr usando 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. Según la regla de elección de la Línea 2, se debe asignar un color único a cada vértice . La restricción en la Línea 3 prohíbe asignar el mismo color a los vértices y si hay un borde que los conecta.
Si combinamos este archivo con una definición de , como
v ( 1..100 ). % 1,...,100 son vértices e ( 1 , 55 ). % hay una ventaja de 1 a 55 . . .y ejecuta smodels en él, con el valor numérico de especificado en la línea de comando, luego 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 suele encontrarse en programas ASP sencillos. La regla de elección describe un conjunto de "soluciones potenciales", un superconjunto simple del conjunto de soluciones al 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 gráfico es un conjunto de vértices adyacentes por pares. El siguiente programa Lparse encuentra un grupo de tamaño en un gráfico dirigido determinado o determina que no existe:
norte { en ( X ) : v ( X )}.:- en ( X ), en ( Y ), X ! = Y , no e ( X , Y ).Este es otro ejemplo de organización de generación y prueba. La regla de elección de la línea 1 "genera" todos los conjuntos formados por vértices. La restricción de la Línea 2 "elimina" los conjuntos que no son camarillas.
Un ciclo hamiltoniano en un gráfico dirigido es un ciclo que pasa por cada vértice del gráfico exactamente una vez. El siguiente programa Lparse se puede utilizar para encontrar un ciclo hamiltoniano en un gráfico dirigido dado, si existe; asumimos que 0 es uno de los vértices.
{ en ( X , Y )} : - mi ( 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 en la Línea 1 "genera" todos los subconjuntos del conjunto de aristas. Las tres restricciones "eliminan" los subconjuntos que no son ciclos hamiltonianos. El último de ellos utiliza el predicado auxiliar (" es accesible desde 0") para prohibir los vértices que no cumplan 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 de "generar, definir y probar": incluye la definición de un predicado auxiliar que nos ayuda a eliminar todas las soluciones potenciales "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 frase latina "Puella pulchra in villa linguam latinam discit", "la chica bonita está aprendiendo latín en la villa". El árbol de sintaxis 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íces ordenadas 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 , atributo ( puella , n , fem , nom , sg )); nodo ( X , atributo ( puella , n , fem , abl , sg )) } 1 : - palabra ( X , puella ). 1 { nodo ( X , atributo ( villa , n , fem , nom , sg )); nodo ( X , atributo ( villa , n , fem , abl , sg )) } 1 : - palabra ( X, villa ). nodo ( X , atributo ( linguam , n , fem , acc , sg )) : - palabra ( X , linguam ). nodo ( X , attr ( discere , v , pres , 3 , sg )) : - palabra ( X , discit ). nodo ( X , atributo ( en , p )) : - palabra ( X , en ). % ********** reglas sintácticas ********** 0 { arc ( X , Y , subj ) } 1 :- nodo ( X , attr ( _ , v , _ , 3 , sg )), nodo ( Y , attr ( _ , n , _ , nom , sg )). 0 { arco ( X , Y , dobj ) } 1 : - nodo ( X , atributo ( _ , v , _ , 3 , sg )), nodo ( Y , atributo ( _ , n , _ , acc , sg )). 0 { arco ( X , Y , atributo ) } 1 : - nodo ( X , atributo ( _ , n , Género , Caso , Número )), nodo ( Y , atributo ( _ , a , Género , Caso), Número )). 0 { arco ( X , Y , prep ) } 1 : - nodo ( X , atributo ( _ , p )), nodo ( Y , atributo ( _ , n , _ , abl , _ )), X < Y . 0 { arco ( X , Y , adv ) } 1 : - nodo ( X , atributo ( _ , v , _ , _ , _ )), nodo ( Y , atributo ( _ , p )), no hoja ( Y ). % ********** garantizando la arborescencia del gráfico ********** 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 ruta ( X , Y ). hoja ( X ) : - nodo ( X , _ ), no arco ( X , _ , _ ).El grupo de trabajo de estandarización de ASP produjo una especificación de lenguaje estándar, llamada ASP-Core-2, [14] hacia la cual están convergiendo los sistemas ASP recientes. ASP-Core-2 es el lenguaje de referencia para el concurso de programación de conjuntos de respuestas, en el que los solucionadores de ASP se comparan periódicamente con una serie de problemas de referencia.
Los primeros sistemas, como smodels, utilizaban el retroceso para encontrar soluciones. A medida que evolucionaron la teoría y la práctica de los solucionadores booleanos SAT , se construyeron varios solucionadores ASP sobre los solucionadores SAT, incluidos ASSAT y Cmodels. Estos convirtieron la fórmula ASP en proposiciones SAT, aplicaron el solucionador SAT y luego convirtieron las soluciones nuevamente al formato ASP. Los sistemas más recientes, como Clasp, utilizan un enfoque híbrido, utilizando algoritmos basados en conflictos inspirados en SAT, sin convertirse completamente a una forma de lógica booleana. Estos enfoques permiten mejoras significativas del rendimiento, a menudo de un orden de magnitud, con respecto a algoritmos de retroceso anteriores.
El proyecto Potassco actúa como un paraguas para muchos de los sistemas siguientes, incluido el cierre , los sistemas de conexión a tierra ( gringo ), los sistemas incrementales ( iclingo ), los solucionadores de restricciones ( clingcon ), el lenguaje de acción para los compiladores ASP ( coala ), las implementaciones distribuidas de la interfaz de paso de mensajes ( brochear ), y muchos otros.
La mayoría de los sistemas admiten variables, pero sólo indirectamente, forzando la conexión a tierra, utilizando 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 puesta a tierra sobre la marcha podrían tener una ventaja. [15]
Las implementaciones basadas en consultas de programación de conjuntos de respuestas, 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 .