Minimum Constraint Removal Problem for Line Segments is NP-hard

One of the most important objectives in motion planning is finding a feasible path from the starting point to a goal without collision with obstacles. The obstacles are either closed doors, which can be opened and removed by the robot, or are obstacles that cannot be passed which can be ignored by the robot with a penalty. Usually, there is no feasible path for some navigation. Recently, some researchers have focused on finding a path for the robot by minimizing the number of removed obstacles. For instance, in Stilman and Kuffner's paper [Stilman and Kuffner, 2005], the robot is able to move the obstacles around and clear its movement space.