This repository maintains open-source implementations of several parallel search-based planning algorithms. Currently, the following algorithms are available:
- wA*: Weighted A* [Pohl 1970]
- ARA*: Anytime Repairing A* [Likhachev et al. 1970]
- PwA*: Parallel Weighted A* (As explained in the ePA*SE and MPLP papers)
- PA*SE: Parallel A* For Slow Expansions [Phillips et al. 2014]
- MPLP: Massively Parallelized Lazy Planning [Mukherjee et al. 2022]
- ePA*SE: Edge-based Parallel A* For Slow Evaluations [Mukherjee et al. 2022]
- GePA*SE: Generalized Edge-Based Parallel A* for Slow Evaluations [Mukherjee et al. 2023]
- A-ePA*SE: Anytime Edge-Based Parallel A* for Slow Evaluations [Yang et al. 2023]
If you use MPLP, please use the following citation:
@article{mukherjee2022mplp,
title = {{MPLP}: Massively Parallelized Lazy Planning},
author = {Mukherjee, Shohin and Aine, Sandip and Likhachev, Maxim},
year = 2022,
journal = {IEEE Robotics and Automation Letters},
publisher = {IEEE},
volume = 7,
number = 3,
pages = {6067--6074}
}
If you use ePA*SE, please use the following citation:
@inproceedings{mukherjee2022epase,
author = {Mukherjee, Shohin and Aine, Sandip and Likhachev, Maxim},
title = {{ePA*SE}: Edge-Based Parallel {A*} for Slow Evaluations},
booktitle = {International Symposium on Combinatorial Search},
volume={15},
number={1},
pages={136--144},
publisher={{AAAI} Press},
year={2022}
}
If you use GePA*SE, please use the following citation:
@inproceedings{mukherjee2023gepase,
title = {{GePA*SE}: Generalized Edge-based Parallel {A*} for Slow Evaluations},
author = {Mukherjee, Shohin and Likhachev, Maxim},
year = 2023,
booktitle = {International Symposium on Combinatorial Search},
publisher = {{AAAI} Press}
}
If you use A-ePA*SE, please use the following citation:
@inproceedings{yang2023aepase,
title = {{A-ePA*SE}: Anytime Edge-based Parallel {A*} for Slow Evaluations},
author = {Yang, Hanlan and Mukherjee, Shohin and Likhachev, Maxim},
year = 2023,
booktitle = {International Symposium on Combinatorial Search},
publisher = {{AAAI} Press}
}
The planning code only uses C++ standard libraries and has no external dependencies. However, the robot_nav_2d example has the following dependencies:
- Boost C++
- OpenCV C++ for visualization
- sbpl package
- Clone the repository.
git clone https://github.com/shohinm/parallel_search.git
- Create build directory and compile.
cd parallel_search && mkdir build && cd build && cmake ../ -DCMAKE_BUILD_TYPE=Release && make
Run the following commands from within the build directory:
- wA*
./run_robot_nav_2d wastar
- ARA*
./run_robot_nav_2d arastar [time_budget] [heuristic_weight] [heuristic_reduction]
- PwA*, MPLP, PA*SE, ePA*SE, GePA*SE
./run_robot_nav_2d [algorithm] [num_threads]
- A-ePA*SE:
./run_robot_nav_2d agepase [num_threads] [time_budget] [heuristic_weight] [heuristic_reduction]
Maintained by : Shohin Mukherjee