Mutli-Path Collision Avoidance 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.
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.