Table of contents

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

About The Project

This project aims to implement A* Algorithm to find a path between start and end point on a given map for a point/rigid robot. The obstacle space is represented as follows:

Built With

• Python
• matplotlib

Getting Started

Prerequisites

• matplotlib

  pip install matplotlib
  

Installation

1. Clone the repo

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

2. Change to A* directory

   cd A\*/
   

Usage

1. Run the python file:

   python astar.py
   

2. Input the following values:
   • Robot dimension:
   • Obstacle clearance:
   • Start X (integer)
   • Start Y (integer)
   • Start ϴ (degrees)
   • Goal X (integer)
   • Goal Y (integer)
   • Step Size (1-10)

Roadmap

• Implement robot action set in 5 directions.

• 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 A* algorithm to search the graph for goal node.
  • Generate the cost to travel to the goal.
  • Implement a threshold distance around the goal.
  • Find duplicate nodes by applying a threshold of 0.5 units in by matrix method.
    • visited[width/threshold][height/threshold][12] where 12 stands for 360/30 as the robot can only rotate 30 degrees.

• 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. Yellow dots are the explored nodes
    2. Green: Chosen nodes of A* (Backtracking) with robot’s direction
    3. Blue: Connects the chosen nodes to see the path (visual aid)

Output

---

---

---

• The Figure 1 below is an output for searching a path using A*.
• The expanded version of the output is shown in Figure 2
• Figure 3 is an output for the following initial conditions.
  • Robot dimension: 2
  • Obstacle clearance: 3
  • Start X (integer): 10
  • Start Y (integer): 10
  • Start ϴ (degrees): 0
  • Goal X (integer): 375
  • Goal Y (integer): 225
  • Step Size (1-10): 3

License

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

Contact

• 

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

References

• A* search algorithm