Skip to content

Latest commit

 

History

History
108 lines (92 loc) · 6.3 KB

readme.md

File metadata and controls

108 lines (92 loc) · 6.3 KB
Raw

Implementation of A* Planning Algorithm in 3D Environment

Build Status Coverage Status

Overview

A* is a widely used algorithm for pathfinding in 2-D environments. This project takes the planning algorithm one step further and applies it to a 3-Dimensional environment.
This project's objective is to buid a planning module for Aerial Vehicles. Provided with the world boundary and Obstacle location data, the module provides the optimal path from start point to the goal by avoiding all obstacles.
This Project is developed using C++11 Standards and a compiler supporting c++11 is necessary to run the tests and demo.
Development of this project follows Solo Iterative Process (SIP) model in Software Engineering.
Tested on Ubuntu 16.04 LTS with GCC 5.4.0.
List of Libraries and Softwares used for development and their License information can be found Here

Description

The World boundary and obstacle data is provided in the (xmin,ymin,zmin,xmax,ymax,zmax) format. The module then uses this data along with the robot dimensions information to discretize the world and build a 3-D Configurtion Space. This C-Space is used to plan the Robot's path using A* Search.

A* Search Algorithm

A* is an algorithm that searches for lowest cost path among all possible paths from start to goal. What A* algorithm does is that at each step it picks the node from open list according to the value f, which is sum of two other parameters g and h.
Here, g value of a node is the cost to move from start to that node and h value is the estimated movement cost to move from that given node to the final destination.There are many ways to calculate h and this project provides an option to select between Euclidean Distance and Manhattan Distance.
Obstacle nodes have the cost of infinity to travel through them and hence, the planner avoids these nodes in path planning.
Typical implementations of A* use a priority queue to perform the repeated selection of minimum (estimated) cost nodes to expand. This priority queue is known as the open list. At each step of the algorithm, the node with the lowest f(x) value is removed from the queue, the f and g values of its neighbors are updated accordingly, and these neighbors are added to the queue. The algorithm continues until a goal node has a lower f value than any node in the queue (or until the queue is empty). The f value of the goal is then the length of the shortest path, since h at the goal is zero in an admissible heuristic.

Solo Iterative Process (SIP)

  1. Iteration 1:
    • Planning of the Project Structure and Repository Setup.
    • Setup Travis and Coveralls.
  2. Iteration 2:
    • Build the Unit Testing Environment and Class Stubs.
    • Implementation of Map Builder and A* Planner with Fully working Path Planner.
    • Release Version 1.0.
  3. Iteration 3:
    • Add Manhattan Distance Heuristic.
    • Explore the Possibility of 3-D Plots.
    • Release Version 2.0.
  4. Iteration 4:
    • Documentation.
    • Code Optimization.

Product and Iteration Backlogs can be found Here

UML Diagrams can be found Here

Status

Skeleton Code and Initial UML Diagrams.
Implementation of Map Builder from Environment Boundary and Obstacle Data.
Implementation of A* Planner.
Release Version 1.0 of the Module.
Version 1.0 is Now Online.
Version 2.0 is Now Online.

To Do (Version 2.0)

Explore Possibility of 3-D Plots.
Add Manhattan Distance Heuristic Function.
Doxygen Comments and Documentation.
 Version 2.0 is Now Online.

Build Instructions (Tested on Ubuntu 16.04 LTS with GCC 5.4.0.)

Compiler supporting c++11 is necessary to run the tests and demo.

git clone --recursive https://github.com/VBot2410/A_Star_3D
cd <path to repository>
mkdir build
cd build
cmake ..
make

Run tests: ./test/A_Star-test
Run program: ./app/A_Star-app

Sample Output:

Start Point:(0,0.5,3) & Goal Point:(3.75,6.25,0)
X,Y,Z resolution 0.25 and Robot Dimensions Margin 0.2
The Planned Path was as follows:

Here

Generating The Documentation

Doxygen is Required for Generating the Documentation for this project.
More Information on Installation Instructions Can be Found Here
To Generate the Documentation, Navigate to the A_Star_3D directory and run following command

doxygen A_Star_3D_Documentation

The Documentation will be Created in Doxygen Directory.

License

This Project is Licensed under the MIT License. Copy of the License Can be Found Here

MIT License

Copyright (c) 2017 Vaibhav Bhilare

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.