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^[1] y el uso de la evaluación de consultas de estilo Prolog para resolver los problemas que surgen en estas aplicaciones.

Historia editar

El método de planificación propuesto en 1993 por Dimopoulos, Nebel y Köhler^[2] es un ejemplo temprano de programación de conjuntos de respuestas. Su enfoque se basa en la relación entre planes y modelos estables.^[3] Soininen y Niemelä ^[4] 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^[5] y en [Niemelä 1999].^[6] De hecho, la nueva terminología de "conjunto de respuestas" en lugar de "modelo estable" fue propuesta por primera vez por Lifschitz^[7] en un documento que aparece en el mismo volumen retrospectivo que el documento Marek-Truszczynski.

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

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*.^[8]^[9] 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

<head> :- <body> .

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

{p,q,r}.

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.^[10] Las reglas de elección pueden tratarse también como abreviaturas para fórmulas proposicionales bajo la semántica del modelo estable.^[11] 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

1{p,q,r}2.

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:

:- 2{p,q,r}.

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

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 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 usar en cuerpos de reglas con la misma semántica. Un literal condicional es de la forma:

p(X):q(X)

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,

q(1..2).
a :- 1 {p(X):q(X)}.

es una abreviatura de

q(1). q(2).
a :- 1 {p(1), p(2)}.

Generando modelos estables editar

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

% lparse ${filename} | smodels

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:

1{p,q,r}2.
s :- not p.

entonces el comando produce la salida

% lparse test | smodels 0
Answer: 1
Stable Model: q p 
Answer: 2
Stable Model: p 
Answer: 3
Stable Model: r p 
Answer: 4
Stable Model: q s 
Answer: 5
Stable Model: r s 
Answer: 6
Stable Model: r q s

Ejemplos de programas ASP editar

Coloración de grafos editar

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:

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 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

v(1..100). % 1,...,100 son vertices
e(1,55). % hay una arista desde el vertice 1 al 55
. . .

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 editar

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:

n {in(X) : v(X)}.
:- in(X), in(Y), v(X), v(Y), X!=Y, not e(X,Y), not e(Y,X).

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 editar

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.

{in(X,Y)} :- e(X,Y).

:- 2 {in(X,Y) : e(X,Y)}, v(X).
:- 2 {in(X,Y) : e(X,Y)}, v(Y).

r(X) :- in(0,X), v(X).
r(Y) :- r(X), in(X,Y), e(X,Y).

:- not 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 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 editar

En el procesamiento del lenguaje natural, el análisis basado en dependencias puede formularse como un problema ASP.^[12] 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.

% ********** sentencias de entrada **********
word(1, puella). word(2, pulchra). word(3, in). word(4, villa). word(5, linguam). word(6, latinam). word(7, discit).
% ********** lexico **********
1{ node(X, attr(pulcher, a, fem, nom, sg));
   node(X, attr(pulcher, a, fem, nom, sg)) }1 :- word(X, pulchra).
node(X, attr(latinus, a, fem, acc, sg)) :- word(X, latinam).
1{ node(X, attr(puella, n, fem, nom, sg));
   node(X, attr(puella, n, fem, abl, sg)) }1 :- word(X, puella).
1{ node(X, attr(villa, n, fem, nom, sg));
   node(X, attr(villa, n, fem, abl, sg)) }1 :- word(X, villa).
node(X, attr(linguam, n, fem, acc, sg)) :- word(X, linguam).
node(X, attr(discere, v, pres, 3, sg)) :- word(X, discit).
node(X, attr(in, p)) :- word(X, in).
% ********** reglas sintácticas **********
0{ arc(X, Y, subj) }1 :- node(X, attr(_, v, _, 3, sg)), node(Y, attr(_, n, _, nom, sg)).
0{ arc(X, Y, dobj) }1 :- node(X, attr(_, v, _, 3, sg)), node(Y, attr(_, n, _, acc, sg)).
0{ arc(X, Y, attr) }1 :- node(X, attr(_, n, Gender, Case, Number)), node(Y, attr(_, a, Gender, Case, Number)).
0{ arc(X, Y, prep) }1 :- node(X, attr(_, p)), node(Y, attr(_, n, _, abl, _)), X < Y.
0{ arc(X, Y, adv) }1 :- node(X, attr(_, v, _, _, _)), node(Y, attr(_, p)), not leaf(Y).
% ********** Garantizando que el grafo pueda tratarse como árbol **********
1{ root(X):node(X, _) }1.
:- arc(X, Z, _), arc(Y, Z, _), X != Y.
:- arc(X, Y, L1), arc(X, Y, L2), L1 != L2.
path(X, Y) :- arc(X, Y, _).
path(X, Z) :- arc(X, Y, _), path(Y, Z).
:- path(X, X).
:- root(X), node(Y, _), X != Y, not path(X, Y).
leaf(X) :- node(X, _), not arc(X, _, _).

Normalización del lenguaje y competencia ASP editar

El grupo de trabajo de estandarización ASP produjo una especificación de lenguaje estándar, llamada ASP-Core-2,^[13] 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 editar

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			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^[14]	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

Véase también editar

Referencias editar

