tuero/pra_star

Implementation of the PRA* pathfinding algorithm

PRA* Implementation

PRA* and A* implementation for CMPUT 658 final project.

Project Walkthrough

• experiments/ Directory containing the data generated by the program
• logs/ Logs of the experimental runs
• scenarios/ Directory containing the maps and scenarios
• scripts/ Scripts to generate search graphs, run all experiments, and create paper figures
• src/algorithm/pra_star/ Implementation for PRA*
• src/algorithm/a_star/ Implementation for A*
• src/algorithm/common/ Common graph structs for search algorithms
• src/util/ Various utility functions/structs, from personal library (tpl)

Dependencies

The following libraries are used in this project.

• abseil-cpp
• spdlog

They are included as git submodules, so it is recommended you install them by using the git --recursive argument. If a non-recursive clone is done initially, use

git submodule init 
git submodule update

Compile the Project

# Enter base project dir
cd pra_star

# Compile
mkdir build && cd build
mkdir Release && cd buiReleaseld
cmake -DCMAKE_BUILD_TYPE=Release ../..
make -j$(nproc)

Run IDA* and BTS

The following command line arguments

cd build/Release

run_multi: Usage:
./src/run_multi <scenario_path> <export_path> <algorithm> <k>

Flags:
    --algorithm (Search algorithm to run); default: "pra_star";
    --export_path (Base directory for saved metrics); default: "/opt/";
    --k (K parameter for PRA*, use 0 as infinity); default: 0;
    --scenario_path (Full path for the scenario); default: "/opt/";

To see the runs used for the project, see runs.txt

Create and Serialize Map Graphs

cd scripts
python create_graphs.py

Run Experiments on All Scenarios

To extract the results from the given solution example run:

cd scripts
python run_algorithms.py

Generate Results Figures

cd scripts
python generate_results_figure.py