ICAPS 2016 Tutorial on Planning with State-Dependent Action Costs

This year’s ICAPS in London is approaching quickly, and I’m already looking forward to it. As always, there will be many exciting talks, invited presentations, etc. Besides, this year I have the honor to give a tutorial on planning with state-dependent action costs together with Florian Geißer, mostly based on our IJCAI 2015 and ICAPS 2016 papers (together with Thomas Keller) on that topic.

Update 1: The slides are now finished and available.

Update 2: And here is the video recording of the tutorial.

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.