We focus on push-based multi-object rearrangement planning using a nonholonomically constrained mobile robot. The simultaneous geometric, kinematic, and physics constraints make this problem especially challenging. Prior work on rearrangement planning often relaxes some of these constraints by assuming dexterous hardware, prehensile manipulation, or sparsely occupied workspaces. Our key insight is that by capturing these constraints into a unified representation, we could empower a constrained robot to tackle difficult problem instances by modifying the environment in its favor. To this end, we introduce a push-traversability graph, whose vertices represent poses that the robot can push objects from, and edges represent optimal, kinematically feasible, and stable transitions between them. Based on this graph, we develop ReloPush, a graph-based planning framework that takes as input a complex multi-object rearrangement task and breaks it down into a sequence of single-object pushing tasks. We evaluate ReloPush across a series of challenging scenarios, involving the rearrangement of densely cluttered workspaces with up to nine objects, using a 1/10-scale robot racecar. ReloPush exhibits orders of magnitude faster runtimes and significantly more robust execution in the real world, evidenced in lower execution times and fewer losses of object contact, compared to two baselines lacking our proposed graph structure.

We present a coordination method for multiple mobile manipulators to sort objects in clutter. We consider the object rearrangement problem in which the objects must be sorted into different groups in a particular order. In clutter, the order constraints could not be easily satisfied since some objects occlude other objects so the occluded ones are not directly accessible to the robots. Those objects occluding others need to be moved more than once to make the occluded objects accessible. Such rearrangement problems fall into the class of nonmonotone rearrangement problems which are computation-ally intractable. While the nonmonotone problems with order constraints are harder, involving with multiple robots requires another computation for task allocation. In this work, we aim to develop a fast method, albeit sub-optimally, for the multi-robot coordination for ordered sorting in clutter. The proposed method finds a sequence of objects to be sorted using a search such that the order constraint in each group is satisfied. The search can solve nonmonotone instances that require temporal relocation of some objects to access the next object to be sorted. Once a complete sorting sequence is found, the objects in the sequence are assigned to multiple mobile manipulators using a greedy task allocation method. We develop four versions of the method with different search strategies. In the experiments, we show that our method can find a sorting sequence quickly (e.g., 4.6 sec with 20 objects sorted into five groups) even though the solved instances include hard nonmonotone ones. The extensive tests and the experiments in simulation show the ability of the method to solve the real-world sorting problem using multiple mobile manipulators.

We consider the problem of retrieving a target object from a confined space by two robotic manipulators where overhand grasps are not allowed. If other movable obstacles occlude the target, more than one object should be relocated to clear the path to reach the target object. With two robots, the relocation could be done efficiently by simultaneously performing relocation tasks. However, the precedence constraint between the tasks (e.g, some objects at the front should be removed to manipulate the objects in the back) makes the simultaneous task execution difficult. We propose a coordination method that determines which robot relocates which object so as to perform tasks simultaneously. Given a set of objects to be relocated, the objective is to maximize the number of switches between the robots in performing relocation tasks. Thus, one robot can pick an object in the clutter while the other robot places an object in hand to the outside of the clutter. However, the object to be relocated may not be accessible to all robots, so switching could not always be achieved. Our method is based on the uniform-cost search so the number of switches can be maximized. We also propose a greedy variant whose computation time is shorter. From experiments, we show that our method reduces the completion time of the mission by at least 22.9% (at most 27.3%) compared to the methods with no consideration of switching.

We consider the problem of rearranging objects in a cluttered and confined space using a robotic manipulator. The goal is to retrieve a target object from the clutter where the target is occluded by other objects. In situations where overhand grasps are not allowed, the robot needs to remove some objects to make the target accessible. In the course of removing the objects, the robot also needs to determine the locations to place the removed objects. If the robot can access enough empty spaces around or inside the clutter, the placement of the objects is trivially simple. If empty spaces are scarce, placing objects should be done in a principled way as an incorrect placement would deplete the empty spaces quickly.In this work, we propose a method that solves the problems of what and where to relocate objects inside the clutter to retrieve the target. Previously, there have been several efficient methods proposed that deal with each of the what and where to relocate problems separately. We solve the problems together using a graph structure constructed from an object configuration. Also, the method runs fast so scalable in the number of objects. Compared to a state-of-the-art method, our method reduces task and motion planning time up to 74.9% (at least 56.7%) and has a higher success rate under a short time limit for planning, which is 3 minutes.

In this paper, we present an automatic collection method of image data for neuro-symbolic task planning for robot navigation. Collecting images for robot task planning would often be overwhelmed by laborious chores to operate the robot, change the environment, and repeatedly capture quality-assured images. We propose a method using a robotic simulator to perform a series of repetitive processes for data collection automatically. It generates (i) a random instance of the navigation problem, (ii) a simulation environment that depicts the instance, (iii) a planning problem instance described in a classical planning language, (iv) a task plan that solves the planning problem, (v) control inputs for the robot to execute the task plan, and (vi) a sequence of cropped images capturing the evolving states of the robot and the world while the robot performs the plan. We use one of the state-of-the-art neuro-symbolic planning models to validate our method. From the evaluation, the model achieves at most 92.6% of the success rate in generating task plans successfully from only a pair of images showing the initial and the desired state.