A-star optimization with minimum turns

Question

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

grid A star like [How to speed up A* algorithm at large spatial scales?](https://stackoverflow.com/a/23779490/2521214) will do you just update your cost according to your specs. So you can use duration of the movement as a cost (accounting for both speed and turns) that would be much better than minimal turns. — Spektre, Jul 20 '18 at 06:54
@Spektre I increased the cost for a turn but it's ended up in more tries to find the best next move — Dmitry Dyachkov, Jul 21 '18 at 21:26
What do you mean by `more tries` grid A* finds only the best way ... may be you have implemented graph DFS/BFS instead. — Spektre, Jul 23 '18 at 12:04

score 1 · Answer 1 · answered Jun 15 '22 at 14:34

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.

Dmitry Dyachkov · Accepted Answer · 2018-07-31T15:11:55.087

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.

This is Dijkstra's which is pretty much A*. I don't see how this would choose straight lines over lines with turns, considering your input is still the same — Glubus, Jul 19 '18 at 13:46

A-star optimization with minimum turns

2 Answers2