While reaching for your morning coffee you may accidentally bump into the table, yet you reroute your motion with ease and grab your cup. An effective autonomous robot will need to have a similarly seamless recovery from unexpected contact. As simple as this may seem, even sensing this contact is a challenge for many robots, and when detected contact is often treated as an error that an operator is expected to resolve. Robots operating in our daily environments will need to reason about the information they have gained from contact and replan autonomously. This thesis examines planning under uncertainty with contact sensitive robot arms. Robots do not have skin and cannot precisely sense the location of contact. This leads to the proposed Collision Hypothesis Set model for representing a belief over the possible occupancy of the world sensed through contact. To capture the specifics of planning in an unknown world with this measurement model, this thesis develops a POMDP approach called the Blindfolded Traveler's Problem. A good prior over the possible obstacles the robot might encounter is key to effective planning. This thesis develops a neural network approach for sampling potential obstacles that are consistent with both what a robot sees from its camera and what it feels through contact.