Time-Aware Probabilistic Roadmaps

This repository contains a Python implementation of the Time-Aware PRM (TA-PRM) algorithm. TA-PRM is a sampling-based path planning algorithm that is able to find a solution to a path planning problem in known time-varying environments. In addition to the algorithm itself, this repository contains a simple simulation environment and a number of example scripts that showcase the core functionalities of the implementation, as well as an evaluation of the algorithm's performance.

Setup

Consider setting up a virtual environment for this project. The following commands will create a virtual environment and install the required dependencies:

python3 -m venv venv
source venv/bin/activate
pip install -r requirements.txt

In some cases, it might be necessary to set the PYTHONPATH environment variable to the root of this repository. This can be done by running the following command:

export PYTHONPATH=.

Example Scripts

The src/examples/ directory contains a number of example scripts. They showcase the core functionalities of this repository and offer an entry point into the codebase. For more detailed insights and edge cases, check out the test suite (below). Demonstration scripts for the following topics are currently available:

• Creation and plotting of defined or random Environment and EnvironmentInstance objects with static and dynamic obstacles, using matplotlib.
• Creation and plotting of Geometry objects, which can be of types Point, Line or Polygon.
• Creation and plotting of Graph objects, which can be generated from random samples in an environment.
• Example scenarios for the usage of the TimeAwarePRM class, which implements the TA-PRM algorithm.

A separate GitHub action is run on every push or pull_request. The status of the latest run can be seen in the badge at the top of this README.

Simulation Videos

The simulate-function of the graph class, allows to simulate a solution path in a time-varying environment and either illustrate the result using matplotlib or save it as a video. While the video is initially save in the avi-format, this results in a very large file size. A subsequent conversion to the more compressed mp4-format is implemented through the ffmpeg-tool. To install it on MacOS, run the following command:

brew install ffmpeg

For the installation of ffmpeg on other operating systems, please refer to the official documentation.

Test Suite

After installing the pytest package, the test suite can be run with the following command:

pytest src/test/

A corresponding GitHub action is also available. The status of the latest run can be seen in the badge at the top of this README.

License

This project is licensed under a AGPL-3.0 License - see the LICENSE file for details.