Math to steer a car

Question

I'm in the early stages of a city driving simulation project, and I'm having trouble with the math to determine how the AI should steer the cars. My car model is very simple, with nothing like physical wheels or friction; the AI simply sets a turning radius (FLT_MAX means drive straight) and an acceleration each frame. My question is, given a starting position and direction, how do I work out the turning radius each frame to have the car arrive at a destination position and direction? As an example, think of a car stopped at a stop sign ready to turn right around the corner. The car should follow a curve so that is is pointing along the road onto which it is turning when it arrives at the "start" of that road.

I think Bezier curves would be helpful, since they can be used to create smooth curves that are tangent to my initial and final directions, but I can't work out exactly how to pick a point a little way ahead along the curve to aim for. I also open to completely different ideas.

Here's my car update code for reference.

mSpeed += mAcceleration * deltaTime;
float distance = mSpeed * deltaTime;
float theta = distance / mTurningRadius;

mPosition += mTurningRadius * sin(theta) * mDirection + mTurningRadius *(1.0f - cos(theta)) * mLeft;

mDirection = rotate(mDirection, theta * 180.0f / PI, mUp);
mLeft = -cross(mDirection, mUp);

Answer 1

Assumed your Ackermann drive simulation model is correct, you can do the following for the usual driving situations (where primarily only need to steer direction):

• Simulate (projection) multiple (e.g. in steps of 20 degrees) possible steering directions, statically. That means: You assume, the driver would put the steering wheel in is fixed position and then just drive forward.
• Simulate (projection) the borders of your car. Stop the simulation as soon as the borders of the car collide with any borders of the lane (or any other obstacle) -OR- if very long time has passed. Measure the time until the collision would happen.
• Select the direction with longest simulation time. If there are multiple of them with the same value (because the timeout was reached) take the average of the angles.
• Optional: Repeat simulation and selection for +/- 10 degrees in smaller steps, to refine the result.
• Simulate (execution) the real simulation for the next time step.

This works as a first approach, but still causes several "problems". The steering may oscillate and lead to unrealistic, quick movement. The reduce this effect, do the following: * Project the next steering direction like above * Calculate the difference between the current and the projected steering direction and reduce it, if it is above a given change-threshold (maximum speed a realistic driver would be able to turn the wheel in a time slice).

You can optimize the refinement by divide and the conquer algorithm (http://en.wikipedia.org/wiki/Divide_and_conquer_algorithm). Meaning: you set a min and a max for the steering direction and then recursively split that range in half and further investigate only the better performing range (left or right half of the old range).

For changing the lane you must allow your car to use both lanes (border of "lane" for collission detection). But, to force the car to actually change lane and not to driving in the middle of both, you have to limit how long the time until which the car must have changed lane (e.g. 10 seconds in future). You can convert this time into a distance using the current speed. Then just let the lane "end" with a straight line (orthographic to the lanes direction) at this distance. Project the lane change, with other cars continuing their current plans. If this works (no collissions, no driving rules are breached) execute the lane change. If not, continue driving on that lane.

Answer 2

For an axis aligned 90 degree turn, the turning radius is simply the minimum of the x and y differences in the positions as long as you start and stop turning at the correct point.

If it isn't axis aligned you can always do a rotation to fix that before doing the calculation as it doesn't affect the radius.

For non-90-degree corners it's a bit more complicated to construct the circle, but the idea is the same.

Answer 3

given a starting position and direction, how do I work out the turning radius each frame to have the car arrive at a destination position and direction?

Note, a simple "calculation" will only work if the "optimal" way is free from obstacles (e.g. other cars, borders of the road) -and- if you can drive there without changing direction (e.g. needed when get out of a paring space).

All more complicated actions can't be just calculated in a simple way. Even just stupidly using a A* search won't work with an "Ackermann drive". A former PhD collegue was looking for a student to do a masters thesis about that, he meant this would need to apply some algorithms as "sampling" (machine learning). This is what is meant by "sampling" in matters of machine learning: http://lear.inrialpes.fr/~jegou/bishopreadinggroup/chap11.pdf

Instead of trying to optimally calculate it, I would let the AI use some machine learning technique. For automatically steering air planes the "Temporal Difference" (=Reinforced Learning) algorithm has been successfully used. I think this would be applicable here. Reinforce your agents by: speed (positive), not obeying the traffic rules (very negative), fuel usage (negative).

Try to train different agents with different "personalities", as speed-affine, high-speed aversive, very accident avoident (very high negative reinforcement for crashes), fuel-safer, only negative reinforcement then getting caught while not obeying rules. You'll get a really realistic scenario this way. You'll even be able to see how changes to street signs, traffic control, speed limits, speed cams will affect driving behaviour and safety on the street in a quite realistic way.