pydecomp โ A Python implementation of DecompUtil for fast convex decomposition of obstacle-free spaces.
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
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.
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.
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.
After installing the dependencies given above, initialize git submodules with
git submodule init
git submodule update
Install the package with
pip install .
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}
}