vss2sn / Path_planning
This repository contains path planning algorithms in C++ for a grid based search.
Stars: ✭ 70
Projects that are alternatives of or similar to Path planning
Glsl Grid
Draws an antialiased grid along the X/Y/Z direction of a mesh.
Stars: ✭ 57 (-18.57%)
Mutual labels: grid
Vehicleroutingproblem
Solved using AI techniques: Savings, Sweep, Genetic Algorithm, Google OR Tools
Stars: ✭ 61 (-12.86%)
Mutual labels: genetic-algorithm
Awesome Grid
A curated list of grid(table) libraries and resources that developers may find useful.
Stars: ✭ 1,142 (+1531.43%)
Mutual labels: grid
Dijkstra Cartography
Using Dijkstra's algorithm ("finding the shortest paths between nodes in a graph") to draw maps 🌍.
Stars: ✭ 1,112 (+1488.57%)
Mutual labels: dijkstra
Dragranksquare
edit personal information which enables users to drag and rank image order
Stars: ✭ 1,115 (+1492.86%)
Mutual labels: grid
React Stonecutter
Animated grid layout component for React
Stars: ✭ 1,089 (+1455.71%)
Mutual labels: grid
Awesome Decision Making Reinforcement Learning
A selection of state-of-the-art research materials on decision making and motion planning.
Stars: ✭ 68 (-2.86%)
Mutual labels: motion-planning
Ocgis
OpenClimateGIS is a set of geoprocessing and calculation tools for CF-compliant climate datasets.
Stars: ✭ 60 (-14.29%)
Mutual labels: grid
Radiate
Radiate is a parallel genetic programming engine capable of evolving solutions to many problems as well as training learning algorithms.
Stars: ✭ 65 (-7.14%)
Mutual labels: genetic-algorithm
Cgp Cnn
A Genetic Programming Approach to Designing CNN Architectures, In GECCO 2017 (oral presentation, Best Paper Award)
Stars: ✭ 59 (-15.71%)
Mutual labels: genetic-algorithm
Mgo
Purely functional genetic algorithms for multi-objective optimisation
Stars: ✭ 63 (-10%)
Mutual labels: genetic-algorithm
Applying eanns
A 2D Unity simulation in which cars learn to navigate themselves through different courses. The cars are steered by a feedforward neural network. The weights of the network are trained using a modified genetic algorithm.
Stars: ✭ 1,093 (+1461.43%)
Mutual labels: genetic-algorithm
Ecommerce Netlify
🛍 A JAMstack Ecommerce Site built with Nuxt and Netlify Functions
Stars: ✭ 1,147 (+1538.57%)
Mutual labels: grid
Genann
simple neural network library in ANSI C
Stars: ✭ 1,088 (+1454.29%)
Mutual labels: genetic-algorithm
Awesome Robotics Libraries
😎 A curated list of robotics libraries and software
Stars: ✭ 1,159 (+1555.71%)
Mutual labels: motion-planning
Lagrit
Los Alamos Grid Toolbox (LaGriT) is a library of user callable tools that provide mesh generation, mesh optimization and dynamic mesh maintenance in two and three dimensions.
Stars: ✭ 67 (-4.29%)
Mutual labels: grid
Super Mario Neat
This program evolves an AI using the NEAT algorithm to play Super Mario Bros.
Stars: ✭ 64 (-8.57%)
Mutual labels: genetic-algorithm
Path Planning
This repository contains path planning algorithms in C++.
Algorithms:
- Dijkstra's algorithm for grid based search.
- AStar (A*) algorithm for grid based search.
- Jump Point Search for grid based search (Modified for 4 way motion; no diagonal motion).
- Lifelong Planning AStar (LPA*) algorithm for grid based search.
- DStarLite (D* Lite) algorithm for grid based search.
- RRT algorithm for grid based search.
- RRTStar (RRT*) algorithm for grid based search.
- Ant Colony Optimization algorithm (ACO) for grid based search.
- Genetic algorithm (GA) for grid based search.
To build and run:
git clone https://github.com/vss2sn/path_planning.git
cd path_planning
mkdir build
cd build
cmake .. && make -j4
./main
Table of contents
- Algorithms
- Instructions
- Table of contents
- Notes
- Notes on CMake Options
- Notes on tests
- Notes on implementations
- TODOs
- Consider
Notes:
-
main
creates a grid of a given size n, with any point set as an obstacle with a probability of 1/n. It then runs all the algorithms in the repository on the given grid. - Documentation can be found on GitHub pages. It has been created using Doxygen, and pip3 packages Sphinx (sphinx==1.8.3), Breathe (breathe==4.12.0), Exhale (exhale==0.2.2) and Read the Docs Sphinx Theme (sphinx_rtd_theme==0.4.3).
Notes on CMake Options:
- To run each algorithm independently, set
BUILD_INDIVIDUAL
toON
(Executables created:dijkstra
,a_star
, etc). If you want to run all of them on the same grid, setBUILD_INDIVIDUAL
toOFF
(Executable created:main
). - To run tests, set
BUILD_INDIVIDUAL
toOFF
and RUN_TESTS toON
. - Set
CHECK_COVERAGE
to check code coverage. - Set
DYNAMIC_ALGOS
to build the dynamic runs of LPA* and D* Lite (No tests check the dynamic runs of these algorithms in the test section; the code implementing the dynamic runs of algorithms has been excluded from the code coverage statistics above) - Set
CUSTOM_DEBUG_HELPER_FUNCION
to build functions that are used primarily for debugging (excluded from code coverage)
Notes on test:
- Unit test framework set up to set algorithms under different grids. This section uses Google Test.
- CMake option RUN_TESTS allows building tests when set when
BUILD_INDIVIDUAL
is setOFF
. - The tests do not cover live runs of the D* Lite and LPAStar algorithm, reducing the code coverage value.
- Given the random nature of RRT, no set has been set up for it yet.
- Files named grid#.cpp are specific grids to check for correctness under certain conditions. gridr.cpp generates a random grid and checks whether Dijkstra, A* and D* Lite (without new obstacles) generate the same cost from start to end.
- Due to the nature of Ant Colony Optimization and accounting for the hyper parameters, the tests are run with a 20% margin above the optimal solution. Similarly for Genetic Algorithm.
- The test function for genetic algorithm has been modified to ensure correct functioning.
Notes on implementations:
- RRT stops as soon as goal is found. It is connects new points to the nearest point, not accounting for total cost to reach that point. In contrast RRT* chooses to connect to a new node to the node that allows the new node to have the minimum cost. RRT* also rewires the preexisting nodes to the new node if that path allows for a lower cost for the preexisting node.
- Acceptable motions can be modified in the GetMotion function in utils.cpp.
- A* and D* Lite use Manhattan distance (L1) as their heuristic (change to L2 if adding diagonal moves to the GetMotion function). D* Lite also uses the same in its C function.
- D* Lite can be run live with random obstacle creation using the RunDStarLite function. For the live run of D* Lite, obstacles are detected on the current path of the bot with a probability of 1/n, n being the number of rows/columns in the grid. D* Lite is implemented based on Sven Koenig's & Maxim Likhachev's paper.
- To specify your own grid, set n to number of rows, created the 2D vector, setting 1 for obstacles and 0 elsewhere, and comment out the MakeGrid function.
- The LPA* algorithm is implemented to run
max_iter_
number of times with default valuen
. Obstacles are created on the current path of the bot with a probability of 1/n, n being the number of rows/columns in the grid, at a random point along the path. It can be run withmax_iter_
set to0
if continuous replanning is to be disabled. - The genetic algorithm has an option
shorten_chromosome
, which allows the shortening of the chromosome (path length) based on the length of the path found that reaches the goal. This reduces computation time and pushes the solution towards the shortest path.
TODOs:
- Alterations for moving node variables into private namespace.
- Prune merged branches.
- Use hash to check if node in list for D* Lite (can be applied to others if required)
- Add test of probabilistic completeness for RRT.
- Formalize pseudocode and add references for ACO.
- Add documentation for jump point search.
- Refactor
Consider:
- Adding namespace to each header file.
- Inheriting node class into each file that requires a modified node (such as A* with heuristic cost, etc).
Note that the project description data, including the texts, logos, images, and/or trademarks,
for each open source project belongs to its rightful owner.
If you wish to add or remove any projects, please contact us at [email protected].