The cloud's vast computation power has great potential to enhance a robot's movement capabilities.  This is because planning a robot's collision-free motion that accomplishes a desired task in a cluttered environment can be computationally demanding, especially for robots with many degrees of freedom (such as mobile manipulators and humanoid robots).  However, battery-powered mobile robots are necessarily power-constrained and thus often do not have the on-board computational ability to solve complex motion planning problems at interactive rates. This talk proposes addressing this challenge by moving large portions of the robot's motion planning computation to the cloud.  Effectively leveraging the cloud's computing power to plan motions for a robot exposes new problems for which this talk presents solutions, including: partitioning motion plan computation between the robot’s onboard computer and the cloud, parallel computation of motion plans in multi-core cloud-based computers, designing concurrent graph and nearest-neighbor data structures, and working around network bottlenecks to enable power-constrained robots to avoid moving obstacles.  The talk demonstrates the solutions' effectiveness on physical robots performing tasks inspired by a vision of robots assisting people in everyday semistructured environments such as homes and warehouses.