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

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.

pydecomp/examples/ellipsoid_decomp_2D.py

Lines 5 to 19 in 1d1c6f9

	import pydecomp as pdc
	# obstacles, path and bounding box
	obstacles = np.loadtxt(
	str(Path(__file__).parent.absolute()) + "/data/decomputil/obstacles.txt"
	)
	path = np.array([[1, 1], [0, 0], [-1, 1]])
	box = np.array([[2, 2]])
	# convex decomposition
	A, b = pdc.convex_decomposition_2D(obstacles, path, box)
	ax = pdc.visualize_environment(Al=A, bl=b, p=path, planar=True)
	ax.plot(obstacles[:, 0], obstacles[:, 1], "o", color="red")
	plt.show()

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!