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.

Initial Release of myND Planner

Today, I can proudly announce the initial release of the myND planner for fully and partially observable nondeterministic planning tasks.

The code as well as some rudimentary documentation in the form of a wiki can be found at Bitbucket.

More technical and detailed descriptions of how the planner works algorithmically can be found in a number of conference publications. They mostly focus on the heuristics used to guide the search, but a brief description of the search algorithm is also given [MOHB10]. The earlier publications [BM08, BM09, MOHB10] deal with fully observable problems, whereas the most recent one [OM13] deals with partial observability. Regarding the heuristics used to guide the search, one publication [BM08] is about a delete-relaxation approach, whereas the others [BM09, MOHB10, OM13] use abstraction heuristics.

References:

[BM08]

Pascal Bercher, Robert Mattmüller: A Planning Graph Heuristic for Forward-Chaining Adversarial Planning. In: Proceedings of the 18th European Conference on Artificial Intelligence (ECAI 2008), pp. 921–922, 2008.

[BM09]

Pascal Bercher, Robert Mattmüller: Solving Non-deterministic Planning Problems with Pattern Database Heuristics. In: Proceedings of the 32nd Annual Conference on Artificial Intelligence (KI 2009), pp. 57–64, 2009.

[MOHB10]

Robert Mattmüller, Manuela Ortlieb, Malte Helmert, Pascal Bercher: Pattern Database Heuristics for Fully Observable Nondeterministic Planning. In: Proceedings of the 20th International Conference on Automated Planning and Scheduling (ICAPS 2010), pp. 105–112, 2010.

[OM13]

Manuela Ortlieb, Robert Mattmüller: Pattern-Database Heuristics for Partially Observable Nondeterministic Planning. In: Proceedings of the 36th German Conference on Artificial Intelligence (KI 2013), pp. 140–151, 2013.