EVMDD Library for Python (pyevmdd)

I started using Edge-valued Multi-valued Decision Diagrams (EVMDDs) [CS02] a bit more than a year ago while working on AI planning with state-dependent action costs [GKM15]. Throughout 2015, we were happy using the wonderful EVMDD library MEDDLY by Junaid Babar and Andrew Miner more or less as a black box. This worked very well for us, both because MEDDLY is stable and efficient, and because it is written in C++, just like the PROST planner in which we employed EVMDDs and MEDDLY.

But now we are planning to release a small tool that translates tasks formulated in a state-dependent action cost extension of PDDL into tasks formulated in PDDL with state-independent action costs. Since this tool will be based on the Fast Downward translator (written in Python) and we want to avoid introducing too many external dependencies, I considered writing my own EVMDD implementation in Python. Besides that, two more things motivated me to implement such a library: first, I wanted to have an EVMDD playground that is easy to play on, ideally with a function that simply takes an arithmetic term written in infix notation, a variable order, and the domain sizes of the variables, and returns a figure of the corresponding reduced ordered EVMDD. Second, I wanted to understand how EVMDDs work internally, in particular, how the basic arithmetic operations are implemented on EVMDDs.

Finally, I was looking for a small programming project to practice my Python software development skills for a while, anyway. So, I used the winter holidays of 2015/2016 to write a first version of the EVMDD Library for Python (pyevmdd).

You can find the sources on GitHub and the documentation on Read the Docs.

References:

[CS02]

Gianfranco Ciardo, Radu Siminiceanu: Using Edge-Valued Decision Diagrams for Symbolic Generation of Shortest Paths. In: Proceedings of the 4th International Conference on Formal Methods in Computer-Aided Design (FMCAD 2002), pp. 256–273, 2002.

[GKM15]

Florian Geißer, Thomas Keller, Robert Mattmüller: Delete Relaxations for Planning with State-Dependent Action Costs. In: Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI 2015), pp. 1573–1579, 2015.