Programació de conjunts de respostes
La programació de conjunts de respostes (ASP) és una forma de programació declarativa orientada a problemes de cerca difícils (principalment NP-hard). Es basa en la semàntica del model estable (conjunt de respostes) de la programació lògica. A ASP, els problemes de cerca es redueixen a calcular models estables, i s'utilitzen solucionadors de conjunts de respostes (programes per generar models estables) per fer la cerca. El procés computacional emprat en el disseny de molts solucionadors de conjunts de respostes és una millora de l'algorisme DPLL i, en principi, sempre acaba (a diferència de l'avaluació de consultes Prolog, que pot conduir a un bucle infinit).
En un sentit més general, ASP inclou totes les aplicacions de conjunts de respostes a la representació i raonament del coneixement [1] i l'ús de l'avaluació de consultes a l'estil Prolog per resoldre problemes que sorgeixen en aquestes aplicacions.
Història[modifica]
Un primer exemple de programació de conjunts de respostes va ser el mètode de planificació proposat el 1997 per Dimopoulos, Nebel i Köhler.[2] El seu enfocament es basa en la relació entre plans i models estables. El 1998 Soininen i Niemelä van aplicar el que ara es coneix com a programació de conjunts de respostes al problema de la configuració del producte.[2] El 1999, el terme "programació del conjunt de respostes" va aparèixer per primera vegada en un llibre The Logic Programming Paradigm com el títol d'una col·lecció de dos articles.[2] El primer d'aquests articles va identificar l'ús de solucionadors de conjunts de respostes per a la cerca com un nou paradigma de programació.[3] Aquell mateix any Niemelä també va proposar "programes lògics amb semàntica de model estable" com a nou paradigma.[4]
Llenguatge de programació del conjunt de respostes AnsProlog[modifica]
Lparse és el nom del programa que es va crear originalment com a eina de connexió a terra (front-end) per al conjunt de respostes solucionador smodels. El llenguatge que accepta Lparse s'anomena ara AnsProlog, abreviatura de Answer Set Programming in Logic.[5] Ara s'utilitza de la mateixa manera en molts altres solucionadors de conjunts de respostes, com ara assat, clasp, cmodels, gNt, nomore++ i pbmodels. (dlv és una excepció; la sintaxi dels programes ASP escrits per a dlv és una mica diferent.)
Normalització ASP[modifica]
El grup de treball d'estandardització d'ASP va produir una especificació de llenguatge estàndard, anomenada ASP-Core-2, [6] cap a la qual convergeixen els sistemes ASP recents. ASP-Core-2 és el llenguatge de referència per al Concurs de programació del conjunt de respostes, en què els solucionadors d'ASP es comparen periòdicament amb una sèrie de problemes de referència.
Comparació d'implementacions[modifica]
Els primers sistemes, com els smodels, utilitzaven la marxa enrere per trobar solucions. A mesura que la teoria i la pràctica dels solucionadors SAT booleans van evolucionar, es van construir diversos solucionadors ASP a sobre dels solucionadors SAT, inclosos ASSAT i Cmodels. Aquests van convertir la fórmula ASP en proposicions SAT, van aplicar el solucionador SAT i després van tornar a convertir les solucions a la forma ASP. Els sistemes més recents, com ara Clasp, utilitzen un enfocament híbrid, utilitzant algorismes basats en conflictes inspirats en SAT, sense convertir-se completament en una forma lògica booleana. Aquests enfocaments permeten millores significatives del rendiment, sovint per un ordre de magnitud, respecte als algorismes de retrocés anteriors.
Referències[modifica]
- ↑ Baral, Chitta. Knowledge Representation, Reasoning and Declarative Problem Solving (en anglès). Cambridge University Press, 2003. ISBN 978-0-521-81802-5.
- ↑ 2,0 2,1 2,2 Lifschitz, Vladimir Proceedings of the 23rd National Conference on Artificial Intelligence, 3, 13-07-2008, pàg. 1594–1597.
- ↑ Marek, V. «Stable models and an alternative logic programming paradigm». A: Apt. The Logic programming paradigm: a 25-year perspective (PDF). Springer, 20 May 1999, p. 169–181. ISBN 978-3-540-65463-6.
- ↑ Niemelä, I. (Postscript,gzipped) Annals of Mathematics and Artificial Intelligence, 25, 3/4, November 1999, pàg. 241–273. DOI: 10.1023/A:1018930122475.
- ↑ Rogelio Davila. «AnsProlog, an overview» (PowerPoint) (en anglès).
- ↑ «ASP-Core-2 Input Language Specification» (en anglès). [Consulta: 14 maig 2018].