Consider a landscape with obstacles on it, and some number of people on the landscape. Suppose all the people have a common goal, a destination on the landscape. How can we get everyone from their individual starting points to the destination (without running into each other on the way) in a globally optimal way?
For the purposes of this project, globally optimal is defined as the minimum sum of travel time for all people over all possible choices of (non-colliding) paths to the destination.
|
|
Discretize the landscape into an m by n grid. |
|
|
Allow obstacles to be places on the landscape where people cannot walk. |
|
|
Turn the accessible region of the landscape into a m by n node graph. |
|
|
Let there be k people with k different starting positions on the grid (x1, y1), ..., (xk, yk) |
|
|
Let there be a single goal position (gx, gy) |
|
|
Find: |
|
|
a set of globally optimal paths for each person such that no one collides with anyone else and everyone reaches the goal. |
|
|
or alternately, a set of paths that are globally optimal given that we are only looking up to HORIZON steps ahead at each time step |
|
|
Create an m by n grid for each time step t (for t between 0 and HORIZON) representing space-time up to the time horizon |
|
|
For each node at (x,y,t), create a directed edge to (x +- 1, y+- 1, t+1) representing a possible move from (x,y) to an adjacent grid cell at time t. |
|
|
For each node at (x,y,t), also create a directed edge to (x,y,t+1), representing the possibility of staying in place at time t. |
|
|
Introduce a sink node T := (gx, gy, HORIZON+1) |
|
|
For each person i, a path in the space-time graph from (xi,yi,0) to T represents a path (in time) from her starting position to the destination |
|
|
Give each edge a capacity of 1. |
|
|
Introduce a source node S which has an outgoing edge to each (xi,yi,0) |
|
|
Each flow from S to T gives a non-colliding* path in space-time for a person to get to the destination |
|
|
Now all we have to do is find k flows from S to T such that the sum of the cost of the edges along the flows is minimized |
Run the max-flow algorithm (find path from S to T, build residual graph, repeat) on the directed graph. Instead of finding an arbitrary path from S to T in the residual graph at each iteration, find the shortest path in the residual graph.
|
|
*To make paths vertex-disjoint, introduce 2 nodes v1, v2 for every 1 node v such that v1 has an edge to v2 , all the edges going into v now go into v1, and all edges coming out of v now come out of v2. |
|
|
For each node (x,y,t) such that (x,y) is adjacent to (gx, gy), create a directed edge to a sink node T:=(gx,gy,HORIZON+1), so that people "disappear" from the graph once they reach the goal |
|
|
For each node (x, y, HORIZON), create a directed edge to T with weight |(x,y) - (gx,gy)| representing the estimated distance to the goal |
|
|
Weights of 1 assigned to edges representing a move in a cardinal direction, weights of sqrt(2) assigned to edges representing a diagonal move. |
|
|
|
|
|
Hopefully more to come in the future... |
|
|
People can currently move a distance of 1 (in one of the four cardinal directions) or a distance of sqrt(2) (in one of the four diagonal directions) in one time step, which means the speed at which people move varies depending on which direction they're headed. Can this be fixed? |
|
|
Other optimization criteria (distance traveled?) |
