I seek to deeply understand and to rigorously address the computational challenges that arise when planning for robots. My research, lying at the intersection of CS and Robotics, is motivated by the key insight that in order to address these challenges, traditional Computer Science algorithms, tools and paradigms need to be revisited. This requires under-standing and analyzing the unique domain-specic computational challenges in robotic planning and, subsequently eveloping algorithms to address these challenges to provide the robotics community foundational tools to solve real-world problems.