Wissensverarbeitung und Informationssysteme

GCplp
Graphs and colorings for answer set programming with preferences

Kathrin Konczak and Torsten Schaub and Thomas Linke

Universität Potsdam, Institut für Informatik, {konczak, torsten, linke}@cs.uni-potsdam.de


Contents


Introduction

The integration of preferences into answer set programming constitutes an important practical device for distinguishing certain preferred answer sets from non-preferred ones. To this end, we elaborate upon rule dependency graphs and their colorings for characterizing a preference handling strategy found in the literature. We exemplarily develop an operational characterization of $<^D$-preferred answer sets in terms of operators on partial colorings. In analogy to the notion of a derivation in proof theory, our operational characterization is expressed as a (non-deterministically formed) sequence of colorings, gradually turning an uncolored graph into a totally colored one.

The GCplp system is divided in several components which read an ordered logic program out of a file, generate the ordered rule dependence graph (DG ), which represents the ordered logic program, and compute $<^D$- preserving admissible colorings , which corresponds to $<^D$- preserving answer sets [2] of ordered logic programs. The implementation is written for different Prolog systems like ECLiPSe, SICStus and SWI.

Architecture

The GCplp system consists of several components for computing $<^D$- preserving answer sets shown in Figure 1.

Figure 1: components of the GCplp system
\begin{figure} \begin{picture}(420, 180)(0, 0) \par \put(102, 80){\framebox (3... ...0,-1){40}} \put(352, 100){\vector(0,-1){40}} \end{picture} \end{figure}

After parsing the ordered logic program out of a file, the DG is constructed. For a better representation the DG is compiled into temporary files. Now a sequence of operators defined in [1] computes $<^D$- preserving admissible colorings of the DG , which corresponds to $<^D$- preserving answer sets of the ordered logic program.

Installation

It is important that you have correctly installed ECLiPSe, SICStus or SWI on your machine. Now you must download and unpack the GCplp files. 
> gunzip gcplp-1.0.tar.gz
> tar -xf gcplp-1.0.tar
After unpacking you find the source files in the /GCplp/Source directory. For starting the GCplp system call the gcplp.pl prolog file and select your prolog system. In the directory /GCplp/Examples are some ordered logic programs for testing the GCplp system. If you want to use the daVinci output you must install the daVinci interface for visualizing the DG (daVinci visualization tool).

Getting started

The best way to explain the use of the GCplp system is to consult an exemplary session under ECLiPSe prolog. We start the session in the /GCplp/Source directory. We proceed in the following way:
  1. Start ECLiPSe.

  2. Next load the GCplp system by typing [gcplp]. and <Return> for confirm the input. 
    [eclipse 1]: [gcplp].
    This loads all necessary files. 
    !!!!! Which Prolog are you working with?
!!!!! (enter number followed by ENTER)
!!!!! (0) ECLIPSe  (1) SWI  (2) Sicstus  (3) Exit
!!!!!
    Press 0 and confirm with <Return>. If you use an other system enter the corresponding value. 
    !!!!!  0
Flag prolog(eclipse) set
Flag output set
*************************************
ECLiPSe version of the GCplp system
*************************************

  .....

  3. For getting an overview of the flags type flags. 
    [eclipse 2]: flags.
output = on
prolog(eclipse) = on
prolog(swi) = off
prolog(sicstus) = off
daVinci = off

  4. In the next step we compute the preferred answer sets of an ordered logic program. Let us consider the following example:
    \begin{displaymath} \begin{array}{lrclccc} r_1: & p & \leftarrow & & r_3 & < ... ... nf& \leftarrow & p, \ensuremath{not}\; f &&&\\ \end{array} \end{displaymath} (1)

    Before computing the preferred answer sets of the program we must load the desired characterization, for example operational characterization I by typing cload(c1). 
    [eclipse 3]: cload(c1).

  5. Now we can call gcplp('../Examples/example.lp', 0). where the first parameter is the name of the normal logic program and the second value the number of preferred answer sets to search (0 stands for all preferred answer sets). 
    [eclipse 4]: gcplp('../Examples/example.lp', 0).
    This call returns conclusion about the number of preferred answer sets and choice points and the duration for computing the order preserving admissible colorings. 
    parse file ... ready

generate DG ... ready

precompile DG ... ready

computing preferred answer sets ...
D-Preferred Answer Set 1: { b, nf, p }

answer sets done


number of choice points    : 1
number of solutions        : 1  (for program ../Examples/example.lp)
duration                   : 0.0s

  6. For creating a daVinci file you must activate the daVinci flag. 
    [eclipse 6]: set_flag(daVinci).
Flag daVinci set

Operators

We have developed different operators for computing deterministic consequences ($P$, $U$), choices ($C$, $D$), and an operator ($H$) for preferred answer set checking. For more details see [1] .

Characterizations

To compute total colorings of DG, which corresponds to preferred answer sets, you have a lot of possibilities. Some of them are listed in Figure 2 and are explained in [1] .

Figure 2: different characterizations
\begin{figure}\par \begin{tabular}{\vert c\vert l\vert c\vert}\hline \begin{ta... ...end{tabular} & \texttt{cload(c4).} \par \end{tabular}\par \par \end{figure}

Download

Figure 3: list of files
\begin{figure}\par \begin{tabular}{\vert l\vert l\vert}\hline \textbf{Files} &... ...les} & contained some example files \ \hline \end{tabular}\par \end{figure}

Bibliography

1
K. Konczak, T. Schaub, and T. Linke.
Graphs and colorings for answer set programming with preferences: Preliminary report.
In M. De Voss and A. Provetti, editors, Proceedings of the Second International Workshop on Answer Set Programming (ASP'03), volume 78, pages 43-56, Messina, 2003. CEUR Workshop Proceedings.

2
T. Schaub and K. Wang.
A semantic framework for preference handling in answer set programming.
Theory and Practice of Logic Programming, 3(4-5):569-607, 2003.