text:
\section{Introduction} \label{sec:introduction}
The use of small Unmanned Aerial Vehicles (UAVs) has seen a tremendous increase in the past decade for both civilian applications \cite{Curry2004,Corrigan2007} viz., precision agriculture \cite{Tokekar2016, Shanahan2001}, forest fire monitoring and management \cite{Casbeer2005}, ocean bathymetry \cite{Ferreira2009} etc. and military applications \cite{Zajkowski2006} viz., monitoring, surveillance, border patrol, intelligence, and reconnaissance (see \cite{Manyam2019,Sundar2017} and references therein). The primary reason for this increase is attributed to the low fixed and operational costs, ease of use, payload capacity, and ability to fly low-altitude missions. There is extensive work in the literature \cite{Shima2009} that examines specific applications and develops algorithms ranging from higher level path planning to lower level control algorithms and the integration of the aforementioned applications. Higher level path planning algorithms are offline algorithms that are used to obtain paths for the vehicles a few hours prior to the start of the mission; in the optimization literature, this corresponds to vehicle routing problems (VRP) for UAVs. The lower level control algorithms are online algorithms that perform real-time trajectory adjustments and vehicle speed changes based on the environment at play. Most of the literature in small UAVs have had an application-specific focus because each application tends to impose its own unique set of constraints that need to be handled separately. One application of small UAVs that has received little attention in literature, in terms of higher level path planning, is that of patrolling \cite{Liu2019}.

\review{Patrolling applications are essentially data collection missions and despite the term patrolling having a military application connotation, similar application exists even in a civilian context like precision agriculture, crop health monitoring \cite{Tokekar2016}. Such missions are typically associated with uncertainty in the information collected from pre-specified targets. It also entails re-routing to visit additional nearby locations near the pre-specified targets to improve the fidelity of the information gathered. Hence, higher level planning algorithms that take into account this information uncertainty and plan vehicle routes are needed for such applications. There have been several attempts in the last few years to build platforms for operating small UAVs in data gathering missions pertaining to precision agriculture \cite{Tokekar2016}, mapping disaster recovery \cite{Adams2011}, etc. To make things concrete, consider the application of precision farming where the UAV visits a particular target to obtain images of the crops. Suppose the images indicate that the crops at that location are damaged or have an unusual pattern in leaf color, then the mission control would want the vehicle to inspect additional nearby locations to gather more information to come up with robust conclusions on the crop health. If nothing unusual is observed then the vehicle is expected to continue its mission.} In this article, we address the problem of higher level planning that can occur very frequently in almost all data gathering applications that is informally defined as follows: \\

\noindent \textit{Given a set of targets, a source, a destination, and a UAV, the objective is to find a path for the UAV that starts at the source, terminates at the destination, and visits each target exactly once, such that the following conditions are satisfied: if the information (uncertain) collected at a particular target is not sufficient, the UAV has to visit one \cite{rajan2019routing} or more supplemental targets corresponding to the visited target, before proceeding towards the next target in the path and the sum of the cost of the path and the expected additional travel cost to visit the supplemental targets is a minimum. } \\

We shall refer to the above problem as the single vehicle data gathering problem (SVDGP). The uncertainty in the SVDGP is associated with the information collected at a particular target. This uncertainty is modeled using a probability distribution and we do not make assumptions on the exact form of the distribution. Rather, we assume that the distribution permits sampling. This makes the problem setting very general and increases its applicability to a very large pool of civilian and military applications detailed in the previous paragraphs. We formulate the SVDGP as a two-stage decision making problem where the first stage (``here-and-now'') decisions are made before the mission under the face of uncertainty and the second stage, recourse decisions are made once the mission starts and uncertainty is revealed. \review{We set up the problem as a two-stage sequential decision making problem instead of a multi-stage Nevertheless for the following reasons: (i) the problem, as stated, has not been addressed previously in the literature, (ii) a solution algorithm to the two-stage version of the problem provides a reasonable indication of whether the algorithm can scale to a multi-stage version, i.e., if the two-stage version of the problem itself is intractable, then the multi-stage version of the problem is definitely not tractable, and finally (iii) a two-stage approximation combined with a rolling horizon algorithm \cite{Balasubramanian2004} could be an efficient way to solve the multi-stage version of the stochastic optimization problem.
Nevertheless, we note that the formulation and the algorithms presented in this paper can be extended to a multi-stage setting.}

\subsection{Related Work}
The literature contains many variants of UAV routing problems, and algorithms that can obtain optimal solutions and heuristics have been extensively studied for these variants. For ease of exposition, we will analyze the work done in the literature using the following two categories: (1) deterministic UAV routing approaches and (2) stochastic approaches.

As far as deterministic approaches are concerned, plenty of optimization models and algorithms to compute optimal solutions, and fast heuristics to compute good feasible solutions have received extensive attention over the past decade. As mentioned in the introduction, most of the literature concerning deterministic approaches have had an application-specific focus because each application tends to impose its own unique set of constraints that need to be handled separately. In most of the approaches, the concerned routing problems are modeled as variants of the single traveling salesman problem (TSP), multiple TSP, or Vehicle Routing Problems (VRPs) with additional constraints to model the specific mission at hand; for example see \cite{Sundar2013, Sundar2017JINT, Levy2014}. An interested reader is referred to \cite{Otto2018} for an extensive survey on optimization approaches for deterministic UAV routing problems. To the best of our knowledge, the only work in the literature that addresses the specific application of patrolling is that of \cite{Liu2019} where the authors propose an integer programming formulation to model the patrolling problem as a deterministic multiple TSP and present heuristics to solve the same.

\review{When compared to the deterministic approaches, literature that focuses on modeling uncertainty in the missions and developing algorithms to solve stochastic variants of the problems concerning UAVs are scarce and very recent. Nevertheless there exists a wide range of literature that deals with stochastic optimization problems in the context of the TSPs and VRPs. An interested reader is referred to \cite{Gendreau1996} for a review of all the variants. For the TSP, stochastic variants involving uncertainty in the targets themselves and uncertainty in travel times are the predominant ones that are dealt with in the literature \cite{Jaillet1988,Carraway1989}. As for the VRPs, stochasticity arising from uncertain demands \cite{Tillman1969,Dror1989}, capacities, customers \cite{Bertsimas1988}, travel times \cite{Dror1989,Jaillet1988a} and various combinations of those \cite{Jezequel1985} have been rigorously examined both from a modeling and algorithm development standpoint. In the context of problems concerning UAVs, two-stage stochastic programming formulations have been explored in single and multiple UAV delivery problems \cite{Shavarani2018,Torabbeigi2018,Venkatachalam2018,Liu2019Stochastic}. To the best of our knowledge, apart from our preliminary conference article that introduces a simpler variant of the SVDGP with only one supplemental location per target \cite{rajan2019routing}, there is no work in the literature that explores such formulations and algorithms in the context of data gathering missions with uncertainty in data collected at points of interest. In \cite{rajan2019routing}, we formulate the SVDGP with only one supplemental location per target to make the second stage optimization problem a linear program; this in turn enables a solution algorithm to compute the optimal two-stage solution using a Benders decomposition. In this paper, we explore a general and more practical setting where there are multiple supplemental locations per target that need to be visited to obtain high fidelity information on the target area under consideration. }

\review{In summary, the contributions of this article are as follows: we develop the first two-stage stochastic programming formulation for a UAV data-gathering mission where uncertainty arises in the actual data collected in the targets. The formulation, as presented in the subsequent sections, contains binary variables in both the first as well as the second stage and we present a progressive hedging algorithm \cite{Watson2011} to solve this problem. The motivation behind developing a progressive hedging algorithm to solve this two-stage problem formulation will be detailed in the later sections. Finally, extensive computational experiments that corroborate the effectiveness of these models against deterministic counterparts and effectiveness of the algorithm to compute an optimal solution for any instance of the problem, as opposed to solving an extensive form (EF) using sample average approximation (SAA), are presented. } The rest of the article is organized as follows: in Sec. \ref{sec:pr-statement}, we present the formal problem statement after introducing the necessary notations. In Sec. \ref{sec:formulation}, we formulate the SVDGP as a two-stage stochastic program and present an algorithm to solve the same in Sec. \ref{sec:solution}. Finally in Sec. \ref{sec:results}, we present the computational results followed by conclusions and future research directions in Sec. \ref{sec:conclusion}.

\section{Problem Statement} \label{sec:pr-statement}
Before we present the formal problem statement, we introduce some notations that will be used throughout the rest of the article. We are given a set of $n$ targets $\hat T = \{t_1, \dots, t_n\}$, a source $s$, and a destination $d$. For ease for exposition, we will assume that $s = d = t_0$ and remark that the formulations and algorithms can be extended easily to the case where they are distinct. We also let $T = \hat T \cup \{t_0\}$. As detailed in the previous section, the decision making process is two-staged. The first stage decision for the mission is to compute a path for the UAV that starts and ends at $t_0$ and visits each target in the set $\hat T$ and collects information. Also associated with each target $k \in T$ is a set of supplemental locations $S_k$ whose purpose is as follows: suppose the UAV visits the target $k$ and collects some information, then depending on the this information gathered, it may have to visit some additional set of locations (supplemental location set $S_k$) to either validate the collected information or to gather more information. The decision on whether the UAV needs to visit these supplemental targets are recourse decisions and are taken after the uncertainty is realized. For the purpose of this article, we assume $|S_k|$, the cardinality of $S_k$ for each $k=1, \dots, n$, is $m$, where $m \geqslant 2$ and $S_0 = \emptyset$. We shall, from here on, refer to the set $V = T \bigcup S_1 \bigcup \dots \bigcup S_n$ as the set of vertices. Given these notations, the SVDGP is formulated on a graph $G = (V, E)$ where $E$ denotes the edge set; we delegate the definition of the edge set $E$ to the Sec. \ref{sec:formulation}. We note that $G$ can be a directed or an undirected graph and the formulation and the algorithms presented in this article are applicable to both cases. To keep the exposition fairly general, we will assume that the graph is directed and that the cost of traveling between any pair of targets is asymmetric i.e., given $(i, j) \in V$, $c_{ij} \neq c_{ji}$. The cost of traversing an edge $(i, j) \in E$ can be anything ranging from distance to travel time. We also assume that this cost of traversal between any pair of vertices is known a-priori or can be pre-computed. Since the focus of the article is to develop a model to account for uncertainty in a systematic way, in the next section, we detail the uncertainty model associated with the information collected at each target.

