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.
@cite_21 aim to find sensible placements for furniture by initially generating a random arrangement, then rearranging it to minimize a cost function that measures the difference between the current arrangement and several positive examples provided by the user. @cite_23 also follow on this idea, and modify the algorithm so it becomes more suitable for robotic applications. Neither study considers heavily cluttered scenes or utilizes high resolution collision checks. @cite_23 , the task is to rearrange objects currently available in the scene to achieve a more tidy arrangement; no new objects are added and there exists no constraints that force a certain set of objects to be on certain surfaces. Furthermore, in these studies, even the initial state is a feasible (collision-free) configuration, and the goal is to improve it in terms of a measure of tidiness.
@cite_21 @cite_23
2087191078 2968156685 2888726795 2419360507
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 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 present a method enabling a robot to automatically arrange objects using task and motion planning. Given an input scene consisting of cluttered objects, our method first constructs a target layout of objects as a guidance to the robot for arranging them. For constructing the layout, we use positive examples and pre-extract hierarchical, spatial and pairwise relationships between objects, to understand the user preference on arranging objects. Our method then enables a robot to arrange input objects to reach their target configurations using any task and motion planner. To efficiently arrange the objects, we also propose a priority layer that decides an order of arranging objects to take a small amount of actions. This is achieved by utilizing a dependency graph between objects. We test our method in three different scenes with varying numbers of objects, and apply our method to two well-known task and motion planners with the virtual PR2 robot. We demonstrate that we can use the robot to automatically arrange objects, and show that our priority layer reduces the total running time up to 2.15 times in those tested planners. 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.