Welcome to EVMDD Library for Python (pyevmdd)’s documentation!¶

Introduction to EVMDDs¶

An Edge-valued Multi-valued Decision Diagram (EVMDD) [CS02] is a data structure that can be used to represent an arithmetic function, comparable to how Binary Decision Diagrams (BDDs) are used to represent logic functions. EVMDDs differ from BDDs in two ways: first, the variables on which the represented functions depend can be multi-valued instead of only binary, and second, the resulting function values are not read from the leaf node(s) of the diagram, but rather from the traversed edges.

EVMDDs can be used in automated planning to represent cost functions of actions with state-dependent costs [GKM15]. This representation allows, among others, (i) an efficient compilation to actions with state-independent costs, which are generally easier to handle algorithmically, and (ii) a faithful representation of action costs during the computation of goal-distance heuristics.

As an example, consider the diagram in the following figure, representing the function \(f(A,B,C) = AB^2 + C + 2\) for variables \(A\) and \(C\) that can take values \(0\) or \(1\) each, and variable \(B\) that can take the values \(0\), \(1\), or \(2\). The variable ordering is \(A, B, C\).

EVMDD Example

To see why this EVMDD represents the function \(f(A,B,C) = AB^2 + C + 2\), consider the valuation \(A = 1\), \(B = 2\), and \(C = 0\). We would then like to be able to read the function value \(f(1,2,0) = 6\) from the EVMDD. This is possible by traversing the path from top to bottom corresponding to the given valuation and summing up the encountered edge weights (given in rectangular boxes in the figure). For \(A = 1\), \(B = 2\), and \(C = 0\), and starting with the dangling incoming edge of the topmost node, we get the desired value \(2+0+4+0 = 6\).

As can be seen in the figure, EVMDDs help detecting and exploiting independencies in the represented arithmetic function. For example, the \(AB^2\) part and the \(C\) part of the example function are additively decomposable and hence independent. As a consequence, the EVMDD allows to first take care of the \(AB^2\) part completely before independently taking care of the \(C\) part. Alternatively, for variable ordering \(C, A, B\), the \(C\) part could have been handled completely before the \(AB^2\) part. Notice also that if \(A=0\), then the \(AB^2\) part has to be zero and there is no point in branching over \(B\) any more. Therefore, on this EVMDD path, \(B\) is skipped.

For arithmetic functions from a finite set of finite-domain variables with ranges \(0, ..., D_i-1\) to the whole numbers, reduced ordered EVMDDs always exist and are unique. The canonicity requirements are similar to those for BDDs (isomorphism reduction, Shannon reduction), and additionally, for each node, the smallest weight of an outgoing edge must be zero.

Below, we will distinguish between fully reduced and quasi-reduced EVMDDs. We call an EVMDD fully reduced if it is Shannon-reduced in the usual sense (there is no node in the diagram such that all outgoing edges carry the same weight and lead to the same successor node). In contrast, we call it quasi-reduced if it is isomorphism reduced, but no Shannon reductions are performed, i.e., on each path from top to bottom, each variable is branched over exactly once. This may include branchings at nodes contributing no additional information, such that all outgoing edges carry the same weight zero and lead to the same successor node. Quasi-reduction instead of full reduction can be necessary when EVMDDs are used to compute heuristics in AI planning [GKM15].

[CS02]

Gianfranco Ciardo and Radu Siminiceanu.
Using Edge-Valued Decision Diagrams for Symbolic Generation of Shortest Paths.
In Proc. FMCAD 2002. (PDF)

[GKM15]

(1, 2)

Florian Geißer, Thomas Keller, and Robert Mattmüller.
Delete Relaxations for Planning with State-Dependent Action Costs.
In Proc. IJCAI 2015. (PDF)

Introduction to the pyevmdd Library¶

The purpose of the pyevmdd project is to provide a lightweight, pure Python EVMDD library. It is still in a very early stage of development. So far, the following features are supported (but unstable):

