5
$\begingroup$

A spaceship moving in two dimensions is at position $(x, y)$ and has a velocity $(v_x, v_y)$. It also has a maximum acceleration $a_{max}$. Its goal is to be at position $(x', y')$ with a velocity of $(v'_x, y'_x)$. What path takes the smallest amount of time?

I see that the problem can be reduced to a spaceship at $(0, 0)$ with a velocity of $(0, 0)$, trying to intercept a object currently at $(x'-x, y'-y)$ with a velocity of $(v'_x - v_x, y'_x - y_x)$.

I have a hunch that the optimal path will always be constant acceleration in one direction, possibly with a reversal somewhere along the way.

I'm curious because I believe the total time will be a consistent and admissable heuristic for a Newtonian pathing algorithm that takes velocity into account.

Clarification

There are no additional constraints. The problem is to minimize time, not to conserve $\Delta v$.

$\endgroup$
1
$\begingroup$

I remember that the Lagrange multiplier can be used for this kind of problem. I hadn't used it much myself so I won't try to explain it from the theoretical standpoint.

In short it is a method for finding local maxima/minima for a given function under some constraints.

This method will give you the solution, but you will need to read up how to use it. Alternatively you can try to find some examples now that you know how it is called, there will probably be something similar to your spaceship problem.

Good Luck!

EDIT :

Look into the Brachistochrone curve article. It is the use of the Lagrange method to a class of problems that is similar to yours.

$\endgroup$
1
$\begingroup$

Your hunch is correct. The optimal solution is acceleration at $a_{max}$ followed by deceleration. The correct ratio (and direction) of the two depends on the relative initial and final velocities.

For the 1D case with velocity changing from $v_i$ to $v_f$, from position $x_i$ to $x_f$, accelerating for $t_1$ and decelerating for $t_2$. You can derive the following equations. $$ v_f=v_i + a(t_1-t_2) $$ $$x_f=x_i+v_i(t_1+t_2)+\frac{1}{2}a(t_1^2−t_2^2)+at_1t_2$$

This is two equations with two unknowns and you can solve for $t_1$ and $t_2$.

If your also changing the direction (so its actually a 2D problem, like you give) its a bit more complicated as you must also optimise the direction of thrust, but the same principles still apply.

As a side note real spacecraft tend not to do this as it is not the most fuel efficient, which is a bigger concern for spacecraft.     

$\endgroup$
  • 1
    $\begingroup$ Thank you for your answer! I'm having trouble deriving the second equation. I feel that $x_f$ cannot be independent of $v_i$. I'm getting $x_f = x_i + v_i(t_1 + t_2) + \frac{1}{2}a({t_1}^2 - {t_2}^2) + at_1t_2$. $\endgroup$ – Matthew Piziak May 17 '14 at 4:19
  • $\begingroup$ yes you are correct. I wasn't paying attention will edit my answer $\endgroup$ – nivag May 18 '14 at 10:40
  • $\begingroup$ I am not so sure if this would be the optimal solution, since you both do not give the criteria for an optimal solution and proof that those are met. To me using maximal acceleration all the time does not seem optimal. For instance when both velocities are (near) zero and you only have to cover a certain distance, then to me it would seem that applying a very small initial impulse at the start and end would suffice (when using that the total expelled $\Delta v$ would be the cost function). $\endgroup$ – fibonatic Nov 13 '14 at 1:44
  • $\begingroup$ Thank you for your comment and question link. I've clarified the problem description. The goal is to find the path which takes the smallest amount of time. $\Delta v$ is not part of the cost function. $\endgroup$ – Matthew Piziak Nov 13 '14 at 3:11

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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