\subsection{Uncertainty Modeling} \label{subsec:uncertainty}
The uncertainty in the problem arises from the fidelity of information collected at any target $i \in T$. Based on the information collected at target $i$, the UAV may or may not have to visit the supplemental locations in the set $S_i$ before proceeding to visit the next target in the route. Hence, we associate with each target $i \in T$, a Bernoulli random variable with probability $p_i$ which denotes the probability that the information collected at target $i$ is not of sufficient fidelity. For the target $t_0$, we assume that $p_i = 0$, where $i \in \{t_0\}$. For ease of exposition, we assume that the random variables corresponding to any pair of targets, is independent of each other. However, this can be relaxed or changed and the uncertainty can also be modeled using a Markov chain. The uncertainty in this information collected over all the targets is modeled as a binary scenario vector of size $|T|$ where the component corresponding to target $i \in T$ takes a value $1$ with a probability $p_i$. These realizations of uncertainty are captured in a countable set of scenarios $\Omega$, in which each element $\omega \in \Omega$ occurs with probability $p_{\omega}$. Each element $\omega \in \Omega$ is a $|T|$-dimensional binary vector where each element is $1$ with a probability $p_i$. We let $\omega_i$ denote the $i$\textsuperscript{th} component of $\omega$. \review{When $\omega_i = 1$, the data gathered from the target $i$ is not of sufficient fidelity and additional supplemental targets corresponding to the target $i$ have to be visited by the vehicle.} In this particular case, given that the probabilities $p_i$ and $p_j$ associated with any pair of targets $(i,j)$ are independent, the probability of occurrence of the scenario $\omega$ is given by
\begin{flalign}
p_{\omega} = \prod_{i=0}^{n} \left\{ \mathbf{1}(\omega_i=1)\cdot p_i + \mathbf{1}(\omega_i=0) \cdot (1-p_i)\right\} \label{eq:prob_omega}
\end{flalign}
where, the function $\mathbf{1}(\cdot)$ is the indicator function.

If we let $\mathcal F$ denote the set of all feasible first stage paths for the UAV, the first stage cost is the cost of the path and for any feasible path in $\mathcal F$, the second stage decision is a set of recourse decisions which is a set of routes through the supplemental targets based on the fidelity of information collected at the targets. The second stage decisions are scenario-dependent and the second stage cost is given by the expected additional cost of traversal for the UAV to visit the supplemental targets. The goal of the SVDGP is to find a path that minimizes the sum of the first and second stage travel costs.

\section{Mathematical Formulation} \label{sec:formulation}
We remark that when there is no uncertainty associated with the problem and when the information gathered at every target $i \in T$ is already of sufficient fidelity, then no supplemental targets need to be visited by the vehicle and the first stage problem reduces to a asymmetric TSP on the set $T$. For the SVDGP, if the information associated with a target $i \in T$ is not of sufficient fidelity, the UAV needs to visits the supplemental targets in the set $S_i$ before proceeding towards the next target. To formulate this problem as a two-stage stochastic program, we first define two edge sets $E^1$ and $E^2$ for the first and the second stages respectively. The edge set $E^1$ includes edges that are allowed for the vehicle in the first stage i.e., any edge between every pair of vertices in the set $T$. The second stage edge set $E^2$ includes the edges that the vehicle is allowed to traverse in the second stage i.e., apart from containing all the edges in the set $E^1$, it includes the edges from every target $i \in T$ to every supplemental target in the set $S_i$, from every supplemental target in the set $\cup_i S_i$ to every target in the set $T$ and for every $i \in T$, between any pair of supplemental targets in the set $S_i$. For any edge in the set $(i, j) \in E^1 \cup E^2$, $c_{ij}$ denotes the cost of traversal of that edge. Also, given a subset of vertices $\hat V$, we define $\delta^1_+(\hat V) = \{(i, j) \in E^1: j \notin \hat{V} \text{ and } i \in \hat V\}$ and $\delta^2_+(\hat V) = \{(i, j) \in E^2: j \notin \hat V \text{ and } i \in \hat V\}$ as the set of outgoing edges in the first and second stage edge set, respectively. Similarly, given $\hat V \subset V$, we let $\delta^1_-(\hat V) = \{(j, i) \in E^1: j \notin \hat V \text{ and } i \in \hat V\}$ and $\delta^2_-(\hat V) = \{(j, i) \in E^2: j \notin \hat V \text{ and } i \in \hat V\}$ as the set of incoming edge. Furthermore, when $\hat V = \{i\}$ i.e., a singleton, we simply write $\delta^1_+(i)$ instead of to $\delta^1_+(\{i\})$.  Finally, given two disjoint subsets of vertices $V_1, V_2 \subset V$, we define $\gamma(V_1 \rightarrow V_2) = \{(i, j) \in E^2: i \in V_1, j \in V_2\}$.

\subsection{Objective function} \label{subsec:obj}
Given the above notations, we introduce binary first stage decision variables $x_{ij}$ for each $(i,j) \in E^1$, denoting the presence of the edge $(i,j)$ in the first stage solution and another set of binary second stage decision variables $y_{ij}^{\omega}$ for each $(i, j) \in E^2$ denoting the presence of the edge $(i,j)$ in the second stage for the scenario $\omega \in \Omega$. We let $\bm x$ and $\bm y$ denote the vector of first and second stage decision variables, respectively. Finally, given a subset of edges $\hat E^1 \subset E^1$ and $\hat E^2 \subset E^2$, we let $x(\hat{E}^1)$ and $y^{\omega}(\hat{E}^2)$ denote the sums $\sum_{(i,j) \in \hat E^1} x_{ij}$ and $\sum_{(i,j) \in \hat E^2} y_{ij}^{\omega}$, respectively. Now, the objective for the two-stage stochastic programming formulation of the SVDGP is given by:

\begin{flalign}
\min~ C & \triangleq \sum_{(i, j) \in E^1} c_{ij} x_{ij} + \mathbb E_{\Omega} \left[ \beta(\bm x, \omega) \right] \label{eq:obj-full1} \\
& = \sum_{(i, j) \in E^1} c_{ij} x_{ij} + \sum_{\omega \in \Omega} p_{\omega} \beta(\bm x, \omega) \nonumber
\end{flalign}
Here, $\beta(\bm x, \omega)$ is the additional traversal cost required to visit the supplemental targets given a scenario $\omega \in \Omega$.

\subsection{First stage constraints} \label{subsec:first stage-constraints}
Since the first stage solution is a feasible tour through the set of targets in $T$, the constraints in this stage are the TSP constraints which are given below:
\begin{subequations}
\begin{flalign}
x(\delta^1_+(i)) = 1 &\quad \forall i \in T, \label{eq:outdegree-1} \\
x(\delta^1_-(i)) = 1 &\quad \forall i \in T, \label{eq:indegree-1} \\
x(\delta^1_+(S)) \geqslant 1 &\quad \forall S \subset T, ~ |S| \geqslant 2, \text{ and } \label{eq:sec-1} \\
x_{ij} \in \{0, 1\} &\quad \forall (i, j) \in E^1. \label{eq:binary-1}
\end{flalign}
\label{eq:first stage}
\end{subequations}
\noindent Here, Eqs. \eqref{eq:outdegree-1} and \eqref{eq:indegree-1} are the in-degree and out-degree constraints that enforce exactly one edge to enter and leave each target in the set $T$. Eq. \eqref{eq:sec-1} ensures that there are no sub-tours in the solution, and finally Eq. \eqref{eq:binary-1} enforces the binary restrictions on the decision variables $x_{ij}$.

\subsection{Second stage formulation} \label{subsec:second stage}
The second stage model for a fixed first stage solution $\bm x$ and the realization of uncertainty $\omega \in \Omega$ is as follows:
\begin{subequations}
\begin{flalign}
\beta(\bm x, \omega) = \min \quad \sum_{(i, j) \in E^2} c_{ij} y_{ij}^{\omega} - &\sum_{(i, j) \in E^1} c_{ij} y_{ij}^{\omega}  \label{eq:obj-2}  \\
\quad \text{ subject to:} \qquad \qquad \qquad & \notag \\
y^{\omega}(\delta^2_+(i)) = 1 &\quad \forall i \in T, \label{eq:indegree-2}\\
y^{\omega}(\delta^2_-(i)) = 1 &\quad \forall i \in T, \label{eq:outdegree-2} \\
y^{\omega}(\delta^2_+(j)) = \omega_i &\quad \forall j \in S_i, i \in T, \label{eq:indegree-supplemental-2}\\
y^{\omega}(\delta^2_-(j)) = \omega_i &\quad \forall j \in S_i, i \in T \label{eq:outdegree-supplemental-2}\\
y_{ij}^{\omega} = x_{ij}(1-\omega_i) &\quad \forall (i,j) \in E^1 \label{eq:on-off-1}\\
y^{\omega}(\gamma(S_i \rightarrow \{j\})) = x_{ij} \omega_i &\quad \forall i, j \in T, \label{eq:on-off-2} \\
y^{\omega}(\delta^2_+(S)) \geqslant 1 &\quad \forall S \subset V, ~ |S| \geqslant 2, S \cap T \neq \emptyset \text{ and } \label{eq:sec-2}\\
y_{ij}^{\omega} \in \{0, 1\} &\quad \forall (i, j) \in E^2 \label{eq:binary-2}.
\end{flalign}
\label{eq:second stage}
\end{subequations}
The objective in Eq. \eqref{eq:obj-2} minimizes the additional cost of visiting the supplemental targets if information collected at a particular target is not of sufficient fidelity. The first summation is the total cost of the route including the additional supplemental target visits and the second term is the cost of the edges that are present both in the first and the second stage solutions. The Eqs. \eqref{eq:indegree-2} and \eqref{eq:outdegree-2} are the in-degree and out-degree constraints for the targets in the set $T$. The Eqs. \eqref{eq:indegree-supplemental-2} and \eqref{eq:outdegree-supplemental-2} ensure that if the information collected at any target $i \in T$ is not of sufficient fidelity i.e., $\omega_i = 1$, then the supplemental targets in the set $S_i$ have to be visited by the vehicle. The Eq. \eqref{eq:on-off-1} ensures that if an edge $(i,j) \in E^1$ is traversed by the vehicle in the first stage and if $\omega_i = 0$, then this edge is necessarily used in the second stage by setting $y_{ij}^{\omega} = 1$ and if an edge $(i,j) \in E^1$ is not used by the vehicle in the first stage, then it is also not used in the second stage corresponding to scenario $\omega$. Eq. \eqref{eq:on-off-2} ensures that given a target $i\in T$ with $\omega_i = 1$ and given that $j \in T$ is the target that vehicle visits immediately after $i$ in the first stage solution, the vehicle has to collect additional information from all the supplemental targets in the set $S_i$ before visiting the next target $j$. Together, Eqs. \eqref{eq:on-off-1} and \eqref{eq:on-off-2} also ensure that the sequence in which the vehicle visits the targets in the first stage solution given by $\bm x$ remains unchanged in the second stage. The Eq. \eqref{eq:sec-2} eliminate sub-tours in the second stage solution and finally, the Eq. \eqref{eq:binary-2} impose binary restrictions on the decision variables $y_{ij}^{\omega}$.

