Implementation of A-Star Algorithm #21
Description
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
-
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.
-
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.
-
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).
-
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.
-
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.
Activity
ShisatoYano commentedon Jan 10, 2025
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.
If you have any questions, let’s discuss here.
shantanu-builds-robots commentedon Jan 21, 2025
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 commentedon Jan 22, 2025
Thank you for submitting the PR! I will check and review it from now on. Please just a moment.