Abstract: Consider a robotic vehicle that is traveling in a cluttered environment or attempting to fulfill tasks that require visiting several locations. What is the maximum speed that this vehicle can achieve and maintain for a long time? How does this speed depend on the agility, perception, actuation, or computation capabilities of the vehicle? To answer these questions, we formulate various control and planning problems in stochastic obstacle fields or stochastic reward fields; subsequently, we establish novel connections between these problems and suitable fundamental problems of statistical mechanics. In particular, we point out critical phenomena, phase transitions, and universality classes in certain control and planning problems. With the help of these results, we propose efficient algorithms with provable performance guarantees.