This paper describes work related to stochastic modeling and decision-theoretic (DT) planning methods applicable to the real-world domain of academic advising.The uncertainty associated with stochastic planning is often approached as a problem of finding a complete mapping from states to actions (a policy). A need to plan for all contingent futures makes (DT) planning an inherently difficult problem in large, real-world domains. This is different from classical planning where the effects of actions are known with certainty, and a step-by-step plan is sufficient for reaching a goal state.Recently, replanning and heuristic planning techniques which operate over determinized (deterministic) versions ofstochastic planning problems have seen much success in competitions and in planning literature. This approach typically involves direct use of deterministic solutions in place of a complete policy or as a heuristic for finding a partial or complete policy. These successes have caused some to call into question the types of problems which are suited to DT planning techniques and to examine the role of approximate planning in stochastic domains [Little and Thiebaux, 2007; ´Sanner, 2008]