Task and Motion Planning for Grasping with Object Rearrangement in Clutter

Abstract

This thesis proposes a manipulation planning algorithm for efficient object rearrangement and grasping of a target object by a mobile manipulator in a cluttered environment with densely packed objects, where the target object is inaccessible. To grasp a single object in an unobstructed space, the precise position of the object, the robot's grasping motion, and the base position of the robot must be determined. However, in cases where objects are densely arranged, there may be occluded objects or objects for which grasping motions cannot be generated. If the target object is obscured by other objects and its position is unknown, object rearrangement is required to locate the target object. Additionally, if the target object's position is known but grasping motions cannot be generated due to surrounding objects, object rearrangement is necessary to create a space where the target object can be grasped. Furthermore, when objects are closely adjacent to each other, with distances narrower than the gripper's finger thickness, grasping the objects without collisions becomes impossible. In such cases, non-prehensile manipulation considering gripper-object collisions is required to generate a space where the gripper can grasp the object.

The problem of manipulating objects by a robot, involving the picking or placing of objects, is proven to be NP-hard. When rearranging objects, the plan generation process for picking and placing actions can vary significantly depending on the algorithm utilized. Therefore, there is a need for an efficient algorithm to facilitate the practical use of robot applications in real-world environments. This thesis focuses on minimizing the time required to generate an object rearrangement plan and minimizing the number of action executions by the robot. To solve the problem, the author proposes local search and global search algorithms and presents a novel planning algorithm that combines both approaches. The local search algorithm generates a plan to rearrange a single object from the current object arrangement state and iteratively generates plans until the target object can be grasped. The local search algorithm generates plans to move objects in the direction where the number of objects is minimal, with the goal of minimizing the number of action executions by the robot. On the other hand, the global search algorithm generates a plan for all objects to be rearranged from the initial object arrangement state to grasp the target object. The global search algorithm creates a tree structure representing the anticipated object arrangement states by moving objects from the initial state and searches for an object arrangement state where the target object can be grasped, which is the goal node. Additionally, a heuristic search is applied to minimize the number of action executions by finding the minimum cost path from the initial node to the goal node. Finally, the author compares the local search and global search algorithms and suggests a novel algorithm that can reduce robot execution time and increase the work success rate in the real environment by improving the disadvantages of the two algorithms.