Finding optimal velocity profile using Dynamic Programming

Question

While continuously reading about Dynamic Programming I have a problem, implementing it in a practical application.

Let's assume we want to optimize our way to school which we go daily by bicycle. Because the way is a bit hilly in addition to resistance due to friction $F_F$ adn air $F_A$ we have also a force dependent on the grade at our current position $F_G(x)$. So our equation might look like this $$m_{ub}\ddot x = F_D - F_F - F_A(\dot x) - F_G(x)$$

where $m_{ub}$ is the mass of us + bicycle.

We know that we want to be at school $x_S = 5 km$ at $t_S = 20 min$.

We want to know how to do that with minimum energy $E = \int F_D \; dx$. So we want to find a control vector $\bar F_D$ along this way which holds values for accelerating or decelerating our bike so that the total energy required for getting to school is minimal. The discretized problem might look like this

$$\Delta x = 0.5km \quad x_i = i * \Delta x \quad i = 0, 1 \dots N_i\\ \Delta v = 5km/h \quad v_j = j * \Delta v \quad j = 0, 1 \dots N_j\\ $$

Recursion

The first step is the recursion, calculating the required force $F_D$ for all possible transitions $x_i \rightarrow x_{i-1}$ starting from $x_S$ for each $dv_{i} = v_{j, i} - v_{j, i-1}$. So in this step we are going from $x_S$ to $x_0$.

Some states will not be hit, for instance our stregth is limited to $ F_D < F_{max}$ and also our brakes won't do more than $ F_D > F_{brake} \quad (F_{brake} < 0)$

Then at the end of this step we have a bunch of transitions with the according transition forces and times $$\Delta F_{i,j \rightarrow i+1,j} \\ \Delta t_{i,j \rightarrow i+1,j}$$

We also know the energy for each transition $E_{i,j \rightarrow i+1,j}$ since we assumend $F_D$ to be constant along $\Delta x$.

Finding Optimum

The big question know is: How do we find the optimal path through these transitions which fulfills the constraints

$$E = min \sum_{i} E_{i \rightarrow i+1,j} \\ \underset{i}{\sum} \Delta t \le t_S$$

Approach 1: We can run through $i = 0, 1 \dots N_i$ taking the transition with the lowes value for energy. If we notice, that we run out of time, we accelerate making sure we get to school in time. BUT: This way, our algorithm will choose the cheapest transitions until time is short being forced to choose very expensive ones later on. So that won't give us the optimal path.

Approach 2: We could simply check all paths, adding up the transition times of each and throw away those with a total time greater than $t_S = 20 min$ which we aimed at. But this would apparently be a brute force method because at each position $x_i$ we can choose about $N_j$ directions (velocities), so that the complexity would be basically $$O(N_i^{N_j})$$ So for our little example that'd result in approximately $10^6 = 1,000,000$ paths. Is that right?

Now what are the actual steps to take to solve the problem in finite time? How do we find the path of minimum energy for a required time $t_S$? Obviously these constraints contradict each other. How to heed them both?

Answer 1

This is a path finding problem, but much more complicated than the usual case where only the shortest path is sought.

I haven't seen a problem similar to yours and can't answer whether or not there's a canned solution, or if it's similar enough to one.

Without the constraint this looks like something dynamic programming could help with, however the constraint is just so unusual (yet its importance so basic).

To actually give you some answer, after ruling out exact solutions I'd run a heuristic; I've worked on similar problems and have had good success with k-opt. Wikipedia doesn't explain it terribly well; basically, what you do is initialize your solution some way or another (random works well enough, but you could use weighted A* or something without constraint to do better), fix all elements except for a few (2 - 4), and exhaustively search for an improvement in those few. The complexity is worse than linear but much better than brute force.

Answer 2

I have an hybrid approach using dinamic programming and steepest descent:

1. Start with the straight line from home to school, with constant speed, and calculate energy.
2. Place a point halfway and minimize the energy varying its position, the starting speed and the speed at the point.
3. Recursively subdivide your subpaths, minimizing as per point 2.
4. Exiting from the recursion you can minimize again moving the mid point and varying speed at the end point.

I don't think this will give you the global optimum, but could give a good local minimum (just like an A* algorithm).

Obviously the function describing the terrain is assumed to be smooth.

Answer 3

You're right, the problem is harder than my first comment suggested. I think the trick is to expand the discretized state space to a third dimension, so that the state is (time, position, velocity) not just (position, velocity). Then you want to end in a state (time <= 20min, position = 5km, velocity = don't care) such that the path to that state has minimal energy usage. The dynamic programming recursion should work after this change.