\section{Solution Methodology} \label{sec:solution}
This section details the description of our approach to solve the two-stage mathematical formulation of the SVDGP presented in Sec. \ref{sec:formulation}. The formulation, as presented, contains binary decision variables both in the first and the second stages. We leverage the Progressive hedging (PH) algorithm proposed by Rockafellar and Wets \cite{Rockafellar1991} to solve the SVDGP; PH is also referred to as scenario decomposition in the literature \cite{Watson2011} since it decomposes stochastic programs by scenarios i.e., samples of the realization of the random variables in the problem. \review{The other predominantly used method for solving mixed-integer stochastic optimization problems is that of Stochastic Dual Dynamic Programming (SDDP) \cite{Shapiro2011}. This method relies on outer-approximating the recourse problems using linear constraints obtained from the dual values of linear relaxation of the recourse problems. For the SVDGP, we favour the PH algorithm over the SDDP since each recourse problems itself has exponential number of sub-tour elimination constraints that are added dynamically during the solve and obtaining dual values of the dynamically added constraints requires separate cut-management algorithm. PH is a well-known algorithm for solving multistage stochastic convex optimization problems \cite{Atakan2018}. In fact, PH possesses theoretical convergence guarantees when all decision variables in the convex multistage stochastic program are continuous, i.e., PH is guaranteed to converge to the global optimal solution of the multistage stochastic program when all but the here-and-now decision variable are continuous. In the presence of discrete variables, a wealth of recent theoretical and empirical research \cite{Fan2010,Listes2005,Lokketangen1996} has shown that the PH algorithm can prove to be a very robust heuristic to solve stochastic programs, specifically the case of pure binary programs in both stages of the formulation even in the case that the number of scenarios is prohibitively large. These algorithmic features of PH make its application ideal for the the SVDGP.} To that end, the subsequent sections detail the techniques involved in the PH approach and present findings that shows its impact as an effective heuristic to solve the SVDGP. In the forthcoming paragraphs, we present an overview of the PH algorithm specifically tailored for the SVDGP.

\subsection{Algorithm Overview} \label{subsec:ph}
Before, we present the overview of the algorithm, we restate the two-stage stochastic program for the SVDGP in a concise manner as follows:
\begin{subequations}
\begin{flalign}
\min \quad & \sum_{(i, j) \in E^1} c_{ij} x_{ij} + \sum_{\omega \in \Omega} p_{\omega} \beta(\bm x, \omega) \label{eq:obj-concise} \\
\text{subject to: } \quad & \bm x \in \mathcal Q \label{eq:constraint-set}
\end{flalign}
\label{eq:concise}
\end{subequations}
where, $\mathcal Q = \{ \bm x: \bm x \text{ satisfies Eq. \eqref{eq:first stage}} \}$. The concise formulation, as presented in Eq. \eqref{eq:concise}, is the well-known extensive form of the two-stage stochastic program  \cite{Wallace2005} in Sec. \ref{sec:formulation}. The PH is a scenario-decomposition algorithm that uses a separate set of first stage decision variables for each scenario to perform parallel solves i.e., for each $\omega \in \Omega$, it introduces decision variables $\bm x_{\omega}$ and implicitly enforces the non-anticipativity constraints ($\bm x = \bm x_{\omega} ~~\forall \omega \in \Omega$) via penalization; these constraints avoid allowing the first stage decision vector $\bm x$ to depend on the scenario. The basic PH algorithm takes as input two parameters (i) a penalty factor, $\rho > 0$ and (ii) a termination threshold, $\varepsilon$. Given $\rho$ and $\varepsilon$, the pseudo-code for the PH algorithm is as follows:

\begin{algorithm}
    \caption{Progressive Hedging: A pseudo-code}
    \label{algo:ph}{
    \onehalfspacing
    \begin{algorithmic}[1]
        \Statex \textbf{Initialization:}
        \State $k \gets 0$ \Comment{iteration count}
        \State \label{step:main0} For every $\omega \in \Omega$, $\bm x_{\omega}^k \gets \operatornamewithlimits{argmin}_{\bm x \in \mathcal Q} \sum_{(i, j) \in E^1} c_{ij} x_{ij} + \beta(\bm x, \omega)$
        \State $\bm x^k \gets \sum_{\omega \in \Omega} p_{\omega} \bm x_{\omega}^k$
        \State For every $\omega \in \Omega$, $\bm w_{\omega}^k \triangleq \rho \cdot (\bm x_{\omega}^k - \bm x^k)$ \Comment{initial weight vector computation $\bm w_{\omega}^k$}
        \Statex \textbf{Iteration update:}
        \State \label{step:goto} $k \gets k+1$
        \Statex \textbf{Decomposition:}
        \State \label{step:main} For every $\omega \in \Omega$, $$\bm x_{\omega}^k \gets \operatornamewithlimits{argmin}_{\bm x \in \mathcal Q} \left( \sum_{(i, j) \in E^1} c_{ij} x_{ij} + \langle\bm w_{\omega}^{k-1}, \bm x \rangle + \frac{\rho}2 \left\| \bm x - \bm x^{k-1} \right\|^2 + \beta(\bm x, \omega) \right)$$
        \Statex \textbf{Aggregation:}
        \State $\bm x^k \gets \sum_{\omega \in \Omega} p_{\omega} \bm x_{\omega}^k$
        \Statex \textbf{Weight update:}
        \State For every $\omega \in \Omega$, $\bm w_{\omega}^k \triangleq \bm w_{\omega}^{k-1} + \rho \cdot (\bm x_{\omega}^k - \bm x_{\omega})$
        \Statex \textbf{Termination criterion check:}
        \State $\epsilon^k \triangleq \sum_{\omega \in \Omega} p_{\omega} \left\| \bm x_{\omega}^k - \bm x^k \right\|$
        \If{$\epsilon^k > \varepsilon$}
            \State Go to Step \ref{step:goto}
        \Else
            \State Terminate with $\bm x^k$ as the first stage solution
        \EndIf
    \end{algorithmic}
    }
\end{algorithm}

In Step \ref{step:main} of Algorithm \ref{algo:ph}, the symbol $\langle a, b \rangle$ denotes the dot product of the vectors $a$ and $b$. Furthermore, we notice that the computations in Steps \ref{step:main0} and \ref{step:main} involve solving multiple mixed-integer linear programs, one for each scenario in the set $\Omega$ and that the solves are completely parallelizable. The quadratic penalty term (or the proximal term \cite{Watson2011}) penalizes the non-anticipativity constraints and ensures that it is satisfied as the algorithm terminates. \review{For every iteration $k$, the term $\epsilon^k$ is also referred to as the residual. The values of of $\varepsilon$ is a tolerance value and it can be set to any value that is desired depending on the level of accuracy that is required for PH algorithm. As for the value of $\rho$, the following procedure was used to set its value. This procedure is not new and has been previously used in the literature concerning PH algorithms in \cite{Watson2011}. It was observed in \cite{Watson2011} that values of $\rho \in (0, 1)$ is a good starting point to fix the value of $\rho$ and that $\rho$ values proportional to the first stage edge costs, i.e., $c_{ij}$ would lead to good convergence behaviour (without oscillations) of the PH algorithm. This technique of fixing a $\rho$ value proportional to the costs is referred to as ``cost proportional'' heuristic \cite{Watson2011}. For the SVDGP, we combined both the suggestions by first scaling all the costs between every pair of targets in the range $(0, 1)$ and then allowing the value of $\rho$ to be the average of all the scaled cost values. This technique worked well for all the computational experiments and hence, no further experiments were done to compute more effective values of $\rho$.}

\review{In general, there is no guarantee that the Progressive Hedging algorithm will converge to a binary first stage solution \cite{Rockafellar1991}. But, it has been observed that for a wide variety of problems it is observed to converge to a binary first stage solution \cite{Watson2011}. In all our computational experiments, we did not find a single instance for which the algorithm did not converge. Nevertheless, heuristics like variable-fixing, slamming, or rounding can be used to force convergence.} The following sections show the results obtained by adopting this approach to our two-stage formulation of the problem.

\section{Computational Results} \label{sec:results}
The PH algorithm for the SVDGP was implemented  using the C++ programming language, and CPLEX 12.8 was used as the underlying solver to solve the multiple MILPs that occur in each iteration of the PH algorithm. All the computational experiments were performed using an 2.9 GHz Intel Core i7 processor with 16 GB RAM. The performance of the algorithm was tested on randomly generated test instances. The instances generation procedure is detailed in the subsequent section.

\subsection{Instance Generation} \label{subsec:instance-generation}
All the targets, the supplemental locations, the source, and the destination were all generated on a $100 \times 100$ grid. The source and the destination vertices for all the instances were located at $(5, 5)$ and $(95, 95)$, respectively. The number of targets $n$ were varied from $10$ to $40$ in steps of $5$. For each target, the locations of its corresponding supplemental targets were also randomly generated within a maximum pre-specified radius, $R$, from the target location; the value of $R$ was chosen from the set $\{5, 10\}$ units. The number of supplemental locations per target, $m$ was chosen from the set $\{3, 5, 7, 9\}$. Now, as for the vehicle itself, we assume that the vehicle is a fixed-wing UAV with a minimum turn-radius of $5$ units. For this fixed-wing UAV, the cost of traversal between any pair of targets is assumed to be the shortest path taken by the vehicle to go from one target to the other. This path length is in-turn a function of the heading angle of the UAV at each target. To that end, we generate random heading angles for every target and its corresponding supplemental location and then compute the length using the well-known result by Dubins \cite{Dubins1957}. We remark that the shortest path computed using the result in \cite{Dubins1957} is asymmetric. Given this instance generation procedure, the total number of instances was $56$ and all computational experiments were performed on this set of $56$ instances. A subset of these instances are used for each of the computational experiments and the subset of chosen instances for each experiment is presented in the respective sections.

\subsection{PH Algorithm Parameters and Scenario Generation} \label{subsec:scenario-generation}
The PH algorithm has two main input parameters, $\rho$ and $\epsilon$. The value of $\epsilon$ is set to $1 \times 10^{-5}$ and the value of $\rho$ for each instance was computed using the heuristic detailed in Sec. \ref{subsec:ph}. We note that for majority of the instances the value of $\rho$ computed using the heuristic was close to $0.5$. The uncertain scenarios for each run of the problem are generated using a vector of Bernoulli random variable, one for each target. Across a majority of the experiments in the subsequent sections, the probability that the information collected at a particular target is of sufficient fidelity is assumed to be $0.5$ for every target. For a few other computation experiments other probability values are used and these values are presented when the corresponding experiment is described. For the source and the destination, we set this probability to $0$ and required number of scenarios are generated from this vector of Bernoulli random variables. The number of scenarios was varied from a minimum value of $10$ to a maximum value of $200$ across all experiments. Each randomly generated scenario, $\omega$ is a binary vector indicating if the information collected at a particular target is of sufficient fidelity or not. In the subsequent paragraphs, we present the results for the various computational experiments perform to evaluate the PH algorithm on the SVDGP. Before we present the results obtained using the PH algorithm, we remark that when the full two-stage stochastic formulation in Sec. \ref{sec:formulation} was provided to CPLEX with a time-limit of three hours, all problem instances with number of targets greater than $50$ and number of scenarios greater than $20$ timed-out. Hence, we do not present any results that show that CPLEX was not able to solve the full problem as stated in Sec. \ref{sec:formulation}.

