Creating and re-purposing objects as tools are universal human capabilities. However, it appears that only a handful of other animals exhibit these behaviors, and these are often regarded as a hallmark of advanced intelligence. In this talk, I will discuss my research aiming to illuminate the computational and cognitive foundations of this kind of flexible physical problem-solving across multiple timescales of experience. By combining perspectives from cognitive science, machine learning, and robotics, my research suggests that the flexibility and efficiency of human physical problem-solving is supported by combining structured knowledge with learning, rather than choosing one or the other. To explain human flexibility, actions must be structured in relational, object-oriented ways. To explain human efficiency, mental simulation in the form of intuitive physics is critical, as relational actions alone are not enough. With these structures in place, learning guides how we search through and adapt our actions over multiple timescales -- either over just a few attempts within a problem, over related problems with shared relational structure, or over a lifetime of embodied experience. I will conclude with recent, unpublished work exploring how these principles extend to tool creation and, time permitting, how our expectations of structure guide the exploration of the physical world.