Thomas Bewley
Director of Flow Control & Coordinated Robotics Labs
UC San Diego

Abstract:
Warm-up: The Find My app reveals that the mean and covariance of the location $\XX\in \Omega$  of your iPhone are $\mathcal{E}\{X\}$ and $\mathcal{E}\{\XX\XX^{T}\}$. For $i=1,\ldots,N$, the position  ${}^{i}{\bf q}(t)\in \Omega$ of search vehicle $i$ evolves via $d^{i}q/dt=f({}^i{\bf q},{}^{i}{\bf u})$. What control inputs ${}^{i}{\bf u}$ both (a) maximizes the probability of finding your phone quickly, while (b) assures that your phone is found eventually?

Starting from this framework, and shifting attention to the search for randomly-moving targets, the It\^o SDE is related to the Fokker–Planck PDE for the PDF $p({\bf x}, t)$ of a Weiner process by:
  \begin{equation*}
   d\XX
   = {\bf u}(\XX,t) dt + {\bf \Sigma} d {\bf W}
   \iff
   \frac{\partial p(\XX,t)}{\partial t}
   =
   - \frac{\partial u_{i}({\bf x},t)p({\bf x},t)}{\partial x_i}
   + \frac{\partial^2 s_{ij}p({\bf x},t)}{\partial x_i \partial x_j}
   ;
  \end{equation*}
the corresponding Langevin equation, assuming friction forces dominate inertial forces, is
\begin{equation*}
    \frac{d \XX(t)}{dt}= {\bf u}(\XX,t)+{\bf{\boldsymbol \xi}}(t)
    \comma
    \mathcal{E}\{{\boldsymbol \xi}(t){\bf{\boldsymbol \xi}}^{T}(t+\tau)\}
    = 2 S \delta^{\sigma}(\tau)
    \comma
    \delta^{\sigma}(\tau)
    = \frac{
       e^{-\tau^2/(2\sigma^2)}
          }{
       \sigma(2\pi)^{1/2}
      }
    .
  \end{equation*}
Given such a setting summarizing Brownian motion, we present an extensible framework for Probabilistic Search, via a series of 5 related model problems of increasing complexity:

1. Consider first a {\bf drunken sailor} who exits a bar at midnight, and moves away from the bar via a random walk thereafter. The statistics representing the sailor's location are nonstationary. What is the best pattern for the search vehicles to find the drunken sailor?

2. Consider a {\bf cougar} known to generally stay within a given (large, noncircular) territory; his movements within it may be modeled as random, with stationary statistics. He is not particularly scared by the noise of the search vehicles. How best to search for the cougar?

3. Consider a skittish {\bf deer}. Like the drunken sailor and the cougar, the motion representing the deer’s location can be modeled as random, but with the added complication that, when he hears the sound of a search vehicle, he moves evasively. How best to search for the deer?

4. Consider next the {\bf coverage of a hurricane} with scores of sensor-laden buoyancy- controlled balloons, each of which trace the local horizontal (100+ mph) winds of the hurricane, at each balloon’s commanded altitude (which itself is controlled by adjusting that balloon’s buoyancy). [Note: each sensor balloon can detect (and, periodically report) the local pressure, temperature, turbulence intensity, and time/location (via GPS), and can thus infer the local time- averaged wind velocity.] How can we model this problem in a meaningful probabilistic fashion, and subsequently coordinate the buoyancies of each of the balloons, to result in an evolving distribution of the sensor balloons over the hurricane to provide the richest, most current measurement data of the hurricane to the corresponding weather forecasting centers?
5. Finally, consider the problem of finding a {\bf methane plume} vent on Mars. Mobile sensor vehicles (rovers and/or small helicopters) measure the local wind velocity and local methane concentration. An ensemble-based data assimilation method, leveraging a simplified model of this wind-driven plume, is used to estimate the distribution and evolution of the local winds and plume concentration over a relevant region. How can we optimize the trajectories of the sensor vehicles to minimize the relevant uncertainty (that is, an appropriately-weighted trace of an ensemble approximation of a covariance matrix) of the corresponding state estimate, and thus optimally search for the plume vent location (and thus, maybe, evidence of Martian microbes)?

Professor Thomas Bewley directs the Flow Control \& Coordinated Robotics Labs at UC San Diego. He works at the intersection of robotics, optimization, control theory, and numerical methods.