The Blindfolded Robot: A Bayesian Approach to Planning with Contact Feedback

Abstract

We address the problem of robot motion planning under uncertainty where the only observations are through contact with the environment. Such problems are typically solved by planning optimistically assuming unknown space is free, moving along the planned path and re-planning if the robot collides. However this approach can lead to many unnecessary collisions and movements. We propose a new formulation, the Blindfolded Traveler’s Problem (BTP), for planning on a graph containing edges with unknown validity, with true validity observed only through attempted traversal by the robot. We prove that BTP is NP-complete and present a number of approximation-based policies. In particular, we analyze the case of a robot arm where it is challenging to construct a reasonable prior over obstacles. We examine a number of belief approximation techniques and finally propose a policy-belief combination. For the policy we propose graph search with edges weights augmented by the probability of collision. For the belief representation we propose a weighted Mixture of Experts of Collision Hypothesis Sets and a Manifold Particle Filter. Empirical evaluation in simulation and on a real robot arm shows that our proposed approach vastly outperforms several baselines as well as a previous approach that does not employ the BTP framework.