Placement and Planning for Rearrangement Problems

Implementation of the methods described in [1].

Dependencies

Dependency	Version Tested On
clingo	5.2.2
DLVHEX	2.5.0
matplotlib	2.2.4
numpy	1.16.4
pandas	0.24.2
Pillow	6.0.0
pybullet	2.5.0
Python	2.7.15
Ubuntu	18.04

Installation

1. install clingo and DLVHEX such that they are callable with clingo and dlvhex, respectively.
2. cd [your virtual environments directory]
3. virtualenv rearrangement
4. source [your virtual environments directory]/rearrangement/bin/activate
5. cd [rearrangement directory]
6. pip install .

About

Given a surface with movable objects (clutter) and immovable objects (obstacles), the goal is to add another set of (new) objects to the surface. The overall approach is explained in [1].

1. The placement stage finds a collision-free final configuration 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, and the amount of movement each object is relocated. At this stage, the number, type, order, and feasibility of the move actions required to achieve this goal configuration are not considered.
2. The planning stage is divided into two:
   1. The discretization stage takes, as input, the initial configurations and the final configurations of all objects on the cluttered surface, and divides the surface into a minimum number of non-uniform grid cells. During gridization of the continuous plane, an object is allowed to span multiple grid cells as long as each grid cell contains the centroid of a single object.
   2. The planning stage aims to find a sequence of feasible move actions to achieve the final placement of the objects in the clutter from their initial discrete placement, while simultaneously minimizing the number of actions and object relocations.

This package contains:

• the physics module: a wrapper of the pybullet implementation of the Bullet physics engine specifically for the problem at hand,
• the search module: a generic search framework with lexicographic comparison,
• the placement module uses local searches to find a goal placement for the problem:
  • the inner submodule: a local search wrapper of pybullet's collision resolver,
  • the middle submodule: a local search that uses a grid-based heuristic on top of inner to minimize the number of objects in collision,
  • the outer submodule: a local search that uses circular constraints on top of middle to minimize the number of original objects moved and their movement,
  • the baselines submodule: naive local search baselines for comparison,
• the planning module uses the hybrid planning architecture [2] to compute a feasible plan of actions to realize the rearrangement:
  • the discretization submodule: an optimal discretizer using clingo,
  • the dlvhex submodule: the planning domain, as well as tools to link DLVHEX to the Python code,
  • the feasibility submodule: a local search that uses middle to act as the low-level feasibility checker for the hybrid planner,
• and some example instances.

All modules are written to be very general, and can be easily extended/wrapped with new features.

Notes

• When resolving collisions, the threshold of penetration depth at which a collision is recognized can be assigned using the physics.engine.set_collision_threshold() method, and can drastically improve performance without sacrificing robustness if set appropriately.
• middle uses a bit of stochasticity when re-placing. This is the only difference from the methods in [1].

Usage

To see a demo of the PGHP algorithm, run python main.py -v True

main.py is available as a sample code of how to use the software. The way to input a problem is by defining a query JSON file, which defines the shapes and sizes (by linking to URDF files which can link to obj or stl files), and poses of each object involved in the problem.

The query JSON file also describes the structure of problem by defining which objects are originals, obstacles, etc. The result can be output as a JSON file, structured identically to the query JSON. Example JSON queries are given in the data folder. Pillow is used to save images of the state at any time, and matplotlib is used to plot discrete configurations and performance measures.

References

• [1]: Dabbour, Abdul Rahman, Esra Erdem, and Volkan Patoglu. "Object Placement on Cluttered Surfaces: A Nested Local Search Approach." arXiv preprint arXiv:1906.08494 (2019).
• [2]: Erdem, Esra, Volkan Patoglu, and Peter Schüller. "A systematic analysis of levels of integration between high-level task planning and low-level feasibility checks." AI Communications 29.2 (2016): 319-349.

License

GNU Affero General Public License v3.0