2
$\begingroup$

I asked a similar question here, except I forgot to specify that the final velocity must be 0.

I have 2 points in 2D space, start = $s$ and target = $t$, and a starting velocity $v_0$.

At each time step $k$, the current point $p$ (which starts as $s$ and is incrementally updated) has the velocity $v$ added to it, so $p_k = p_{k-1}+v_{k-1}$. Additionally, the velocity has some acceleration $a$ applied to it which we can control (although this acceleration has a maximum magnitude of $m$) after the position has been updated, so $v_k = v_{k-1} + a_k$.

The idea is to (by controlling only the acceleration) finish at the target point $t$ with a final velocity of $v=(0,0)$ (so that you actually remain stationary at the point and don't overshoot)

To clarify this problem, I have provided an example below: enter image description here In this case: $$p_0 = s = (1,3)$$ $$t = (2,1)$$ $$v_0 = (1,-1)$$

(In this case, the acceleration had a maximum allowed magnitude of 1, so $m=1$)

  1. At time step $k=1$, first the velocity $v=(1,-1)$ is applied to $p=(1,3)$, to get the resultant point $p=(2,2)$, then, the acceleration $a=(-1,0)$ is applied to the velocity $v$ to get $v=(0,-1)$

  2. At time step $k=2$, first the velocity $v=(0,-1)$ is applied to $p=(2,2)$, to get the resultant point $p=(2,1)$, then, the acceleration $a=(0,1)$ is applied to the velocity $v$ to get $v=(0,0)$

  3. At time step $k=3$, the velocity is 0 and we have finished at the target, so that was a valid path

*Note while I only used whole numbers here, floats are perfectly fine for use too

I am trying to find an algorithmic approach to this such that I can solve this in the minimum number of time steps.

To put it simply: I want to find the list of accelerations required to reach the target in the minimum number of time steps with a final velocity of (0, 0)

$\endgroup$
1
  • $\begingroup$ Let $a_0,a_1,a_2,\dots$ denote the acceleration applied in each step. Suppose we are hoping to find a trajectory that works with $k$ steps. Then there is a trajectory that meets your conditions iff there exists $a_0,\dots,a_{k-1}$ that satisfy all of the following conditions: $$(k-1) a_0 + (k-2) a_1 + \dots + a_{k-1} = t - s - k v_0$$ $$a_0 + a_1 + \dots + a_{k-1} = -v_0$$ $$\|a_0\| \le m, \dots, \|a_{k-1}\| \le m$$ Perhaps folks on Math.SE can suggest how to check whether there is a solution for this system of vector equations? $\endgroup$ – D.W. 13 hours ago

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.