# Modeling Pedestrian Motion in Crowded Scenes Based on the Shortest Path Principle
## 3 Model Learning
### Generalized Path Likelihood  
We combine the shortest path likelihood with the connectivity between trajectories to propose a generalized path likelihood. As above, we take the trajectory \(ab\) as an example. As shown in Figure 5b, we suppose that there is a possible connection between the trajectories \(ab\) and \(a^{\prime}b^{\prime}\), and trajectory \(ab\) is in front of trajectory \(a^{\prime}b^{\prime}\) in time. We connect trajectory \(ab\) with trajectory \(a^{\prime}b^{\prime}\) to construct a generalized trajectory \(\overline{ab^{\prime}}\). Since the trajectory \(\overline{ab^{\prime}}\) does not practically exist, we generate an approximate trajectory \(ab^{\prime}\) to represent the generalized trajectory \(\overline{ab^{\prime}}\) based on the shortest path principle. The trajectory \(ab^{\prime}\) is composed of  
Figure 5: (**a**) An example to explain the definition of shortest path likelihood. The yellow line is the trajectory \(ab\); the small circles represent the grids of the start point, end point, candidate origin and destination of the trajectory \(ab\). The dashed lines represent the shortest paths between two grids generated by the shortest path graph. The yellow dashed line is the ideal shortest path from origin \(g_{\circ}\) to destination \(g_{d}\). The blue dashed line, the green dashed line and the red dashed line combine into the feasible shortest path of trajectory \(ab\) from origin \(g_{\circ}\) to destination \(g_{d}\). (**b**) An example to explain the definition of generalized path likelihood. The yellow lines represent the trajectory \(ab\) and trajectory \(a^{\prime}b^{\prime}\); the green dashed line represents the approximate trajectory \(ab^{\prime}\) of the generalized trajectory \(\overline{ab^{\prime}}\). The representations of other symbols are the same as in (**a**). trajectory \(ab\), trajectory \(a^{\prime}b^{\prime}\) and the shortest path between the points \(b\) and \(a^{\prime}\). We defined the shortest path likelihood of the generalized trajectory \(\overline{ab^{\prime}}\) reaching the origin \(g_{o}\) and destination \(g_{d}\) as:  
\[L_{\overline{ab^{\prime}}}(g_{o},g_{d})=P_{\overline{ab^{\prime}}}\cdot L_{ab^{ \prime}}(g_{o},g_{d}). \tag{2}\]  
where,  
\[P_{\overline{ab^{\prime}}}=\frac{5(g_{o},g_{d})-5(g_{o},g_{d})}{S_{tr}(g_{d},g _{d})},\]  
\[L_{ab^{\prime}}(g_{o},g_{d})=\frac{S(g_{o},g_{d})-S(g_{o},g_{d})-S(g_{V},g_{d} )}{S(g_{o},g_{d})+S_{tr}(g_{d},g_{V})+S(g_{V},g_{d})},\]  
\[S_{tr}(g_{a},g_{b^{\prime}})=S_{tr}(g_{a},g_{b})+S(g_{b},g_{a^{\prime}})+S_{tr }(g_{a^{\prime}},g_{b^{\prime}}).\]  
Here, \(P_{\overline{ab^{\prime}}}\) represents the probability of the existence of generalized trajectory \(\overline{ab^{\prime}}\). \(S_{tr}(g_{a},g_{b^{\prime}})\) represents the length of a feasible shortest path of generalized trajectory \(\overline{ab^{\prime}}\), \(S(g_{o},g_{b^{\prime}})-S(g_{o},g_{a})\) represents the effective projection length of generalized trajectory \(\overline{ab^{\prime}}\) on the ideal shortest path from origin \(g_{o}\) to grid \(g_{b^{\prime}}\). We use the ratio between them to measure the probability of the existence of generalized trajectory \(\overline{ab^{\prime}}\). \(L_{ab^{\prime}}(g_{o},g_{d})\) is the shortest path likelihood of the trajectory \(ab^{\prime}\). Then, we replace the trajectory \(ab\) with the generalized trajectory \(\overline{ab^{\prime}}\) and connect the trajectory with another trajectory to construct a new generalized trajectory. We update the shortest path likelihood of the new generalized trajectory and then iterate the above process until the likelihood is no longer increased. We start with trajectory \(ab\), and use \(A^{*}\) algorithm to search the generalized trajectory, which has the maximum shortest path likelihood in all possible trajectory connections, and take the shortest path likelihood of this generalized trajectory as the generalized path likelihood of the trajectory \(ab\) reaching the origin \(g_{o}\) and destination \(g_{d}\).