The demand for autonomous, robust, intelligent robotic systems is growing rapidly, given their potential to make our societies more productive and increase our welfare. To achieve this, robots are increasingly expected to operate in human-populated environments, maneuver in remote and cluttered environments, maintain and repair facilities, take care of our health, and streamline manufacturing and assembly lines. However, computational issues limit the ability of robots to plan complex motions in constrained and contact-rich environments, interact with humans safely, and exploit dynamics to gracefully maneuver, manipulate, fly, or explore the oceans. This talk will be centered around planning and decision-making algorithms for robust and agile robots operating in complex environments. In particular, I will present novel computational approaches necessary to enable real-time and robust motion planning of highly dynamic bipedal locomotion over rough terrain. This planning approach revolves around robust disturbance metric, optimal recovery controller, and foot placement re-planning strategies. Extending this motion planning approach to generalized whole-body locomotion behaviors, I will talk about our recent progress on high-level reactive task planner synthesis for multi-contact, template-based locomotion interacting with constrained environments and how to integrate formal methods for mission-capable locomotion. This talk will also present biased-maximum likelihood trajectory optimization algorithm capable of handling contact uncertainties and without enumerating contact modes. I will end this talk with current and upcoming research directions.