Parallel Search-Based Planning Algorithms

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}
}

Usage

Dependencies

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

Building

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

Running the example

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