This repository implements the Space-Time Graphs of Convex Sets (ST-GCS) from the following paper:
- *Jingtao Tang, Zining Mao, Lufan Yang, and Hang Ma. "Space-Time Graphs of Convex Sets for Multi-Robot Motion Planning." [paper], [project]
- Python dependencies can be installed via
pip install -r requirements.txt - Mosek solver should be installed, which is used in the Drake library for the GCS program solving.
- [Optional] You can also use Gurobi solver for Drake, however, building Drake from source is required. See detailed installation guidance here.
-
baselines/
- st_rrt_star/: the directory containing the ST-RRT* algorithm.
- tprm/: the directory containing the T-PRM algorithm.
- rp_stgcs.py: the random-prioritized planner (RP) and sequential planner (SP) for Multi-Robot Motion Planning (MRMP), with ST-GCS as the low-level single-robot planner.
- sp_strrtstar.py: the sequential planner (SP) for MRMP with ST-RRT* as the low-level single-robot planner.
- sp_tprm.py: the sequential planner (SP) for MRMP with T-PRM as the low-level single-robot planner.
-
data: the directory containing the problem instances and experiment results.
-
demos: a collection of demonstrations for space-time single-robot motion planning and MRMP.
-
environment:
- examples.py: a collection of env examples.
- env.py: the Environment class of the environment.
- obstacle.py: a simple implementation of static obstacles and dynamic obstacles.
- problems.py: code for generating random problems.
-
mrmp/
- ecd.py: Exact Convex Decomposition implementation.
- graph.py: the graph of convex sets class, adapted from GCS*.
- interval.py: a simple class representing an interval.
- pbs.py: Prioritized-Based Search implementation, adapted from the conflict solver for multi-robot coverage path planning.
- stgcs.py: the Space-Time Graphs of Convex Sets class.
- utils.py: a collection of utility functions.
-
exp.py: the experiment runner
-
plot.py: plot functions for the experiments
@misc{tang2025spacetimegraphsconvexsets,
title={Space-Time Graphs of Convex Sets for Multi-Robot Motion Planning},
author={Jingtao Tang and Zining Mao and Lufan Yang and Hang Ma},
year={2025},
eprint={2503.00583},
archivePrefix={arXiv},
primaryClass={cs.RO},
url={https://arxiv.org/abs/2503.00583},
}
ST-GCS is released under the GPL version 3. See LICENSE.txt for further details.