Robot Motion Planning with Complementarity Constraints: When is it easy?

This research is on robotics motion planning, where the goal is to find a path for a robot from a start to a goal configuration without hitting obstacles in the environment. An instance of a robot motion planning problem consists of a geometric model of an environment with obstacles, a model of a robot, and its initial and goal configurations. Computationally, robot motion planning is known to be NP-hard (more accurately, PSPACE-hard), which means that there are instances of the motion planning problem where it is computationally very expensive to compute a feasible or collision-free path, even if there exists one. Practically, this means that there are motion planning problems that are unsolvable in a reasonable time. The purpose of my research project is to understand a related question: Can we characterize the set of motion planning instances where the motion planning problem is solvable in polynomial time? Understanding this question will help us devise more reliable robotic systems and help us understand the performance of robotic systems in certain deployed scenarios such as in a home environment. It may also allow the robot to reason about its environment and understand how some of the obstacles may be rearranged, if possible, to obtain a feasible motion plan. The question above is quite challenging since the question is also related to the underlying motion planning algorithm that is being used. Within the context of this overarching problem, my goal is to understand the above question for point holonomic robots moving in a 2D or 3D environment. Up to now, I have considered the obstacles to be circular non-overlapping obstacles. We can prove that in this environment all motion planning problems are easy, i.e., it is possible to solve the motion planning problem in polynomial time. The computational model of this problem was created using a discrete-time kinematic motion model of the robot and position-level complementarity constraint. The collision model was created for this project at the kinematic level using a complementarity constraint. For collision avoidance, we applied a velocity to the robot to bring the normal component of the robot's velocity to zero based on the complementarity constraint for collision avoidance. The environment creation and the simulation of this movement of the robot using the mathematical model and complementarity constraint has been done in Python where it has been proved that the model works for any complex environment with non-overlapping circular obstacles. After proving our theory with circular obstacles in the 2D environment the same implementation was extended to prove our model in a 3D environment with Spherical obstacles. In our future work we plan to study the problem of characterizing computationally efficient motion planning instances using polygonal obstacles.