For planning rearrangements of objects in a clutter, it is required to know the goal configuration of the objects. However, in real life scenarios, this information is not available most of the time. We introduce a novel method that computes a collision-free placement of objects on a cluttered surface, while minimizing the total number and amount of displacements of the existing moveable objects. Our method applies nested local searches that perform multi-objective optimizations guided by heuristics. Experimental evaluations demonstrate high computational efficiency and success rate of our method, as well as good quality of solutions.
Related work in robotics Rearrangement of multiple movable objects, a challenging problem that involves planning, manipulation and geometric reasoning, has received much attention in robotics. In particular, planning for geometric rearrangement with multiple movable objects and its variations, such as navigation among movable obstacles @cite_29 @cite_5 , have been studied using various approaches. Since even a simplified variant the rearrangement problem with only one movable obstacle has been proved to be NP-hard @cite_16 @cite_11 , most studies introduce several important restrictions to the problem, like monotonicity of plans @cite_18 @cite_25 @cite_10 @cite_1 @cite_7 , where each object can be moved at most once. Recent work have focused on generating non-monotonic plans @cite_13 @cite_4 @cite_30 @cite_6 @cite_22 @cite_23 . However, in most of these studies @cite_18 @cite_25 @cite_10 @cite_1 @cite_4 @cite_30 @cite_6 @cite_22 , it is assumed that the goal configuration is known. Finding suitable arrangements for objects on a cluttered surface has received relatively less attention.
@cite_13 @cite_30 @cite_18 @cite_4 @cite_22 @cite_7 @cite_29 @cite_1 @cite_6 @cite_23 @cite_5 @cite_16 @cite_10 @cite_25 @cite_11
2015241127 2968156685 2087191078 2419360507
This work proposes a method for efficiently computing manipulation paths to rearrange similar objects in a cluttered space. Rearrangement is a challenging problem as it involves combinatorially large, continuous configuration spaces due to the presence of multiple bodies and kinematically complex manipulators. This work leverages ideas from multi-robot motion planning and manipulation planning to propose appropriate graphical representations for this challenge. These representations allow to quickly reason whether manipulation paths allow the transition between entire sets of object arrangements without having to explicitly store these arrangements. The proposed method also takes advantage of precomputation given a manipulation roadmap for transferring a single object in the space. The approach is evaluated in simulation for a realistic model of a Baxter robot and executed on the real system, showing that the method solves complex instances and is promising in terms of scalability and success ratio. We present an algorithm that produces a plan for relocating obstacles in order to grasp a target in clutter by a robotic manipulator without collisions. We consider configurations where objects are densely populated in a constrained and confined space. Thus, there exists no collision-free path for the manipulator without relocating obstacles. Since the problem of planning for object rearrangement has shown to be NP-hard, it is difficult to perform manipulation tasks efficiently which could frequently happen in service domains (e.g., taking out a target from a shelf or a fridge).Our proposed planner employs a collision avoidance scheme which has been widely used in mobile robot navigation. The planner determines an obstacle to be removed quickly in real time. It also can deal with dynamic changes in the configuration (e.g., changes in object poses). Our method is shown to be complete and runs in polynomial time. Experimental results in a realistic simulated environment show that our method improves up to 31 of the execution time compared to other competitors. We introduce a novel computational method for geometric rearrangement of multiple movable objects on a cluttered surface, where objects can change locations more than once by pick and or push actions. This method consists of four stages: (i) finding tentative collision-free final configurations for all objects (all the new objects together with all other objects in the clutter) while also trying to minimize the number of object relocations, (ii) gridization of the continuous plane for a discrete placement of the initial configurations and the tentative final configurations of objects on the cluttered surface, (iii) finding a sequence of feasible pick and push actions to achieve the final discrete placement for the objects in the clutter from their initial discrete place, while simultaneously minimizing the number of object relocations, and (iv) finding feasible final configurations for all objects according to the optimal task plan calculated in stage (iii). For (i) and (iv), we introduce algorithms that utilize local search with random restarts; for (ii), we introduce a mathematical modeling of the discretization problem and use the state-of-the-art ASP reasoners to solve it; for (iii) we introduce a formal hybrid reasoning framework that allows embedding of geometric reasoning in task planning, and use the expressive formalisms and reasoners of ASP. We illustrate the usefulness of our integrated AI approach with several scenarios that cannot be solved by the existing approaches. We also provide a dynamic simulation for one of the scenarios, as supplementary material. We address the problem of a mobile manipulation robot searching for an object in a cluttered domain that is populated with an unknown number of objects in an unknown arrangement. The robot must move around its environment, looking in containers, moving occluding objects to improve its view, and reasoning about collocation of objects of different types, all in service of finding a desired object. The key contribution in reasoning is a Markov-chain Monte Carlo (MCMC) method for drawing samples of the arrangements of objects in an occluded container, conditioned on previous observations of other objects as well as spatial constraints. The key contribution in planning is a receding-horizon forward search in the space of distributions over arrangements (including number and type) of objects in the domain; to maintain tractability the search is formulated in a model that abstracts both the observations and actions available to the robot. The strategy is shown empirically to improve upon a baseline systematic search strategy, and sometimes outperforms a method from previous work.