このプロジェクトは、多目的連続時間MAPFに対する多目的連続時間CBS(MOCCBS)をC++で実装しています。
MOCCBSは、先行研究であるBB-MO-CBSを拡張したアルゴリズムであり、そのレポジトリはこちらになります。
本コードは、学術的および非営利目的での使用に限り配布されます。 本ソフトウェアは「現状有姿」で提供され、明示的または黙示的ないかなる保証もありません。これには商品性、特定目的適合性、権利非侵害の保証が含まれますが、これらに限定されません。いかなる場合においても、 作者または著作権者は、契約、不法行為その他のいかなる法的根拠に基づくものであれ、 本ソフトウェアまたはその使用もしくはその他の取引に起因し、 または関連して生じる一切の請求、損害賠償その他の責任について、 一切の責任を負いません。
コードのコンパイルには、CMake (version 3.26.4で動作確認)とC++17 対応のコンパイラ (Clang 17.0.0で動作確認)が必要です。 異なるバージョンのC++でも動作する可能性があります。
README.md- 本ファイル。cpp/include- ヘッダファイルcpp/source- ソースコードcpp/test- テスト用のサンプルコード。map/- マップデータ。MAPF Benchmarkに対応。
cpp/libに、
hog2/utils at PDB-refactor · nathansttt/hog2から持ってきたScenarioLoader.hとScenarioLoader.cppを配置。
MAPF Benchmarks のマップデータ、シナリオデータを利用可能。
mkdir build
cd cpp
cmake -B build
cmake --build build
build/test_avetime_nb
本レポジトリは、以下の論文およびレポジトリを利用して作成されました。 ここに感謝を示します。
-
[1] Binary Branching Multi-Objective Conflict-Based Search for Multi-Agent Path Finding
Zhongqiang Ren, Jiaoyang Li, Han Zhang, Sven Koenig, Sivakumar Rathinam and Howie Choset.
International Conference on Automated Planning and Scheduling (ICAPS), 2023. -
[2] rap-lab-org/public_bbmocbs: Binary Branching Multi-Objective Conflict-Based Search [Link]
-
[3] rap-lab-org/public_mosipp: C++ Implementation of Multi-Objective Safe-Interval Path Planning [Link]
-
[4] Multi-Agent Pathfinding with Continuous Time
Anton Andreychuk, Konstantin Yakovlev, Dor Atzmon and Roni Stern. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI-19), 2019. -
[5] PathPlanning/Continuous-CBS: Continuous CBS - a modification of conflict based search algorithm, that allows to perform actions (move, wait) of arbitrary duration. Timeline is not discretized, i.e. is continuous. [Link]
-
[6] nathansttt/hog2: Pathfinding and search testbed/visualization suite. Current code is in PDB-refactor branch. [Link]
-
[7] MAPF Benchmarks [Link]