Wissensverarbeitung und Informationssysteme

[Photo]

`noMoRe`
A Graph-Based System for Non-Monotonic Reasoning with Logic Programs under Answer Set Semantics

Thomas Linke

Andreas Bösel

Christian Anger

Martin Gebser

Kathrin Konczak

Download

Here you can download version 1.0 of the noMoRe system including examples (file nomore.tar.gz).
Download lparse (needed for dealing with variables).
Download daVinci (needed for visualization of ruel dependency graphs).
The former noMoRe release are still available¹.

Introduction

noMoRe is an answer set solver for propositional normal nested logic programs ( ). Those programs are sets of rules of the following form:

(1)

where are propositional atoms and are conjunctions of literals or (true) or (false). Here by a literal we mean either a propositional atom or the default negation of some propositional atom . For a rule of the form (1) and denote the sets and , respectively.

For computing answer sets of logic programs the dependencies between rules, heads and bodies given through a program play a crucial role. These dependencies can be represented as graphs; any graph representing some dependency relation for a program is called a program dependency graphs (PDGs).

noMoRe implements a novel graph-based paradigm to compute answer sets of by computing non-standard graph colorings of three different types of PDGs associated to a given logic program. More precisely, noMoRe deals with body-head-graphs ( -graphs) where the bodies and heads are the nodes of the graph, rule-head-graphs ( -graphs) where the rules and heads are the nodes of the graph, and rule-graphs ( -graphs), where the rules are the nodes of the graph. Accordingly the represented dependencies for -, - and -graphs are between bodies and heads, rules and heads and rules, respectively. Any of those graphs contains information about positive ( - and -arcs) and negative ( -arcs) dependencies between its nodes. Observe that the -graph for is a generalization of the rule dependency graph (RDG) initially defined for normal programs in [6,5].²

