University of Southern California (USC): Urbashi Mitra, Shrikanth Narayanan, and Gaurav Sukhatame
Massachusetts Institute of Technology (MIT): Franz Hover
Northeastern University (NEU): Milica Stojanovic
Graduate Students: Mei Yi Cheung, Eric Gilbertson, and Brooks Reed
The oceans cover 71% of the earth's surface and are integral to climate regulation, nutrient production, oil retrieval, and transportation; yet they represent one of the least explored frontiers. Marine robotic vehicle platforms and sensor technology are maturing rapidly, making multiple-vehicle operations an attractive solution for tracking dynamic targets, as well as increasing the spatial and temporal resolution of oceanographic observation. Future scientific and technology efforts to achieve better understanding of the oceans and water-related applications will rely heavily on our ability to jointly consider communications, actuation, and sensing in a unified system that includes instruments, vehicles, human operators, and sensors of all types.
Networks of mobile agents are attractive, but wireless communication leads to fundamental challenges in control. Underwater, wireless communication over distances beyond about one hundred meters is made almost exclusively via acoustics, which suffer from low data rates, packet loss, and long delays. These characteristics have limited the use of acoustic communications (acomms) in high-performance, real-time tasks.
The Hover research group aims to enable truly dynamic multi-vehicle missions underwater, through integrated design of control and communication. A primary goal is to develop advanced control analysis and synthesis methods for feedback control, taking into account the lossy and rate-limited acoustic channel. A centralized architecture such as this allows integration with remote sensing, large-scale computations (such as data assimilation), and human-in-the-loop decision-making.
In support of this overall vision, we have studied approaches for autonomous adaptive relay positioning, describing functions for quantized and lossy channels, and robust multicast routing. As a straightforward example of the integrated mission, we demonstrated multi-vehicle joint estimation and pursuit of dynamic targets using acoustics. More broadly, we have developed a framework for the oceanographic version of target pursuit where multiple vehicles collaborate to track dynamic ocean features such as fronts or plumes, leveraging global ocean model information as well as advanced networked control techniques.
As vehicle fleet sizes grow, network routing becomes a dominant issue, and multicast plays an important role when control commands must be disseminated to many vehicles. However, the acoustic channel is stochastic, and power is limited. In this work, we consider underwater acomms multicast routing with power control, via a centralized robust approach. While the large size and ad-hoc nature of many RF wireless applications motivate distributed routing methods based on network discovery, the high latency and unreliability of acomms suggests that these algorithms could exhibit poor convergence in the underwater domain. In addition, considering large-scale ocean missions, data assimilation, and planning are typically centralized today, and marine assets are expensive and carefully tracked. These aspects of acomms and ocean missions motivate optimization methods which can take into account motion plans, global channel information, and operator input.
We studied the minimum energy wireless transmission problem [MET], augmented by the practical condition that constraints on link power must be satisfied in probability. For this, we formulated the robust counterpart of the multicommodity mixed-integer linear programming (MILP) model from Haugland and Yuan, 2011, and derived scaled power levels that account for uncertainty. Our main result is that the deterministic formulation with these scaled power levels recovers exactly the optimal robust solution in the absence of correlations, and therefore allows for efficient solution via MILP. This approach achieves significant power improvements over heuristics, and naturally lends itself to vehicle networks. The figure below shows a summary comparison; even at low uncertainty, Robust MET achieves an objective which is 41% better than that of the heuristic.
Acoustic channel performance depends strongly on local water properties, bathymetry, and other environmental variables. In shallow-water and man-made environments like harbors, multipath and scattering interference results in significant variability across physical space. A key insight, however, lies in recognizing that acoustic nodes can learn about and exploit the statistics of the channel at their current location, even while receiving and transmitting useful information acoustically. For the purpose of improving acomms during a multi-vehicle mission, we have considered the case of deploying a mobile acoustic relay to adapt to acoustic link variations in physical space.
The relay must balance visiting and transmitting at unknown sites to gain more information, which may pay off in the future, against exploiting already-visited sites for immediate reward. This is a classic exploration vs. exploitation problem that is well-described by a multi-armed bandit framework (MAB).
We formulated the MAB for the problem of adaptive acoustic relay positioning and applied in field tests an optimal solution in the form of Gittins indices. This indexable solution holds if the cost associated with changing sites is negligible (for example, in a fixed sensor network). However, for an autonomous ocean vehicle traveling between distant waypoints, the time costs of traveling (switching costs) are significant. The multi-armed bandit with switching costs (MABSC) has no optimal index policy, so we developed an adaptation of the Gittins rule with limited policy enumeration, exploiting a 1996 result from Asawa & Teneketzis. Our results show that the algorithm is practically implementable in the field, and we performed hybrid experiments with real acoustic data to characterize the performance of MAB and MABSC compared to epsilon-greedy heuristics.
As one would expect, demand on throughput grows to fill the available channel capacity in wirelessly connected robotic systems; in a clean short-range RF setting, entire images may be transferred in each cycle, as part of a vision-based control system, whereas in the ocean, acoustic channels with perhaps twenty bits per second allow only the most basic sensor and command information to be shared regularly. Packet-based wireless communication systems like these that operate near their limits are necessarily quantized, and often prone to loss. These properties directly impact the overall system performance, and thus methodologies for understanding and designing feedback systems with quantization and packet loss are valuable. This work makes several contributions to feedback control of systems subject to quantization and stochastic packet loss in the sensor feedback channel.
First, we derive and verify describing functions (DFs) for information channels subject to quantization and packet loss. The DFs represent the loss and quantization effects by frequency- and amplitude-dependent gains and phases, similar to transfer functions. These DFs are unique because, unlike most other DFs that describe hardware and physical elements, these describe stochastic information channels. DFs are presented for a general codec algorithm, and for four commonly-used sensor-feedback codecs: Zero-Output (QLZ), Hold-Output (QLH), Linear Filter (QLF), and Modified Information Filter (QLM) (Gupta et al. 2007). These are each given as closed-form mathematical expressions of the provably optimal gains and phases for each case, with each decoder a specific case of the general codec algorithm.
Second, we show how the DFs can be used as analysis tools to predict limit cycles in dynamic feedback control systems. Computation times using the DFs are shown to be orders of magnitude faster than those from simulation for these calculations.
Third, we propose a synthesis method to use the DFs to design a codec for the sensor feedback channel that decreases limit cycle amplitudes induced by quantization and packet loss for a large class of systems. Up to three-fold reductions in limit cycle amplitudes are shown, with the tradeoff being slightly higher system sensitivity to disturbances and slightly higher steady state errors to step inputs. The designed codec is of the special and simple form of a constant times the sent signal if the signal is received and a different constant times the previous decoded signal if the sent signal is lost. This is the equivalent structure and computation complexity to both Zero-Output and Hold-Output decoders. A DF for this decoder allows the constants to be solved for as functions of target limit cycle amplitudes. The constants reduce to solutions of cubic equations, which are guaranteed to have a real root, and thus the codec is physically realizable. The codec allows for multiple limit cycle frequency solutions for the same amplitude solution. The analysis and synthesis tools are verified both by numerical examples, and by a physical experiment controlling heading of a small robotic raft where the designed decoder results in smaller limit cycles than does a linear-filter-based decoder.
In this work we address through experiments the capability of acoustics to sustain highly dynamic, multi-agent missions, in particular range-only pursuit in a challenging shallow-water environment. Our key experiment in joint localization and pursuit has two mobile agents sharing sensor information and commands through acoustic links. We make scalar range measurements at each agent, and thus tracking is impossible without their coordination. One agent is designated as the leader that coordinates the measurements and the actions of the followers. This arrangement involves lossy channels at both locations in the feedback loop. The mobile agents attempt to stay close to the target, and in a formation conducive to good sensor performance. Estimation and control are tightly coupled in this mission, allowing us to study the effects of packet loss, quantization, delays, and scheduling on the frequency response of the integrated closed-loop system.
We have carried out extensive shallow-water field tests on this problem. In one set, we compared the tracking performance of three different communication configurations: full-sized packets ("FSK0") with negligible quantization and a 23s cycle, RF wireless communication ("WiFi") with a 4s cycle and negligible quantization, and 13-bit mini-packets ("MP") with a 12s cycle. With 13-bit mini-packets, we employed logarithmic quantization for 3-bit range measurements.
Recalling our broad objective to achieve dynamic control through mobile acoustic networks, it is revealing to ask what effective closed-loop estimation bandwidth was achieved. A direct FFT-based empirical transfer function for the estimation error divided by target motion is shown for each condition below. The FSK0 test had a break frequency for tracking the motion of the target at approximately 0.065 rad/s, slightly less than half the Nyquist rate for the twenty-three-second cycle. The wifi test had a break frequency of approximately 0.5rad/s. The MP test had a break frequency of approximately 0.13rad/s. These outcomes show definitively that aggressive dynamic control of multi-agent systems underwater is tractable today.
In May 2014, we achieved similar pursuit results using three vehicles and time-difference-of-arrival (hyperbolic) navigation, which opens the way to tracking targets without time synchronization.
The behavior of ocean fronts and similar structures such as plumes and filaments has long been of interest to oceanographers. Modeling of ocean fronts at the mesoscale and smaller remains challenging, and hence has emerged as a primary focus area for mobile sensing systems. While single vehicles have executed measurement-driven trajectories and ocean modeling is increasingly integrated with vehicle path-planning, multi-vehicle coordination under communication constraints has not yet been integrated with global model information until now.
In this work, we combine the themes above to focus on tracking and pursuit of dynamic ocean fronts by multiple unmanned vehicles, posing the problem in such a way as to accommodate the most promising developments in communication-constrained feedback control. As diagrammed in the above figure, this method fits as an intermediary between high-bandwidth vehicle flight control (at the seconds time scale) and lower-frequency procedures in numerical ocean modeling, assimilation, and adaptive sampling. Our approach uses ocean model predictions to design closed-loop networked control at short time scales, and the primary innovation is to represent model uncertainty via a projection of ensemble forecasts into local linearized vehicle coordinates. Based on this projection, we identify a stochastic linear time-invariant model for estimation and control design. The methodology accurately decomposes spatial and temporal variations, exploits coupling between sites along the feature, and allows for advanced methods in communication-constrained control. These elements all enable a reactive control methodology for dynamically sampling the ocean that surpasses approaches used today.
We have worked with three specific example cases: an LTI chained mass system, a double gyre model, and hindcast data of a temperature front off Taiwan (see Gawarkiewicz et al., 2011). For each dataset, we performed a stochastic identification process on an ensemble, and compared five controllers, each subject to vehicle navigation noise and physical disturbances. The "Non-reacting" controller places vehicles at reference frontal points, and "Loners" uses a set of independent LQG controllers designed with local models to servo to the estimated front. "Lower Bound" applies a standard LQG controller design given a fully coupled model. Perfect communication is assumed, and hence this controller is expected to be the best. We also considered two controllers that use the fully coupled model, require communication, and are subject to stochastic packet losses in each direction between the controller and each vehicle. "Naive" applies a standard LQG controller design, while "All-or-none" uses the dynamic programming procedure of Imer et al. (2006).
The left plot of the comparison figure shows the Lower Bound estimation error for each dataset as a function of the field sensor noise variance R_phi. The right plots show differences between the estimation error of each control method and that of Lower Bound. The Non-reacting method performs poorly, demonstrating the benefits of active pursuit. As noise increases, All-or-none outperforms Loners, demonstrating that the benefits of exploiting coupling outweigh the detrimental effects of packet loss.
Despite obvious challenges in local linearization and stochastic identification, we firmly believe that linear stochastic models are key to cogent analysis and design procedures when multiple vehicles operate with realistic navigation and communication limits. The LTI model allows for classical and scalable multivariable estimation and control, as well as rigorous contemporary approaches for lossy communications.
Currently we are developing a modeling framework and control/estimation strategy for implementation in realistic multi-vehicle ocean systems, where schedules, delays, packet loss, and quantization are all present. A stochastic jump linear system incorporates control trajectory buffering and the above acomms constraints. Our approach uses multirate model predictive control and an adjustable-window Kalman Filter for estimation with delayed and lossy control packet acknowledgements. We plan to test this system using three autonomous vehicles connected to a shore computation center via an acoustic relay buoy.
Reed, B., Stojanovic, M., Mitra, U., and F. Hover, "Robust Minimum Energy Wireless Routing for Underwater Acoustic Communication Networks," IEEE Globecom 2012 Workshop on Wireless Networking and Control for Unmanned Autonomous Vehicles: Architectures, Protocols and Applications (Wi-UAV), December 2012. (Link to Full Text at IEEE Xplore)
Cheung, M., Leighton, J., and F. Hover, "Autonomous Mobile Acoustic Relay Positioning as a Multi-Armed Bandit with Switching Costs," IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), November 2013. (Link to full text at IEEE Xplore)
Cheung, M., Leighton, J., and F. Hover, "Multi-armed Bandit Formulation for Autonomous Mobile Acoustic Relay Adaptive Positioning", IEEE International Conference on Robotics and Automation (ICRA), May 2013. (Full Text, PDF) Best Conference Paper Finalist, top 5 out of 873 accepted papers.
Reed, B., and F. Hover, "Tracking Ocean Fronts with Multiple Vehicles and Mixed Communication Losses", IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), November 2013. (Link to full text at IEEE Xplore)
Reed, B., Leighton, J., Stojanovic, M., and F. Hover, "Multi-Vehicle Dynamic Pursuit using Underwater Acoustics," International Symposium on Robotics Research (ISRR), December 2013, to appear. (Abstract, PDF)
Reed, B. and F. Hover, "Oceanographic Pursuit: Networked Control of Multiple Vehicles Tracking Dynamic Ocean Features," Methods in Oceanography, Special Issue on Autonomous Vehicles, May 2014. (Link to Open Access PDF)
Cheung, M., Leighton, J., Mitra, U., Singh, H., and F. Hover, "Performance of Bandit Methods in Acoustic Relay Positioning," American Control Conference (ACC), June 2014, to appear. (Abstract, PDF)
Portions of this work were also supported by the Office of Naval Research.