I've been working on a problem involving a moving target and a pursuer, where the goal is to have the pursuer intercept the target in the shortest possible time. First some basic terms:

$\newcommand{\R}{\mathbb{R}}$ $\newcommand{\Norm}[1]{\left \lVert #1 \right \rVert}$ $\newcommand{\diff}{\mathop{}\!\mathrm{d}}$

  • $ \phi \in C^0(\R^{\ge 0}, \R^N) $ ($ \phi $ is the target trajectory, and is a continuous curve in $ \R^N $)

  • $ \mathbf{x_0}, \mathbf{v_0} \in \R^N $ ($ \mathbf{x_0} $ is the pursuer's initial position and $ \mathbf{v_0} $ is the pursuer's initial velocity)

  • $ V, A \in \R^+ $ ($ V $ is the pursuer's maximum speed and $ A $ is the pursuer's maximum acceleration)

  • $ \begin{align} X_\tau = \{\psi \in C^2(\R^{\ge 0}, \R^N) ~|~ & \psi(\tau) = \phi(\tau) \\ ~\wedge~ & \psi(0) = \mathbf{x_0} \\ ~\wedge~ & \psi'(0) = \mathbf{v_0} \\ ~\wedge~ & \sup_{0 \le t \le \tau} \Norm{\psi'(t)} \le V \\ ~\wedge~ & \sup_{0 \le t \le \tau} \Norm{\psi''(t)} \le A\} \end{align} $

($ X_\tau $ is the set of all twice continuously differentiable curves in $ \R^N $ that intersect $ \phi $ at time $ \tau $, and which satisfy the initial position, initial velocity, maximum speed, and maximum acceleration constraints given by $ \mathbf{x_0} $, $ \mathbf{v_0} $, $ V $, and $ A $)

$ ~ $

I'm looking for the minimum $ \tau^* \in \R^{\ge 0} $ such that $ X_{\tau^*} $ is non-empty, supposing it exists. I suspect (though haven't proven) that if $ \tau^* $ does exist, then $ X_{\tau^*} $ is a singleton set, i.e. there is a unique feasible pursuer trajectory $ \psi $ that will intercept $ \phi $ in the shortest amount of time. Furthermore, I have a fairly strong hunch about the form that the desired pursuer trajectory will take: the pursuer will accelerate at the maximum possible rate toward a given velocity of maximum speed, and then travel in a straight line at this velocity until intercepting the target.

I've done some work to determine, for a given constant acceleration $ \mathbf{\alpha} \in \R^N $ with $ \Norm{\mathbf{\alpha}} = A $, what the associated trajectory $ \psi_{\mathbf{\alpha}} $ of this form looks like. I could test any such trajectory to see if it intercepts $ \phi $, and if so then when. However, this doesn't actually help me find the optimal acceleration to minimize the intercept time.

Even though I've presented the target trajectory as any continuous curve, in practice it will be of the form $ \phi(t) = \mathbf{r} + \mathbf{v} t + \frac{1}{2} \mathbf{a} t^2 $ where $ \mathbf{r} $, $ \mathbf{v} $, and $ \mathbf{a} \in \R^N $ are the measured position, velocity, and acceleration of the target, respectively. I suspect that getting a general exact solution for the optimal pursuer trajectory will be near impossible, but I'm trying to come up with a way to iteratively and numerically zero in on it, and am getting stuck with where to go. Any help would be greatly appreciated.


Disclaimer: this is not an answer but only a hint. I would have written this as a comment but I don't have enough reputation.

Assuming that the initial velocity of the pursuer is 0, the set of points that you can reach at time $t$ is a ball of a certain radius $r(t)$. The size of this radius depends on your constraints. If $\mathbf{v}_0 \neq 0$, this region is probably ellipse-like (but still a convex domain).

To have a hit you need the function $\phi$ to intersect this ball, that is, you need (squaring for simplicity). $$\Vert \phi(t) - \mathbf{x}_0 \Vert^2 = r(t)^2$$ (for the convex case you can work with the projection of $\phi$ on the domain, or maybe consider $\Vert \phi(t) - \mathbf{x}_0 - \mathbf{v}_0 t \Vert^2 = r(t)^2$).

To solve (for $t$) $$\Vert \phi(t) - \mathbf{x}_0 \Vert^2 = r(t)^2$$ you can use Newton method (if $\phi$ is differentiable). Otherwise some bisection approach.

Once you find when they hit, you can find where they hit, and then you can just look for the shortest path to it (for the shortest path you have to minimize its length, which can be expressed as an integral).


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.