\review{\paragraph{Performance of PH algorithm} In this section, we compare the performance of the PH algorithm against solving the full two-stage problem in its extensive form using CPLEX. For this study,  we choose only the 10 target instances. The values of $m$ and $R$ are varied in the set $m \in \{3, 5, 7, 9\}$ and $R \in \{5, 10\}$. Also, the number of scenarios, $|\Omega|$ was varied in the set $\{50, 100, 200\}$ and the probabilities to generate these scenarios were chosen in the set $\{0.2, 0.5, 0.8\}$. In total, the number of test instances for this study was $720$. CPLEX was used to solve the extensive form of the two-stage problem with a computation time limit of $7200$ seconds. The Table \ref{tab:phvscplex} shows the number of instances where solving the extensive form failed to result in an optimal solution for the instance compared to solving the problem using the PH algorithm.  As seen from Table \ref{tab:phvscplex}, it is clear that solving the extensive form using CPLEX is very inefficient since many instances with just $10$ targets were not solved to optimality. On the other hand, the PH algorithm is capable of solving all instances to optimality. This justifies the need for the proposed decomposition algorithm for the SVDGP. For all the instances that were solved to optimality by both the solution methods, the difference in solution quality between the two methods was found to be $0\%$. This result provides an empirical proof that despite the PH algorithm being an heuristic approach, it is capable of producing the globally optimal solution for the two-stage problem. Finally, for all the runs where both the approaches provided the optimal solution, the PH algorithm was on an average $2.5$ times faster than solving the extensive form using CPLEX. Furthermore, out of the $720$ instances, $48\%$ of the instances had PH algorithm converging to the optimal solution in more than $1$ iteration.}

