


\subsection{Distance-based Optimization}

In this scenario, the policy optimization process is based on the total traveling distance of all the agents, i.e., the optimizer aims to minimize the traveling distance when optimizing the policies. We verify our optimizer with 2 cases: one without the simulation but the accumulated Euclidean distance by traversing all the items in the shopping list, while the other using live simulations to collect the actual translation data of the agent model traveling in the 3D environment.

The experiments are conducted as follows. To calculate the Euclidean distance without running the simulation, we generate a random shopping list with $i$ shopping items, then accumulate the path length from the entrance to the 1st item, then from the 1st item to the 2nd, etc., eventually from the $(i-1)$-th item to the $i$-th item. Similarly, for the simulation-based experiment, the path length is calculated by sampling the positions of the agents by each frame.

The results in Figure \ref{fig:unittest} show that the optimization approach we used can be applied to the traveling distance data collected via simulation. The shaded part of the optimization curve shows the range of traveling distance of all the children in the current generation. As is shown in the graph, starting from a directional policy (\ref{subfig:init_dist}), both experiments reduce the total travel distance as the optimization proceeds. Both experiments show similar convergence rates, the variance of the simulation experiment is larger and the convergence speed is slower. A possible reason causing such variance is the simulation artifacts. The traveling distance is calculated by accumulating the translation of the agents by each frame, which is influenced by the position sampling interval, locomotion, and animation system. A higher sampling rate can help record the data with higher accuracy.

\begin{figure}
  \centering
    \begin{subfigure}[h]{1.0\linewidth}
    \centering
        \begin{subfigure}[h]{0.5\linewidth}
            \centering
            \includegraphics[width=\linewidth]{images/simple/begin.png}
            \caption{Initial graph}
            \label{subfig:init_dist}
        \end{subfigure}
    \end{subfigure}
    
    \begin{subfigure}[h]{1.0\linewidth}
      \begin{subfigure}[h]{0.49\linewidth}
        \centering
        \includegraphics[width=\linewidth]{images/simple/curve_theory.png}
        \caption{Static convergence curve}
        \label{subfig:opt_proc_th}
      \end{subfigure}
      \hfill
      \begin{subfigure}[h]{0.49\linewidth}
            \centering
            \includegraphics[width=\linewidth]{images/simple/end_theory.png}
            \caption{Static optimized graph}
            \label{subfig:opt_dist_th}
      \end{subfigure}
    \end{subfigure}
    
    \begin{subfigure}[h]{1.0\linewidth}
        \begin{subfigure}[h]{0.49\linewidth}
            \centering
            \includegraphics[width=\linewidth]{images/simple/curve_sim.png}
            \caption{Simulated convergence curve}
            \label{subfig:opt_proc_sim}
        \end{subfigure}
        \hfill
        \begin{subfigure}[h]{0.49\linewidth}
            \centering
            \includegraphics[width=\linewidth]{images/simple/end_sim.png}
            \caption{Simulated optimized graph}
            \label{subfig:opt_dist_sim}
        \end{subfigure}
    \end{subfigure}    
    
    \caption{\ref{subfig:init_dist} shows the initial policy graph with uni-directional edges for the optimization, \ref{subfig:opt_dist_th} shows an optimal policy optimized for static distance (theoretical), \ref{subfig:opt_dist_sim} shows an optimal policy optimized for simulated distance, \ref{subfig:opt_proc_th} shows the objective convergence for \ref{subfig:opt_dist_th}, and \ref{subfig:opt_proc_sim} shows the objective convergence for \ref{subfig:opt_dist_sim}.}
    \label{fig:unittest}
\end{figure}

\subsection{Virtual Retail Environment}



We created a virtual grocery store that resembles a typical configuration of a grocery market with vertically aligned shelves and horizontal hallways. Based on a constant occupancy setting, we conducted a complete simulation-optimization experiment to search for the optimal policy for this scenario. The optimization starts with the graph that consists of no directional constraints, as is shown in Figure \ref{subfig:begin_graph}. This is considered as the baseline case for a store environment: normally, all customers can move in the store freely in any direction. Apparently, this policy can potentially cause jamming and blockage, leading to a high \ac{SDI} value.