Internal EVMDD representation.
EVMDD output as a Graphviz file plus visualization.
Function evaluation.
Arithmetic operations \(+\) (addition), \(-\) (subtraction, unary negation), and \(*\) (multiplication) on EVMDDs.
Choice between fully reduced and quasi-reduced EVMDDs.
Input of arithmetic functions in Python syntax.

If you are looking for an excellent, mature, efficient, and general EVMDD library that you can use in a serious application, we strongly recommend you to first consider using MEDDLY instead of pyevmdd. Compared to pyevmdd, MEDDLY has many advantages:

Higher performance (C++ instead of Python, more optimization)
Higher stability
More supported operations

The pyevmdd library is explicitly not meant to compete with MEDDLY, but rather to serve as a playground for small experiments with extremely small EVMDDs. Compared to the EVMDDs MEDDLY has to handle in typical application scenarios, the EVMDDs that result from cost functions in AI planning are relatively small, which is why we developed this little EVMDD playground in the first place.

We only recommend using pyevmdd instead of MEDDLY if you agree with all of the following points:

I do not care about performance.
I do not care about maturity or stability.
I do not care about few supported EVMDD operations (addition, subtraction and multiplication are enough for me).
I am fine with a library that needs Python 3, likely because my client code is written in Python 3 as well.
I want a simple high-level Python interface to EVMDDs.
I want to easily visualize my EVMDDs.
I want to avoid the hassle of installing/using/interfacing to a C++ library.

Installing the pyevmdd Library¶

The sources can be cloned from the following git repository:

https://github.com/robertmattmueller/pyevmdd

This library has the following requirements and dependencies:

It requires Python 3.
For EVMDD visualization, it requires Graphviz
- Additionally, under Linux, it requires xdot to display EVMDDs.
- Under Mac OS X, EVMDDs are displayed in the Safari browser after dot conversion to SVG.
Several planned features (variable orderings, EVMDD based action compilation, evaluation of relaxed/abstract states), will probably make use of the NetworkX library.

Using the pyevmdd Library¶

Example Script¶

Let us step through a small script that makes use of the interesting pyevmdd features:

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

from evmdd import term_to_evmdd, evaluate, EvmddVisualizer

# EVMDD construction
function_term = 'A*B*B + C + 2'
var_names = ['A', 'B', 'C']
var_domains = {'A': 2, 'B': 3, 'C': 2}
evmdd, manager = term_to_evmdd(function_term, var_names=var_names,
                               var_domains=var_domains, fully_reduced=True)

# EVMDD evaluation
valuation = {'A': 1, 'B': 2, 'C': 0}
value = evaluate(evmdd, valuation, manager)
print(value)

# EVMDD visualization
visualizer = EvmddVisualizer(manager)
visualizer.visualize(evmdd)

EVMDD Construction¶

To construct an EVMDD, first, we give the function term to be represented as an EVMDD, for instance \(AB^2 + C + 2\). The term must be given in Python syntax using only variable names, constants, addition, subtraction, and multiplication. Hence, we have to write:

function_term = 'A*B*B + C + 2'

Although the variable names are clear from the given function term, the desired variable ordering is not. To enforce the ordering \(A, B, C\), we state:

var_names = ['A', 'B', 'C']

This information is still insufficient to construct an EVMDD, since the variable domain sizes that determine the branching width at variable test nodes still need to be given. Let us assume that variables \(A\) and \(C\) can take two values each (\(0\) and \(1\)), and that variable \(B\) can take three values (\(0\), \(1\), and \(2\)):

var_domains = {'A': 2, 'B': 3, 'C': 2}

Putting all this together, we can generate the desired EVMDD:

evmdd, manager = term_to_evmdd(function_term, var_names=var_names,
                               var_domains=var_domains, fully_reduced=True)

The function term is a required argument. The rest is optional. If no variable ordering is given, the lexicographic ordering is used. If no domain sizes are given, they are assumed to be \(2\) for all variables. Finally, if fully_reduced is not specified, it is true by default, i.e., EVMDDs will be fully reduced as opposed to quasi-reduced. The function term_to_evmdd returns the generated EVMDD together with the EvmddManager responsible for managing its variables.

