@conference {149,
title = {Computational Tradeoffs of Search Methods for Minimum Constraint Removal Paths},
booktitle = {Symposium on Combinatorial Search (SoCS)},
year = {2015},
month = {06/2015},
address = {Dead Sea, Israel},
abstract = {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.},
url = {http://www.cs.rutgers.edu/~kb572/pubs/Krontiris_SoCS2015_MCR.pdf},
author = {Krontiris, A. and Bekris, K. E.}
}