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