PoliTO System and Device Programming project Quer 1 (The Path-Planning Algorithm A*)
- D'Andrea Giuseppe s303378
- De Rosa Mattia s303379
binaries
- Precompiled binaries for windows and linuxdata
- Graph input files and raw output filesdocumentation
- Documentation markdown sourcegraph_generation
- C++ source code for k-neighbors graph generationhdastar_message_passing
- C++ source code for Hash Distributed A* with message passinghdastar_shared
- C++ source code for Hash Distributed A* with shared memoryinclude
boost_1_80_0
- Minimal version of Boost C++ Library v1.80.0graph_utils
- C++ source code for common operations for the different algorithmsstats
- C++ source code for stats gathering helper class
scripts
- Python helper scriptslauncher.py
- Wrapper to run multiple versions of A*osm_to_graph.py
- Script to convert OpenStreetMap XML files to graphs
sequential_astar
- C++ source code for sequential A*
Multiple helper scripts have been used to generate the graphs used to test the algorithms.
graph_generation/main.cpp
: generate a random 2D graph, in a square grid of size S*S with N nodes, each connected with its K nearest neighbors.- Usage:
graph_generation.exe S N [K]
. If K is omitted is calculated as $ K = 2elog(n) $
- Usage:
scripts/osm_to_graph.py
: python script to convert OpenStreetMap XML files to graph text files.- Usage:
python osm_to_graph_py INPUT_FILE
- Input files for this script have been obtained thanks to Overpass Api and Overpass Turbo
- Usage:
The different algorithms are contained in the following folders:
sequential_astar
: Sequential version of A*hdastar_message_passing
: Parallel version of Hash Distributed A* that uses message_passing and barriers to synchronize threadshdastar_shared
: Parallel version of Hash Distributed A* that uses shared memory and barriers to synchronize threads
Precompiled binaries are provided for windows_x86_64 and for linux_x86_64 in the folder binaries
It is suggested to build the project with gcc on linux or with MSVC on Windows. MinGW on Windows causes issues with the barriers and the parallel versions don't work properly.
The project contains CMakeLists.txt
which can be used to build the different versions of the algorithm.
Targets:
graph_generation
sequential_astar
hdastar_message_passing
hdastar_shared
Example:
cmake -S SDP-Astar/ -B build_folder/
cmake --build build_folder/ --target sequential_astar -j 12
All versions of A* have the same usage: ./executable FILENAME STARTING_SEED [N_SEEDS=1] [N_REPS=1]
The first two parameters are mandatory and have to be the name of the graph file and the seed used to randomly generate the start and end nodes. The following two parameters are used to execute the algorithm multiple times with different seeds and multiple time per seed respectively.
Examples:
sequential_astar berlin.txt 24
executes sequential A* once with given seedhdastar_shared turin.txt 1234 5 3
executes shared memory A* a total of 15 times, 3 for each different seed, starting from the given one
Execution results are dumped in a csv file (AstarReport.csv
) for every run performed, containing multiple statistics, including found path, number of steps, total weight of path and execution time for every phase.
A summary of these results is also printed in stdout for every run.
The project includes part of the boost C++ library. Version 1.80.0 of Boost has been used to code and test the algorithms and a minimal version of boost including only the required classes has been included in the zip file.
If you want to manually add the library download it from the official site https://www.boost.org/users/download/ and unzip in the include directory. If the version is not the 1.80.0 or the folder is not called boost_1_80_0
the CMakeLists.txt
should be updated with the new location of the library.