I have an assignment in numerical methods where we make a very simple simulation of self-driving cars that adjust their speed based on the car in front. The implementation is done in MATLAB. We are to try out several known methods, of which the first is Euler's method. One of the problems is to determine the upper limit of the step size $h$ so that the cars can't pass each other, i.e. break the model. These are the details:
$M$ cars drive after each other. The position of car $i$ at the time $t$ is called $x_1(t)$. The cars are ordered so that
$x_i(t) < x_{i+1}(t)$ for $i = 1, …, M – 1$.
Each car adjusts its velocity based on the distance to the car in front. The positions of the cars $1, …, M -1 $ are thus given by the differential equations
$x_t'(t) = f(x_{i+1}(t) – x_i(t))$, $i = 1, …, M – 1$
The first car $M$ does not have a car in front and instead solves the differential equation
$x_M'(t) = g(x_M(t)$
where $g$ is a function that is either acceleration or deceleration according to later specification.
$f(x)$ is a velocity function defined as 0 when $x \leq 0$, $v_M$ when $x > d$ and a linear function for $x \in [0, d]$ where $v_M$ is the max velocity and $d$ is the safe distance to the car in front at which this car starts slowing down. These are constants in our case and $v_M = 25$ m/s and $d = 75$ m (the "three second rule").
The first assignment is to implement Euler's method to solve this system of differential equations:
$x_i^{n+1} = x_i^n + h f(x_{i+1}^n – x_i^n), i = 1, …, M – 1$
$x_M^{n+1} = x_M^n + h g(x_M^n)$
where $x_i^n$ is the Euler-approximation after $n$ steps and $h$ is the step size The solution is to be plotted as an animation over the time interval $[0, 40]$ using the step size $h = 0.1$ and $M = 10$. The two cases acceleration and deceleration are done by just substituting the function $g$ with the constant 25 m/s for acceleration or 5 m/s for deceleration. The cars are initially placed at distance $d$ from each other, then the simulation is run.
One of the theoretical questions, i.e. that should be done by calculation and not by running the simulation, is to find at what exact value of $h$ the model breaks down in that the cars can drive past each other, in other words, that $x_i^n > x_{i+1}^n$ for some time step $n$.
One naive approach I've tried is to identify that the first car always moves $5h$ and if the next car moves more than that it can pass. But this is looking just at the two cars and the problem can occur due to propagation, so it makes no sense.
Another line of thinking is that if the error in the approximation is larger than the distance moved by each car, the models breaks. Since there is no "known" function to compare to, I'd calculate the error as the difference between this and the last iteration? I'm not sure how to work this out.
Any help or suggestions on how to approach this specific part is much welcome.
Best Answer
Another approach from a purely mathematical side is just to explore the constraints of the stability of the method. The slope of $f$ in each of the two variables $x_i$ and $x_{i+1}$ is at most $\pm 25[m/s]/(75 [m])=1/(3 [s])$, which makes a Lipschitz constant of $f$ of about $L=2/3 [s^{-1}]$.
The heuristic for the step size in the explicit Euler method is that you need $Lh$ to be smaller than $1$ to get barely qualitatively correct results and about $0.1$ to start getting also quantitatively correct results, giving $h=1.5 [s]$ or $h=0.15[s]$, respectively. See Step size in Euler's forward method for an extended discussion and Maximum timestep for RK4 for a similar discussion for the RK4 method.