Table of contents

• Table of contents
• About The Project
  • Built With
• Getting Started
  • Prerequisites
  • Installation
• Usage
• Roadmap
• Output
• Contributing
  • License
  • Contact
• References

About The Project

This project aims to implement Dijkstra’s Algorithm to find a path between start and end point on a given map for a point robot. The obstacle space is represented in the following image.

Built With

• Python
• OpenCV

Getting Started

Prerequisites

• opencv

  pip install opencv-python
  

Installation

1. Clone the repo

   git clone https://github.com/vishalgattani/Path-Planning.git
   

2. Change to Djikstra directory

   cd Djikstra
   

Usage

1. Run the python file:

   python dijkstra.py
   

2. Input the following values:
   • dimension
   • clearance
   • startx
   • starty
   • goalx
   • goaly
   • live animation
   • video save
3. If the user wishes a live animation, the opencv library will show node exploration.
4. If the user wishes to save the video, user requires to to input [y/n].
5. Given map dimensions, each whitespace inside the map has the follwoing index: index = j*width+i where i and j are the nodes (whitespace pixel grid) coordinates.
6. The open set and closed set are dictionaries with key being the index and value being the node.

Roadmap

• Implement robot action set in 8 directions; Up, Up-Right, Right, Down-Right, Down, Down-Left, Left, Up-Left.

• Implement obstacle space.

• Generate enlarged obstacle space when robot dimensions and clearance values are given:
  • Enlarge obstacle spaces using half-plane methods.
  • Enlarge obstacle spaces by moving the robot around the osbtacle to better the configuration space.
• Implement the Dijkstra’s algorithm to search the graph for goal node.
  • Generate the cost to travel to the goal.

• Implement the backtracking to find the optimal path.

• Visualize output
  • Black: Obstacles
  • Red: Enlarged obstacle space by Robot’s dimension and clearance
  • White: Confiugration space
  • During exploration:
    1. Green: Explored nodes
    2. Blue: Connects the chosen nodes to see the path (visual aid)

Output

---

---

Contributing

If you have a suggestion that would make this better, please fork the repo and create a pull request. You can also simply open an issue with the tag “enhancement”. Don’t forget to give the project a star! Thanks again!

License

Distributed under the MIT License. See LICENSE for more information.

Contact

• 

Project Link: https://github.com/vishalgattani/Path-Planning

References

• Dijkstra’s algorithm