I've been thinking about path planning and am trying to make good heuristics for cases with multiple agents.
Suppose there are sets $S_i$ of coordinates in $\mathbb R^2$ or $\mathbb R^3$, each of the same size n, for each possible value of $i$ where $i \in [0, ... k]$.
A path is defined as k line segments connecting a sequence of k+1 coordinates, made up of one coordinate from each set $S_i$ in consecutive order. I want to find n paths such that (a) no two paths have the same point for a given index i in the sequence, and b) the combined path length of all the paths is minimized. In other words, assign coordinates from each set without replacement to construct paths with the goal of making the total path length as small as possible.
Right now i can do the minimization from some $i$ to $i+1$, but I am not sure if locally minimizing each step will yield a global minimum. I know I could brute force it, but that explodes really quickly.