EVMDD Evaluation¶

To determine function values, we first need the variable assignment for which we want to evaluate our function. Let us assume we want to know the value of the function \(f(A,B,C) = AB^2 + C + 2\), under the valuation \(A = 1\), \(B = 2\), and \(C = 0\). We first define the valuation:

valuation = {'A': 1, 'B': 2, 'C': 0}

Afterwards, we can compute \(f(1,2,0)\):

value = evaluate(evmdd, valuation, manager)
print(value)

As expected, this prints the number \(6\).

EVMDD Visualization¶

Finally, especially for debugging and for didactic purposes, it is useful to have easy access to visualizations of EVMDDs. We use EvmddVisualizers for that purpose:

visualizer = EvmddVisualizer(manager)
visualizer.visualize(evmdd)

Depending on OS details, this visualizes the EVMDD using Graphviz and either xdot display or conversion to SVG and web browser display. Figure EVMDD Example above was produced this way.

Note

The temporary files needed for visualization are not deleted after use. DOT and SVG files are stored in /tmp/evmdd-gvz-<UUID>.dot and /tmp/evmdd-gvz-<UUID>.dot.svg, respectively. Optionally, a file prefix can be given as a named argument file_prefix to visualize. The default corresponds to visualize(evmdd, file_prefix='/tmp/evmdd-gvz-<UUID>').

Planned Features and Applications¶

Planned features and applications of this library include:

Evaluation of relaxed/abstract states in AI planning.
EVMDD-based action compilation and integration with Fast-Downward translator.
Experiments with (static) variable orders.

Public API Reference¶

The public API is still unstable and likely subject to changes in the future. Currently, it consists of three modules:

A core module (evmdd.evmdd) responsible for the internal representation of EVMDDs, arithmetic operations on them, and computation of function values.
An input module (evmdd.parser) responsible for translating arithmetic function terms specified in Python syntax to EVMDDs.
An output module (evmdd.graphviz) responsible for dumping EVMDDs in Graphviz format and displaying them.

In the following, we give the API documentation of the three modules.

EVMDD Core Module¶

This core module is responsible for the internal representation of EVMDDs via Nodes and Edges, for arithmetic operations on them, and for the computation of function values.

It supports quasi-reduced and fully reduced EVMDDs, but does not allow mixing them. Many functions and methods have an optional boolean parameter fully_reduced or is_fully_reduced that determines whether they are supposed to deal with fully reduced (if true) or quasi-reduced (if false) EVMDDs.

evmdd.evmdd.Edge(*args, **kwargs)¶

An edge in an EVMDD, specifying weight and successor node.

The weight of an edge e is the partial function value associated with the variable-value pair corresponding to e (conditional on variable-value pairs at higher levels).

The successor succ of e is the next node reached by e, either a test node for the next variable, or the sink node.

Additionally, each edge e has a flag is_fully_reduced that denotes whether the EVMDD represented by this edge is fully reduced or only quasi-reduced. By default, EVMDDs are fully reduced.

The “dangling incoming edge” from the literature is also represented by an object of this class that is required to have exactly one child node in the collection succ, i.e., len(succ) == 1 must hold for this edge. Since EVMDDs can be identified by their dangling incoming edge, we do not need a separate EVMDD class, but rather use Edges to represent EVMDDs.

evmdd.evmdd.Node(*args, **kwargs)¶

A node in an EVMDD specifying level and children.

The level of a node n specifies how far from the sink node n is located. Level 0 is reserved for the sink node, and levels increase bottom-up. The level of the top-most branching is the number of variables in the EVMDD (assuming that the EVMDD is quasi-reduced).

The sink node is identified as the unique node without any outgoing edges.

Notice that only for a given variable ordering, levels will uniquely correspond to variable names. EVMDDs are constructed independently of a list of variable names, and variable names only come into play when an EVMDD is evaluated.

The list of children holds edges to lower-level nodes for all values of the variable tested at this node. The list has to be ordered, and the index in this ordering is the domain value. I.e., if the current node represents a test of variable \(v\), and \(v\) can take the three values \(0\), \(1\), and \(2\), then children contains three edges to the successor nodes for the cases \(v=0\), \(v=1\), and \(v=2\), respectively, in that order.

