2
$\begingroup$

I have several point-bodies (shown below in black) moving at constant speed, with no change in orientation. Given an arbitrary point (such as the red point), how can I find which direction to move in which will most quickly maximize the distance between it and every other point? Note that the direction can only be selected once, there is no re-planning.

Example

My current approach is to run an optimizer to maximize the sum of the distances from the red point to every other point. This works well enough if the other points aren't moving, but fails in situations such as below, where the direction which would maximize distance from static obstacles would result in colliding with them given the direction they are moving in.

Collision Example

Any suggestions for how to approach this?

$\endgroup$
8
  • $\begingroup$ Do you want to maximize the distance between one specific moving dot and all the rest? and you can only set the speed of that specific point? you do not set the speed of the other dots at will? $\endgroup$
    – user65081
    Feb 8, 2020 at 17:17
  • 1
    $\begingroup$ Your goal is a maximal distance, but maximal distance when? A direction might good at first but bad later, and in general the total distance will be a function of time. $\endgroup$ Feb 8, 2020 at 17:21
  • $\begingroup$ @Wolphramjonny, Yes, from one point to the rest, and I can only modify that point. $\endgroup$ Feb 8, 2020 at 17:42
  • $\begingroup$ @BobJacobsen, Excellent question, and one that I hadn't thought about. There is an initial state, but I haven't set a goal or end time. Maybe one could be set at an "arbitrary" horizon and then planned using that? $\endgroup$ Feb 8, 2020 at 17:46
  • 1
    $\begingroup$ how do prevent that the black dots clash among them? $\endgroup$
    – user65081
    Feb 8, 2020 at 23:25

4 Answers 4

1
$\begingroup$

For each moving particle, calculate the minimum distance $d_i$ with the moving point. Then try to maximize the minimum of all them.

  • Put a co-moving coordinate system on the target point.

  • Describe the motion of each particle relative to the target point. So at time $t=0$ the position vectors of each particle is $\vec{r}_i$, and they move with speed $\vec{v}_i$ (all relative).

  • The minimum distance of the particle to the coordinate system is $$d_i = \sqrt{ \| \vec{r}_i \|^2 - \frac{ (\vec{r}_i \cdot \vec{v}_i)^2 }{ \| \vec{v}_i \|^2 } } $$

  • This occurs at time $$ t = - \frac{ \vec{r}_i \cdot \vec{v}_i }{ \| \vec{v}_i \|^2 } $$

Your control knob is the direction of movement of the reference point which changes each $\vec{v}_i$ and hence the value of $ \vec{r}_i \cdot \vec{v}_i$.

If you use the formula for the dot product $ | \vec{a} \cdot \vec{b} | = |\vec{a}| |\vec{b}| \cos \theta$ then the distance is

$$d_i = \sqrt{ \| \vec{r}_i \|^2 (1-\cos^2 \theta_i )} = \| \vec{r}_i \| \sin \theta_i $$

where $\theta_i$ is the angle between $\vec{r}_i$ and $\vec{v}_i$

$\endgroup$
2
  • $\begingroup$ what d you man by co-moving coordinate system? One where the target point is the origin? $\endgroup$ Feb 9, 2020 at 20:57
  • $\begingroup$ Yes, one where the target point is the origin and is moving with the same constant velocity as the point (what you are looking for). So the relative velocity of the i-th point is $$\vec{v}_i = \dot{\vec{\rm target}}_i - \dot{\vec{\rm point}}$$ $\endgroup$ Feb 9, 2020 at 21:05
0
$\begingroup$

Calculate the position of the center of mass of the black particles, it will be a function of t. Once you have that, if you want to minimize the distance at a certain time t, you chose the angle such that your red particle will initially move away from the location that the center of mass will have at time t.

If you need a math justification let me know.

$\endgroup$
6
  • $\begingroup$ Does your algorithm guarantee that the red particle will not collide with a black particle? Or that it will maximise the distance from any black particle? I am sceptical because reducing the positions of several particles down to the position of the COM throws away a lot of potentially important information. $\endgroup$ Feb 8, 2020 at 21:19
  • $\begingroup$ For example 4 black particles could be arranged in a square all directed toward the centre. If the red particle is located on any diagonal then your algorithm guarantees that it will collide with a black particle. $\endgroup$ Feb 8, 2020 at 21:33
  • 1
    $\begingroup$ @sammygerbil I only maximized the square of the distance to all particles simultaneously as a function of time, it does not guarantee lack of collisions $\endgroup$
    – user65081
    Feb 8, 2020 at 21:33
  • $\begingroup$ @sammygerbil actually, avoiding collisions, I have no clue how to due it in a simple way $\endgroup$
    – user65081
    Feb 8, 2020 at 21:35
  • 1
    $\begingroup$ I agree, plus I guess the particles are not point masses, otherwise the likelihood of collisions is of measure zero, unless the initial conditions are very special $\endgroup$
    – user65081
    Feb 8, 2020 at 22:23
