A robot should be able to autonomously modify and utilize its environment to assist its task completion. While mobile manipulators and humanoid robots have both locomotion and manipulation capabilities, planning systems typically just consider one or the other. In traditional motion planning the planner attempts to find a collision free path from the robot's current configuration to some goal configuration. In general, this process entirely ignores the fact that the robot has manipulation capabilities. This is in contrast to how humans naturally act - utilizing their manipulation capabilities to modify the environment to assist locomotion. If necessary, humans do not hesitate to move objects, such as chairs, out of their way or even place an object, such as a board, on the ground to reach an otherwise unreachable goal. We argue that robots should demonstrate similar behavior. Robots should use their manipulation capabilities to move or even use environment objects. This thesis aims at bringing robots closer to such capabilities. There are two primary challenges in developing practical systems that allow a real robotic system to tightly couple its manipulation and locomotion capabilities: the inevitable inaccuracies in perception as well as actuation that occur on physical systems, and the exponential size of the search space. To address these challenges, this thesis first extends the previously introduced domain of Navigation Among Movable Obstacles (NAMO), which allows a robot to move obstacles out of its way. We extend the NAMO domain to handle the underlying issue of uncertainty. In fact, this thesis introduces the first NAMO framework that allows a real robotic systems to consider sensing and action uncertainties while reasoning about moving objects out of the way. However, the NAMO domain itself has the shortcoming that it only considers a robot's manipulation capabilities in the context of clearing a path. This thesis therefore also generalizes the NAMO domain itself to the Navigation Using Manipulable Obstacles (NUMO) domain. The NUMO domain enables a robot to more generally consider the coupling between manipulation and locomotion capabilities and supports reasoning about using objects in the environment. This thesis shows the relationship between the NAMO and NUMO domain, both in terms of complexity as well as solution approaches, and presents multiple realizations of the NUMO domain. The first NUMO realization enables a robot to use its manipulation capabilities to assist its locomotion by changing the geometry of the environment for scenarios in which obstructions can be overcome through the usage of a single object. The system led a real humanoid robot to autonomously build itself a bridge to cross a gap and a stair step to get on a platform. A second NUMO realization then introduces reasoning about force constraints using knowledge about the mechanical advantages of a lever and battering ram. The discussed system allows a robot to consider increasing its effective force though the use of objects, such as utilizing a rod as a lever. Finally this thesis extends the NUMO framework for geometric constraints to scenarios in which the robot is faced with a substantial lack of initial state information and only has access to onboard sensing. In summary, this thesis enables robots to autonomously modify their environment to achieve task completion in the presence of lack of support for mobility, the need to increase force capabilities and partial knowledge.