Locally Optimal Solutions to Constraint Displacement Problems via Path-Obstacle Overlaps

We present a unified approach for constraint displacement problems in which a robot finds a feasible path by displacing constraints or obstacles. To this end, we propose a two stage process that returns locally optimal obstacle displacements to enable a feasible path for the robot. In the second stage, these obstacles are displaced to make the computed robot trajectory feasible, that is, collision-free. Several examples are provided that successfully demonstrate our approach on two distinct classes of constraint displacement problems. Introduction As humans, we encounter various situations in our day to day life in which we alter the location of objects - opening closed doors, repositioning chairs or other movable objects, clear objects while picking an object of interest from a cluttered table-top. As opposed to avoiding each object, altering or displacing these objects or constraints allow us to expand the solution space of feasible paths. In such situations, constraints, such as movable obstacles, may be cleared to find feasible paths. Manipulators often need to rearrange or move obstacles aside to accomplish a given set of tasks - a futuristic robot cooking dinner at home, manipulation in industrial settings, shelves replenishment in a grocery store. Service robots may need to reposition chairs or other movable objects to accomplish a task. A robot may need to plan a path through dynamic obstacles as they might clear the path while moving. We define a constraint displacement problem as one that finds a feasible path by displacing constraints while minimizing a problem-specific objective function.