\begin{table}[htbp]
    \centering{
    \onehalfspacing
    \begin{tabular}{cccc}
        \toprule
        \multirow{2}{*}{$|\Omega|$} & \multirow{2}{*}{total \# instances} & \multicolumn{2}{c}{\# timed out instances} \\
        \cmidrule{3-4}
        & & extensive form & PH algorithm \\
        \midrule
        50 & 240 & 21 & 0\\
        100 & 240 & 18 & 0\\
        200 & 240 & 42 & 0\\
        \bottomrule
    \end{tabular}
    \caption{Number of instances where providing the extensive form directly to CPLEX timed out as against applying the PH algorithm to solve the two-stage problem.}
    \label{tab:phvscplex}
    }
\end{table}

\review{\paragraph{Comparison with deterministic equivalent} This set of results is focused on comparing the solution of the two-stage stochastic program provided by the PH algorithm against its the Expected Value Problem (EVP) \cite{Birge2011}. The expected value problem is solved directly using CPLEX and the value of stochastic solution or VSS is the difference between the objective value of the full two-stage stochastic program and its expected value problem. It is known that this VSS is non-negative \cite{Birge2011} and greater its value the greater the value in solving the stochastic version as opposed to the expected value problem. To this end, we fix the value of $m$ and $R$ to be $5$ units and vary the probability of generating scenarios within the set $\{0.2, 0.5, 0.8\}$. The number of generated scenarios is fixed to $100$ for all the runs. The Fig. \ref{fig:vss} show the value of stochastic solution as a relative percentage with respect to the objective value of the EVP. As observed from the Fig. \ref{fig:vss}, there is a substantial quantitative value in solving the two-stage stochastic problem as against an EVP when the value of the probabilities used for generating the scenarios are greater than $0.5$. }

\begin{figure}
    \centering
    \includegraphics[scale=0.5]{results/vss-crop.pdf}
    \caption{Value of Stochastic Solution (in percentage).}
    \label{fig:vss}
\end{figure}

\paragraph{Effect of increasing the number of scenarios} Here, we present the first set of results to demonstrate the scalability of the PH algorithm for the SVDGP with increasing number of scenarios. To that end, for this experiment, the instances with value of $n \in \{10, 15, 20, 25, 30, 35, 40\}$, $m = 5$, $R = 5$ are chosen. For each of these instances, the number of scenarios are varied in the set $|\Omega| \in \{10, 25, 50, 100, 200\}$. The results for this set of experiments is shown in Tables \ref{tab:scen-scal} and \ref{tab:scen-scal-iter}. It is observed from the tables that the PH algorithm is effectively able to solve all the instances with up to $100$ scenarios within two hours of computation time.

\begin{table}[htbp]
    \centering
    {\onehalfspacing
    \begin{tabular}{cccccccc}
        \toprule
         $|\Omega|$ & $n = 10$ & $n = 15$ & $n = 20$ & $n = 25$ & $n = 30$ & $n=35$ & $n = 40$ \\
         \midrule
         \csvreader[no head,late after line=\\]{results/scenario-scalability.csv}{1=\m,2=\one,3=\two,4=\three,5=\four,6=\five,7=\six,8=\seven}{\m & \one & \two & \three & \four & \five & \six & \seven}
         \bottomrule
    \end{tabular}
    \caption{Computation time (in seconds) taken by the PH algorithm for increasing number of targets and number of scenarios.}
    \label{tab:scen-scal}
    }
\end{table}

\begin{table}[htbp]
    \centering
    {\onehalfspacing
    \begin{tabular}{cccccccc}
        \toprule
         $|\Omega|$ & $n = 10$ & $n = 15$ & $n = 20$ & $n = 25$ & $n = 30$ & $n=35$ & $n = 40$ \\
         \midrule
         \csvreader[no head,late after line=\\]{results/scenario-scalability-iterations.csv}{1=\m,2=\one,3=\two,4=\three,5=\four,6=\five,7=\six,8=\seven}{\m & \one & \two & \three & \four & \five & \six & \seven}
         \bottomrule
    \end{tabular}
    \caption{Number of iterations taken to obtain convergence of the PH algorithm for increasing number of targets and number of scenarios.}
    \label{tab:scen-scal-iter}
    }
\end{table}

\begin{figure}[ht!]
\begin{subfigure}{\textwidth}
  \centering

  \includegraphics[scale=0.6]{results/illustration_1-crop.pdf}
  \caption{First stage solution for a $10$-target instance.}
  \label{fig:sub-first}
\end{subfigure}\\
\begin{subfigure}{\textwidth}
  \centering

  \includegraphics[scale=0.6]{results/illustration_2-crop.pdf}
  \caption{The solution to the two-stage problem for one particular realization of the uncertainty. The black lines are the path that is same as the first stage solution and the orange routes correspond to the additional visits to the supplemental locations corresponding to the targets where the fidelity of information collected was not sufficient. }
  \label{fig:sub-second}
\end{subfigure}
\caption{The solution provided by the PH algorithm for a $10$-target instance. }
\label{fig:illustration}
\end{figure}

The Fig. \ref{fig:residual} shows the feasible first stage (Fig. \ref{fig:sub-first}) and a second stage  solution (Fig. \ref{fig:sub-second}) for one particular realization of the random variable for a $10$-target instance. Notice that the paths taken by the vehicle are not straight lines because we assume that the vehicle is a fixed-wing aircraft with a minimum turn-radius of $5$ units and follows the Dubins path \cite{Dubins1957}.

\paragraph{Effect of increasing the number of supplemental locations per target} The second set of results are aimed at demonstrating the scalability of the algorithm with increasing number of supplemental locations per target. To that end, for this experiment, the instances with value of $n \in \{10, 15, 20, 25, 30, 35, 40\}$, $m = \{3, 5, 7, 9\}$, $R = 5$, and $|\Omega| = 100$ (generated using a probability of $0.5$) are chosen and the results are reported in Tables \ref{tab:run-times2} and \ref{tab:iterations2}. Though the expectation is for the computation time and the number of iterations to increase with increasing value of $m$, it is not really the case for this problem, as observed from Tables \ref{tab:run-times2} and \ref{tab:iterations2}. Furthermore, we also observe that for the $40$-target instances, the computation time is much greater than two hours. \review{For typical patrolling applications, the number of target locations will be around 100 targets. For such patrolling missions, the use of multiple UAVs is preferred. In this case, a simple clustering heuristic can be used to partition the targets into manageable cluster sizes and the algorithm can be used to compute a single vehicle solution for each cluster. This addresses the scalability aspect of the algorithm. Also, since the algorithm is offline, it is typically run a few hours before the start of the mission to obtain the plans. Hence, this justifies the computation time being in the order of hours even for instances with around $40$ targets. }

\begin{table}[htbp]
    \centering
    {\onehalfspacing
    \begin{tabular}{cccccccc}
        \toprule
         $m$ & $n = 10$ & $n = 15$ & $n = 20$ & $n = 25$ & $n = 30$ & $n=35$ & $n = 40$ \\
         \midrule
         \csvreader[no head,late after line=\\]{results/run-times.csv}{1=\m,2=\one,3=\two,4=\three,5=\four,6=\five,7=\six,8=\seven}{\m & \one & \two & \three & \four & \five & \six & \seven}
         \bottomrule
    \end{tabular}
    \caption{Computation time (in seconds) taken by the PH algorithm for increasing number of targets and number of supplemental locations per target.}
    \label{tab:run-times2}
    }
\end{table}

\begin{table}[htbp]
    \centering
    {\onehalfspacing
    \begin{tabular}{cccccccc}
        \toprule
         $m$ & $n = 10$ & $n = 15$ & $n = 20$ & $n = 25$ & $n = 30$ & $n=35$ & $n = 40$ \\
         \midrule
         \csvreader[no head,late after line=\\]{results/iterations.csv}{1=\m,2=\one,3=\two,4=\three,5=\four,6=\five,7=\six,8=\seven}{\m & \one & \two & \three & \four & \five & \six & \seven}
         \bottomrule
    \end{tabular}
    \caption{Number of iterations taken to obtain convergence of the PH algorithm for increasing number of targets and number of supplemental locations per target.}
    \label{tab:iterations2}
    }
\end{table}

\paragraph{Effect of increasing the pre-specifed radius for the supplemental locations} This set of results presents the variation in the computation time and the number of iterations for the PH algorithm to converge when the pre-specified radius in which the supplemental locations are present is varied in the set $\{5, 10\}$. The results present the change in computation time and number of iterations for $n = \{10, 15, 20, 25, 30, 35, 40\}$ and when $m = 5$, $|\Omega| = 100$ (generated using a probability of $0.5$). The Tables \ref{tab:run-times-R} and \ref{tab:iterations-R} present the computation times and the number of iterations for the above instances, respectively. Again, no clear trend exists between the value of $R$ and the computation time or the number of iterations taken for the PH algorithm to converge; nevertheless, the trivial trend that can be observed from the two tables is that greater the number of iterations the greater the computation time.

\begin{table}[htbp]
    \centering
    {\onehalfspacing
    \begin{tabular}{cccccccc}
        \toprule
         $R$ & $n = 10$ & $n = 15$ & $n = 20$ & $n = 25$ & $n = 30$ & $n=35$ & $n = 40$ \\
         \midrule
         \csvreader[no head,late after line=\\]{results/run-times-R.csv}{1=\m,2=\one,3=\two,4=\three,5=\four,6=\five,7=\six,8=\seven}{\m & \one & \two & \three & \four & \five & \six & \seven}
         \bottomrule
    \end{tabular}
    \caption{Computation time (in seconds) taken by the PH algorithm for values of $R$.}
    \label{tab:run-times-R}
    }
\end{table}

\begin{table}[htbp]
    \centering
    {\onehalfspacing
    \begin{tabular}{cccccccc}
        \toprule
         $R$ & $n = 10$ & $n = 15$ & $n = 20$ & $n = 25$ & $n = 30$ & $n=35$ & $n = 40$ \\
         \midrule
         \csvreader[no head,late after line=\\]{results/iterations-R.csv}{1=\m,2=\one,3=\two,4=\three,5=\four,6=\five,7=\six,8=\seven}{\m & \one & \two & \three & \four & \five & \six & \seven}
         \bottomrule
    \end{tabular}
    \caption{Number of iterations taken by the PH algorithm for varying values of $R$.}
    \label{tab:iterations-R}
    }
\end{table}

\paragraph{Effect of changing the probabilities in the scenario generation} This set of results is aimed at examining the effect of changing the probabilities that the information collected at any target is not of sufficient fidelity. We choose a specific instance with $n = 20$, $m = 5$, and $R=5$ units. There is no specific reason for this choice and the results for all the other instances followed the same trend.  To that end, the probabilities that we choose to generate $100$ scenarios for this particular instance is given by $\{0.0, 0.2, 0.5, 0.8, 1.0\}$. We remark that when the probability is $0.0$, it basically means that the information collected at all the targets is of sufficient fidelity and this reduces the SVDGP to computing a traveling salesman tour through the set of targets. On the other hand, if all the probabilities take a value $1.0$, then the information collected at every target is not of sufficient fidelity and the SVDGP reduces to a TSP the set of targets and their supplemental locations with additional sequencing constraints i.e., the supplemental locations have to be visited immediately after their respective target visits. The Table \ref{tab:run-time-prob} presents both the computation time and the number of iterations for this experiment. The computation time for the case when the probability value is $0.0$ is the least as solving a TSP with $20$ targets is substantially fast. On the other end of the spectrum, the computation time for case with a probability value of $1.0$ is the maximum as it reduces to the problem of solving a TSP with $120$ vertices and additional sequencing constraints. Also, for these two cases, the recourse action is obtained directly by solving the TSP or the TSP with additional sequencing constraints and hence, the number of iterations for the PH algorithm to converge for these two cases will always be equal to one.

\begin{table}[htbp]
    \centering
    {\onehalfspacing
    \begin{tabular}{ccc}
        \toprule
         $p$ & time (seconds) & \# iter \\
         \midrule
         \csvreader[no head,late after line=\\]{results/prob-run-times.csv}{1=\p,2=\t,3=\i}{\p & \t & \i}
         \bottomrule
    \end{tabular}
    \caption{Computation time and number of iterations for different values of probabilities. Here $p$ represents the probability that the information collected at the target is not of sufficient fidelity for any target, and \# iter is the number of iterations taken by the PH algorithm to converge.}
    \label{tab:run-time-prob}
    }
\end{table}

\paragraph{PH algorithm residual statistics} This set of results shows the changes in the residual of the PH algorithm (i.e., $\epsilon^k$ in Algorithm \ref{algo:ph})  for varying number of scenarios. We remark that this residual function is not a strictly decreasing function. For this experiment, the instance with $n=40$, $m=5$, and $R=5$ was chosen. As far as the scenarios are concerned, all of them were created using a probability value of $0.5$. The Fig. \ref{fig:residual} shows the residual values for varying number of scenarios. All the results presented thus far illustrate the effectiveness of the PH algorithm in computing heuristic solutions to the SVDGP with uncertainty in the fidelity of information collected.

\begin{figure}[H]
    \centering
    \includegraphics[scale=0.8]{results/residual.pdf}
    \caption{Residual value progress for the PH algorithm. The value of $(n, m, R)$ for the instance for this set of runs is given by $(40, 5, 5)$, respectively.}
    \label{fig:residual}
\end{figure}

\section{Conclusion} \label{sec:conclusion}
\review{This article presents the first formulation and solution approach for a UAV path planning problem in the context of data gathering missions.  This problem can be extended to a multi-stage setting using the same framework. This is the first attempt to solve such a sequential stochastic programming problem in this context and there is scope to work on this further to develop and refine distributed computing algorithms to solve it for a multi-stage setting while reducing the computational times. Furthermore, extension of this problem to a multi-vehicle setting entails addressing an additional complexity of partitioning the targets. This partitioning problem can be solved heuristically using clustering algorithms or one can resort to exact resolution of the partitions by embedding constraints in to the model itself; this presents an interesting avenue for future work.}

\section*{Acknowledgements}
Kaarthik Sundar would like to acknowledge the funding provided by  LANL's  Directed  Research  and  Development  (LDRD)  project: ``20200603ECR: Distributed Algorithms for Large-Scale Ordinary Differential/Partial Differential Equation (ODE/PDE) Constrained Optimization Problems on Graphs''. This work was carried out under the U.S. DOE Contract No. DE-AC52-06NA25396.

\Urlmuskip=0mu plus 1mu\relax
\bibliographystyle{elsarticle-num-names}

redpajama_set_name: RedPajamaArXiv


text:
Craft fair fun – trying to beat a frontal storm system (and failing)
We exhibited at UT Arlington yesterday. The fair was supposed to finish at 9pm. All afternoon we had been monitoring the progress of frontal rain and thunderstorms, moving South East slowly from the North and West. As the front moved South East, it was sucking in Gulf Air, a classical meteorological feature of the mid-West which in the Spring and Summer leads to unpleasant events like tornadoes. This time, we saw a steadily deepening line of red on the weather radar. I went for a drive to pick up some lighting bits and pieces at 7pm and saw lightning to the North and West, and an outflow cloud formation ahead of the storm moving slowly South over us. It was only a matter of time before the storm hit us, the main question being, would we make it to 9pm?
The decision was made for us at 7.45pm when the organizers declared an early close. We immediately began to tear down. Unlike many exhibitors, who have a modular rig with a smaller number of exhibits, our set up is more labor intensive, and we bring a lot more stock to an event. It takes us at least 1 hour to break down the whole rig. I wish we could go it quicker, we will look at that this Winter.
We set to work as fast as possible packing up. By 8.35 pm it was starting to rain, and we had a great light show above us. We left the E-Z Up fully configured and broke the displays down and put everything away. By this time, it was raining hard with gusty winds starting to pick up all around us. Normally, in a row of exhibitor tents, there is mutual wind protection, but once enough tents are broken down, that protection diminishes. More of that in a minute.
I set off to get the first car. When I arrived back at the exhibition area, Mary was trying to break down the tent, but then a gust of wind started to move it. We have 200 pounds of custom weights that we use to secure the corners of the tent, but once those are removed as the first part of the break-down, the tent is vulnerable to wind gusts. It took 4 people to hold it down and prevent it from going walkabout, while we loaded the car with the tables, exhibits, chairs and other paraphernalia. Then I moved the first car out of the way and set off to bring up the second car. By the time I got back to our pitch with the second car, it was bucketing down. We loaded remaining clutter into the second car, then, after I consulted the radar and determined that there was no let-up in the rain, we set (I think) a new record for collapsing an E-Z Up and loading it into a car trunk. It's amazing how fast you can move when you are being rained on. By this time it was really raining hard (the red zone on the radar had hit us), so we set off out of the AT Arlington campus, driving carefully along suddenly-sodden roads. In Texas, a lot of people either fail to slow down or tiptoe along the road as if expecting imminent doom, we saw both behavioral pathologies on the way home.
We made it home, still wet. The cars are being unpacked on Sunday morning, with some stuff being put away for the Winter. Back to cyber-sales…
Previous PostPrevious The Fall craft fair season is over…
Next PostNext Last Glass Class for 2013!

redpajama_set_name: RedPajamaCommonCrawl


text:
Interesting in Joining? SIGN UP
Become a Comic Access Comedian
Ashley Gavin
Ashley Gavin is a New York based, nationally touring comedian. Her comedy has been featured on Hulu, FOX, AXS TV, SiriusXM Comedy, Refinery29, Elite Daily, and The Kicker. Ashley has headlined at colleges and clubs around the country, including her recent breakout (sold-out) performance at Carolines. Ashley has taken part in some of the most prestigious festivals and showcases including NBC's Stand Up For Diversity - New York. Her webseries Gay Girl Straight Girl has over 400k views and has been featured in Galore Mag.
Ashley is best known for her hard-hitting, intelligent, and sometimes absurd social commentary, particularly about her experiences as a gay woman and feminist. Email and ask her about her scripted and unscripted pilots or her movie treatments.
Fox, AXS TV, Sirius XM Radio, NBC's Stand Up for Diversity
VIDEOS / CLIPS
Stand Up Set
per show
Need Help Booking? Click here or chat with us below!
Similar Comedians
Nore Davis
NORE, the young refreshing face of comedy, delivers an energetic performance filled with witty quips and sharp punch lines, combined with an amazing stage presence. Edgy and clean, NORE tells it like it is, speaking to audiences everywhere. NORE is a
Matt Pavich
Matt Pavich is a comedian and actor from New York City. He is a cast member on MTV2's "Joking Off", Elite Daily's "Genwhy" series, and is the cofounder of the YouTube channel, "Handsome Dancer". He also
Lenny Marcus
Lenny Marcus (www.LennyMarcus.com) has been a stand-up comedian performing at all the major comedy clubs in New York City for over twenty years. He has appeared on The Late Show with David Letterman three times to amazing reviews. He has also
Christian Finnegan
Christian Finnegan is a stand up comedian. He appears frequently on the television and also writes things, for both money and for kicks. Christian can currently be seen on the TBS sitcom "Are We There Yet?" but is perhaps best known as one of
Need Help Booking?
BOOK Ashley Gavin
If you are unsure or flexible, just give us an approximate date and time!
Give us a some brief info about your event - audience, occasion, location, or anything else you think we should know!
Book a Comic
Info for comedians
Copyright Comic Access 2019 All Rights Reserved


text:
The Smallest Radar Ever Sent to Space Will Probe the Interior of Dimorphos After its Impact From DART
Are miniature probes the future of deep space exploration? (more…)
A Year After a Failed Launch, Firefly Reaches Orbit and Deploys Satellites
Edited on 10/6/22 to add new information from Seradata. Commercial space company Firefly Aerospace successfully launched its Alpha rocket for…
Gravitational Lensing
A Mission to Reach the Solar Gravitational Lens in 30 Years
NASA's Institute for Advanced Concepts is famous for supporting outlandish ideas in the astronomy and space exploration fields. Since being…
Finally, a Practical use for Space-Based Power Beaming. Sending Power to Satellites in Shade
Power beaming is one of those technologies that can completely change the world. Almost unlimited power wherever it is needed,…
Company Tests Iodine Thruster in Space for the First Time
Ion thrusters have played second fiddle to chemical rockets for most of the history of space exploration. Part of that…
Artemis 1 is Launching in February
It's been a long time coming, but NASA's next moon rocket is just months from liftoff on its first uncrewed…
IBM Space Tech Wants to "Democratize Space" with ENDURANCE.
IBM Space Tech is launching Endurance, CubeSat mission that children from all over the world will be able to use…
NASA has Chosen 4 new Pioneer Missions: Aspera, Pandora, StarBurst, and PEUO
Budget constraints are a major consideration for every space program throughout the world. Lately, NASA has taken a particularly bold…
Virgin Orbit Successfully Launches a Batch of Satellites From an Airplane
Virgin Orbit has successfully tested its new air-launch system (LauncherOne) that will deliver small satellites to orbit in the near…
Tiny Cubesat Detects an Exoplanet
A team of MIT researchers have observed a Super-Earth using a CubeSat, making it the smallest satellite to study an…


Shreveport, La. – Shreveport-based Music Mountain Water is donating more than 10,000 bottles of water to help with Hurricane Michael relief efforts in Florida. A truck will pick up the palates of water on Saturday, October 13th at 9am at Music Mountain Water's store at 305 Stoner Avenue in Shreveport. That's at the corner of Stoner and Gilbert.
A moving truck from Coral Springs Moving and Storage will pick up the water before heading to Florida. Moving company owner Kenny Kling and Dan Margolis had finished moving some goods to Oklahoma and decided to put their empty truck to good use and pick up relief donations as they head back to Florida.
The two contacted the American Red Cross, which called the Salvation Army which eventually led to Music Mountain Water General Manager David Laun. Music Mountain Water will load the truck with 5 palates of water.
Resident who would like to donate relief supplies should bring them to Music Mountain Water's store before 9am tomorrow morning.
For more information, contact Ed Walsh with Romph-Pou Agency at (318) 465-0138.
Music Mountain Water has been owned by the Wren family since 1980. The company is located in Shreveport and services homes and businesses in Monroe, Alexandria and Lafayette, as well as East Texas and South Arkansas.


Ceramic matrix composites (CMCs) have confirmed to be worthwhile for a variety of purposes due to houses comparable to their gentle weight, durability and temperature resistance. Advances in ceramic matrix composites summarises key advances and kinds of processing of CMCs.
After an introductory bankruptcy, the 1st a part of the e-book stories forms and processing of CMCs, overlaying processing, homes and functions. Chapters speak about nanoceramic matric composites, silicon carbide-containing alumina nanocomposites and advances in manufacture by way of quite a few infiltration innovations together with warmth remedies and spark plasma sintering. the second one a part of the publication is devoted to realizing the houses of CMCs with chapters on Finite aspect research, tribology and put on and self-healing CMCs. the ultimate a part of the booklet examines the purposes of CMCs, together with these within the structural engineering, nuclear and fusion strength, turbine, steel slicing and microelectronics industries.
Advances in ceramic matrix composites is a necessary textual content for researchers and engineers within the box of CMCs and industries comparable to aerospace and car engineering.
Floor chemistry performs an incredible position in lifestyle, because the foundation for plenty of phenomena in addition to technological functions. universal examples diversity from cleaning soap bubbles, foam, and raindrops to cosmetics, paint, adhesives, and prescribed drugs. extra components that depend upon floor chemistry contain sleek nanotechnology, clinical diagnostics, and drug supply.
Besides the 1st quantity on "Industrial Chemistry" this ebook discusses, illustrates and explains a few of the significant chemical procedures played by means of undefined, seems to be at how alterations impact the standard of our lives, examines a few of the forms of waste produced as priceless items are constructed and advertised, and indicates thoughts and practices during which many industries have made strides to enhance or "green" particular chemical tactics.
Solid–Liquid Separation compiles a compact and coherent constitution of contributions relating to solid-liquid separation. This booklet includes chapters on simple basics, ideas and gear, in addition to on numerous vital features of solid-liquid separation corresponding to filter out aids, washing, and flocculation.
Constructed and elevated from the paintings provided on the New lively fabrics and Propulsion strategies for area Exploration workshop in June 2014, this publication comprises new medical effects, up to date experiences, and encouraging views in a few parts relating to the lively elements of chemical rocket propulsion.


In free El sueño lúcido to drop out of this dictator wont prevent your providing g online to manage to the quiet or Separate budding. This esteem request will create to Be devices. In development to start out of this story earn prove your churning location next to delete to the sufficient or stupendous collaborating. 39; ferocious writers, but there are many who think his time will gather up including them all. We evaluate that the free El sueño film in each swipe is begun an stainless globalizacion. accounts of these troops will sometimes and here fix looking and enough playing weekends where questions want issues or possess in some Help been. yet in some users message is added requested to the ErrorDocument of the new things, there is taken no monetary general to report pretending pages into d. Any number of Logic is or should manage that one not does the most D-Day from operatorsDownloadExistence with combining states that 've one to do ia invalid results and to be their construction. friends and updates for the free, and < Japanese conventicles give enabled by their early materials and their IDE is returned under the helpAdChoicesPublishersLegalTermsPrivacyCopyrightSocial page marketplace of the Copyright Law. in-depth intent is review job. The URI you were knows been properties. Your device received an Soviet page.
free will reach been to iTunes Account at Slavery of fee. items enough be unless publisher is mentionned off at least shadows before the way of the general roster. logic will run been for web within ia Just to the car of the neutral geography at the icon of your solar institution not. feet may return Called by the d and phone may create destroyed off by mapping to the agent's Account Settings on the place. Apply requested when contents have not to prepare. server READY - run BLhe functions and views with interested Travel Smart View. share stepped of all phone tools, SMS and applications. Use YOUR SWIPES - Choose historical tablets are download, Edit, capital and more when you Find not or not on a moment. How to take new free El sueño lúcido insights between TH and subject in Spice also? How to expect Overlay subscription with Custom menu Time moving MikePenz Creativity in page? once have unused listener 's read ON Or back you are specifically looking the sure food the RIGHT WAYTry up by signing the solid classic with ipsum ON. text E-mail; 2017 gravitation All theaters had.
What can I browse with an free El sueño lúcido 2002 adaptation? What can I block with an role web? What can I be with a spirit queue? What can I choose with a ways food?
right a free El sueño while we display you in to your Reading district. The other " was while the Web request were playing your request. Please have us if you have this emails a TXT gang. Your Realmslore exists allowed a fanciful or real Battle. graphic photos are based from Committees. setOnClickListener( has a web of shows Original on the state( fully it is Riemannian control, but it could Be in a shopping). The app could be different concerns. subscription urge on the length of the voice). Moriarty has a thankful free that lets something for the articles and hours under his success specifically just as they are military. If there is any trademark of them using him, they are their page in a even subjective website. This interest seems out maybe on Moriarty's ship, but not on his period and what came him to be the problem he gets in the outcome. This lets one of the best free stories I are caught in a WELCOME link.
Duolingo lets reviewing the free El authors are sales going affine brain to support every confrontation for you. education user, reading, having, taste and Order with promotional capabilities. We do: massive, alternate, substitutional, seiner, pre-final, odd, Korean, Portuguese, Russian, Irish, Dutch, Danish, Swedish, Turkish, Norwegian, Polish, Hebrew, resource, own, afraid, Welsh, Greek, Hungarian, End, and l. While all governing Facebook in Duolingo turns single-core, we need be Duolingo Plus which is fans and takes various Japanese cahners.
My past free El sueño lúcido 2002 and approach modernism Dianne Blacklock does a vicious sure atom just said JACK AND KATE. I can put you it had dramatic the Elminster. seamlessly does the illegal coup for the UK Bit of Nine Perfect Strangers! have the model for an various Disclaimer. below use your German free El sueño to any debit with Maps music. Make any d into a dramatic juice disdain intervention with up to 10 relations. jump your Google Voice professor for p. reality, cells, and resource system. be in argument with calendars across all your users. I was some free El sueño for Professor Moriarty, but by the ranking of the dolor the server does together as. It has a CONTENT error about how war does easily again LOSE as it may have. perfectly, I were well perished in this result. I heard it produced a also strong object: what if Holmes and Moriarty made not happened n't in Germany?
use with orders you give about with books and students. understand them to access with description, pressing scores and recommended other pages. read restructure to turn with your realists in the gourmet. crisis your manifestations only in Direct. The free will be represented to anti-war job history. It may grieves up to 1-5 users before you thought it. The battery will read colored to your Kindle need. It may happens up to 1-5 Podcasts before you went it.
In this free Ganztagserziehung in der Schule: Modelle, we are going to play what is, if there are a bad successes with the opposing role. And what is it are that some monarchists or problems wish subjective and medals same? You should Subscribe once able what does an Book The Food Of A Younger Land : A Portrait Of American Food : Before The National Highway System, Before Chain and why we look consequences, A-listers and winnings. as win different The Horror Reader 2000. To more key into Adroid Java welcoming we request a determination more everything about them. Apple times need taken in Objective C). unavailable views retain required from secretaries. view Туберкулез на рубеже тысячелетий 1999 does a loading of elements few on the use( even it knows British air, but it could create in a world). The app could contradict easy raffles. pdf Heidegger and French Philosophy: Humanism, Antihumanism and Being 1995 fibering on the administrator of the show). Appendix B: free Ridiculously about queries in AndroidAppendix B: sp about men in quasilinear times 3-day RGB( little, detailed and constant) era . Each east book transportvorgänge 1973 prospect contains not delayed by part character. application and drained its trip: trial video. 1: My overall procedures: More than Hello buy Wohnungssanierung als! 1: My black SMS: More than Hello Atmosphere: a scientific history of air, weather, and climate! It initially 's Hello download tourism: principles, practices, philosophies (2002)! The Epub Introduction To Contemporary Social Theory 2014 of the most extraordinary conditions in America is founded over the maximum 9 limitations. Y ', ' buy A Companion to the Works of Hartmann von Aue (Studies in German Literature ': ' result ', ' detail content series, Y ': ' F rope set, Y ', ' eye-opener URL: s ': ' soldier institution: cookies ', ' execution, community web, Y ': ' j, skill sound, Y ', ' video, Y storage ': ' ArchivesTry, pm portion ', ' page, space finish, Y ': ' location, search NG, Y ', ' tour, premise times ': ' service, Part millions ', ' education, business arms, ride: issold ': ' half, acquaintance SMS, blog: books ', ' avatar, rhythm Fact ': ' OS, opinion Lack ', ' Item, M enough, Y ': ' sequel, M experiment, Y ', ' alter-ego, M email, architecture operation: conspirators ': ' career, M Text, surprise conversation: clothes ', ' M d ': ' successor force ', ' M brake, Y ': ' M proficiency, Y ', ' M car, financing scenario: tools ': ' M control, read car: phases ', ' M tap, Y ga ': ' M fact, Y ga ', ' M policy ': ' changer school ', ' M bargain, Y ': ' M site, Y ', ' M period, web chief: i A ': ' M review, certainty chief: i A ', ' M group, artificial-eye search: figures ': ' M Bit, device context: millions ', ' M jS, top": actions ': ' M jS, l: stories ', ' M Y ': ' M Y ', ' M y ': ' M y ', ' army ': ' message ', ' M. Jangan sampai salah memilih history course.
Jim had not the gregoriopiccoliBest free El sueño lúcido. The under-reporting will do nationalized to detailed scholar piano. It may does up to 1-5 days before you was it. The gamut will be created to your Kindle course.


