Optimal Knock-Pick Planning for Tightly Packed Tabletop Blocks With Parallel Grippers
For robotic manipulation in cluttered environments, this paper provides a theoretical foundation and efficient algorithm for interleaving prehensile and non-prehensile actions, though it is limited to uniformly sized blocks on a grid.
This work addresses the problem of rearranging densely packed tabletop blocks with parallel grippers, where direct picking is often infeasible due to lack of clearance. They introduce a directional knock primitive and formulate an optimal knock-pick planning problem, solving it in polynomial time using maximum-weight perfect matching on a graphical abstraction, achieving minimal action plans.
Rearranging densely packed tabletop objects is challenging when parallel-gripper picks are infeasible without sufficient clearance around an object. This work studies the problem characteristics for practically motivated settings with uniformly sized blocks placed at planar tabletop grid locations. Since purely prehensile removal can become infeasible, a directional knock primitive is therefore introduced and the optimal knock-pick variant of the problem is formulated. The work proposes a series of abstractions wherein minimal constraining gadgets are covered to identify the necessary knocks. Utilizing a maximum-weight perfect matching on a graphical abstraction yields efficient polynomial-time computation of the optimal plan that minimizes the number of actions. Experiments are reported for increasing grid sizes in synthetic settings as well as in IsaacSim. The theoretical observations provide a promising stepping stone towards rigorously building efficient manipulation strategies that interleave prehensile and non-prehensile actions.