A* with less turns

[benji]

hey folks, ive been doing studies latley on the A-star algorithm to find the shortest path
,its very effective though sometimes this shortest path would be full of turns.
this is somthing i want to get rid of,, turns,, cuz it makes the movement a little sick..
how do i do this? well i read somewhere that you should add a direction change cost penalty.
some text book also mentioned that the function would be somthing like this >

ADDED COST = D * NUMBER OF TURNS

where D is the cost of moving from a square to another (the turns are 45 degrees so if you want to turn 90 the num will be 2)

unfortunately in many cases this formula seems to fail (you can try it with some maps n see what i mean)

someone have read about a WORKING solution for path smoothing ?? help in need

thanks,,

Ben

[JesseWelling]

Look for "Field D*" by Dave Ferguson and Anthony Stentz and also "Layered Field D*" by Juan Pablo Gonzalez, Bryan Nagy and Anthony Stentz. I think both of them are CMU papers so start there, or IM me your e-mail and I can send them to you (they are to large to post).

Also consider a object avoidance algorithm (such as nearness diagrams, potential fields, of vector field histograms) layered with a waypoint finding algorithm (such as A* , D* and variants, or wave front propagation).

[benji]

i downloading the FIELD D* bok, thanks a lot.
anyways ive read somewhere that D* handels dynamic objects, i dont need this cuz my environment is static
, all i need is how to generate a smoother path
(my bot has 45 degrees turns)

[benji]

hey folks, finally its working, its not a multiplier or anything, its a constant number you add to the cost each time a turn is taken
let say the G cost to moving from  one square to another is 10 and the G cost to moving from one square to another diagonally is 14
so if there is a turn also then you add 3 to the G cost ,so if you are turning from north to (north-right) you add a cost of 14 + 3 = 17
and so on,,
this way the algorithm finds the smoothest-shortest path,,great
but i guess in robotics the turn cost should be higher as it consumes more power (maybe) than adding a little more length to the path
, anyways, here is a big book about pathfinding for mobile robots,its FREE to download

http://planning.cs.uiuc.edu/

[Asellith]

Just a quick thought about A*.

Why couldn't you make the squares smaller and associate the robot with more squares. Say the robot is 5 by 3 'squares'. The idea behind this is to get more resolution in the movements of the robot so it tends to move diagonally instead of in straight lines and turn. It will be harder on computations but I think it can be done by running the algorithm for all 5 width squares and average them together to get the vector the robot should be traveling. With the average you might be able to get a smooth movement for the robot instead of the jerky turns. Obviously it will be another case of computation power vs performance to find the best ratio based on the robot.

As a disclaimer if this is a really stupid idea I have never programmed my own A* system. I have only read about them and Admin's cool wavefront tutorial

[benji]

Why couldn't you make the squares smaller and associate the robot with more squares.

that is exactly what i m doing, not to smooth the path but to make my bot more inteligent, my bot is big
its about 50 cm by 40 cm, so itl be very dumb to treat small obstacles this size

i wasnt sure that this would automatically smooth the path but i thought i should use the smoothing method i suggested to garantee
path smoothing,,
by using the method i suggested you can also define how much does it cost to turn
in case of mine(hexapod) it takes too much power (5 times more) to make a 45 degrees turn,so i would penalize turns like this

turn cost = 5 * movement cost

this way my bot sometimes would choose a little longer paths but with less turns

this means that itl sacrifice walking another 5 steps to not make a turn

[Admin]

Why couldn't you make the squares smaller and associate the robot with more squares. Say the robot is 5 by 3 'squares'.

Another common solution is make the robot a single tiny point, but make all the obstacles stored in the map artificially bigger.