xyboxu / pydecomp

A Python based implementation for fast convex decomposition of obstacle-free spaces.

pydecomp — A Python implementation of DecompUtil for fast convex decomposition of obstacle-free spaces.

Quickstart

Install dependencies with

    sudo apt-get install libcdd-dev libblas3 libblas-dev liblapack3 liblapack-dev gfortran

and (in a virtual environment) install from PyPI with

    pip install pydecomp

Examples

Convex decomposition of free space from occupancy grid map

Given an occupancy grid map and a pieciwise linear path, the package returns a convex decomposition of the free space. The free space is represented by a collection of convex sets, whose halspace representation fulfills Ax-b<0. The package returns the matrixes A and b for each convex set. The matrix A is a n x 3 matrix and b is a n x 1 vector, where n is the number of planes in the halfspace.

To check a script to perform a convex decomposition out of a given occupancy grid map, see this file for a planar (2D) case or this file for a spatial (3D) case. We provide two exemplary maps (forest and office), which you can select by modifying this line.

Forest - 2D	Office - 2D	Office - 3D

For the most minimal example see this file, which replicates a test case in the original DecompUtil repository.

Environment generation

Run this file to see how to generate random corridors. When doing so, feel free to change the randomization parameters. These are given in this function definition.

Note: Currently the randomization algorithm works better for 3D (set planar=False in here). For 2D, the randomization algorithm is not very good and, in some cases, the resultant corridor has a weird shape. This should be fixed in the future.

See here two examples of corridors (planar and spatial) generated with the randomization algorithm:

Planar	Spatial

The blue polyhedrons are the convex decomposition of the obstacle-free space. The inner black line depicts the underlying piecewise linear path used to construct the polyhedrons. The green and red dots, alongside their frames, refer to the starting and ending pose of the agent.

Transformation and normalization of the polyhedrons

When using the environment generator for generating a dataset of corridors, it might be beneficial to represent all of them in a normalized and standard representation. Towards this aim, we provide the feature to normalize and translate the polyhedrons, so that the matrixes for the halfspaces are given by values between 0 and 1 and the origin coincides with the starting pose of the agent (green dot and frame). See these functions for more details.

Installing from source

After installing the dependencies given above, initialize git submodules with

    git submodule init
    git submodule update

Install the package with

    pip install .

Citing

If you use this framework please cite our paper:

@article{arrizabalaga2022spatially,
  title={Spatially Constrained Time-Optimal Motion Planning},
  author={Arrizabalaga, Jon and Ryll, Markus},
  journal={arXiv preprint arXiv:2210.02345},
  year={2022}
}