Comparisons of the performance of solution algorithms for Markov decis
ion processes rely heavily on problem generators to provide sizeable s
ets of test problems. Existing generation techniques allow little cont
rol over the properties of the test problems and often result in probl
ems which are not typical of real-world examples. This paper identifie
s the properties of Markov decision processes which affect the perform
ance of solution algorithms, and also describes a new problem generati
on technique which allows all of these properties to be controlled.