  Motion planning seeks a collision-free path in a configuration space
(C-space), representing all possible robot configurations in the environment.
As it is challenging to construct a C-space explicitly for a high-dimensional
robot, we generally build a graph structure called a roadmap, a discrete
approximation of a complex continuous C-space, to reason about connectivity.
Checking collision-free connectivity in the roadmap requires expensive
edge-evaluation computations, and thus, reducing the number of evaluations has
become a significant research objective. However, in practice, we often face
infeasible problems: those in which there is no collision-free path in the
roadmap between the start and the goal locations. Existing studies often
overlook the possibility of infeasibility, becoming highly inefficient by
performing many edge evaluations.
  In this work, we address this oversight in scenarios where a prior roadmap is
available; that is, the edges of the roadmap contain the probability of being a
collision-free edge learned from past experience. To this end, we propose an
algorithm called iterative path and cut finding (IPC) that iteratively searches
for a path and a cut in a prior roadmap to detect infeasibility while reducing
expensive edge evaluations as much as possible. We further improve the
efficiency of IPC by introducing a second algorithm, iterative decomposition
and path and cut finding (IDPC), that leverages the fact that cut-finding
algorithms partition the roadmap into smaller subgraphs. We analyze the
theoretical properties of IPC and IDPC, such as completeness and computational
complexity, and evaluate their performance in terms of completion time and the
number of edge evaluations in large-scale simulations.
