Computational Tradeoffs of Search Methods for Minimum Constraint Removal Paths
Submitted by bekris on Mon, 04/06/2015  17:05
Title  Computational Tradeoffs of Search Methods for Minimum Constraint Removal Paths 
Publication Type  Conference Paper 
Year of Publication  2015 
Authors  Krontiris, A, Bekris, KE 
Conference Name  Symposium on Combinatorial Search (SoCS) 
Date Published  06/2015 
Conference Location  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 boundedlength 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 