This section describes the input language, PPDDL1.0, that was used for the probabilistic track. PPDDL1.0 is essentially a syntactic extension of Levels 1 and 2 of PDDL2.1 (Fox & Long, 2003). The complete syntax for PPDDL1.0 is given in Appendix A. We assume that the reader is familiar with PDDL2.1, so we focus on the new language features, which include probabilistic effects and rewards. A more detailed account of PPDDL1.0 is provided by Younes and Littman (2004). The semantics of a PPDDL1.0 planning problem is given in terms of a discrete-time Markov decision process (Howard, 1960,1971;Puterman, 1994).