Like Edges, Nodes keep track of whether they belong to a fully reduced or a quasi-reduced EVMDD via the flag is_fully_reduced.

class evmdd.evmdd.EvmddManager(var_names, var_domains, fully_reduced=True)¶

Manager for EVMDDs taking care of variable names and orderings, variable domain sizes, and construction of basic EVMDDs representing numeric constants and variables.

The variable names var_names are given in the desired variable order.

The domain sizes are given as a separate list var_domains in the same ordering as the variable names, i.e., the \(i\)-th entry in var_domains specifies the domain size of the \(i\)-th variable in var_names. Note that var_domains only holds the domain sizes, not the domains themselves. We assume throughout that all variables have domains from \(0\) to var_domains[i] - 1.

The EVMDDs generated and managed by this manager can be either fully reduced or quasi-reduced. They will be fully reduced iff the flag fully_reduced is set to true (default).

make_const_evmdd(number)¶

Construct an EVMDD representing a given constant number.

This is the EVMDD with a single edge immediately leading to the sink node, labeled with the given constant as its edge weight.

Args:: number (int): a constant arithmetic function.
Returns:: Edge: the EVMDD representing the given number.

make_var_evmdd_for_var(var_name)¶

Construct an EVMDD representing a given variable.

Args:: var_name (string): a variable name.
Returns:: Edge: the EVMDD representing the given variable according to the variable order of this manager.
Note:: Fails if the given variable name is not known.

var_name_of(node)¶

Determine the variable name associated with a given node.

Args:: node (Node): an EVMDD node.
Returns:: string: the name of the variable associated with the given node.

evmdd.evmdd.evaluate(evmdd, valuation, manager)¶

Evaluate an EVMDD evmdd for given valuation valuation and EvmddManager manager.

This function traverses the given EVMDD from top to bottom, following the unique path consistent with valuation. Along the way, it adds up the encountered edge weights. In order to match the variable names mentioned in valuation to levels in the EVMDD, this function needs to have access to the variable ordering provided by the manager. At each interior node n, the variable name v associated with n is looked up by the manager, and the value that v has is looked up in valuation. Then, the corresponding edge is traversed.

Args:

evmdd (Edge): an EVMDD.

valuation (dict[string->int]): a variable-value mapping to be evaluated.

manager (EvmddManager): an EvmddManager that knows variable names and orderings.

Returns:

int: the value the function represented by evmdd has under valuation.

Examples:

>>> var_names = ['A', 'B']
>>> var_domains = [2, 2]
>>> manager = EvmddManager(var_names, var_domains)
>>>
>>> N00 = _make_sink_node()
>>> N10 = Node(level=1, children=[Edge(weight=0, succ=N00), Edge(weight=1, succ=N00)])
>>> N11 = Node(level=1, children=[Edge(weight=0, succ=N00), Edge(weight=2, succ=N00)])
>>> N20 = Node(level=2, children=[Edge(weight=0, succ=N10), Edge(weight=1, succ=N11)])
>>> evmdd = Edge(weight=2, succ=N20)
>>>
>>> s = { 'A': 0, 'B': 0 }
>>> evaluate(evmdd, s, manager)
2
>>> s = { 'A': 0, 'B': 1 }
>>> evaluate(evmdd, s, manager)
3
>>> s = { 'A': 1, 'B': 0 }
>>> evaluate(evmdd, s, manager)
3
>>> s = { 'A': 1, 'B': 1 }
>>> evaluate(evmdd, s, manager)
5

Function Term Input Module¶

This input and parser module is responsible for translating arithmetic function terms specified in Python syntax to EVMDDs.

evmdd.parser.term_to_evmdd(function_term, **kwargs)¶

Translate a function term to the corresponding EVMDD.

The variable names in the desired variable ordering can be optionally specified. If no variable ordering is specified, the variable names are determined from the function term and ordered lexicographically.

