Abstract: Autonomous agents that act in the real-world can often improve their success by capturing the uncertainty that arises because of their imperfect knowledge and potentially faulty actions. By making plans robust to uncertainty, agents can be prepared to counteract plan failure or act upon information that becomes available during plan execution. Such robust plans are valuable, but are often difficult to construct when uncertainty is high and goal achievement requires many actions. Unfortunately, current approaches to planning under uncertainty are not scalable: they focus on small problems where the challenge is finding an optimal solution. I study (non-deterministic and probabilistic) conformant and conditional planning in large problems where just finding a feasible solution is the challenge. I develop scalable heuristic search techniques that are inspired both by optimal approaches to planning under uncertainty (based on Markov decision processes) and scalable approaches for classical planning (based on planning graph reachability heuristics). Specifically, I develop measures for the cost of completing partial plans, heuristics that estimate the measures, efficient data-structures and inference techniques to compute the heuristics, and a multi-objective heuristic search algorithm that uses the heuristics. Through extensive empirical evaluation, I show the resulting set of techniques significantly improves the scalability of planning under uncertainty.