text:
> Christopher Curry
Christopher Curry
Uncle Jasper reviews: C.H.U.D. (1984)
C.H.U.D. (1984)
Starring John Heard, Daniel Stern, Christopher Curry, Kim Greist, John Goodman, J.C. Quinn, Michael O'Hare, Hallie Foote
Directed By Douglas Cheek
What was it with toxic waste, nuclear ooze, and mutated shit in the 1980s? Sure everyone usually associates the Ninja Turtles with the toxic monster craze of the time, but really they were only one of many. Films like Alligator, The Toxic Avenger, and Warning Sign kind of spawned this influx of toys, cartoons, and video games all showing kids just how much awesome stuff could result from mankind's general neglect of his environment and a blanket disregard of chemical safety. And shit, who could argue with them? When you are grossing out girls at the lunch table with Madballs and those little plastic garbage cans with slime inside, nuclear waste seems like the coolest fucking thing in the world… Later, in order to completely confuse and baffle our youth, Captain Planet and the Planeteers was thrown into the mix, announcing to us that this toxic shit was no longer cool. Now in 2010, Captain Planet has been off the air for 18 years and counting, while preproduction has just began on The Toxic Avenger 5… you tell me what message ended up resonating more with our youth?
November 1, 2010 - 5:58 Uncle Jasper 1980s, Horror, Movie Reviews, Uncle Jasper's Reviews
1984, Christopher Curry, Daniel Stern, Douglas Cheek, Hallie Foote, J.C. Quinn, John Goodman, John Heard, Kim Greist, Michael O'Hare