Clearly, -graphs should be the first choice, since they give the most compact representation of a program. In fact, in most cases -graphs also give the best computational results. However, for experimental reasons also the two other graph types are implemented. Formally, we define:
$\begin{definition}Let $P$ be a logic program. \par The \emph{BH-graph (body-h... ...math{\mathit{Body}(\r)}\xspace \}. \end{array}\end{displaymath}\end{definition}$
The a-colorings of correspond to the answer sets of . If is normal or normal with at most one positive body atom, the same holds for and , repectively. See [] for details.

Given a logic program noMoRe first computes the corresponding PDG. Next its a-colorings are computed. These are finally reinterpreted as answer sets of the underlying logic program. The core system was designed for propositional programs only. Thus, we have integrated different grounders (lparse and dlv ) in order to deal with variables. Because neither lparse nor dlv can hanlde normal nested programs, only normal programs can be processed, when variables are present. Furthermore, we have included an interface to the graph drawing tool daVinci [8] for visualization of PDGs and their colorings [4]. The noMoRe-system is implemented in ECLiPSe Prolog³.

Installation

In order to install noMoRe, you need to have a correctly installed ECLiPSe system on your machine. To use all features of the system, including the visual output of graphs, a correctly installed daVinci [8] is also required. If you want to use normal logic programs with variables you also need to have installed lparse ⁴. Installation under Unix/Linux then is very easy; you just need to unpack the file nomore.tar.gz. In order to install noMoRe type the following:

> gunzip nomore.tar.gz
> tar -xvf nomore.tar

This results in a new directory named noMoRe containing all necessary files.

If you detect any bugs or errors please send an e-mail to Thomas Linke.

Getting Started

The best way of getting started is to consult an exemplary session under ECLiPSe Prolog [1]. We start this session in the subdirectory noMoRe/Examples by invoking ECLiPSe . This has the advantage that we have direct access to the *.lp files which contain different exemplary logic programs. We proceed in the following way:

Start ECLiPSe .
Next load noMoRe by typing [nomore]. <Ret> to the prolog-prompt.
```
[eclipse 1]: [nomore].

...

nomore.pl  compiled traceable 28 bytes in 0.06 seconds

Yes (0.06s cpu)
[eclipse 2]:
```
This consults all necessary files and the actual flag settings (stored in file flags.ini) of the noMoRe system. In order to get a printout of the current flag settings you can type flags. to the prolog prompt any time after consluting the noMoRe source code.
```
[eclipse 2]: flags. 
----------- User Flags --------------
output     = on
lookahead  = on
backprop   = on
ignore     = off
v_operator = on
show       = off
animate    = off
ground     = off
asp_bh     = on
asp_rh     = off
asp_r      = off


Yes (0.00s cpu)

[eclipse 3]:
```
See Section 7 for details on how to change system behavior by setting or clearing binary noMoRe-flags.
Let us consider a small example program stored in file penguin.lp containing the following logic program:

(2)

With the command nomore/2 (see Section 7) the desired number of answer sets for the program of the given file are computed. noMoRe also gives information about the time used and about how many solutions were found and how many choices and assignments were needed in order to compute the answer sets of a given logic program.
```
[eclipse 3]: nomore('penguin.lp',0).
```
noMoRe now computes all answer sets (indicated through the zero as second argument of nomore/2) of logic program (2).
```
parsing file penguin.lp ...
5 rules and 0 preference successfully parsed
parsing done

computing answer sets ...

Answer Set 1: { bird, fly, penguin, wings }

Answer Set 2: { bird, nofly, penguin, wings }

answer sets done

---------------------------------------------
total number of assignments   : 33
total number of choices       : 1
---------------------------------------------

number of solutions        : 2  (for program penguin.lp)
duration                   : 0.0s

No (0.01s cpu)
[eclipse 4]:
```
It is also possible to give the number of answer sets to be computed, by giving a number as the second argument to the command nomore/2. For example, to compute only one answer set type nomore('penguin.lp',1).
For getting a visual of the RDG simply type set_flag(show) which sets the noMoRe-flag show. Repeat the last command: nomore('penguin.lp',1). Now noMoRe starts the graph drawing tool daVinci and sends the actual RDG to daVinci before the answer sets of penguin.lp are computed. Different kinds of animated coloring sequences are possible, depending on the current settings. See Section 8 for information on how to control the animated coloring sequences depicted in daVinci .

Other example files can be processed analogously.

Architecture

noMoRe computes answer sets of a normal nested logic program in two steps (see Figure 1).

**Figure 1:** The architecture of `noMoRe`.
$\begin{figure}\begin{center} \begin{pspicture}(-10,-13)(80,12) \psframe[fills... ...cline{E}{daVinci} \ncline{D}{F} \end{pspicture} \end{center}\par\end{figure}$

At first, the -graph for is computed according to the settings of flags asp_bh, asp_rh and asp_r. Secondly, the a-colorings are computed by an efficient coloring procedure. To read logic programs we use a parser and there is a separate part for interpretation of a-colorings into answer sets. For information and debugging purposes there is yet another part for visualizing PDGs using the graph drawing tool daVinci [8]. This feature is especially interesting for analyzing small programs (around 50 rules). Even if the core system was designed for propositional logic programs, it is possible to handle normal logic programs with variables. By setting the ground flag lparse [10] is used for grounding, and a file <name>.glp is created which contains the ground program corresponding to program <name>.lp⁵.

For an visualisation example, program (2) can be depicted as in Figure 2, that is, the actual rules are used as node labels. On the other hand, it is also possible to use the internal noMoRe symbols as node labels. Depending on the size of the program under consideration both settings are useful.

**Figure 2:** The rule graph of program (2) in two different drawing modes.
$\scalebox{0.6}{\includegraphics{penguin.ps}}$ $\scalebox{0.6}{\includegraphics{penguin1.ps}}$

Syntax

In general, noMoRe deals with propositional normal nested logic programs. The syntax accepted by the system is Prolog-like, except that noMoRe accepts each ground Prolog term as a propositional atom, e.g. and are both treated as propositional atoms. As indicated in the formal definition (1), conjunction is allowed in the body and in the head, whereas disjunction is only allowed in the body in order to form disjunctions of conjunctions as bodies. Each line beginning with a % is regarded as a comment line. For example, normal logic program (2) is represented by the following file:

       penguin.
       bird :- penguin.
       wings :- bird.
       fly :- bird, not nofly.
       nofly :- penguin, not fly.

For another example, we consider the rule with nested body. Rules like this can be expressed as

       a,b :- (c, not d);(e).

in noMoRe.

It is also possible to include so called integrity constraints as rules into a logic program. Integrity constraints have the form

        :- p1, ... ,pn.

Intuitively, an integrity constraint states that there should be no answer set which contains all of the atoms p1, ... ,pn.

Commands and Configuration

Working with logic programs:

There are the following commands for computing answer sets of propositional logic programs stored in file <File>.

nomore/1: nomore(<File>) computes all answer sets of logic program stored in file <File>.
nomore/2: nomore(<File>,<N>) computes <N> answer sets of logic program stored in file <File>. For all answer sets are computed.
nomore/4: nomore(<Name>,<N>,<AS>,<CP>) computes <N> answer sets <AS> of logic program stored in file <Name> and returns the number of choice points <CP>.

Accessing flag values:

Each flag <Flag> is represented by some ground Prolog term. With the commands set_flag/1 and clear_flag/1 it is possible to set and clear the available binary flags of the noMoRe system. For a listing of all flags and their current settings use command flags/0. Default flag settings are defined in file noMoRe/Source/flags.ini. You can change the behavior of noMoRe by editing this file or using the following commands during a prolog session to change the flag settings.

flags/0: flags shows the current flag setting.
set_flag/1: set_flag(<Flag>) sets the flag <Flag>. set_flag(<Flag>) also accepts a prolog list of noMoRe flags for <Flag>, which then are all set.
clear_flag/1: clear_flag(<Flag>) clears the flag <Flag>. After applying this flag get_flag(<Flag>) fails. clear_flag(<Flag>) also accept a prolog list of flags for <Flag>, which then are all cleared.
get_flag/1: get_flag(<Flag>) is true iff the flag <Flag> is set.

A description of all currently supported flags is shown in Table 1. By just giving a valid flag name from that Table as a command to noMoRe the corresponding flag is toggled, that is, the flag is cleared if it is currently set and vis versa. This provides the user with some nice shortcuts to influence the system behavior.

Observe, that some flags depend on some other flags. More precisely, flag animate depends on flag show, because the dynamic visualization of the construction of some a-coloring is only possible if the graph was visualized before. noMoRe automatically keeps track of flag dependencies, this means, if the user sets flag animate then flag show will be automatically set if it is currently cleared and vis versa. If both flags animate and show are set and the user clears flag show then flag animate is cleared automatically.

Furthermore, it is required that exactly one of the flags asp_bh, asp_rh and asp_r is set. noMoRe automatically keeps that the users flag settings are consistent with this requirement.

flag	controls	default
`output`	output answer sets	on
`lookahead`	heuristic does lookahead	on
`backprop`	backward propagation	on
`ignore`	if a rule with a certain head is colored with , then all other rules with same head are ignored	on
`v_operator`	extended propagation	on
`show`	visualization of the PDG	off
`animate`	dynamic visualization of coloring	off
`ground`	use of lparse as grounder; if set, the ground version of a program located in a file named `<name>.lp` is written into a file named `<name>.glp`.	off
`asp_bh`	computation of the -graph	on
`asp_rh`	computation of the -graph	off
`asp_r`	computation of the -graph	off

Miscellaneous commands:

clear/0: clear deletes all temporary files in the current working directory.

Visualization

The flags show, animation and names influence the visualization component of the noMoRe system. By setting flag show the visualization is activated, which enables noMoRe to use daVinci as output tool for rule dependency graphs and their colorings. After calling the command nomore/2 (or nomore/4) the daVinci API is used to draw the actual PDG. The flag names determines if the original rules of a program (names set) or the internal noMoRe identifiers (names cleared) are used as node labels. By setting the flag animation the daVinci API is used to animate the noMoRe coloring procedure during run time. So noMoRe is not a black box anymore but a vitreous one. Furthermore, the animated coloring sequences may be used for debugging of small logic programs under answer set semantics, because the user gets access to the full construction process of the answer sets. Hence we are able to detect the rules which are responsible for a specific answer sets.

Let's demonstrate the visualization component by computing the answer sets of program (2):

Start ECLiPSe , load noMoRe and ensure that flag show is set by set_flag(show). This activates the visualization tool. Furthermore, ensure that the flag animation is set by set_flag(animation), since we are interested in an animated coloring sequence. Observe, that due to flag dependency handling it is sufficient to set flag animation; then flag show is set automatically.
Continue by typing nomore('penguin.lp',0). After noMoRe has computed the PDG of program (2) it is translated in the daVinci term representation. Then daVinci is started as a child process and the translated PDG is send to daVinci . Figure 8 illustrates the output after an initial coloring step.
Now daVinci takes control and awaits an input by the user in order to process a number of coloring steps (a coloring step is the coloring of exactly one node.). The number of coloring steps which are preformed without interruption depends on the setting of the Edit submenu Stopping criterion of daVinci . By default it is set to every node, which causes the noMoRe coloring procedure to stop after each single coloring step. However, now we are able to change some daVinci specific settings, such as Node presentation, Stopping criterion and Animation speed. For a complete description of the posssible daVinci settings see Table 2. Finally, to continue the computation type Alt-G or click the Go-icon on the upper left side of the daVinci window.
Step by step every coloring of the noMoRe algorithm is visualized in daVinci . Observe that nodes which are used as choices during computation are marked by a double circle.
Finally an a-coloring is obtained (Figure 8). The corresponding answer set is {bird, nofly, penguin, wings}. The noMoRe algorithm tries to compute other a-colorings via backtracking. This is modeled by discoloring the corresponding nodes. See Figure 8 for the complete coloring sequence for program (2).

**Figure 3:** The rule dependency graph of (2) after the first coloring step.
$\scalebox{0.5}{\includegraphics{penguin2.ps}}$

**Figure 4:** The rule dependency graph of (2) after a second coloring step.
$\scalebox{0.5}{\includegraphics{penguin3.ps}}$

**Figure 5:** A complete coloring.
$\scalebox{0.5}{\includegraphics{penguin6.ps}}$

Figure 6: The complete coloring sequence for program (2).

$\scalebox{0.4}{\includegraphics{penguin1.ps}}$	$\scalebox{0.4}{\includegraphics{penguin2.ps}}$	$\scalebox{0.4}{\includegraphics{penguin3.ps}}$	$\scalebox{0.4}{\includegraphics{penguin4.ps}}$
$\scalebox{0.4}{\includegraphics{penguin5.ps}}$	$\scalebox{0.4}{\includegraphics{penguin6.ps}}$	$\scalebox{0.4}{\includegraphics{penguin7.ps}}$	$\scalebox{0.4}{\includegraphics{penguin7.1.ps}}$
$\scalebox{0.4}{\includegraphics{penguin8.ps}}$	$\scalebox{0.4}{\includegraphics{penguin9.ps}}$	$\scalebox{0.4}{\includegraphics{penguin8.ps}}$	$\scalebox{0.4}{\includegraphics{penguin7.1.ps}}$

Beside the flags show, animation and names (see Table 1) there are several settings that affect the style of the visualization. Those settings are accessible via the Edit menu of daVinci . See Table 2 for a complete listing of all possibilities to influence the presentation of PDGs and their animated colorings. By right clicking on a single node it is also possible to change the node representation of that node.

`Edit` menu items	shortcut	function
`Toggle Node Labels`	`Alt-T`	toggles between internal `noMoRe` identifiers and the actual rules as node labels
`Toggle Dependency Graph`	`Alt-I`	toggles between the actual PDG and the `noMoRe` internal representation
`Go`	`Alt-G`	start animation until stopping criterion is reached
`Abort`	`Alt-A`	abort answer set computation and exit `daVinci`
`Stop At`	none	submenu for choosing one of the following as stopping criterion for the animation: `Choices, Each Node, Full Coloring, No Stop`
`Animation Speed`	none	submenu for choosing the speed of animation, possible choices are: `Slow, Normal, Fast`

Bibliography

1: A. Aggoun, D. Chan, P. Dufresne, et al.
Eclipse user manual release 5.0, 2000.
2: C. Anger.
Constraint transformation.
http://www.cs.uni-potsdam.de/~christian/translation/, 2001.
3: C. Anger, K. Konczak, and T. Linke.
NoMoRe: Non-monotonic reasoning with logic programs.
In G. Ianni and S. Flesca, editors, Eighth European Workshop on Logics in Artificial Intelligence (JELIA'02), volume 2424 of Lecture Notes in Artificial Intelligence. Springer Verlag, 2002.
4: A. Bösel, T. Linke, and T. Schaub.
Profiling answer set programming: The visualization component of the noMoRe system.
2003.
submitted to LPNMR.
5: K. Konczak, T. Linke, and T. Schaub.
Graphs and colorings for answer set programming: Abridged report.
2003.
Submitted to LPNMR.
6: T. Linke.
Graph theoretical characterization and computation of answer sets.
In B. Nebel, editor, Proceedings of the International Joint Conference on Artificial Intelligence, pages 641-645. Morgan Kaufmann Publishers, 2001.
7: T. Linke.
Using nested logic programs for answer set programming.
2003.
submitted to LPNMR.
8: M.Werner.
davinci v2.1.x online documentation, 1998.
9: I. Niemelä and P. Simons.
Extending the smodels system with cardinality and weight constraints.
Logic-Based Artificial Intelligence, pages 491-521, 2000.
10: T. Syrjänen.
Lparse 1.0 user's manual, 2000.

noMoRe A Graph-Based System for Non-Monotonic Reasoning with Logic Programs under Answer Set Semantics

Contents