Implementation of A-Star Algorithm

[shantanuparabumd]

Proposal for New Algorithm: A* for Path Planning

Algorithm Name

A*

Description

A* is a robust global pathfinding algorithm that computes the shortest path between two points while avoiding obstacles. It combines the benefits of both Dijkstra’s Algorithm and Greedy Best-First Search, providing an optimal path that efficiently navigates through a grid-based map. Its computational efficiency and proven effectiveness make it ideal for autonomous driving applications.

Plan for Implementation

1. Map Representation

   • The environment will be modeled as a grid map, where each cell represents a small area.
   • The map will include obstacles, a start point, and a destination point.

2. Vehicle Representation

   • Initially, the vehicle will be treated as a point object for simplicity.
   • To account for real-world scenarios, the algorithm will factor in the vehicle’s clearance space (length and width) to avoid obstacles adequately.

3. Pathfinding with A*

   • A* will compute the global path from the start point to the destination.
   • Euclidean or Manhattan distance will be used as the heuristic for path cost estimation.
   • The algorithm will prioritize paths with the lowest total cost (path cost + estimated distance to the goal).

4. Local Path Planning with Virtual Force Field (VFF)

   • Once the global path is computed, the vehicle will follow it using the Virtual Force Field (VFF) method.
   • VFF will generate forces to steer the vehicle around obstacles along the path, ensuring smooth navigation.

5. Clearance Space

   • Clearance space will be included in the path planning process, ensuring the vehicle can maneuver through tight spots without collisions.

References

• Hybrid A* for Motion Planning in Dynamic Environments
  Hybrid A* Paper (Stanford)
  This reference explains hybrid A* for motion planning. While it focuses on post-processing for vehicle dynamics, we’ll keep it simple by implementing standard A* for beginners.

• Virtual Force Field Algorithms for Robot Navigation
  VFF Overview
  Details about the Virtual Force Field (VFF) algorithm for robot navigation.

Expected Outcome

• A foundational global path planning solution using A* that efficiently calculates paths in a grid-based environment.
• Local path planning with Virtual Force Field to navigate dynamic obstacles while adhering to the computed global path.

---

[ShisatoYano]

Thank you for proposing!! I agree with your proposal to add A* algorithm and VFF algorithm. I think it is better for us to separate into 2 steps as follow.

1. Implement A* planner module class as a component and global planning simulation with it. After implementation, please send me 1st PR for this implementation.
2. Implement Virtual Force Field controller module class as a component and path tracking simulation with it. After implementation, please send me 2nd PR for this implementation.

If you have any questions, let’s discuss here.

[shantanuparabumd]

I’ve created an initial draft implementation of an A* path planner for the repository and submitted a PR for your review. This implementation includes features like obstacle handling, grid-based planning, sparse path generation, and integration with cubic spline trajectory creation.

Here’s a quick summary:

Features:
Grid-based A* planner with adjustable resolution for balancing exploration speed and detail.
Obstacle clearance and vehicle safety handling (currently assuming a point object).
Sparse path generation compatible with CubicSplineCourse for trajectory planning.
Visualization of the grid, exploration, and reconstructed path (aesthetics and animation speed can be improved).
This is an initial draft, and I plan to iterate further to address enhancements such as:

Transitioning from a point-object model to a car-specific configuration space (C-space).
Refining the action set to incorporate vehicle kinematics.
Improving visualization aesthetics and playback speed.
You can find the detailed description, code, and an example output in the PR here: [https://github.com//pull/22].

Please take a look when you have time and let me know your thoughts or suggestions for improvement.

[ShisatoYano]

Thank you for submitting the PR! I will check and review it from now on. Please just a moment.