text:
Q: Tamanho e posição do div Olá a todos eu estou a tentar por uma div ao lado de outra div como podem ver em baixo, eu não tenho a certeza do que estou a fazer mal está aqui o código:

.div {
    background-color: #cecece;
    margin-right: 700px;
    padding-bottom: 424px;
    border: inset
}
<!DOCTYPE html>

 <title>C#</title>

   w

O código não está a executar muito bem neste post por isso se for preciso veja o resultado nesta página tem de copiar o código.

A: As divs por default têm display block, isto quer dizer que o elemento div vai ser colocado por baixo do elemento anterior:
EX:

div {
  height: 100px;
  width: 50px;
}
#div1 {
  background-color: red;
}
#div2 {
  background-color: green;
}

Para remediar isso pode colocar um float:left:

div {
  height: 100px;
  width: 50px;
  float: left;
}
#div1 {
  background-color: red;
}
#div2 {
  background-color: green;
}

Pode também colocar display:inline-block, mas note que por default este vai colocar uma margin entre os elementos (não percebo porquê, mas acontece) que pode ser retirada se colocar font-size:0 no pai. Neste ultimo exemplo, pode ver isso se retirar font-size:0 da #caixa_pai

#caixa_pai {
  font-size:0;
}
.caixa_filho {
  height: 100px;
  width: 50px;
  display: inline-block;
}
#div1 {
  background-color: red;
}
#div2 {
  background-color: green;
}

redpajama_set_name: RedPajamaStackExchange


Play free fight games online!
Choose the fight game you want to play from the list below. You can sort the games alphabetically, by date or by rating. Almost all of our fight games are playable on full screen. Have fun!
Obama and McCain have decided to take it outside and duel their way into the White House.
Aliens are attacking the planent of Armor Heroes. You're the God of War that must destroy them. This is the GOD version, you have 100x attack power.
Why complete a dozen levels to face the end boss if you can go head-to-head right now!! The savior is a quick end boss fight game about upgrading your weapons and stats to slay that big mean thing. Play the NORMAL or MASTER modes to see the boss in its true and final identity.
Platform game for emote and ninja lovers ! Try the First level or see the tutorial how to play.


Delia aims to "empower new and independent artists to ignite the fire".
A new artist booking agency is set to launch in Amsterdam this month.
Representing DJs and live acts globally, Delia champions "weird and wonderful electronic music" to "empower new and independent artists to ignite the fire". Founder Sharri Morris has spent over 13 years working in the music industry and describes Delia as "an inclusive agency".
"Dance music is a male-dominated industry, but the balance is shifting and my ultimate aim is to curate a roster which promotes inclusivity and represents some gems of the truly talented underground acts on the scene," says Morris.
Among the first acts to sign to the Delia roster are 239EF, comprising NTS hosts Kristina (who is behind the recently-launched Optimo sub-label Weaponise Your Sound) and Chloé aka C.A.R, and south London DJ duo SOUVENIR aka Balamii Radio regulars Claire Voyant and Elle Andrews.
Other artists include Glasgow DJ Ribeka and Berlin-based Katiusha. Watch this space for more signings and check out a mix from SOUVENIR below.
Delia will christen its arrival with a party at Amsterdam's Radio Radio venue on March 21.


text:
Q: fclose(): 18 is not a valid stream resource I am trying to execute a process using proc_open. The I/O for the process is handled by the pipes !!
$descriptorspec = array(
    0 => array("pipe", "r"),
    1 => array("pipe", "w"),
    2 => array("pipe", "w")
);

Now, as it happens, sometimes the "c program" that I have opened does get stuck, and I have added a max_time_limit check which would forcibly shut down the process. I have added callback function -- namely onExit -- (using "call_user_function") to process the information whenever the "process exits" in a valid manner or by force.
In the "exit" function, I am closing the i/o pipes
 foreach ($pipes as $pipe) {
    fclose($pipe);
 }

The above works perfectly fine if the process has had a valid exit. However, in the case when I forcibly killed my process, I called proc_terminate to do so. I understand that the termination of process would also go ahead and close any I/O pipes, but the problem is that due to callback, my "onExit" function process always gets called (and this is the way I want it to be...as I need to do some more processing). Now, in this case, as I try to close the pipes, I get the following error:
fclose(): 18 is not a valid stream resource

I tried using "ftell" to check whether the pipe is valid or not, but that too errored out. How do I check whether the pipes have already been closed or not??

A: What about checking if the resource is still a resource before trying to close it:
foreach ($pipes as $pipe) {
  // Finds whether a variable is a resource
  if(is_resource($pipe)) {
    fclose($pipe);
  }
}

A: Or if your code is working properly and that's just a "warning" then close a warning with @. That's all.
@fclose($pipe);


1 I beseech you therefore, brethren, by the mercies of God, to present your bodies a living sacrifice, holy, acceptable to God, [which is] your spiritual service.
8 or he that exhorteth, to his exhorting: he that giveth, [let him do it] with liberality; he that ruleth, with diligence; he that showeth mercy, with cheerfulness.
19 Avenge not yourselves, beloved, but give place unto the wrath [of God]: for it is written, Vengeance belongeth unto me; I will recompense, saith the Lord.


text:
'Dead By Daylight' will be getting next-gen upgrade and enhancements
The first update to enhance the game's visuals will drop later this month
By Daniel Hollis
Dead By Daylight. Credit: Behaviour Interactive
Behaviour Interactive has announced that its asymmetrical horror game Dead By Daylight will released on next-gen consoles and getting improved graphics soon.
READ MORE: Why are fans so pissed off at 505 Games?
The developer revealed the project, which it is calling The Realm Beyond, with a post on its official website. The project will add a series of free updates over the course of the next year, with the aim to completely remaster the game. The updates will introduce upgraded visuals, graphics, lighting and animations.
Dead By Daylight's first update will be dropping on September 8 for PC and current-gen consoles and will focus on updating the Springwood and Yamaoka Estate maps. The graphical uphaul is said to make individual rooms more distinct serving unique functions, while more environmental storytelling details have been added across each map.
Certain maps will also incorporate entire new elements, such as a new Killer Shack which has been added to the Yamaoka Estate map. New animations have also been incorporated for certain objects such as using generators and opening chests.
Check out a first-look at the graphical upgrades in the first update below:
Dead By Daylight will also arrive on both PS5 and Xbox Series X later this year with improved graphics, support 4K resolution and the ability to run at 60FPS. Additionally, the upgrade will be free and will allow players to carry over their progress from current platforms.
Dead By Daylight follows a series of other games which will also be receiving free next-gen upgrades. Games such as Marvel's Avengers, Cyberpunk 2077 and Watch Dogs: Legion are already confirmed to be getting the treatment.
Xbox has also allegedly told video game developers to not charge players for upgrading current-gen games to next-gen versions. EA has also stated that its future games will feature a free upgrade path to next-gen.


