CODEWITHSUNDEEP
algorithma-star
Dmitry Dyachkov
Dmitry Dyachkov

Reputation: 1795

A-star optimization with minimum turns

I'm working on A-star optimization which would avoid excessive circumflexing of corners and find a way with mininum turns, because talking about robots it's much more effective just move forward without constant stops and calculating further steps.

I've developped own approach but something is missing. This approach is based on pre calculating of cross cells that stay on the crossing of free lines and columns, but there is a problem: I through out from consideration lines and columns that contain non passable cells.

To fix this I need also include sub lines beetween obstacles. And so on.

Perhaps there is better registered algorithm more optimal to my needs.

This picture shows how the path is built using minimum turns

This is the same length, but more optimal considering an absence of turns

Sample

Upvotes: 1

Views: 1013

Answers (2)

Raghav Thakar
Raghav Thakar

Reputation: 143

For anyone who stumbles across this question in the future, looking for an answer. One can modify A* to get the shortest path with minimum turns.

Assumptions:

  • Shorter path is still the priority. Even if an alternate path may have fewer turns, we will prefer a path with more turns that is shorter.
  • Your heuristic function f(n) is made of 2 independent function g(n) and h(n) such that f(n) = g(n) + h(n) where g(n) is the weight of traversing from current cell to proposed neighbouring cell, and h(n) is the apparent distance of proposed neighbouring cell to target cell (doesn't matter which distance we consider, but for most practical applications involving turns and grid-like maps, we prefer Manhattan Distance).

Modification: In the A* loop, after the f(n) has been computed for all possible succeeding cells, add a small delta (much smaller than edge weight of transition into any cell) to each f(n) that involves the agent making a turn. This way, when choosing between 2 or more equally attractive choices, the path always go through the cell that invloves not making any turn.

Upvotes: 1

Dmitry Dyachkov
Dmitry Dyachkov

Reputation: 1795

While looking for solution I've found that Best-First Search meets my needs, it's pretty close to what I need but it gives false movements.

// This pseudocode is adapted from below 
// source:
// https://courses.cs.washington.edu/
Best-First-Search(Grah g, Node start)
    1) Create an empty PriorityQueue
       PriorityQueue pq;
    2) Insert "start" in pq.
       pq.insert(start)
    3) Until PriorityQueue is empty
          u = PriorityQueue.DeleteMin
          If u is the goal
             Exit
          Else
             Foreach neighbor v of u
                If v "Unvisited"
                    Mark v "Visited"                    
                    pq.insert(v)
             Mark v "Examined"                    
End procedure

Best approach I've come up with was to find all crosses on free row and columns and finding the closest cell from the crosses to the newly found neighbors which is the closest to the goal.

So, I've finished with updating Neighbor property implementation from the Grid class without updating A* algorithm.

Upvotes: 0

Related Questions