The ability to plan under a variety of constraints, environments, and uncertainties is one of the greatest puzzles of human intelligence. Planning in human-like domains remains intractable for machine learning algorithms, where the greatest challenges is designing appropriate representations and state-evaluation heuristics. How do humans navigate their natural world so efficiently? Which computations drive them? Existing studies have investigated planning in simple tasks, such as gambles and multi-armed bandits, with little resemblance to natural tasks. We analyze human behavior in a search-and-rescue mission in a large 3D environment, designed to simulate a real-world context. We propose a hierarchical planning framework, which jointly solves an orienteering problem on the high level and a set of local Partially Observable Markov Decision Processes on the low level. Using this framework, we evaluate alternative computational models of human planning that captures core mental representations of human spatial planning.