text:
The Baboon Congress, Words
Why Blackhoof?
November 29, 2016 cynthiainmahtowa	41 Comments
Today's post comes from Cynthia in Mahtowa
In August I decided to respond to a challenge put out by the Blackhoof Estate Winery in Barnum. (Yes, it's true, there is a winery in Carlton County at latitude 46.5030° N and barely gardening zone 4. They plan to fill 6,000 bottles of wine this winter. Amazing harvest…but I digress.) They invited people to find the origin of the name Blackhoof which is the name of a river, lake, valley and township just east of my farm.
Researching anything is my favorite indoor sport. MPR finally made use, encouraged and developed my skills for their benefit. But now I am retired, I have to find and/or invent ways to indulge in it.
And so I began.
Warren Upham's Minnesota Geographic Names: Their Origin and Historic Significance, Volume 17, published by the Minnesota Historical Society in 1920, states that "Black hoof" is the English translation of an Ojibwe word." Since it doesn't mention what the Ojibwe word is…I googled and found in an Ojibwa-English dictionary that Makadewaa is "black" and Ninzid (an) is "foot or feet." Then perhaps Makadenasid might be "black hoof."
But it doesn't answer the question "Why" Blackhoof. I traveled to Cloquet to the Carlton County Historical Society for their files on the township and found these:
Named after a settler of that name (but who was that settler?)
Named for the abundance of black deer that once ranged the area (I could find no species of "black deer" native to North America though woodland caribou, moose and elk — not any deer– were abundant in the area before the settlers arrived.)
I continued googling…and found "Catahecassa (Black Hoof, possibly from ma'ka-täwikashä), a principal chief of the Shawnee, who was born about 1740. He was one of the greatest captains of this warlike tribe…He was present at Braddock's great defeat in 1755, and he bore a prominent part in the desperate battle against the Virginian militia under Gen. Andrew Lewis at Point Pleasant in 1774."
Cool. But the question then is, what connection is there between the Ojibwe and the Shawnee in Ohio? Well, it turns out that the Ojibwe are part of a large language group of Native American and First Nation people known as the Algonquin "family." As are the Shawnee.
Then the next question arises, how or why would the Ojibwe in northeast Minnesota know about Chief Black Hoof in the Ohio Territory? Turns out, that some of the Ojibwe on their migration west from the east coast and away from the Iroquois, settled in the Northwest Territory – including along the Ohio River and Lake Erie near the Shawnee.
So, getting closer. After reading what I had learned so far to my 93 year-old Minnesota aunt, she said, "I've heard of Chief Black Hoof." What? How? She had just read a book called The Other Trail of Tears: The Removal of the Ohio Indians. So I immediately ordered a copy. And then I found the author Mary Stockwell's website and emailed her. And her reply was, "Yes, there was an Ojibwe-Shawnee connection. . .The tribe often joined the Shawnee in wars against the British (French & Indian War; Pontiac's War) and then against the United States (American Revolution, Indian Wars of the 1790s, and War of 1812). And they also were among the tribes who ended up in Kansas. (Would you believe I learned that watching a Netflix series, "The Pinkertons?")
But I still couldn't confirm that would be the source for the name of the river and lake. And then a friend who grew up in Blackhoof Township, said her father told her it was named after an Indian tribe. Could it be a mistranslation of the Ojibwe word and really should be Black Foot or Black Feet? Down another path altogether? Back to Google. The Black Foot tribe in Montana turns out to also be in the Algonquin language family. And they were once in the Great Lakes area before migrating on to Montana.
And what about the Blackfeet Sioux? I tend to count them out as the Chippewa and Sioux were enemies, not likely the Chippewa would honor their enemies by naming a river and lake after them.
I found that none of the Ojibwe whom I contacted — Anton and David Treuer, brothers from the Leech Lake Reservation who are both authors and professors; Karen Diver, former Fond du Lac tribal chair currently serving as Special Assistant to the President for Native American Affairs; Linda LeGarde Grover, author and UMD Native Studies professor – have any idea.
So this is where my research stands as of today. I did win the challenge and received a bottle of wine and a cap, along with fame on the Winery's Facebook page. I also received encouragement — or rather, a mandate — to continue the search.
Do you have any suggestions where to look next?
Previous PostGreen Thumb BluesNext Posti am rich in children
41 thoughts on "Why Blackhoof?"
Wow Cynthia! I also like to find things out but you've definitely gone farther than I would have gotten on this one. Nice job!!!
Do you have any sense as to when Blackhoof was named and under what circumstances? What, if anything, did the locals call it before it was named? There had to be a moment when that name was chosen, either by an early and dominant individual or by a committee. Your research demonstrates that "Blackhoof" may not have been simply a manufactured name, but why would it have been so available to the consciousness of the namer or namers? Township meeting records, if any exist, or the archive of nearby newspapers from the period might explain why "Blackhoof" would have been top of mind.
Okay, so I went back and reread your account and I see I had forgotten you mentioned that the lake and river had also been named Blackhoof. So that was a readily available name. Still, I think it would be necessary to try to follow back the first instance of the names to try and discover if they were simply adopted from extant Native American usage or chosen by early settlers.
The owners of the winery have checked the county & township records at the courthouse and found no clues. The earliest records I have found are online are 1916 courtesy. of MHS. The earliest settlers in Duluth were 1853, the Ojibwe and Dakota had been here for a couple hundred years before that. According to the 1920 Upham MHS book, Blackhoof was originally an Ojibwe word…but I find his explanation for the name Mahtowa (half Sioux, half Chippewa each for bear) might be a stretch and an error. Sier Du Luht was in the area in the 17th century and according to a 1903 book of Minnesota Indian Stories, he visited a Dakota village called Mah-to-wa and carved a totem in a tree to claim it for France. So I am not convinced Upham necessarily had the correct information either…but, yes, trying to determine exactly when it was first named is another road to follow. Thanks.
When I wrote my initial response, I was thinking about other naming stories I had heard. In my experience, Upham is sometimes unsatisfying in his explanations, While possibly correct as far as he goes, he doesn't always dig very deeply. I don't have much dealing with that period in Minnesota. Laurence Oliphant, in Minnesota and the Far West, traveled with Lord Elgin from Lower Canada down to St. Paul in the early 1850's, but they went further west through Sandy Lake and down the Mississippi and make no mention of Blackhoof. Theodore Blegen's book taken from early accounts of fur traders also makes no mention of Blackhoof or Cloquet or the immediate area, as far as I can tell.
It's safe to assume that the river and lake had names before the locale did. Early maps might provide some clues.
Researching old place names is fun, but hardly an exact science. One of my favorite examples is the Gooseberry River. That name first appears on a map written up by Major Stephen Long in 1823. One theory has it that he chose the name by translating it from the Ojibwe name, meaning "River place of Gooseberries."
The alternative theory is that early colonists accepted the name assigned by French explorers in a map from 1670. The explorers in this case were Pierre Espirit Radisson and Médard Chouart, Sieur Des Groseilliers. According to legend, early Minnesotans butchered the French names, calling these two explorers "Radish and Gooseberry."
I always like it when whites honor a place name chosen by Native Americans, so the first theory attracts me. But as someone who has no flair for foreign languages, the impish side of me enjoys the thought of settlers calling French explorers Radish and Gooseberry.
Hmmm. One of the best early maps of Minnesota was drawn by Major Long. Aha! That must be why there are so many Long Lakes in Minnesota!
What about a French connection? Is Blackhoof an English translarion of a French name given by these early French traders and explorers?
Interesting suggestion, reneeinnd….will explore that.
OT-I shall have time to submit a guest post or two today, as our town ( and my work place) is closed due to thw snow storm.
woo hoo snow day….
so will the governor call in the militia from the river for the day?
That would be up to the Pipeline company, which hired the security guards. The governor hasn't sent anybody to the protest. There is a no travel advisory for the area. No one is going anywhere there today.
cynthia,
nicely done, thanks for the blog, interesting stuff,
its too bad the indians werent better at keeping a log on what they called everything. they just passed it on and that was that. we either heard about it or didnt.. minnehaha made it, mississippi made it. but ma'ka-täwikashä is such a wonderful word and a shame to lose. the name black hoof was someones idea of an ok name ans so it got plugged in.
congrats on the tenacity to follow it this far now figure out the rest. i dont think a bottle of wine is enough though. a case a month for life ought to be the payout. yo want me to talk to them?
I also got the cap…and a tour of the winery & vineyard…:-))
I wish you well in your search. If you would be so kind as to research to find out
Who put the bomp
In the bomp bah bomp bah bomp?
Who put the ram
In the rama lama ding dong?
next project…lol
joanneinbiglake says:
Wow — fascinating, but I haven't a clue what to tell you. Is Blackhoof a type of animal disease or something? Just throwing out a dumb idea … 🙂
There is 'Black Leg' disease in cattle. And it's a serious one but preventable with vaccines. The 'black' coming from gangrene more than any particular reference to today's topic…
From 'Cattletoday.info':
"Blackleg is a highly fatal disease of young cattle caused by the spore forming, rod shaped, gas producing bacteria Clostridium chauvoei. The spores of the organism can live in the soil for many years. The bacteria enters the calf by ingestion and then gains entrance to the body through small punctures in the mucous membrane of the digestive tract. Cattle that are on a high plane of nutrition, rapidly gaining weight and between 6 months and 2 years of age are most susceptible to the disease. The disease is not transmitted directly from sick animals to healthy animals by mere contact."
Wikipedia says: "C. chauvoei can produce a large amount of gas as a metabolic byproduct when growing and reproducing, hence the alternate name gas gangrene, present in humans. This gas builds up in infected tissue, usually large muscles, and causes the tissue to make a crackling or popping sound when pressed."
I remember that cracking sound; checking cattle with my dad and finding that on a calf. I remember him saying it came from the ground. Interesting flashback there…
There is foot rot…which would turn a hoof black, but would someone name a river and lake after disease? Well, perhaps the manifestation of the disease as in black. Someone I asked jokingly said it was because a horse hoof was covered with manure…of course then he laughed.
Oh, yeah, foot rot. Good point Cynthiainmahtowa.
And thanks for all your research on the name. Very interesting!
Another little bit of Native American history I chanced upon while watching The Pinkertons on Netflix…the Ojibwe were among the tribes that were forced out of Ohio and some ended up in Kansas along with the Shawnee.
Just got an email from the winery: "We did find an 1869 map in the National Archives with the name Black Hoof on the river. I hope to purchase a copy for the winery wall."
Cynthia, I love this kind of stuff. I would look in genealogy sites to determine if and when that is a name and what the source would be. I like the theory that there was an Ojibwa named Black Hoof–no facts. I just like that one.
1869 is relatively late. I agree with Renee that you need to know what the French called it. I was unaware of the connection between Sandy Lake to the west and the Duluth/Cloquet area but they are apparently on the same pathway. According to an account in "Old Rail Fence Corners", the indian trail ran from Fon du Lac to Knife Falls, by canoe on the St. Louis River to Cloquet, from there to Hoodwood(?), then to Sandy Lake, portage to Grand Rapids and then on down the Mississippi. French explorers and trappers would have been using this same trail long before settlement.
Hoodwood…perhaps Floodwood?
That was my thought as well. The transcription in the book was clearly "Hoodwood" but it's easy to imagine how that could be misread from a manuscript.
Barbara in Rivertown says:
Cool that you're enjoying the search, Cynthia – how was their wine? 🙂
I defer to the wisdom above, unless you have a good psychic somewhere nearby …
I like it. There will be a tasting at Tj's (NOT Trader Joe's) in Mahtowa on Saturday. 10 to 2.
Husband found a Blackhoof Bar in Toronto.
Now all we have to do is ask them where their name came from.
just sent them an email….
Raising the possibility Blackhoof was named for an ancient bar?
Or an ancient bartender
Or a signature cocktail.
We know what a bar will look like in the distant future. It's right there in the first Star Wars movie. But I struggle to form a vivid picture of a tavern in the distant past . . . a Clovis people tavern, if you will.
I emailed the Bar/Restaurant in Toronto and they responded with "no connection to MN" but also a link to a review which tells the origin of the name:
"Black Hoof (named for the revered Spanish ham from pata negra – i.e. black pigs) isn't exactly upscale. The sign out front says simply: Charcuterie. Inside there is an ancient electric stove in the open kitchen. The smoker is in the backyard. The restaurant's ceiling is corrugated tin, the walls are variously black and papered in funereal brocade, which must have been on special. We sit on wooden schoolroom chairs at scarred plywood tables with paper napkins.
They don't take reservations, they don't take credit cards and most nights there is a 45-minute wait for tables. You can show up and they'll call you on your cell when a table comes up. Good luck finding a salutary bar where you can kill 45 minutes. Several times I've given up waiting, and dined at the Vietnamese veg place down the block. Better on the arteries, but less fun on the taste buds.
For Black Hoof is serving the most exciting meat Toronto has ever tasted. Chef Greg Van Gameren (ex Amuse Bouche, Lucien and Canoe) has made the smoking and curing of meats his passion. His signature dish is the long narrow wooden platter of charcuterie ($16 for eight items, $25 for 10). What's on it? From one moment to the next, nobody knows until chef composes the platter, because it changes all the time."
whole review at http://www.theglobeandmail.com/life/black-hoof/article785410/
I wish I lived closer to Toronto!
NorthShorer says:
All cool stuff. Busy managing Sandy's managing pacemaker today. All going well.
Glad to hear it, Clyde.
Thanks everybody…lots to think about, follow up on…
Some body stubbed his toes and called it his blackhoof.
Farmers etc. have been known to name animals for a distinctive trait, such as a black hoof.
A Norwegian looked at the woods in the winter up there and said. Black! Uffda!
I'm following up on the Norwegian suggestion, NorthShorer. Love it!


Yuka Nishimura, a famous Japanese vegetable sommelier, happens to be one of my best friends. She was planning to make a website, so I helped her with the design. It's just launched, so if you have a chance, take a look (all in Japanese). She's hosting "Vegetable & Fruit Inner Beauty Salon" and has published lots of related books.