The discrete minimum constraint removal motion planning problem

Abstract

Many planning problems for robots are of considerable interest. In this paper, we consider the discrete minimum constraint removal motion planning problem that can be used for a motion planning formulation with explanations for failure. We consider an efficient approach to solve the problem. In particular, we consider an explicit reduction from the decision version of the problem to the satisfiability problem. We present the results of computational experiments for different satisfiability algorithms.