During the simulation, the environment is initially empty, and the agents start entering and conduct their shopping behaviors by visiting each target item shown in their shopping lists. When the occupancy load is reached, no more agents are allowed to enter, until any agent in the scene finishes the checkout behavior and exits the scene. Figure \ref{fig:sim_vis} shows 3 typical states of one simulation session: agent entering, shopping, and exiting.

The experiment uses 1 edit distance to produce the children of every generation, and the size of each generation is 5. The window size $w$ is 20 and the stopping threshold is $10^{-5}$. We run the simulation for a simulated time of 30 seconds of each scenario to collect data for the \ac{SDI} model, then the optimizer decides the graphs to use for the next iteration using the returned result of SDI. The optimization process finished in 93 generations. As is shown in Figure \ref{subfig:exp_curve}, The results show that our optimization process reduced \ac{SDI} by about 20\%. Similar to \ref{subfig:opt_dist_th} and \ref{subfig:opt_proc_th}, the shaded area shows the range of the \ac{SDI} values of all the children in a generation.

\begin{figure*}[h!]
  \centering
  \begin{subfigure}[b]{0.55\linewidth}
      \begin{subfigure}[b]{0.44\linewidth}
        \centering
        \includegraphics[width=\linewidth]{images/exp1_begin.png}
        \caption{Beginning state of the graph}
        \label{subfig:begin_graph}
      \end{subfigure}
      \hfill
      \begin{subfigure}[b]{0.50\linewidth}
        \centering
        \includegraphics[width=\linewidth]{images/heat_begin.png}
        \caption{Initial heatmap (agent positions)}
        \label{subfig:begin_heat}
      \end{subfigure}
      
      \begin{subfigure}[b]{0.44\linewidth}
        \centering
        \includegraphics[width=\linewidth]{images/exp1_end.png}
        \caption{Optimized policy}
        \label{subfig:end_graph}
      \end{subfigure}
      \hfill
      \begin{subfigure}[b]{0.50\linewidth}
        \centering
        \includegraphics[width=\linewidth]{images/heat_end.png}
        \caption{Final heatmap (agent positions)}
        \label{subfig:end_heat}
      \end{subfigure}
  \end{subfigure}
  \hfill
  \begin{subfigure}[b]{0.4\linewidth}
    \centering
    \includegraphics[width=\linewidth]{images/exp1_curve.png}
    \caption{Optimization process}
    \label{subfig:exp_curve}
  \end{subfigure}
  \caption{The policy optimization example of a virtual retail store. \ac{SDI} is used as the optimization scoring metric. \ref{subfig:begin_graph} shows an initial policy graph, \ref{subfig:begin_heat} shows the starting heatmap of agent positions, \ref{subfig:end_graph} shows the optimized policy, \ref{subfig:end_heat} shows the ending heatmap of agent positions, and \ref{subfig:exp_curve} shows the objective convergence.}
  \label{fig:experiment_simple}
\end{figure*}

\begin{figure*}[h!]
  \begin{subfigure}[b]{0.33\linewidth}
    \centering
    \includegraphics[width=0.75\linewidth]{images/sim_1_start.png}
   
  \end{subfigure}
  \hfill
  \begin{subfigure}[b]{0.33\linewidth}
    \centering
    \includegraphics[width=0.75\linewidth]{images/sim_2_shopping.png}
   
  \end{subfigure}
  \hfill
  \begin{subfigure}[b]{0.33\linewidth}
    \centering
    \includegraphics[width=0.75\linewidth]{images/sim_3_exit.png}
   
  \end{subfigure}
  \caption{Simulation snapshots: (Left) In the beginning, agents are entering the facility, (Middle) During the simulation, agents are shopping the items following the policies, and (Right) At the end, agents are gradually finishing up the shopping and starting to queue up at the checkout counters.}
  \label{fig:sim_vis}