Also, the user may optionally specify the domain sizes of the variables. If no domain sized are specified, they default to 2 for all variables.

Args:

function_term (string): a function term in Python syntax using only constants, variables, addition, subtraction exponentiation to natural- numbered powers, and multiplication.

**kwargs: optionally, the variable names in the desired ordering, var_names (list of strings), their domain sizes var_domains (dict from strings to ints), and a flag fully_reduced determining whether the EVMDD should be fully reduced or quasi-reduced.

Returns:

a tuple consisting of the corresponding EVMDD and its manager.

The following example code constructs the fully reduced EVMDD for the running example \(f(A,B,C) = AB^2 + C + 2\) for variable ordering \(A, B, C\) and evaluates it for the valuation \(A=1\), \(B=2\), and \(C=0\).

Example:

>>> from .evmdd import evaluate
>>> expr = 'A*B**2 + C + 2'
>>> var_names = ['A', 'B', 'C']
>>> var_domains = {'A': 2, 'B': 3, 'C': 2}
>>> evmdd, manager = term_to_evmdd(
...                      expr, var_names=var_names,
...                      var_domains=var_domains, fully_reduced=True)
>>> valuation = {'A': 1, 'B': 2, 'C': 0}
>>> evaluate(evmdd, valuation, manager)
6

The next example shows that this works across a range of function terms, variable orderings, valuations, and both for fully and quasi-reduced EVMDDs.

Example:

>>> from itertools import permutations, product
>>> from .evmdd import evaluate
>>>
>>> def collect_variables(function_term):
...     variables = set()
...     expression = ast.parse(function_term, mode='eval')
...     for node in ast.walk(expression):
...         if(type(node) == ast.Name):
...             name = node.id
...             variables.add(name)
...     return variables
...
>>>
>>> exprs = [
...     '0', '1',
...     'A', 'B', '0*A', '2*A', '0*B', '2*B',
...     'A+B', 'B+A', '1-A', '1-B',
...     '-A', 'A-B', 'B-A', '-(A+B)',
...     'A*B + B', 'B + A*B',
...     'A*B*B + C + 2', 'A*B - 17',
...     'A*B - A*B', 'A-A',
...     '1*(A+2)', 'A*(B+2)', 'A*(B+2)*(B+2) + C + 2',
... ]
...
>>> domain_size = 4
>>>
>>> all_results_as_expected = True
>>> for expr in exprs:
...     var_set = collect_variables(expr)
...     var_domains = {var: domain_size for var in var_set}
...     for fully_reduced in [True, False]:
...         for var_names in permutations(var_set):
...             for valuation in product(range(domain_size), repeat=len(var_set)):
...                 valuation = {var:val for var, val in zip(var_names,valuation)}
...                 evmdd, manager = term_to_evmdd(expr,
...                                  var_names=var_names, var_domains=var_domains,
...                                  fully_reduced=fully_reduced)
...                 actual = evaluate(evmdd, valuation, manager)
...                 expected = eval(expr, valuation)
...                 if actual != expected:
...                     all_results_as_expected = False
...
>>> all_results_as_expected
True

Visualization/Output Module¶

Graphviz output and display of EVMDDs.

class evmdd.graphviz.EvmddVisualizer(manager)¶

Helper class that displays EVMDDs on the screen.

visualize(evmdd, file_prefix=None)¶

Visualize a given EVMDD.

The given EVMDD is first exported in Graphviz/DOT syntax and written to a temporary DOT file. Then, depending on the OS, the DOT file is either displayed using xdot (under Linux), or converted to SVG using dot and subsequently openend in a Browser (Safari, under Mac OS X).

In both cases, we assume that Graphviz is installed.

Notice that generated DOT/SVG files are not deleted after visualization.

Args:

evmdd (Edge): the EVMDD to be visualized.

file_prefix (string, optional): path and file name of dot file to write to (/tmp/evmdd-gvz-UUID by default)

Returns:

None

Side effect:

visualization of the given EVMDD.

License¶

This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program. If not, see <http://www.gnu.org/licenses/>