This question has been asked on scicomp but I thought maybe it's more a mathematical problem of how Bellman's idea is to be applied here.

The main problem for me is: How to introduce the time constraint? A hint has been given that the time also has to be considered a state variable, but I'm still confused. I wondered how to actually get the cost function? If the energy consumption has to be minimized, is there anything else which has to be considered to set up a cost function?

I'd be great to get some input on how to approach this kind of problem. If possible please in a way a non mathematician can comprehend. I've got a book of Bellman here, but it's just... a different world to me.

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

enter image description here

$$\Delta x = 0.5km \quad x_k = k * \Delta x \quad k = 0, 1 \dots K\\ \Delta v = 5km/h \quad v_m = m * \Delta v \quad m = 0, 1 \dots M\\ $$


The first step is the recursion, calculating the required force $F_D$ for all possible transitions $x_k \rightarrow x_{k-1}$ starting from $x_S$ for each $dv_{k} = v_{m, k} - v_{m, k-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_{k,m \rightarrow k+1,m} \\ \Delta t_{k,m \rightarrow k+1,m}$$

We also know the energy for each transition $E_{k,m \rightarrow k+1,m}$ since we assumed $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_{k} E_{k \rightarrow k+1,m} \\ \underset{k}{\sum} \Delta t \le t_S$$

Approach 1: We can run through $k = 0, 1 \dots K$ taking the transition with the lowest 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_k$ we can choose about $M$ directions (velocities), so that the complexity would be basically $$O(M^K)$$ 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?

  • $\begingroup$ For the time constraint, why not just divide total distance traveled (so far by a given subpath) by average velocity? Also, it seems like a modified version of Dijkstra's algorithm could work well on this problem. It is not totally clear that this problem can be imbedded with subproblems in a tractable way (ie without doing BFS from destination node). Does this particular problem come from a Dynamic Programming text? $\endgroup$ – A.E Sep 8 '14 at 14:35
  • $\begingroup$ It is indeed a problem which can be solved by Dynamic Programming and there are papers on this topic, but it's not so easy for me to deduce those equations written there to a concrete problem. A BFS routine I wrote works for little number of steps K. Right now I found an approach which adds the time as dimension so that in the backwards computations you can force the profile to end in a given time. This approach find indeed optimal transitions. The transitions do not exactly end on a vertex of the mesh, cause velocity, position and time are dependent on each other. $\endgroup$ – esol Sep 14 '14 at 18:20
  • $\begingroup$ Right now I simply choose the closest time on the mesh and apply the cost function. By doing so at any state, the optimal profile to the final point is already determined. Just I'd like to know: Are there other approaches? Is such an approach correct? One paper which deals with optimal trajectories is this but I have not yet figured out, how they do it... $\endgroup$ – esol Sep 14 '14 at 18:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.