First of all: I know basically nothing about Euler-Lagrange equations, I'm a first year civil engineering student simply doing this to learn some new stuff. If there are better ways to do this, feel free to tell me.
I have a two-dimensional grid of lines (4x6 intersections, all evenly spaced), six green objects are spread across the intersections, four red ones as well, no intersection contains more than one object. The goal is to grab all green objects, avoiding contact with any red objects and return to the starting position as fast as possible. It is up to me to write an algorithm that minimizes the time spent driving around.
An obvious solution is to stay on the lines, and proclaim your path as 'the fastest path if you stay on the lines'. However, just as a personal challenge, I would like to find a very fast (not necessarily the fastest, preferably close to the fastest) path by going off the lines.
Restrictions:
- to ensure the car can correctly collect a green object, it is necessary to approach the line at a specified angle.
- The car has a maximal velocity per wheel, so when turning, the car actually goes slower than in a straight line as the inner wheel moves slower than its maximal speed: $v = v_m - \lvert \theta' \rvert \cdot d$ where $v$ is the speed of the car, $v_m$ is the maximal speed of a wheel, $\theta'$ is the rotational velocity of the car and $d$ is half the width of the car's axles. Furthermore, the car has a maximal rotational speed: $\lvert\theta'\rvert\leq \frac{v_m}{d}$.
Simplifications:
- We assume the speed of a wheel can be changed practically instantaneously.
- As I'm rather sure it's significantly harder to solve this problem if you were to solve for the path collecting all green objects than to generate all possible paths where you collect one green object and then find the fastest combination of these paths, we will assume the path to be found has a startpoint and an endpoint, but no points it has to pass inbetween. It does however have to avoid red objects.
- A numerical solution is no problem, however, the further we can get analytically, the better of course.
- There is always a difference in x-value between the start and endpoint of a path, if there is not, the x-axis and y-axis get rotated to ensure there is a difference in x-value. This is to ensure that the time integral further on is not zero.
What I've got so far (it's not a lot): Given $theta$ being the angle the car is at (where the long side of the field from left to right defines the positive x axis), $v_m$ the maximal speed of a wheel, $r$ the distance to keep from any red object at all times and $d$ half the length of the wheel axles. We assume the path starts in the origin at and ends in $(x_e, y_e)$ (the location of a green object). The starting angle and angle to reach the green object at, $\theta_0$ and $\theta_e$ respectively, are also known. The speed of the car at any point is, as previously stated, $v = v_m - \lvert \theta' \rvert \cdot d$.
We can use the Euler-Lagrange method: The objective to minimize is the time $T$ spent driving, we can calculate it as the integral over the difference in x value of the horizontal speed: $$T = \int_0^{x_e}\frac{dx}{v\cdot\cos(\theta(x))}=\int_0^{x_e}\frac{dx}{(v_m - \lvert \theta(x)' \rvert \cdot d)\cdot\cos(\theta(x))}$$ There are several constraints:
- The car has to end up at $Y=y_e$: $$Y=\int_0^{x_e}\tan(\theta(x))dx=y_e$$
- The car has to avoid all red objects, this can be done mathematically by defining a penalty function $P(x,y)$, the function value is zero if the distance from the nearest red object is greater than $r$, and otherwise the function is of another form (I am not sure yet which form would be optimal). Then the total penalty has to be zero:$$Q=\int_0^{x_e}P(x,y)dx=\int_0^{x_e}P_1(x,\int_0^x\tan(\theta(t))dt)dx=0$$
- A similar penalty function would have to be applied to ensure that $\lvert\theta'\rvert\leq\frac{v_m}{d}$: $$R=\int_0^{x_e}P_2(\theta'(x)) dx=0$$
- Using Lagrange multipliers, we can define a total function to minimize:$$K=T+\lambda_1Y+\lambda_2Q+\lambda_3R$$
- As I understand it, the Euler-Lagrange equation can be used with $$L(x,\theta,\theta')=(v_m-\lvert\theta(x)'\rvert\cdot d)^{-1}+\lambda_1\tan(\theta(x))+\lambda_2P_1(x,\int_0^x\tan(\theta(t)dt)+\lambda_3P_2(\theta'(x))$$ to find functions that minimize $K$, and therefore minimize $T$ with respect to the conditions $Y$, $Q$ and $R$ if $\lambda_1$, $\lambda_2$ and $\lambda_3$ are chosen correctly.
I have not worked this out further, as I do not adequately understand the following steps yet. A few questions I have:
- In this case, what would be a good choice of $P_1$ and $P_2$? The simplest would be '0 if you are not close to a red object, 1 otherwise' and '0 if you the absolute value of the angular momentum does not exceed the boundary and 1 otherwise' but these functions are not differentiable on certain points so I suppose that would lead to problems.
- How would I solve this numerically? Are there methods best suited for this specifically or should I use a regular numerical differential equation solver? If it helps, I'm doing this with Python 3 currently.
- How do I find $\lambda_1$ and $\lambda_2$? I have heard it's best to find them by trying a few options and simply taking the one where both conditions are met, but as I assume they are also dependent on the location of the endpoint and the red objects, it would be great to have a more efficient method of determining them.
- How do I ensure that the solution returned is the one where $\theta(0)=\theta_0$ and $\theta(x_e)=\theta_e$. Do I simply pass those as the conditions of the differential equation that the Euler Lagrange equation produces or do I have to do that differently?
I'm sorry for the long question, but any help at all is greatly appreciated.