Browsing by Author "Perri, Simona"

Now showing 1 - 3 of 3

Design and implementation of a modern ASP grounder
(2018-01-19) Zangari, Jessica; Leone, Nicola; Calimeri, Francesco; Perri, Simona
Answer Set Programming (ASP) is a declarative programming paradigm proposed in the area of non-monotonic reasoning and logic programming in the late '80 and early '90. Thanks to its expressivity and capability of dealing with incomplete knowledge, ASP that became widely used in AI and recognized as a powerful tool for Knowledge Representation and Reasoning (KRR). On the other hand, its high expressivity comes at the price of a high computational cost, thus requiring reliable and high-performance implementations. Throughout the years, a signi cant e ort has been spent in order to de ne techniques for an e cient computation of its semantics. In turn, the availability of e cient ASP systems made ASP a powerful tool for developing advanced applications in many research areas as well as in industrial contexts. Furthermore, a signi cant amount of work has been carried out in order to extend the basic language and ease knowledge representation tasks with ASP, and recently a standard input language, namely ASP-Core-2, has been de ned, also with the aim of fostering interoperability among ASP systems. Although di erent approaches for the evaluation of ASP logic programs have been proposed, the canonical approach, which is adopted in mainstream ASP systems, mimics the de nition of answer set semantics by relying on a grounding module (grounder), that generates a propositional theory semantically equivalent to the input program, coupled with a subsequent module (solver ) that applies propositional techniques for generating its answer sets. The former phase, called grounding or instantiation, plays a key role for the successful deployment in real-world contexts, as in general the produced ground program is potentially of exponential size with respect to the input program, and therefore the subsequent solving step, in the worst case, takes exponential time in the size of the input. To mitigate these issues, modern grounders employ smart procedures to obtain ground programs signi cantly smaller than the theoretical instantiation, in general. This thesis focuses on the ex-novo design and implementation of a new modern and e cient ASP instantiator. To this end, we study a series of techniques geared towards the optimization of the grounding process, questioning the techniques employed by modern grounders with the aim of improving them and introducing further optimization strategies, which lend themselves to the integration into a generic grounder module of a traditional ASP system following a ground & solve approach. In particular, we herein present the novel system I-DLV that incorporates all these techniques leveraging on their synergy to perform an e cient instantiation. The system features full support to ASP-Core-2 standard language, advanced exibility and customizability mechanisms, and is endowed with extensible design that eases the incorporation of language upi dates and optimization techniques. Moreover, its usage is twofold: besides being a stand-alone grounder, it is also a full- edged deductive database engine. In addition, along with the solver wasp it has been integrated in the new version of the widespread ASP system DLV recently released.
Eccient evaluation of disjunctive logic programs
(2014-03-31) Catalano, Gelsomina; Leone, Nicola; Perri, Simona
Agli inizi degli anni ‘80, Jack Minker propose di accrescere la potenza della programmazione logica consentendo l’utilizzo della disgiunzione nelle teste delle regole e specificando come l’assunzione di mondo chiuso potesse essere estesa al linguaggio risultante, chiamato Programmazione Logica Disgiuntiva (DLP) [Minker, 1982; 1994]. Pi`u tardi, Michael Gelfond e Vladimir Lifschitz fornirono una semantica per la DLP, detta Answer Set Semantics [Gelfond and Lifschitz, 1991], che ha ricevuto larghi consensi nella comunit`a scientifica ed `e ora generalmente adottata per la DLP (detta anche Answer Set Programming – ASP). In accordo a tale semantica un programma logico disgiuntivo pu`o avere pi`u modelli alternativi (ma anche nessuno) ognuno corrispondente a una possibile visione del mondo rappresentato dal programma. Il linguaggio per la rappresentazione della conoscenza DLP `e molto espressivo in un senso matematicamente preciso; la DLP pu`o rappresentare ogni problema nella classe di complessit`a §P 2 (NPNP ) [Eiter et al., 1997b]. Dunque, sotto assunzioni ampiamente accettate, la DLP risulta strettamente pi`u espressiva della programmazione logica normale (senza disgiunzione), la cui espressivit`a `e limitata alle propriet`a decidibili in NP. L’espressivit`a della Programmazione Logica Disgiuntiva, ha importanti implicazioni pratiche, poich`e esistono problemi che possono essere rappresentati tramite un programma logico disgiuntivo, ma che non `e possibile esprimere con programmi logici senza disgiunzione, considerata la loro complessit`a [Eiter et al., 1997b]. Inoltre, la disgiunzione consente di rappresentare in modo pi`u semplice e naturale problemi di classi di complessit`a pi`u bassa. La DLP, con la Answer Set Semantics, `e oggi ampiamente riconosciuta come uno strumento potente per la rappresentazione della conoscenza e il ragionamento di senso comune [Baral and Gelfond, 1994; Lobo et al., 1992; Wolfinger, 1994; Eiter et al., 1999; Gelfond and Lifschitz, 1991; Lifschitz, 1996; Minker, 1994; Baral, 2002]. L’elevata complessit`a della DLP ha scoraggiato per molti anni la realizzazione di sistemi che implementassero tutte le caratteristiche di tale linguaggio. Dopo alcuni anni di ricerca sia teorica che algoritmica, oggi esistono diversi sistemi che supportano la DLP o parte di essa. Oltre ai sistemi di programmazione logica (non disgiuntivi) Smodels [Simons et al., 2002] e ASSAT [Lin and Zhao, 2002], sono disponibili anche alcuni sistemi di programmazione logica (disgiuntiva): DLV [Leone et al., 2006], GnT [Janhunen et al., 2003], and cmodels-3 [Lierler, 2005]. 3 In questa tesi ci concentriamo sul sistema DLV, che `e riconosciuto essere lo stato dell’arte della Programmazione Logica Disgiuntiva. DLV `e ampiamente sfruttato in tutto il mondo sia a scopo di ricerca che didattico. Per esempio, `e stato impiegato al CERN, il Laboratorio Europeo di Fisica delle Particelle di Ginevra, per un’applicazione di Basi di Dati deduttive che coinvolge la manipolazione di conoscenza complessa su basi di dati di grandi dimensioni. La compagnia polacca Rodan Systems S.A. sfrutta DLV in uno strumento per scoprire le manipolazioni dei prezzi e l’uso non autorizzato di informazioni confidenziali. Noi crediamo che la forza di DLV – la sua espressivit`a e l’ implementazione solida – lo renda attrattivo per tali applicazioni complesse. Anche dal punto di vista dell’efficienza, esso `e competitivo con i pi`u avanzati sistemi in quest’area come confermano i recenti confronti e valutazione delle prestazioni [Leone et al., 2006; Dix et al., 2003; Arieli et al., 2004], e i risultati della Prima Competizione di Sistemi Answer Set Programming http://asparagus.cs. uni-potsdam.de/contest/, in cui DLV `e risultato vincitore per le categorie DLP e MGS Competition (detta anche categoria “Royal”). Lo sviluppo di DLV `e iniziato nel 1996 al Politecnico di Vienna, nell’ambito di un progetto finanziato dalla Austrian Science Funds (FWF); oggi, DLV `e oggetto di una cooperazione internazionale tra l’Universit`a della Calabria e il Politecnico di Vienna. Il presente lavoro di tesi `e incentrato sullo studio della Programmazione Logica Disgiuntiva e l’ottimizzazione del sistema DLV, che implementa la DLP. I nostri studi hanno evidenziato che negli ultimi anni, la disponibilit`a di sistemi DLP affidabili, ha indotto a sfruttare la DLP in diverse aree applicative, ma i sistemi attuali non sono sufficientemente efficienti per molte di queste applicazioni. Questo lavoro affronta questo aspetto, proponendosi di superare questa limitazione, migliorando l’efficienza dei sistemi DLP e del sistema DLV tramite il progetto e l’implementazione di nuove tecniche di ottimizzazione. I moduli della maggior parte dei sistemi DLP operano su un’istanziazione ground del programma in input, cio`e un programma che non contiene alcuna variabile, ma `e semanticamente equivalente all’input originale [Eiter et al., 1997c]. Ogni programma P in input, inizialmente sottoposto alla cosiddetta procedura di istanziazione (detta anche istanziatore) che calcola, a partire da P, un programma ground P0 semanticamente equivalente. Poich`e questa fase pu`o essere molto costosa, avere un buon istanziatore `e un aspetto cruciale dei sistemi DLP. La ragione `e dovuta al fatto che ogni atomo di ciascuna regola pu`o essere istanziato utiliz4 zando ogni costante dell’Universo di Herbrand del programma, con una evidente esplosione esponenziale. L’istanziatore dovrebbe essere in grado di produrre un programma ground P0 avente gli stessi answer set di P e tale che: (i) P0 sia calcolato efficientemente da P, e (ii) P0 sia il pi`u piccolo possibile, e quindi possa essere valutato pi`u efficientemente da un solver DLP. Alcune applicazioni della DLP in aree emergenti come la gestione della conoscenza e l’integrazione delle informazioni, in cui devono essere processate grandi quantit`a di dati, hanno reso evidente la necessit`a di migliorare significativamente gli istanziatori DLP. La nostra attenzione `e stata rivolta al modulo di instanziazione di DLV, investigando nuove possibili direzioni per aumentarne l’efficienza. In particolare, in questa tesi, presentiamo due proposte per migliorare la procedura di istanziazione: ² Una nuova tecnica di Backjumping per l’istanziatore di DLV e ² Nuove tecniche di Indicizzazione per l’istanziatore di DLV Di seguito descriviamo brevemente queste due linee di ricerca. Backjumping. Proponiamo di sfruttare tecniche di backjumping che riduce la taglia del programma ground generato e ottimizza il tempo di esecuzione necessario a produrlo. In particolare, data una regola r che deve essere resa ground, tale algoritmo sfrutta informazioni semantiche e strutturali su r, per calcolare efficientemente le istanze ground di r, evitando la generazione di regole “inutili”. Cio`e per ogni regola r si calcola solo un sottoinsieme rilevante delle sue istanze ground, preservandone la semantica. Implementiamo questo algoritmo in DLV e conduciamo un’attivit`a di sperimentazione su un’ampia collezione di problemi. I risultati sperimentali sono molto positivi: la nuova tecnica migliora sensibilmente l’efficienza del sistema DLV su molte classi di problemi. Indicizzazione. Proponiamo di adoperare tecniche di indicizzazione per migliorare le performance della procedura di istanziazione di DLV, cio`e tecniche per il progetto e l’implementazione di strutture dati che permettano di accedere pi`u efficientemente a grandi datasets. In particolare, adattiamo al nostro contesto, una tecnica classica di indicizzazione sul primo argomento e proponiamo una strategia 5 di indicizzazione “on demand” in base alla quale gli indici non sono predeterminati, ma piuttosto vengono calcolati su un argomento qualsiasi durante la valutazione (e solo se sfruttabili). In pi`u definiamo due euristiche che possono essere usate per stabilire l’argomento pi`u appropriato da indicizzare, quando esistono diverse possibilit`a. Inoltre, implementiamo le tecniche di indicizzazione proposte in DLV e confrontiamo sperimentalmente le nostre strategie su una collezione di problemi provenienti da diversi domini comprese anche istanze di problemi reali. Il quadro generale risultante dagli esperimenti `e molto positivo: - Tutte le tecniche proposte e testate permettono di ottenere notevoli miglioramenti per l’esecuzione dell’istanziazione. - Lo schema di indicizzazione on demand d`a risultati migliori rispetto al classico schema sul primo argomento in un numero maggiore di casi e le performance migliorano particolarmente quando viene utilizzata una buona euristica. In definitiva, i metodi proposti migliorano sensibilmente l’efficienza dell’ istanziatore di DLV, consentendo l’utilizzo del sistema anche in applicazioni dataintensive. Comunque, per verificare ulteriormente la potenza del nuovo istanziatore conduciamo una profonda analisi sperimentale per confrontarlo con gli altri due pi`u popolari istanziatori, Lparse [Niemel¨a and Simons, 1997; Syrj¨anen, 2002] e GrinGo [Gebser et al., 2007b]. L’analisi conferma che, il nuovo istanziatore ha performance migliori degli altri su tutti i problemi testati, mentre il vecchio mostra performance simili agli altri. I risultati presentati in questa tesi sono rilevanti anche per altri due aspetti: da una parte, l’istanziatore di DLV pu`o essere sfruttato proficuamente da altri sistemi che non hanno un istanziatore proprio, per esempio ASSAT [Lin and Zhao, 2002] e Cmodels [Lierler and Maratea, 2004; Babovich, since 2002]. Infatti, questi sistemi possono usare DLV per ottenere il programma ground (lanciando DLV con l’opzione “-instantiate”), e poi applicare le proprie procedure per la valutazione del programma ground; d’altra parte, tutti i metodi proposti sono abbastanza generali e quindi, possono essere facilmente adattati per essere integrati nella fase di calcolo di altri istanziatori. In realt`a la nostra tecnica di backjumping `e stata gi`a integrata in altri due istanziatori, GrinGo e FO+ [Wittocx et al., 2008], con buoni risultati. Le buone performance di GrinGo in alcuni degli esperimenti condotti, infatti, sono dovuti all’utilizzo della nostra tecnica. 6 I principali contributi della tesi possono essere riassunti come segue: 1. Studiamo la DLP, la sua complessit`a e il suo utilizzo per la rappresentazione della conoscenza e il ragionamento non monotono. 2. Progettiamo un nuovo metodo, basato su una tecnica di backjumping, che consente di ridurre sia la taglia dell’istanziazione dei programmi DLP che il tempo necessario per generarla. Implementiamo il metodo proposto in DLV e conduciamo un’attivit`a di sperimentazione. 3. Definiamo due nuove strategie di indicizzazione, per ottimizzare il tempo di istanziazione di DLV. Inoltre, implementiamo il metodo proposto nel sistema DLV ed effettuiamo un’analisi sperimentale. 4. Confrontiamo l’istanziatore di DLV con altri due istanziatori, Lparse e GrinGo e discutiamo i risultati.
Tools and Techniques for Easing the Application of Answer Set Programming
(2018-01-19) Fuscà, Davide; Leone, Nicola; Calimeri, Francesco; Perri, Simona
Answer Set Programming (ASP) is a well-established declarative problem solving paradigm; it features high expressiveness and the ability to deal with incomplete knowledge, so it became widely used in AI and it is now recognized as a powerful tool for knowledge representation and reasoning (KRR). Thanks to the expressive language and the availability of diverse robust systems, Answer Set Programming has recently gained popularity and has been applied fruitfully to a wide range of domains. This made clear the need for proper tools and interoperability mechanisms that ease the development of ASP-based applications. Also, the spreading of ASP from a strictly theoretical ambit to more practical aspects requires additional features for easing the interoperability and integration with other software; furthermore, improving the performance of actual ASP system is crucial for allowing the use of the potential of ASP in new practical contexts. The contribution of this thesis aims at addressing such challenges; we introduce new tools and techniques for easing the application of ASP. In particular, we present EMBASP: a framework for the integration of ASP in external systems for general applications to different platforms and ASP reasoners. The framework features explicit mechanisms for two-way translations between strings recognisable by ASP solvers and objects in the programming language. Furthermore, we define proper means for handling external computations in ASP programs, and implement a proper framework for explicit calls to Python scripts via external atoms into the ASP grounder I-DLV. We also define and implement, into the same system, an additional framework for creating ad-hoc directives for interoperability and make use of it for providing some ready-made ones for the connection with relational and graph databases. Eventually, we work at improving the ASP computation, and present two new ASP systems: DLV2 and I-DLV+MS. DLV2 updates DLV with modern evaluation techniques, combining I-DLV with the solver wasp, while I-DLV+MS is a new ASP system that integrates I-DLV, with an automatic solver selector for inductively choose the best solver, depending on some inherent features of the instantiation produced by I-DLV.