0
$\begingroup$

Start by writing a function that'll give your desired metric, i.e. the sum of distances (if that's your criteria) at some time $t$ and with the particle at $x$ and $y$:

$$ D(x, y, t) = \sum_{particles} (x(t) - X_i(t))^2+(y(t) - Y_i(t))^2 $$

in which $X_i(t)$ and $Y_i(t)$ are numbers at any particular instant; the position of the ith particle at time t.

If the motions are linear $X_i(t) = V_{xi} t + X_{0i}$ then you can write

$$ D(x, y, t) = \sum_{particles} \sqrt{(x(t) - V_{xi} t + X_{0i})^2+(y(t) - V_{yi} t + Y_{0i})^2} $$

then assuming a linear motion of your red particle, you can directly insert that trajectory to get $D$ as just a function of time and initial velocity. This becomes (for simplicity, assuming it starts at the origin):

$$ D(t, v_x, v_y) = \sum_{particles} \sqrt{(v_x t - V_{xi} t + X_{0i})^2+(v_y t - V_{yi} t + Y_{0i})^2} $$

Finally, differentiate first by $v_x$ and then $v_y$ to give a function that will be at an extremum (hopefully a maximum) when zero. That'll still be a function of time, because one set of $v_x, v_y$ might give a maximum at one time, while another gives a different one at a different time. You need to think through your problem statement to know how to deal with this.

Note there's nothing in this that prevents the red ball from hitting a black one. That can even be the right solution for maximizing the total distance.

Another note: All this math gets a lot simpler if you metric is the smallest distance squared. Because of how $d u^2 / dx$ works, this will reduce to linear equations.

$\endgroup$
2
  • $\begingroup$ if you differentiate with respect to the speeds you will get a minimum, as the speed can be as large as you want to get away from the rest, and you will find no maximum. You need to differentiate with respect to the angle, using $v_x=v cos \theta$, etc, with v fixed $\endgroup$
    – user65081
    Feb 8, 2020 at 22:27
  • $\begingroup$ DF/dx=0 is an extremism. At a particular time, there’s a maximum, finite value. I agree that as time -> infinity the distance grows, but I’m not suggesting differentiating with respect to time. But the problem could also be cast to angle and speed. $\endgroup$ Feb 9, 2020 at 1:45
0
$\begingroup$

Far as possible from all three would put it at the center of a circle drawn through the three points. That point will move as the particles move. Let's say the movement of that center is on a straight line. If that straight line does not go through the "red" particle's initial position, then at best you'll be able only to give the red particle a kick that lets it hit that moving center at one point along its trajectory. IF the straight line does go through the point of the red particle, it's easy: just calculate the velocity of the center and give the red particle a velocity that's the same as the center's velocity.

$\endgroup$
4
  • $\begingroup$ "Far as possible from all three would put it at the center of a circle drawn through the three points" is not this wrong? what about moving it as far as possible from the dots? $\endgroup$
    – user65081
    Feb 9, 2020 at 14:55
  • $\begingroup$ I suppose one could shoot the red particle in practically any direction at near the speed of light to get it far away from all the particles. I was making a guess at what the OP really wants--- $\endgroup$
    – S. McGrew
    Feb 9, 2020 at 19:02
  • $\begingroup$ The above is a single example, the red and black particles may lie anywhere in the environment, so the centerpoint won't always be valid. $\endgroup$ Feb 9, 2020 at 20:53
  • $\begingroup$ Ok, then it's not clear what you mean by "direction to move in which will most quickly maximize the distance between it and every other point". You need to define that composite "distance" (sum of the squares of the individual distances, perhaps?). Then your optimizer might work. But (without doing the math) I suspect the quickest direction will depend on how fast the red particle moves. $\endgroup$
    – S. McGrew
    Feb 9, 2020 at 21:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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