\end{figure*}


\subsection{Graph-based Representation of Crowd Management Policies}
\label{subsec:graph-based-representation}



We propose a graph representation of the directional policies enforced in the environment using a tuple of directed graphs $<g,h>$. The graphs are represented with nodes and directed edges. Each tuple of graphs contains (i) a \textit{structural} graph $g$ and (ii) a \textit{navigational} graph $h$.

\begin{table}
    \centering
    \small
    \begin{tabular}{c|c||c|c}
        \hline
        Symbol & Notation & Symbol & Notation\\
        \hline
        $h$ & Time factor & $m$ & Min distance\\
        $q$ & Max distance & $t$ & Time\\
        $O_{L}$ & Occupancy load & $e, e_{ij}$ & Edge\\
        \hline
        $g,g_c$ & Structural graph & $G,G_c$ & Set of $g,g_c$\\
        $h$ & Navigational graph & $H$ & Set of $h$\\
        $n,n_i$ & Node & $N,N_g,N_h$ & Set of $n,n_i$\\
        \hline
    \end{tabular}
    \caption{Symbols used in this paper.}
    \label{tab:term}
\end{table}

For each environment, a \textit{structural} graph is a static and abstract model that describes the high-level features of the environment, i.e., the directional policies enforced on the edges and the key nodes in the environment. Such key nodes in the structural graph represent significant locations in the environment, e.g., the entrance, the exit, or a joint location of paths. An edge in the graph is considered as an abstract relation between two nodes, i.e., a policy that allows the agent to pass from one node to the other, or forbids such motion. These policies enforce that traveling between any two nodes can only be either bi-directional, single-way, or blocked (disjoint).

\begin{figure}[htbp]
  \begin{subfigure}[b]{\linewidth}
    \centering
    \includegraphics[width=0.8\linewidth]{images/graphs.pdf}
   
    \label{subfig:navgraph}
  \end{subfigure}
  \par \medskip
  \begin{subfigure}[b]{\linewidth}
    \centering
    \includegraphics[width=0.75\linewidth]{images/SplitScreenAgents.JPG}
   
    \label{subfig:splitscreenagent}
  \end{subfigure}
  \caption{(Top) Example of nodes and edges for the structural and navigational graphs. There are $2$ structural nodes $A$ and $B$ with a directional edge from $A$ to $B$. Along this edge, there are $6$ navigational nodes ($AB_1,AB_2\ldots,AB_6$) and $16$ corresponding navigational edges connecting them. (Bottom) During simulation, the agents will follow the direction for pathfinding. The colored arrows represent the directional policies (e.g., $\textit{Green} \rightarrow \textit{Red}$).}
  \label{fig:graphs}
\end{figure}

Based on the structural graph, we dynamically generate a corresponding \textit{navigational} graph during runtime for the pathfinding of the agents.
Nodes in the navigational graph contain detailed navigation points of interest such as a specific shopping item. The navigational edges enumerate all possible paths between any two nodes in the structural graph so that when any agent traverses from one node to another, they can also approach a target shopping item without violating the policies. Figure \ref{fig:graphs} shows the relationship and difference between the structural and navigational graphs.

\subsection{Human Behavior Simulation} \label{subsec:hbs}

The human behavior simulation (also known as crowd simulation) uses a Unity-based framework, ADAPT~\cite{kapadia2014adapt}, to design and author meaningful animation, navigation, and agent behaviors in virtual environments. The framework consists of three layers: (i) a goal-directed locomotion and collision avoidance layer, (ii) a navigation layer for path planning, and (iii) a behavior tree layer for parameterized agent behaviors.

