1

I am implementing A* for path finding of a mobile robot inside the corridor. As of now the path is produced inside the corridor but it slides over to the right following all the edges of the obstacles, but I prefer the path should lie in the middle of the corridor. 1.Is there any smoothing algo to do it? 2. How to include the steering constraints so that i can get realistic/feasible path? 3. How to give penalty for 'turn' so as to avoid zig-zag paths.

Since I am new to A* algo, I find difficlty in the above issues. Ref to any link, book is also welcome.. Thanks..

user1785307
  • 21
  • 5
  • You either want to use path-smoothing, or an [any-angle pathfinding algorithm](http://stackoverflow.com/a/14328161/238419). Both are fairly simple to implement, though any-angle algorithms tend to do a better job at finding near-optimal paths. – BlueRaja - Danny Pflughoeft Mar 27 '13 at 15:27

2 Answers2

1

You can pre-form the field on which you run A* by say shrinking it by 1 tile, so that a cell that borders impassable cell in 4-way neighborhood will become impassable. Then your resultant A* path will be closer to the center of the corridor. Of course, several corridors might become impassable completely, but this is what's expected as we are practically simulating a 3x3 cross-shaped robot to walk around the grid, and 3x3 cross can't go through 2xN path.

About adding cost to turn - you have to add current direction to the array that holds A* data, and implement a two-argument function that will return a non-negative value for (old direction, new direction) pair of arguments. Say, "if old_direction is not equal to new direction, return 1, else return 0". Then add the result of that function to whatever cost you computed for each step of A* iteration.

Vesper
  • 18,599
  • 6
  • 39
  • 61
  • The idea for adding cost to turn sounds good. Could you explain a bit more about how to find the direction of old or new move? Thanks. – user1785307 Apr 04 '13 at 12:56
  • You make yourself an enum/set of constants and a field `direction`, and when you add a new reachable cell in A* you take the coordinate difference between that and the currently processed cell, derive the direction from there. – Vesper Apr 04 '13 at 13:02
0

You could simply limit the usable area to the middle of the corridor.

Karoly Horvath
  • 94,607
  • 11
  • 117
  • 176