How do car drivers drive ?

That is what I have been wondering, how would I write a program able to adapt my speed to not crush the next obstacle in front of me ?
Before thinking of machine learning algorithms that can learn from tricky situations (pedestrian crossing the street without looking or plane landing on the road), we can think of the basic principles of the driving algorithm.

The goal is to run as fast as one could allow himself to, and to respect small or bigger security distances between someone and the nearest obstacle.

Here are the rules I can think of
– if there is no obstacle nearby and I am not running fast enough, speed up
– if there is one obstacle nearby, running at a high speed, i will keep the same speed
– if there is one obstacle nearby, running at a lower speed, i will slow down until I can keep the security distance
– if there is one obstacle nearby, not moving, i will slow down until I stop my own car.

Obviously, there is not one behavior of drivers.
Some of them are really conscencious, they take care about not provoking accidents, they will sometimes slow down dozens of meters before the next obstacle.
Some of them are crazy, them don’t care about orange lights and want to respect the least possible security distance.

I have tried to simulate these behaviors with an algorithm. I don’t know if it is realistic or not, but I tried to represent the above algorithm in Java. For you to see. I think it could do an excellent coding puzzle for an interview.

public Situation movingForward(Side direction, DrivingBehavior behavior, Situation nextObstacle) {
    int iterationsBeforeSpeedAdaptation = speed == 0 ? 1 :
            (int)Math.ceil(Math.sqrt((2 * (speed-nextObstacle.speed)) /
            Math.pow(behavior.getAccelerationAmplitude(), 2)));
    float nextObstacleDistance = nextObstacle.getPosition().distanceFrom(this.position) - behavior.getDistanceWithNextObstacle();
    int iterationsBeforeNextObstacle = speed == 0 ? 50 : (int)Math.floor(nextObstacleDistance / speed);
    boolean shouldDecideToBrake = iterationsBeforeSpeedAdaptation > iterationsBeforeNextObstacle + 1;
    int nextWillDecideToBrake = nextObstacleDistance < 10 && speed - nextObstacle.speed < 10 ? YES_NOW  :
            willDecideToBrake == NO && shouldDecideToBrake ?  YES :
            shouldDecideToBrake ? Math.max(willDecideToBrake - 1, NOW) : NO;
    float nextAcceleration = willDecideToBrake == NOW || nextWillDecideToBrake == YES_NOW ?
            -behavior.getAccelerationAmplitude() :
            nextObstacleDistance < 10 ? behavior.getAccelerationAmplitude() / 2 :
            speed < behavior.getMaxSpeed() ? behavior.getAccelerationAmplitude() : 0;
    float nextSpeed = Math.max(0, speed + nextAcceleration);
    Position vector = direction.asVector();
    boolean diagonal = Math.abs(vector.getX()) + Math.abs(vector.getY()) == 2;
    final float coeff = (nextSpeed < 1E-3 ? 0 : nextSpeed) / 10;
    double speed = diagonal ? Math.sqrt(coeff) : coeff;
    final float deltaX = (float) speed * vector.getX();
    final float deltaY = (float) speed * vector.getY();
    return new Situation(
            new Position(this.getPosition().getX() + deltaX, this.getPosition().getY() + deltaY),
            nextSpeed, nextAcceleration, nextWillDecideToBrake);
}

crossing.gif

You can run and play with the project by yourself at https://github.com/libetl/crossing

Leave a Reply

Your email address will not be published. Required fields are marked *

*

This site uses Akismet to reduce spam. Learn how your comment data is processed.