I have a point cloud of size n (in the example on picture n = 5). The starting coordinates are in green, destination coordinates are in red. What I need is to move the points from the starting coordinates to the destination ones so that the total distance, traveled by all points is minimal.

There is one important restriction - points' trajectories should not intersect (so, trajectories could be curvy). To handle this, we may introduce some ε to denote the minimum distance between two trajectories, after which they will be considered intersecting.

For the particular case described at the picture, the minimal path will look like A -> F + B -> G + C -> H + D -> I + J -> E.

Solutions that came to my mind:

• The greedy approach will not work, because if we start from point A and choose the nearest destination point, we'll end up with E moving to F, which is far from being optimal.
• Brute dynamic programming solution will result in something like O(n!) complexity, which is not really acceptable.

None of those solutions save me from intersecting trajectories.

My gut tells me, that some kind of gradient descent may be useful for this task, but I can't figure out how to apply it to this task.

What I need is not a working code, but advises or directions to related topics/articles/papers which will help me to understand how to solve this task.

P.S. I saw Assign m agents to N points by minimizing the total distance and Given 2 sets of n points: minimize sum of traveled distances but wondered how this task can be handled after the introduction of the aforementioned trajectory-related restriction.

P.P.S. Non-intersecting trajectories can be changed in favor of non-colliding points (the distance between several points can't be smaller than ε at the same moment of time) if that makes the task easier to solve (if not - let's stick to the original conditions).

I have a point cloud of size n (in the example on picture n = 5). The starting coordinates are in green, destination coordinates are in red. What I need is to move the points from the starting coordinates to the destination ones so that the total distance, traveled by all points is minimal.

There is one important restriction - points' trajectories should not intersect (so, trajectories could be curvy). To handle this, we may introduce some ε to denote the minimum distance between two trajectories, after which they will be considered intersecting.

Non-intersecting trajectories can be changed in favor of non-colliding points (the distance between several points can't be smaller than ε at the same moment of time) if that makes the task easier to solve (if not - let's stick to the original conditions). In such a case maximum point speed, V, should be introduced.

More than 2 points may lay on a line (e.g. 2 starting points and 2 destination ones may be collinear).

For the particular case described at the picture, the minimal path will look like A -> F + B -> G + C -> H + D -> I + J -> E.

Solutions that came to my mind:

• The greedy approach will not work, because if we start from point A and choose the nearest destination point, we'll end up with E moving to F, which is far from being optimal.
• Brute dynamic programming solution will result in something like O(n!) complexity, which is not really acceptable.

None of those solutions save me from intersecting trajectories.

My gut tells me, that some kind of gradient descent may be useful for this task, but I can't figure out how to apply it to this task.

What I need is not a working code, but advises or directions to related topics/articles/papers which will help me to understand how to solve this task.

P.S. I saw Assign m agents to N points by minimizing the total distance and Given 2 sets of n points: minimize sum of traveled distances but wondered how this task can be handled after the introduction of the aforementioned trajectory-related restriction.

I have a point cloud of size n (in the example on picture n = 5). The starting coordinates are in green, destination coordinates are in red. What I need is to move the points from the starting coordinates to the destination ones so that the total distance, traveled by all points is minimal.

There is one important restriction - points' trajectories should not intersect (so, trajectories could be curvy). To handle this, we may introduce some ε to denote the minimum distance between two trajectories, after which they will be considered intersecting.

For the particular case described at the picture, the minimal path will look like A -> F + B -> G + C -> H + D -> I + J -> E.

Solutions that came to my mind:

• The greedy approach will not work, because if we start from point A and choose the nearest destination point, we'll end up with E moving to F, which is far from being optimal.
• Brute dynamic programming solution will result in something like O(n!) complexity, which is not really acceptable.

None of those solutions save me from intersecting trajectories.

My gut tells me, that some kind of gradient descent may be useful for this task, but I can't figure out how to apply it to this task.

What I need is not a working code, but advises or directions to related topics/articles/papers which will help me to understand how to solve this task.

P.S. I saw Assign m agents to N points by minimizing the total distance and Given 2 sets of n points: minimize sum of traveled distances but wondered how this task can be handled after the introduction of the aforementioned trajectory-related restriction.

I have a point cloud of size n (in the example on picture n = 5). The starting coordinates are in green, destination coordinates are in red. What I need is to move the points from the starting coordinates to the destination ones so that the total distance, traveled by all points is minimal.

There is one important restriction - points' trajectories should not intersect (so, trajectories could be curvy). To handle this, we may introduce some ε to denote the minimum distance between two trajectories, after which they will be considered intersecting.

For the particular case described at the picture, the minimal path will look like A -> F + B -> G + C -> H + D -> I + J -> E.

Solutions that came to my mind:

• The greedy approach will not work, because if we start from point A and choose the nearest destination point, we'll end up with E moving to F, which is far from being optimal.
• Brute dynamic programming solution will result in something like O(n!) complexity, which is not really acceptable.

None of those solutions save me from intersecting trajectories.

My gut tells me, that some kind of gradient descent may be useful for this task, but I can't figure out how to apply it to this task.

What I need is not a working code, but advises or directions to related topics/articles/papers which will help me to understand how to solve this task.

P.S. I saw Assign m agents to N points by minimizing the total distance and Given 2 sets of n points: minimize sum of traveled distances but wondered how this task can be handled after the introduction of the aforementioned trajectory-related restriction.

P.P.S. Non-intersecting trajectories can be changed in favor of non-colliding points (the distance between several points can't be smaller than ε at the same moment of time) if that makes the task easier to solve (if not - let's stick to the original conditions).