Programación de conjuntos de respuestas
# Programación de conjuntos de respuestas

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 la computación de modelos estables y los solucionadores de conjuntos de respuestas (programas para generar modelos estables) se utilizan para realizar búsquedas. 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 a la representación del conocimiento y el uso de la evaluación de consultas de estilo Prolog para resolver los problemas que surgen en estas aplicaciones.

## Historia

El método de planificación propuesto en 1993 por Dimopoulos, Nebel y Köhler es un ejemplo temprano de programación de conjuntos de respuestas. Su enfoque se basa en la relación entre planes y modelos estables. Soininen y Niemelä aplicaron lo que ahora se conoce como programación de conjunto de respuestas al problema de la configuración del producto. Marek y Truszczyński identificaron el uso de solucionadores de conjuntos de respuestas para la búsqueda como un nuevo paradigma de programación en un documento que apareció en una perspectiva de 25 años sobre el paradigma de programación lógica publicado en 1999 y en [Niemelä 1999]. De hecho, la nueva terminología de "conjunto de respuestas" en lugar de "modelo estable" fue propuesta por primera vez por Lifschitz en un documento que aparece en el mismo volumen retrospectivo que el documento Marek-Truszczynski.

## Lenguaje de programación de conjuntos de respuestas: AnsProlog

Lparse es el nombre del programa que se creó originalmente como una herramienta de symbol grounding para los smodels solucionadores de conjuntos de respuestas. El lenguaje que acepta Lparse ahora se llama comúnmente AnsProlog*, Ahora se utiliza de la misma manera que en muchos otros solucionadores del conjunto de respuestas, incluyendo Assat, broche, cmodels, GNT, nomore++ y pbmodels. ( dlv es una excepción; la sintaxis de los programas ASP escritos para dlv es un poco diferente)

Un programa AnsProlog consta de reglas de la forma

El símbolo :- ("if") se descarta si <body> está vacío; tales reglas se llaman hechos. El tipo más simple de reglas Lparse son las reglas con restricciones.

Otra construcción útil incluida en este lenguaje es la elección. Por ejemplo, la regla de elección

dice: elige arbitrariamente cuál de los átomos $p,q,r$ se incluirán en el modelo estable. El programa lparse que contiene esta regla de elección y ninguna otra regla tiene 8 modelos estables: todos los subconjuntos arbitrarios de $\{p,q,r\}$. La definición de un modelo estable se generalizó a programas con reglas de elección. Las reglas de elección pueden tratarse también como abreviaturas para fórmulas proposicionales bajo la semántica del modelo estable. Por ejemplo, la regla de elección anterior se puede ver como una forma abreviada de la conjunción de tres fórmulas "de terceros excluidos":

    $(p\lor \neg p)\land (q\lor \neg q)\land (r\lor \neg r).$

El lenguaje de lparse nos permite también escribir reglas de elección "restringidas", como

Esta regla dice: elige al menos 1 de los átomos $p,q,r$, 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

    $(p\lor \neg p)\land (q\lor \neg q)\land (r\lor \neg r)$
       $\land \,(p\lor q\lor r)\land \neg (p\land q\land r).$

Los límites de cardinalidad también se pueden usar en el cuerpo de una regla, por ejemplo:

Agregar esta restricción a un programa Lparse elimina los modelos estables que contienen al menos 2 de los átomos. $p,q,r$. El significado de esta regla puede ser representado por la fórmula proposicional

       $\neg ((p\land q)\lor (p\land r)\lor (q\land r)).$

Las variables (en mayúscula, como en Prolog) se usan 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

tiene el mismo significado que

El programa

es una abreviatura de

Un rango tiene la forma:

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 manera compatible. Por ejemplo, el hecho

es un atajo para

Los rangos también se pueden usar en cuerpos de reglas con la misma semántica.

Un literal condicional es de la forma:

Si la extensión de q es {q (a1); q (a2); ... ; q (aN)}, la condición anterior es semánticamente equivalente a escribir p (a1), p (a2), ..., p (aN) en lugar de la condición. Por ejemplo,

es una abreviatura de

## Generando modelos estables

Para encontrar un modelo estable del programa Lparse almacenado en el archivo ${filename} usamos el comando

La opción 0 le indica a los smodels que busquen todos los modelos estables del programa. Por ejemplo, si el archivo test contiene las reglas:

entonces el comando produce la salida

## Ejemplos de programas ASP

### Coloración de grafos

Una $n$-coloración de un grafo $G=\left\langle V,E\right\rangle$ es una función $\mathrm {color} :V\to \{1,\dots ,n\}$ tal que $\mathrm {color} (x)\neq \mathrm {color} (y)$ por cada par de vértices adyacentes $(x,y)\in E$ . Nos gustaría usar ASP para encontrar una $n$ -coloración de un grafo dado (o determinar que no existe).

Esto se puede lograr utilizando el siguiente programa Lparse:

La línea 1 define que los números. $1,\dots ,n$ sean colores. De acuerdo con la regla de elección en la línea 2, un color único $i$ debe asignarse a cada vértice $x$ . La restricción en la línea 3 prohíbe asignar el mismo color a los vértices $x$ y $y$ si hay un borde que los conecta.

Si combinamos este archivo con una definición de $G$, como

y ejecutamos smodels en él, con el valor numérico de $n$ especificado en la línea de comando, luego los átomos de la forma $\mathrm {color} (\dots ,\dots )$ en la salida de smodels representará una $n$-coloración de $G$.

