This paper reports on recent progress addressing two issues, one of importance to theoretical and experimental research in generative planning and the second of importvalce to the practical application of probabilistic planning methods. The first issue concerns what makes planning problems hard from a computational perspective. We report on research investigating threshold phenomena in deterministic planning problems. The observed phenomena are similar to those observed in boolean satisfiability problems, but raise interesting issues concerning the random generation of planning instances. The second issue concerns the problem of learning models for stochastic domains. Developing planning systems currently requires the tedious hand construction of domain models. We survey Bayesian methods for learning such models from data, augqnented with expert knowledge when available.