pydecomp 2.0.0

A Python package for decomposing obstacle free spaces into convex polygons

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

Quickstart

Install dependencies the following:

• Linux:

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

• Mac:

      brew install cddlib gmp eigen openblas cython boost
  

  Note: Remember to set LDFLAGS and CPPFLAGS to the correct paths for the libraries.

In a virtual environment, install from PyPI with

    pip install pydecomp

Conda

pycddlib does not ship Linux/macOS wheels, so pip builds it from source and needs the cddlib C headers. In a conda environment the easiest path is to let conda-forge supply cddlib and point pip at the env's include/lib paths:

conda create -n pydecomp_env python=3.12 -y
conda activate pydecomp_env
conda install -c conda-forge cddlib tk -y           # tk gives matplotlib a working GUI backend

export CPPFLAGS="-I$CONDA_PREFIX/include"
export LDFLAGS="-L$CONDA_PREFIX/lib"

pip install pydecomp
python -c "import pydecomp; print(pydecomp.__version__)"

If plt.show() produces no window, matplotlib has no interactive backend — conda install -c conda-forge tk (above) fixes it; alternatively pip install pyqt5.

Examples

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

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.

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

https://github.com/jonarriza96/pydecomp/blob/1d1c6f97d6eff1f2b3b90bdb2f038eed0caa8578/examples/ellipsoid_decomp_2D.py#L5-L19

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 papers:

@misc{arrizabalaga2024differentiablecollisionfreeparametriccorridors,
      title={Differentiable Collision-Free Parametric Corridors}, 
      author={Jon Arrizabalaga and Zachary Manchester and Markus Ryll},
      year={2024},
      eprint={2407.12283},
      archivePrefix={arXiv},
      primaryClass={cs.RO},
      url={https://arxiv.org/abs/2407.12283}, 
}

@inproceedings{arrizabalaga2023sctomp,
  title={SCTOMP: Spatially Constrained Time-Optimal Motion Planning},
  author={Arrizabalaga, Jon and Ryll, Markus},
  booktitle={2023 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)},
  pages={4827--4834},
  year={2023},
  organization={IEEE}
}

Related repositories

For computing continuous and differentiable collision-free corridors, check out CorrGen!