Trade-off in the computation of minimum constraint removal paths for manipulation planning. (17th December 2017)

• Record Type: Journal Article
• Authors: Krontiris, Athanasios; Bekris, Kostas E.
• Is Part Of: Advanced robotics. Volume 31:Number 23/24(2018)
• Page Start: 1313
• Page End: 1324
• Publication Date: 2017-12-17
• Subjects: Shortest path -- constraint removal -- manipulation planning -- multiple objects -- rearrangement; Robotics -- Periodicals; Robotics -- Japan -- Periodicals; Robotics; Japan; Periodicals; 629.89205
• DOI: 10.1080/01691864.2017.1378593
• Languages: English
• ISSNs: 0169-1864

Abstract

Graphical Abstract: Abstract: The typical objective in path planning is to find the shortest feasible path. Many times, however, such paths may not be available given constraints, such as movable obstacles. This frequently happens in manipulation planning, where it may be desirable to identify the minimum set of movable obstacles to be cleared to manipulate a target object. This is a similar objective to that of the Minimum Constraint Removal (MCR) problem, which, however, does not exhibit dynamic programming properties, i.e. subsets of optimum solutions are not necessarily optimal. Thus, searching for MCR paths is computationally expensive. Motivated by this challenge and related work, this paper investigates approximations for computing MCR paths in the context of manipulation planning. The proposed framework searches for MCR paths up to a certain length of solution in terms of end-effector distance. This length can be defined as a multiple of the shortest path length in the space when movable objects are ignored. Given experimental evaluation on simulated manipulation planning challenges, the bounded-length approximation provides a desirable trade-off between minimizing constraints, computational cost, and path length.