\subsubsection{Locomotion and collision avoidance.} This layer controls the steering capabilities of the agents in the virtual environment. It uses ORCA (Optimal Reciprocal Collision Avoidance)~\cite{van2011reciprocal} to find the optimal velocities for the agents using gradient descent. It communicates with the navigation layer for agents' path planning. Certain crowd steering configurations such as walking speed, stopping conditions, and maintaining social distances are also set in this layer.

\subsubsection{Path planning.} The planning layer uses Unity's AI system for pathfinding in the environment. To compute the path from any two nodes in the graph, our nagivational graph first breaks the path down into small trajectory snippets, then for each trajectory snippet, we provide its starting and ending position to Unity's navigation system to conduct the actual locomotion. The navigation graphs are meticulously designed that any trajectory snippet is small enough to prevent the agents from violating the policies.

\subsubsection{Behavior tree.} The behavior tree layer defines all the permissible actions that agents can perform during the simulation. These actions include walking, shopping, queuing, and entering/exiting the environment. The behavior tree layer is also responsible for scheduling and managing the sequence of behaviors that agents carry out during the simulation in an ordered fashion. Please refer to~\cite{shoulson2011parameterizing} for more details on the underlying implementation and authoring of behavior trees. \newline

In the simulation process, we first load the environment model. All the furniture items (e.g., item shelves and checkout counters) are then procedurally generated. Next, the agents are initialized at the entrances. Initially, there is no agent present in the environment. We gradually let the agents enter the facility at a varying rate until the capped maximum capacity of the environment is reached. Afterward, a new agent is spawned only when an existing agent leaves the environment after performing the assigned behaviors. When an agent is spawned in the environment, it is given a list of randomly generated shopping items. The agents' tasks are to shop all the items from the list by traversing the environment and obeying any enforced navigation policies. Once all the items are obtained, the agent queues up at the checkout counter to pay for the items, and exits the environment. In our experiments, we scaled up the simulation speed for higher runtime efficiency.

\subsection{Spatial Distancing Index} \label{subsec:sdi}

We present \ac{SDI} as a function of the occupancy load over time for the given environment. The \ac{SDI} considers the ability to maintain distances between the occupants, and for a given design (and its navigation policy), the ability to maintain distances at the various occupancy loads allowed in the environment space. For more details, see Section~\ref{sec:sdi}.

\subsection{Optimization}

Based on the graph representation of the policies, we devise a hybrid optimization process using the genetic algorithm (GA) and simulated annealing (SA) to approach the optimal policy with the best value of SDI or another arbitrary measuring metric. Details about the optimization framework and implementation of the algorithms are elaborated in Section \ref{optimization}.





\subsection{Optimization Formulation}

Given the structural policy graph $g$ and a specified occupancy load parameter $O_L$, the optimization problem is formulated as
\[\argmin_{e_{ij}\in G} L(g|O_L)\text{ s.t. } \forall v_{i},v_{j}\in g,v_{j}\in R_{G}(v_i)\]
where $e_{ij}$ is an edge connecting nodes $v_i$ and $v_j$ in the structural graph $g$, and $L(g|O_L)$ can be an arbitrary scoring metric that measures the performance of the graph, e.g., $L(g)\coloneqq \texttt{SDI}(G|O_L)$. $R_G(v_i)$ is the set of all the strongly connected components of $v_i$.

In other words, our optimization process minimizes the target function by changing the state of the edges, while maintaining the strong connectivity of the structural graph. As an NP-optimization (NPO) problem, this process is an NP-complete combinatorial optimization that requires probabilistic methods (e.g., simulated annealing) to approach the optimal.

\subsection{Optimization Approach}

Due to the NP complexity with regard to the number of nodes in the graph, we use a mixed approach by combining GA and SA to search for the optimal policy. Our GA-SA approach is based on a few definitions and assumptions.

\subsubsection{Edit Distance}

