Computational Tradeoffs of Search Methods for Minimum Constraint Removal Paths

TitleComputational Tradeoffs of Search Methods for Minimum Constraint Removal Paths
Publication TypeConference Paper
Year of Publication2015
AuthorsKrontiris, A, Bekris, KE
Conference NameSymposium on Combinatorial Search (SoCS)
Date Published06/2015
Conference LocationDead Sea, Israel

The typical objective of path planning is to find the shortest
feasible path. Many times, however, there may be no solution given the
existence of constraints, such as obstacles. In these cases, the
minimum constraint removal problem asks for the minimum set of
constraints that need to be removed from the state space to find a
solution. For instance, in manipulation planning, it is desirable to
compute the minimum set of obstacles to be cleared from the workspace
to manipulate a target object. Unfortunately, minimum constraint
removal paths do not exhibit dynamic programming properties, i.e.,
subsets of optimum solutions are not necessarily optimal. Thus,
searching for such solutions is computationally expensive. This leads
to approximate methods, which balance the cost of computing a solution
and its quality. This work investigates alternatives in this context
and evaluates their performance in terms of such tradeoffs. Solutions
that follow a bounded-length approach, i.e., searching for paths up to
a certain length, seem to provide a good balance between minimizing
constraints, computational cost and path length.