pic: A Star Path Planning

[StevenB]

Originally Posted by faust1706

I'm aware of this fact, but I have no idea how to implement it so that it outputs curved paths. It returns the coordinates of the nodes needed to get from a to b. For it turn return a curved path, it works either have to return so many points it appears as a curve (it takes about a second to go through 100 steps of the algorithm), or for it to output a function or something of the matter.

You can get part of the way there pretty easily: Extend your state space to include the robot's orientation as well as position. Instead of finding the least-cost path through a 2D world, you now have a 3D state space. Moving in the direction you're pointed (forward or back) incurs a cost of 1 (or maybe 1.4 for diagonals). Changing direction incurs a cost of, say, 2. The "goal state" can now be a specific position and orientation, or can include all the states where the position is correct. Make sense?

You could imagine extending this further, to include speed as another state variable. It costs something to increase speed, but at higher speeds, moving in the same direction incurs less cost. Turning can only occur at low speeds (or incurs absurd costs at high speeds).

To actually get smoother paths, you have to do something to further discretize your space. I'll think more about how this could work and post back...