↑ Baral, Chitta (2003). Knowledge Representation, Reasoning and Declarative Problem Solving. Cambridge University Press. ISBN 978-0-521-81802-5.
↑ Dimopoulos, Y.; Nebel, B.; Köhler, J. (1997). «Encoding planning problems in non-monotonic logic programs». En Steel, Sam; Alami, Rachid, eds. Recent Advances in AI Planning: 4th European Conference on Planning, ECP'97, Toulouse, France, September 24–26, 1997, Proceedings. Lecture Notes in Computer Science: Lecture Notes in Artificial Intelligence 1348. Springer. pp. 273-285. ISBN 978-3-540-63912-1. as Postscript
↑ Subrahmanian, V.S.; Zaniolo, C. (1995). «Relating stable models and AI planning domains». En Sterling, Leon, ed. Logic Programming: Proceedings of the Twelfth International Conference on Logic Programming. MIT Press. pp. 233-247. ISBN 978-0-262-69177-2. as Postscript
↑ Soininen, T.; Niemelä, I. (1998), Formalizing configuration knowledge using rules with choices (Postscript) (TKO-B142) .
↑ Marek, V.; Truszczyński, M. (1999). «Stable models and an alternative logic programming paradigm» (PDF). En Apt, Krzysztof R., ed. The Logic programming paradigm: a 25-year perspective. Springer. pp. 169-181. ISBN 978-3-540-65463-6.
↑ Niemelä, I. (1999). «Logic programs with stable model semantics as a constraint programming paradigm» (Postscript,gzipped). Annals of Mathematics and Artificial Intelligence 25 (3/4): 241-273. doi:10.1023/A:1018930122475.
↑ Lifschitz, V. (1999). Action Languages, Answer Sets, and Planning. InApt, 1999
↑ (Ph.D.). University of Bath. 2009. Falta el |título= (ayuda)
↑ Rogelio Davila. «AnsProlog, an overview» (PowerPoint).
↑ Niemelä, I.; Simons, P.; Soinenen, T. (2000). «Stable model semantics of weight constraint rules». En Gelfond, Michael; Leone, Nicole; Pfeifer, eds. Logic Programming and Nonmonotonic Reasoning: 5th International Conference, LPNMR '99, El Paso, Texas, USA, December 2–4, 1999 Proceedings. Lecture Notes in Computer Science: Lecture Notes in Artificial Intelligence 1730. Springer. pp. 317-331. ISBN 978-3-540-66749-0. as Postscript
↑ Ferraris, P.; Lifschitz, V. (January 2005). «Weight constraints as nested expressions». Theory and Practice of Logic Programming 5 (1–2): 45-74. arXiv:cs/0312045. doi:10.1017/S1471068403001923. as Postscript
↑ «Dependency parsing». Archivado desde el original el 15 de abril de 2015. Consultado el 15 de abril de 2015.
↑ «ASP-Core-2 Input Language Specification». Consultado el 14 de mayo de 2018.
↑ «DLV System company page». DLVSYSTEM s.r.l. Consultado el 16 de noviembre de 2011.

Enlaces externos editar

Datos: Q2852531

[1] Baral, Chitta (2003). Knowledge Representation, Reasoning and Declarative Problem Solving. Cambridge University Press. ISBN 978-0-521-81802-5.

[2] Dimopoulos, Y.; Nebel, B.; Köhler, J. (1997). «Encoding planning problems in non-monotonic logic programs». En Steel, Sam; Alami, Rachid, eds. Recent Advances in AI Planning: 4th European Conference on Planning, ECP'97, Toulouse, France, September 24–26, 1997, Proceedings. Lecture Notes in Computer Science: Lecture Notes in Artificial Intelligence 1348. Springer. pp. 273-285. ISBN 978-3-540-63912-1. as Postscript

[3] Subrahmanian, V.S.; Zaniolo, C. (1995). «Relating stable models and AI planning domains». En Sterling, Leon, ed. Logic Programming: Proceedings of the Twelfth International Conference on Logic Programming. MIT Press. pp. 233-247. ISBN 978-0-262-69177-2. as Postscript

[4] Soininen, T.; Niemelä, I. (1998), Formalizing configuration knowledge using rules with choices (Postscript) (TKO-B142) .

[5] Marek, V.; Truszczyński, M. (1999). «Stable models and an alternative logic programming paradigm» (PDF). En Apt, Krzysztof R., ed. The Logic programming paradigm: a 25-year perspective. Springer. pp. 169-181. ISBN 978-3-540-65463-6.

[6] Niemelä, I. (1999). «Logic programs with stable model semantics as a constraint programming paradigm» (Postscript,gzipped). Annals of Mathematics and Artificial Intelligence 25 (3/4): 241-273. doi:10.1023/A:1018930122475.

[7] Lifschitz, V. (1999). Action Languages, Answer Sets, and Planning. InApt, 1999

[8] (Ph.D.). University of Bath. 2009. Falta el |título= (ayuda)

[9] Rogelio Davila. «AnsProlog, an overview» (PowerPoint).

[10] Niemelä, I.; Simons, P.; Soinenen, T. (2000). «Stable model semantics of weight constraint rules». En Gelfond, Michael; Leone, Nicole; Pfeifer, eds. Logic Programming and Nonmonotonic Reasoning: 5th International Conference, LPNMR '99, El Paso, Texas, USA, December 2–4, 1999 Proceedings. Lecture Notes in Computer Science: Lecture Notes in Artificial Intelligence 1730. Springer. pp. 317-331. ISBN 978-3-540-66749-0. as Postscript

[11] Ferraris, P.; Lifschitz, V. (January 2005). «Weight constraints as nested expressions». Theory and Practice of Logic Programming 5 (1–2): 45-74. arXiv:cs/0312045. doi:10.1017/S1471068403001923. as Postscript

[12] «Dependency parsing». Archivado desde el original el 15 de abril de 2015. Consultado el 15 de abril de 2015.

[13] «ASP-Core-2 Input Language Specification». Consultado el 14 de mayo de 2018.

[dlvsystem.com-14] «DLV System company page». DLVSYSTEM s.r.l. Consultado el 16 de noviembre de 2011.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]