6
$\begingroup$

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_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?

$\endgroup$
  • $\begingroup$ You can get the same answer as Approach 2 in a cheaper way, and the key point is that for each (position, velocity) pair there is a best time and path to get to that state. So Approach 3 would take something like NiNjNj, so linear in the number of x positions and quadratic in the number of discrete velocities. $\endgroup$ – k20 Aug 14 '14 at 14:39
  • $\begingroup$ @k20 Saying for each (position, velocity) pair there is a best time and path to get to that state, what do you mean by best time? How to figure out or how to consider the time at (x_i, v_j) making sure one arrives in time at x_S? Because the time has to be sufficient small to reach x_S in time but one does not want to waste energy by driving to fast getting to the final destination too early... I also think it can be done in NiNj^2 somehow, but I can't figure *how $\endgroup$ – esol Aug 14 '14 at 14:49
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Yes, somehow like this. But I thought that we need to find a cost function, so that each step generated minimum cost. Still I have no clue how to heed this "global" time constraint for each step cause the single time step size apparently is not important but only in the end the sum of all steps is (close to) t_s.. $\endgroup$ – esol Aug 25 '14 at 8:53
  • $\begingroup$ At each (time, position, velocity) triple, you can choose among a finite number of force choices that will each lead to a later and farther (time, position, velocity) states and will each have an associated cost. These are the dynamic programming transitions. You can heed the time and distance constraints by looking for the state with time=20, position=4 that has smallest cost. $\endgroup$ – k20 Aug 25 '14 at 15:02

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.