El programa en este ejemplo ilustra la estructura de "generar y evaluar" que a menudo se encuentra 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 .

### Clan grande

Un clan en un grafo es un conjunto de vértices adyacentes por pares. El siguiente programa lparse encuentra un clan de tamaño $\geq n$ en un gráfico dado, o determina que no existe:

Este es otro ejemplo de la organización de "generar y evaluar". La regla de elección en la línea 1 "genera" todos los conjuntos que consisten en $\geq n$ vértices La restricción en la línea 2 "elimina" los conjuntos que no son clanes.

### Ciclo hamiltoniano

Un ciclo hamiltoniano en un grafo dirigido es un ciclo que pasa a través de cada vértice del grafo exactamente una vez. El siguiente programa Lparse se puede usar para encontrar un ciclo hamiltoniano (si existe) en un grafo dirigido dado; Suponemos que 0 es uno de los vértices.

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 usa el predicado auxiliar. $r(x)$ ("$x$ es accesible desde 0") para prohibir vértices que no satisfagan esta condición. Este predicado se define de forma recursiva en las líneas 4 y 5.

Este programa es un ejemplo de una 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".

### Análisis de dependencia

En el procesamiento del lenguaje natural, el análisis basado en dependencias puede formularse como un problema ASP. El siguiente código analiza la oración latina "Puella pulchra in villa linguam latinam discit" ("la niña 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 enraizado ordenado linealmente.

## Normalización del lenguaje y competencia ASP

El grupo de trabajo de estandarización ASP produjo una especificación de lenguaje estándar, llamada ASP-Core-2, hacia el cual convergen los sistemas ASP recientes. ASP-Core-2 es el lenguaje de referencia para la Competencia de programación del conjunto de respuestas, en el que los solucionadores de ASP se comparan periódicamente con una serie de problemas de referencia.

## Comparación de implementaciones

Los primeros sistemas, tales como Smodels, usaban backtracking para encontrar soluciones. A medida que la teoría y la práctica de los solucionadores SAT booleanos evolucionaron, se construyeron varios solucionadores ASP sobre los solucionadores SAT, incluidos ASSAT y Cmodels. Estos convirtieron la fórmula ASP en propuestas SAT, aplicaron el solucionador SAT y luego volvieron a convertir las soluciones a la forma ASP. Los sistemas más recientes, como Clasp, utilizan un enfoque híbrido, utilizando algoritmos controlados por conflictos inspirados por SAT, sin conversión completa en una forma de lógica booleana. Estos enfoques permiten mejoras significativas en el rendimiento, a menudo en un orden de magnitud, sobre los algoritmos de retroceso anteriores.

El proyecto Potassco actúa como un paraguas para muchos de los sistemas nombrados a continuación, incluyendo clasp, grounding systems como gringo, sistemas incrementales (iclingo), solucionadores de restricciones (clingcon), lenguaje de acción para compiladores ASP (coala), implementaciones distribuidas de MPI (claspar) y muchos otros.

La mayoría de los sistemas admiten variables pero solo indirectamente, forzando el grounding, 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 causar una explosión combinatoria de cláusulas; por lo tanto, los sistemas que realizan grounding sobre la marcha podrían tener una ventaja.

| Plataforma | Plataforma | Plataforma | Características | Características | Características | Características | Características | Mecánica |
| - | - | - | - | - | - | - | - | - |
| Nombre | OS | Licencia | Variables | Símbolos de función | Conjuntos explícitos | Listas explícitas | Soporte disyuntivo (reglas de elección) | |
| ASPeRiX Archivado el 8 de noviembre de 2016 en Wayback Machine. | Linux | GPL | Sí | | | | No | Grounding sobre la marcha |
| ASSAT | Solaris | Freeware | | | | | Sí | Basado en solucionadores SAT |
| Clasp Answer Set Solver | Linux, macOS, Windows | Licencia MIT | Sí, en Clingo | Sí | No | No | Sí | incremental, inspirado en un solucionador SAT (dirigido por conflictos) |
| Cmodels | Linux, Solaris | GPL | Requiere grounding | | | | Sí | incremental, inspirado en un solucionador SAT (dirigido por conflictos). |
| delSAT | Linux, macOS, Windows ( máquina virtual Java ) | Licencia MIT | Requiere grounding | | | | | incremental, inspirado en un solucionador SAT (dirigido por conflictos). Soporta resolución de problemas probabilísticos y sampling de conjuntos de respuesta. |
| DLV | Linux, macOS, Windows | Libre para uso educacional no comercial y académico y para organizaciones sin fines de lucro | Sí | Sí | No | No | Sí | No compatible con Lparse |
| DLV-Complex | Linux, macOS, Windows | GPL | | Sí | Sí | Sí | Sí | Construido sobre DLV - no compatible con Lparse |
| GnT | Linux | GPL | Requiere grounding | | | | Sí | Construido sobre smodels |
| nomore ++ | Linux | GPL | | | | | | Combinación basada en reglas y literales. |
| Platypus | Linux, Solaris, Windows | GPL | | | | | | distribuido, multithread |
| Pbmodels | Linux | ? | | | | | | pseudo-booleano |
| Smodels | Linux, macOS, Windows | GPL | Requiere grounding | No | No | No | No | |
| Smodels-cc Archivado el 15 de noviembre de 2015 en Wayback Machine. | Linux | ? | Requiere grounding | | | | | Basado en SAT-solucionador; smodels con cláusulas de conflicto. |
| Supr | Linux | ? | | | | | | Basado en SAT-solucionador |
