Dynamic Shortest Path with Linear Programming
Consider a grid with $x=5$ columns, $y=5$ rows, and $T$ timesteps.
There are $N=2$ agents in this grid, which can move vertically or horizontally. The positions of each agent $x$ at timestep $t$ is denoted as $A_{xt}$. For this example, consider $A_{00}=1$ and $A_{10}=23$. The goal is to carry a ball from node $1$ to node $G=15$. Each agent can carry the ball or throw it at distance $k=2$ (measured in Manhattan distance). The shortest path is, in this case, for Agent $0$ to carry the ball until node $3$, while Agent $1$ moves to node $13$. Then, Agent $0$ throws the ball to Agent $1$, which kicks it to the goal node.
How can this be modeled? If agents cannot move without the ball (not a dynamic graph), the problem is fairly simple. Assume $X_{ijt}=1$ (an activated edge) when the ball is carried or is kicked from node $i$ to $j$ at timestep $t$, and all actions cost (or have weight) $1$. All nodes (except starting and goal nodes) must have the same amount of ball 'entrances' as 'exits'.
$ \sum X_{ijt_1} = \sum X_{jit_2}, \forall i,j,t_1,t_2$, where $t_1<t_2, d(i,j)=1$ (adjacent nodes) or $j=A_{xt}$ (passing towards an agent)
The entrance and exit nodes will have a single activated edge.
$ \sum X_{A_{00}j0} + \sum X_{A_{00}A_{x0}0} = 1, \forall j,x$, where $x\neq0, d(A_{00},j)=1, d(A_{00},A_{X0})\leq k$
$ \sum X_{iGT} = 1, \forall i$, where $d(i,G)\leq k$
However, if all agents can move at any given point, then the graph is dynamic, since the passes that can be performed are different in each timestep. I don't know how to model this. Before, because $A_{1t}$ was static until it got the ball, I could list all the restrictions a priori, but now, I cannot do it. I can create a set of restrictions based on $A_{xt} \forall x,t$, but I don't know how to then input this problem into a linear programming solver (for example, a simplex method).
algorithms optimization shortest-path linear-programming modelling
BlueMoon93
BlueMoon93BlueMoon93
Our matrix is modelled as a graph $G = (V,E)$ with directed edges $E$ between cells $V$. We denote $V_{kl}$ as the set of nodes $j$ that respect $d_{jl} \leq k$. The edges $E$ exist between all nodes $j \in V_{kl}$ and node $l$, for any $l \in V$. Activated edges represent movements (such as players moving with the ball to an adjacent cell or passing the ball to a faraway agent). All player actions (moving, kicking or passing) take exactly $1$ action, therefore the weight of all edges in our graph is always $1$. Throughout this paper, unless specified otherwise, we use $i \in [1, p]$ to identify an agent, $t \in [0, T]$ to identify different timesteps and $l,j \in V$ to identify nodes. We must define the position and movements of each agent $i$, as well as the position and movements of the ball, all across $t$. Assuming $l_1 \in V_{1l}$ and $l_k \in V_{kl}$, then
\begin{equation} \begin{split} A_{ijt} = & \begin{cases} 1 ,& \textrm{if Agent $i$ is on cell $j$ at timestep $t$} \\ 0 ,& \textrm{otherwise} \end{cases} \\ Y_{ill_1t} = & \begin{cases} 1 ,& \textrm{if Agent $i$ moved from cell $l$ at timestep $t$ to cell $l_1$ at timestep $t+1$} \\ 0 ,& \textrm{otherwise} \end{cases} \\ B_{jt} = & \begin{cases} 1 ,& \textrm{if Ball is on cell $j$ at timestep $t$} \\ 0 ,& \textrm{otherwise} \end{cases} \\ X_{ll_kt} = & \begin{cases} 1 ,& \textrm{if Ball moved from cell $l$ at timestep $t$ to cell $l_k$ at timestep $t+1$} \\ 0 ,& \textrm{otherwise} \end{cases} \end{split} \end{equation}
These definitions inherently model the behaviour of our agents and ball, by limiting agents to only move $1$ unit of distance at most, and the ball to move $k$ units of distance at most. Both $B_{j0}$ and $A_{ij0}$ are defined for all $j,i$. We must now model the relation between $A$ and $Y$, as well as between $B$ and $X$. In fact, $A_{i,l,t+1}$ (representing agent $i$ being on cell $l$ at timestep $t+1$) must be the sum of $A_{i,l,t}$ (agent $i$ may have been in that cell in the previous timestep and remained stationary) with $\sum_j Y_{ijlt} - \sum_j Y_{iljt}$ (agent $i$'s movements entering or leaving that cell). If the agent remains stationary, the latter part of the sum is equal to $0$. Analogously, a similar relation exists between $B$ and $X$. Formally, for all $i$, $l$, $t$,
\begin{equation} \begin{split} A_{i,l,t+1} & = A_{i,l,t} + \sum_{j \in V_{1l}} Y_{ijlt} - \sum_{j \in V_{1l}} Y_{iljt}, \\ % player positions are related to their movements B_{l,t+1} & = B_{l,t} + \sum_{j \in V_{kl}} X_{jlt} - \sum_{j \in V_{kl}} X_{ljt}. \\ % ball positions are related to its movements \end{split} \end{equation}
Our optimization function now differs in the fact that $t$ must be taken into account. This is necessary due to the fact that the ball may remain in the same place for several turns, which counts as movement to the same cell. In other words, reaching the goal $G$ on the second timestep $t$ and waiting there for $50$ turns is equivalent to waiting $50$ turns and then entering the goal. Therefore, our objective functions is now
\begin{equation} Z = \sum_{t,l \in V_{kG} \setminus G} ( t * X_{lGt} ) . \end{equation}
We must update the previously described constraints so that the ball enters the goal $G$ only once at any timestep $t$ and leaves the source $S$ at timestep $0$. Our modeling of $B$ dependent on $X$ will ensure that the ball will move among the cells from $S$ to $G$.
\begin{equation} \begin{split} \sum_{l \in V_{kS}} X_{Sl0} & = 1, \\ % ball leaves Source once \sum_{j \in V_{kG} \setminus G,t} X_{jGt} & = 1, \\ % ball enters Goal once \end{split} \end{equation}
Finally, we must guarantee that the agents do not overlap and that they carry the ball, kick it to the goal $G$, or pass it at each other. In other words, the amount of agents at node $j$ cannot exceed $1$ and the ball must either be at one of the agent's positions or at the goal $G$. Formally, for all $j$, $t$,
\begin{equation} \begin{split} \sum_{i} A_{ijt} \leq & 1, \\ % only 1 agent per cell B_{jt} \leq & \sum_i A_{ijt} + B_{Gt}. \\ % ball can only exist at Goal or where there are agents \end{split} \end{equation}
First of all, you can't solve this using linear programming. You have to use integer programming.
Second, you can just use a configuration graph. The configuration graph has as vertex set all possible configurations (in your case, locations of the agent and the ball), and edges correspond to possible moves that can happen within one time step. Now you can use a shortest path algorithm (possibly using heuristic search) to find the shortest number of moves to get from your initial state to one of the goal states.
Yuval FilmusYuval Filmus
Not the answer you're looking for? Browse other questions tagged algorithms optimization shortest-path linear-programming modelling or ask your own question.
State-of-the-Art techniques on dynamic shortest path computations
Formalization of the shortest path algorithm to a linear program
Optimality in multi-agent multi-target path finding
Linear programming formulation for the single-source shortest path problem
Why does A* fail to find the fastest path when it reaches the goal?
Number of `m` length walks from a vertice with steps in [1, s]