1
$\begingroup$

I need an algorithm which can do the following:

Given some finite number of particles (circles) each with the same radius, and a list of prescribed points for each particle, find paths in $\mathbb{R}^2$ for the particles to take so they won't collide.

The list of points for a particle specifies the order in which the particle must visit those points. All particles start moving at the same time. The time elapsed for a particle to travel from any prescribed point to the next is constant for every particle regardless of distance. I'd like to find a continuous trajectory for each particle, so they won't collide (the circles won't overlap). Ideally, I would like to find the solution which minimizes total path length under the constraint that there are no collisions.

Assume that the distance between the n'th prescribed point of different particles are at least the particle's diameter apart so that there are no unfixable collisions.

My best solution is just making splines for every path, and keeping a record of all the collisions. I have been reading papers about potentially adding more prescribed points to bend the paths, and 'elastic bands', but I'm not sure exactly how to do it.

$\endgroup$
6
  • $\begingroup$ This is in 2 dimensions. I do specify the order in which the points are visited. Particles do start at the same time. My best solution is just making splines for every path, and keeping a record of all the collisions. I have been reading papers about potentially adding more prescribed points to bend the paths, and 'elastic bands', but I have made no progress on actually implementing any of them. I should also say that the particles can access the positions of each other at any point in time. $\endgroup$
    – JJJJJJJJJJJJJJJJ
    Jan 25, 2020 at 3:03
  • $\begingroup$ Thanks! Check if my edit matches your intent. And welcome to CS.SE! $\endgroup$
    – D.W. ♦
    Jan 25, 2020 at 3:44
  • $\begingroup$ Is the time from one point to the next the same for all particles, or does it vary from particle to particle? $\endgroup$
    – D.W. ♦
    Jan 25, 2020 at 3:45
  • $\begingroup$ Time does not vary from one point to the next $\endgroup$
    – JJJJJJJJJJJJJJJJ
    Jan 25, 2020 at 18:19
  • $\begingroup$ That's not what I'm asking. I'm not asking if it varies from point to point, I'm asking if it varies from particle to particle. $\endgroup$
    – D.W. ♦
    Jan 25, 2020 at 18:46

2 Answers 2

Reset to default
0
$\begingroup$

Let me first discuss some possible solutions for the case of $n$ particles and 2 points per particle, then extend it to an arbitrary number of points.

Suppose we're given $n$ particles and 2 points per particle. Assume we're also given an additional constraint: the initial direction of each particle is also specified. For each particle, it's easy enough to draw a path from the starting point to the ending point. Now consider the collection of those paths, and find all collisions. If we don't have any limit on the velocities or accelerations of each particle, it should be straightforward to pick a particle, choose the speed at which it traverses its path (if a constant speed causes collisions, slow down until you reach the collision point, then speed up afterwards, and adjust until there are no more collisions), and repeat, one particle at a time.

Let's suppose you have an algorithm you're happy with, for $m=2$ points per particle. Then you can use that to solve the problem for $n$ particles and $m$ points per particle, for any $m \ge 2$: you simply solve it for each pair of adjacent time steps (i.e., the $i$th and $i+1$th points), then combine those solutions.

Probably this could be improved, by finding a better way to handle the $m=2$ case. For instance, if there is an algorithm for laying out a graph as a planar graph, given pre-specified locations for all vertices, that might help find better solutions. However, maybe this illustrates one approach that can find at least a possible solution, even if it's not optimal.

$\endgroup$
1
  • $\begingroup$ I'm not sure what path you want to draw between the two points (the segment with these endpoints?), but not all collisions can be avoided by only changing the speed: if we have two particles traveling on the segment between the pairs of points $s_1,t_1$ and $s_2,t_2$, then if the points are on the same line in the order $s_1,t_2,t_1,s_2$, neither point can traverse their given path without collisions. $\endgroup$
    – Discrete lizard ♦
    Mar 18 at 11:34
0
$\begingroup$

Leave the points immobile. They won't collide.

$\endgroup$
3
  • $\begingroup$ "The list of points for a particle specifies the order in which the particle must visit those points." $\endgroup$
    – D.W. ♦
    Feb 12 at 19:57
  • $\begingroup$ @D.W.: I assume that I misunderstand the problem statement. Also, "collisions" can be avoided by letting one of the particles on hold. $\endgroup$
    – Yves Daoust
    Feb 12 at 20:00
  • $\begingroup$ Yup, that seems like it should work. I find the problem statement a bit hard to understand / a little bit vague. $\endgroup$
    – D.W. ♦
    Feb 12 at 20:16

Your Answer

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

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