I am currently working on the Hybrid A* algorithm and facing challenges with move selection and weight calculation. Here's a brief overview of my implementation: I have a grid representation where each cell corresponds to a unit distance. The algorithm considers six maneuvers, all measured in terms of cells in the grid:
Straight: Distance of 10 cells. Backward: Distance of 10 cells. Arc (Right): Direction is right, with an angle of 30 degrees and a radius of 10 cells. Arc (Right): Direction is right, with an angle of 60 degrees and a radius of 10 cells. Arc (Left): Direction is left, with an angle of 30 degrees and a radius of 10 cells. Arc (Left): Direction is left, with an angle of 60 degrees and a radius of 10 cells. Turn: Direction is right. Turn: Direction is left.
Currently, my weight calculation solely relies on the number of cells covered multiplied by the weight assigned to each cell. However, this approach disrupts a desired move prioritisation order : the straight move the most preferred, followed by arc turns, turns, and finally backwards and also doesn't provide optimal solution. The existing implementation utilizes an Euclidean distance heuristic that solely considers the shortest path without accounting for obstacles. As a result, the move selection process and heuristic calculation are further disrupted, leading to suboptimal paths or sometimes even no solution and reduced algorithm performance.
here is a short algorithm:
1. Create and initialize the following data structures:
- g_score: a 2D vector of integers initialized with maximum values.
- f_score: a 2D vector of integers initialized with maximum values.
- open_set_hash: an unordered set to store objects in the open set.
- open_set: a priority queue of tuples, sorted in ascending order by the first element (int) of each tuple.
- moves: a vector of tuples to store the moves made during the algorithm.
2. Create an object, temp, with the start position and add it to the open set with a priority of 0.
- Set the g_score of the start position to 0.
- Set the f_score of the start position to the heuristic value using the heuristics() function.
- Insert the temp object into the open_set_hash.
3. Start a loop until the open set is empty:
- Get the current object from the top of the open set and remove it from the open_set_hash.
- Convert the current object's position to grid coordinates.
- Get the current cells (feet) under the object using the getFoot() function.
4. Check if the end position is among the neighboring cells:
- If true, print the start position, construct the path using the moves, delete the temp object, and return.
5. Get the neighboring objects (including the move taken) and their weights using the getNeighbours() function.
6. Iterate through each neighboring object:
- Calculate the weight for the current move and object.
- Calculate the temporary g_score by adding the weight to the g_score of the current cell.
- Check if the temporary g_score is lower than the g_score of the neighboring cell:
- If true, update the moves vector, update the g_score and f_score of the neighboring cell and its feet,
and add the neighboring object to the open set if it's not already in the open_set_hash.
7. Continue the loop until the open set is empty or the optimal path is found.
8. If the loop finishes without finding the optimal path, print "done".
Note: The algorithm assumes the existence of several helper functions, including heuristics(), construct_path(), calc_weight(), getFoot(), and getNeighbours(), which are not included in the provided code snippet.
I would greatly appreciate any insights, suggestions.
Do let me know If I have to add any code snippets.