algorithm - Adding bot turn costs to A* search in pathfinding within a grid - Stack Overflow

admin管理员组

文章数量:1313338

I have an NxM grid of square cells. traversal can only happen in North, South, East and West directions in the cells. Some of the cells are blocked and cannot be traversed.

A bot is given a start and end location and needs to find the path that takes the least amount of time.

Traversing between neighboring cells costs 1 unit of time. So N cells traversed should be equal to N units of time.

However in this problem there as slight issue. If a bot ends up making a 90 degree turn in any direction. The turn itself (which is in place) will cost 2.3 units of time.

I currently have a simple A* search implementation that is able to accomplish the normal path finding, however I'm stuck on how to incorporate the turn cost, as it can only be known in the third cell that is traversed - in short maintaining a window of length 3 in the path and determining if a turn has occurred.

What is the best way(s) to incorporate such a turn penalty in A* search?

I have an NxM grid of square cells. traversal can only happen in North, South, East and West directions in the cells. Some of the cells are blocked and cannot be traversed.

A bot is given a start and end location and needs to find the path that takes the least amount of time.

Traversing between neighboring cells costs 1 unit of time. So N cells traversed should be equal to N units of time.

However in this problem there as slight issue. If a bot ends up making a 90 degree turn in any direction. The turn itself (which is in place) will cost 2.3 units of time.

I currently have a simple A* search implementation that is able to accomplish the normal path finding, however I'm stuck on how to incorporate the turn cost, as it can only be known in the third cell that is traversed - in short maintaining a window of length 3 in the path and determining if a turn has occurred.

What is the best way(s) to incorporate such a turn penalty in A* search?

• algorithm
• constraints
• path-finding
• a-star

Share Improve this question Follow asked Jan 31 at 1:26 Lucinda RigettiLucinda Rigetti 61666 silver badges1313 bronze badges 2

• 1 The cost of moving without a turn is 1 and the cost of moving with a turn is 3.3? Could you minimize this cost? global_min_cost = min(global_min_cost, current_cost) – aaa Commented Jan 31 at 1:33
• 2 The lower-bound-costs used for A* should be manhatten-distance. You can improve this lower bound a bit by also including the minimum needed rotations: + minimum number of needed rotations * 2.3 (which is number of rotations you need to turn into direction of the goal (+1 if the goal is not in the same row and not in the same column) (that can be 0,1 or 2 rotations)) – MrSmith42 Commented Jan 31 at 10:30

Add a comment  | 

1 Answer 1

Sorted by: Reset to default 5

One simple way is to encode the unit's direction as part of the graph itself. You can do this by making four copies of the graph - one for each direction - and then connecting the each node in each graph to its neighbors in the appropriate graphs.

For example, in the "facing up" graph, each node would be connected to:

• The node above it, in the same graph and with the usual length
• The node to the left in the "facing left" graph, with the cost to turn added to its usual weight
• Similarly with the node on the right

Once the graph is setup, you can run any off-the-shelf pathfinding implementation.

本文标签： algorithmAdding bot turn costs to A* search in pathfinding within a gridStack Overflow