Optimal-time acceleration sequence of a line-following robot following a moving obstacle

Question

Say we have a line-following robot that has a moving obstacle in front, that is a one-dimensional problem. The moving obstacle is defined by its initial state and a sequence of (longitudinal) acceleration changes (the acceleration function is piecewise constant). Let's say the robot can be controlled by specifying again a sequence of acceleration changes and its initial state. However, the robot has a maximum and minimum acceleration and a maximum and minimum velocity. How can I calculate the sequence of accelerations minimizing the time the robot needs to reach a goal. Note that the final velocity must not necessarily be zero.

Can you briefly explain how this problem can be addressed or point me to some references where an algorithm is described? Or point out closely related problems?

Furthermore, does the solution depend on the goal position or could the robot just brake as late as possible all the time (avoiding collisions) and still reach any goal in optimal time?

A more formal problem description: Given the position of the obstacle $x_B(t) = x_{B,0} + \int_{t_0}^t v_B(t) dt$, and the velocity of the obstacle $v_B(t) = v_{B,0} + \int_{t_0}^t a_B(t) dt$, where $a_B$ is a known piecewise constant function:

$$a_B(t) = \begin{cases} a_{B,1} & \text{for } t_0 \leq t < t_1 \\ a_{B,2} & \text{for } t_1 \leq t < t_2 \\ \dots & \\ \end{cases}$$

and given the initial state of the line-follower $x_{A,0}, v_{A,0} \in \mathbb{R}$ we search for piecewise constant functions $a_A$, where $a_{min} \leq a_A(t) \leq a_{max}$, $v_{min} \leq v_A(t) \leq v_{max}$ and $x_A(t) \leq x_B(t)$ (collision freeness) holds at all times. Reasonable assumptions are e.g. $v_B(t) \geq 0$ and $x_{B,0} \geq x_{A,0}$. Among the feasible solutions I would like to pick those minimizing $\int_{t_0}^{\infty} x_B(t) - x_A(t) dt$ or a similar objective. Approximation algorithms are also ok.

Some numbers for those who would like a test input: http://pastebin.com/iZsm2UhB

Answer 1

Assuming constant accelerations, "stopping" (slowing) distance can be calculated with:

$$ x = x_0 + v_0 t + \frac{1}{2} a t^2 \\ $$

where $x_0$ is your initial position, $v_0$ is your initial speed, $a$ is your acceleration, and $t$ is time. Assuming you are trying to get from one constant speed to another constant speed, you can calculate the time required to achieve the speed change with:

$$ v = v_0 + a t \\ t = \frac{v - v_0}{a} \\ $$

You question isn't especially clear to me - do you know the moving obstacle's acceleration profile before the challenge starts? Do you program your line-following robot completely before the start of competition? (i.e., you don't just look at the distance between yourself and the obstacle?)

If you know and program everything in advance, then you should have your robot as close to the obstacle as possible any time the obstacle is about to have a positive acceleration and you should leave the correct "stopping" distance between yourself and the obstacle any time the obstacle is about to have a negative acceleration. You have to take the obstacle's slowing and accelerating distances into account as well.

I would start at the end - you know your speed ($0$) and position ($x_{\mbox{end}}$) at the end of the course, and you should be able to calculate the obstacle's position, speed, and acceleration at the end of the course as well, by using the speed and position equations together with the acceleration profile.

Assuming obstacle initial conditions of $x_0 = 0$ and $v_0 = 0$ at $t_0 = 0$, then you can calculate the speed and position after the first acceleration period: $$ x_1 = x_0 + v_0 t + \frac{1}{2} a t^2 \\ x_1 = x_0 + v_0 (t_1 - t_0) + \frac{1}{2} a (t_1 - t_0)^2 \\ x_1 = 0 + 0 (t_1 - 0) + \frac{1}{2} a (t_1 - 0)^2 \\ \boxed{x_1 = \frac{1}{2} a (t_1)^2 \\} $$

$$ v = v_0 + at \\ v = v_0 + a (t_1 - t_0) \\ v = 0 + a (t_1 - 0) \\ \boxed{v = a (t_1) \\} $$

For each segment in the acceleration profile N, you can increment the speeds and positions:

$$ x_N = x_{N-1} + v_{N-1}(t_N - t_{N-1}) + \frac{1}{2} a_N (t_N - t_{N-1})^2 \\ v_N = v_{N-1} + a_N (t_N - t_{N-1}) \\ $$

Keep incrementing through the acceleration profile until $x_N >= x_{\mbox{end}}$.

Now, work backwards. This depends in part on the problem definition - you will reach the goal faster if you can "tag" the goal like a baseball player would "tag" home - running over it at full speed. However, you may need to stop at the goal in order to have "reached" the goal. This is a point you should seek clarification on. In any event, the line follower's $x_N$ should be $x_{\mbox{end}}$ and the $v_N$ should be:

1. $v_{\mbox{max}}$, if the obstacle's $v_N$ at that point is higher than the line follower's $V_{\mbox{max}}$, or
2. $v_{\mbox{line follower}}$, if the obstacle's speed is lower than your $v_{\mbox{max}}$ at that point, or
3. 0, if you're required to be stationary at the the target.

From your end conditions, work backward, trying to put the line-follower as close as possible to the obstacle while always allowing for braking/slowing distances. You can check your answer by incrementing through the positions and velocities again, this time using differential values:

$$ x_{N_{\mbox{diff}}} = x_{(N-1)_{\mbox{diff}}} + v_{(N-1)_{\mbox{diff}}} (t_N - t_{N-1}) + \frac{1}{2} a_{N_{\mbox{diff}}} (t_N - t_{N-1})^2 \\ $$ $$ v_{N_{\mbox{diff}}} = v_{(N-1)_{\mbox{diff}}} + a_{N_{\mbox{diff}}}(t_N - t_{N-1})\\ $$

where the differential values are $x_{\mbox{diff}} = x_{\mbox{obstacle}} - x_{\mbox{line follower}}$ and $v_{\mbox{diff}} = v_{\mbox{obstacle}} - v_{\mbox{line follower}}$. With these equations you're looking at the differential position - the distance between the obstacle and the line follower - if $x_{\mbox{diff}}$ is ever less than zero you're doing something wrong because it means your line follower is further ahead than your obstacle is!

Answer 2

The paper “Optimizing Train Speed Profiles to Improve Regeneration Efficiency of Transit Operations” (in JRC2014-3795.pdf) by Haichuan Tang et al addresses some of the issues mentioned in the question and sets out a dynamic programming method for solving related problems. The paper's goals are different than yours, but its method and some of its references may be helpful.