Algorithm for GMP1R with single hole
Jagrati Singh, Anmol Darak, Sanket S. Dash, Kalpesh Kapoor · 2014
In this paper, we are given an undirected, un-weighted, connected simple graph with n vertices. We have a movable robot and a hole at two distinct vertices, and non-distinct obstacles at the rest of the vertices. Each vertex holds either a robot or an obstacle or is empty. The empty vertex is said to have a hole. In one step the robot or an obstacle is free to move along an edge to reside at an adjacent vacant vertex containing hole. We analyze the motion planning problem where a robot initially at some given vertex, is required to be taken to a particular destination vertex. We describe a configuration graph approach to solve this type of problem and present O(n3) algorithms with similar backgrounds.