Given two isomorphic structural graphs $g_1$ and $g_2$, the edit distance $d(g_1,g_2)$ is defined as the total number of edge edits to make $g_1$ and $g_2$ identical. Formally,
$$d(g_1,g_2)=\sum_{e_{ij}\in g_1,e'_{ij}\in g_2}{d_e(e_{ij},e'_{ij})}.$$
Given two isomorphic edges, the edit distance value $d_e(e_{ij},e'_{ij})$ is defined by Figure \ref{fig:edit_dist}, which shows a total of 4 possible states of edges between nodes $n_1$ and $n_2$: (i) $n_1\rightarrow n_2$, (ii) $n_1\leftrightarrow n_2$, (iii) $n_1\quad n_2$, and (iv) $n_1\leftarrow n_2$. The solid lines mark 1 edit between states, while the broken lines mark 2 edits, e.g., the cost from state (i) to (ii) requires 1 edit, and that from state (i) to (iv) requires 2 edits.

\begin{figure}
  \centering
  \includegraphics[width=.6\linewidth]{images/edit_distance.pdf}
  \caption{Definition of the edit distance for a pair of isomorphic edges. Edges with shorter edit distance are considered as more similar.}
  \label{fig:edit_dist}
\end{figure}

\subsubsection{Similarity Monotonicity}

We assume that graphs with greater similarity yield closer \ac{SDI} values. Formally, given graphs $g,g_1,g_2$ and an arbitrary mapping function $f(g):g\rightarrow\mathbb{R}$, we have
$$d(g,g_1)\leq d(g,g_2)\Rightarrow|f(g)-f(g_1)|\leq|f(g)-f(g_2)|.$$
That said, given a graph $g$ and its corresponding score $s_g$, we will get larger score difference if we apply more edge edits on $g$. Note that we assume ``greater similarity'' is just sufficient to conclude ``smaller difference,'' so this assumption is not reversible: we don't assume that graphs are more similar \textit{due to} smaller \ac{SDI} difference.

\subsection{Algorithms}

Based on the formulation above, we propose this GA-SA method, described in the following algorithms. The pipeline of the optimization process is described in Algorithm \ref{alg:overview} and Figure \ref{fig:optim_pipe}, and detailed implementation of some functions are expanded in Algorithm \ref{alg:production}.

\begin{algorithm}
\small
  \SetKwInOut{Input}{input}
  \SetKwInOut{Output}{output}
  \SetAlgoNoEnd
  
  \Input{Structural graph $g_0$, Children count $n_c$, Edit distance $d$, Window size $w$, Optimization threshold $\hat{t}$, SA scalar $a$}
  
  $g\gets g_0$\tcp*[f]{Initial graph}\\
  $n\gets0$\tcp*[f]{Generation counter}\\
  $m_0\gets0$\tcp*[f]{Average SDI of most recent $w$ generations}\\
  $m_{-1}\gets0$\tcp*[f]{Average SDI of previous $w$ generations}\\
  $S\gets\emptyset$\tcp*[f]{Array of the final SDI of each generation}\\
  \While{$n<w$ \textbf{or} $n\geq w$ \textbf{and} $\frac{|m_0-m_{-1}|}{m_{-1}}>\hat{t}$}{
    $G\gets Produce(g,n_c,d)$\\
    \For{each $g'\in G$}{
      $h\gets Populate(g')$\tcp*[f]{A new navigational graph}\\
      Run simulation based on $h$\\
      Calculate \ac{SDI} of $g'$
    }
    \If{$Random(0,1)<a\exp(-\frac{1}{n})$}{
      $g\gets g'\in G$ with best \ac{SDI}\tcp*[f]{Conditional accepting}
    }
    $S\gets S\cup\{\text{ SDI of }g\}$\tcp*[f]{Save final SDI of generations}\\
    $n\gets n+1$\\
    \If{$n>w$}{
      $m_{-1}\gets m_0$\\
      $m_0\gets\frac{1}{w}\sum_{i=n-w}^{n}{s_i\in S}$\tcp*[f]{Average SDI}
    }
  }
\caption{Optimization iteration overview. We start with the initial graph $g_0$ and produce a generation of size $n_c$, then run the simulation with each child and get their corresponding \ac{SDI} values. We pick the best child as the parent for the next generation with a probability, and terminate the optimization process when the SDI value doesn't change significantly.}
\label{alg:overview}
\end{algorithm}

When starting the optimization process, we run the optimization process on the first $w$ generations of graphs. Starting from the $n$-th generation ($n\geq w+1$), we keep track of the mean value of the best \ac{SDI} scores of the recent $w$ generations and that of the $(n-1)$-th generation. When a generation is finished, we check if the value change is greater than a threshold and if so, the optimization process is considered ended.

As is shown in Figure \ref{fig:graphs}, the $Populate(\cdot)$ function processes the structural graph with the following steps:

\begin{enumerate}
  \item Inherit all the nodes in the structural graph to the navigational graph;
  \item Populate navigation nodes between the structural nodes with proper information, i.e., coordinates and item tags;
  \item Connect item nodes with joint nodes with edges complying to the policies defined in the corresponding structural graph.
\end{enumerate}

The navigational graphs are only used during the simulation and to calculate the scores of the graphs, and hence are discarded when the current iteration is over and will not be carried to the next generation.

The production function uses the GA method to generate new graphs in the next generation. In the $RandomizeState(\cdot)$ function, the state of the edge will mutate according to the transition relationship shown in Figure \ref{fig:edit_dist}. There are four states that the edges $e$ connecting nodes $n_1$ and $n_2$ can mutate to, and the edge must mutate to one of the rest 3 states where it is not currently in.

\begin{algorithm}
\small
  \SetKwInOut{Input}{input}
  \SetKwInOut{Output}{output}
  \SetAlgoNoEnd
  
  \Input{Base structural graph $g$, Sibling count $s$, Edit distance $d$}
  $n\gets 0$\\
  $G'\gets\emptyset$\\
  \While{$n\leq s$}{
    $n_e\gets0$\\
    $g'\gets\emptyset$\\
    \While{$n_e\leq d$}{
      Randomly pick one edge $e\in g$\\
      $e'\gets RandomizeState(e)$\tcp*[f]{Mutate edge}\\
      $n_e\gets n_e+d_e(e,e')$\\
      $g'\gets g'\cup\{e'\}$\\
    }
    \If{$g'\in G'$ \textbf{or} $g'$ is not strongly connected}{
      \textbf{continue}\\
    }
    $G'\gets G'\cup\{g'\}$\\
    $n\gets n+1$\\
  }
  \Return{$G'$}\\
    
\caption{Production function $Produce(\cdot)$. This function mutates the parent graph and generates all the children structural graphs for the next simulation sessions.}
\label{alg:production}
\end{algorithm}

When all the children from the current generation finish simulation and evaluation, all the SDI values are used by the optimizer to decide whether to accept the best-performed children as the parent for the next generation or reject it with a threshold and keep the original parent. The threshold decreases as the generation counter increase. This process uses the concept of conditional acceptance in the SA approach, as is shown in line 12--13 of algorithm \ref{alg:overview}, to prevent the algorithm from falling into a local optimum.



\section{Introduction} \label{sec:intro}
\input{sections/introduction}


\section{Related Work} \label{sec:related}
\input{sections/related_work}

\section{Overview and Preliminaries} \label{sec:overview}
\input{sections/methodology}

\section{Spatial Distancing Index} \label{sec:sdi}
\input{sections/sdi_metric}

\section{Optimization Framework} \label{optimization}
\input{sections/optimization}

\section{Evaluation and Case Study}\label{sec:eval}
\input{sections/evaluation}
\input{sections/experiments.tex}


\section{Conclusion}\label{sec:conclusion}
\input{sections/conclusion}


\begin{acks}
This research has been partially funded by grants from ISSUM, and in 
part by NSF awards: IIS-1703883, IIS-1955404, and IIS-1955365.
\end{acks}
\bibliographystyle{ACM-Reference-Format}
