We propose a general method for combinatorial online learning problems whose offline optimization problem can be solved efficiently via a dynamic programming algorithm defined by an arbitrary min-sum recurrence. Examples include online learning of Binary Search Trees, Matrix-Chain Multiplications, k -sets, Knapsacks, Rod Cuttings, and Weighted Interval Schedulings. For each of these problems we use the underlying graph of subproblems (called a multi-DAG) for defining a representation of the solutions of the dynamic programming problem by encoding them as a generalized version of paths (called multipaths). These multipaths encode each solution as a series of successive decisions or components over which the loss is linear. We then show that the dynamic programming algorithm for each problem leads to online algorithms for learning multipaths in the underlying multi-DAG. The algorithms maintain a distribution over the multipaths in a concise form as their hypothesis. More specifically we generalize the existing Expanded Hedge (Takimoto and Warmuth, 2003) and Component Hedge (Koolen et al., 2010) algorithms for the online shortest path problem to learning multipaths. Additionally, we introduce a new and faster prediction technique for Component Hedge which in our case directly samples from a distribution over multipaths, bypassing the need to decompose the distribution over multipaths into a mixture with small support.

Predicting the future behavior of road users is one of the most challenging and important problems in autonomous driving. Applying deep learning to this problem requires fusing heterogeneous world state in the form of rich perception signals and map information, and inferring highly multi-modal distributions over possible futures. In this paper, we present MultiPath++, a future prediction model that achieves state-of-the-art performance on popular benchmarks. MultiPath++ improves the MultiPath architecture by revisiting many design choices. The first key design difference is a departure from dense image-based encoding of the input world state in favor of a sparse encoding of heterogeneous scene elements: MultiPath++ consumes compact and efficient polylines to describe road features, and raw agent state information directly (e.g., position, velocity, acceleration). We propose a context-aware fusion of these elements and develop a reusable multi-context gating fusion component. Second, we reconsider the choice of pre-defined, static anchors, and develop a way to learn latent anchor embeddings end-to-end in the model. Lastly, we explore ensembling and output aggregation techniques -- common in other ML domains -- and find effective variants for our probabilistic multimodal output representation. We perform an extensive ablation on these design choices, and show that our proposed model achieves state-of-the-art performance on the Argoverse Motion Forecasting Competition and the Waymo Open Dataset Motion Prediction Challenge.

The Internet of Things (IoT) is a collection of Internet connected devices capable of interacting with the physical world and computer systems. It is estimated that the IoT will consist of approximately fifty billion devices by the year 2020. In addition to the sheer numbers, the need for IoT security is exacerbated by the fact that many of the edge devices employ weak to no encryption of the communication link. It has been estimated that almost 70% of IoT devices use no form of encryption. Previous research has suggested the use of Specific Emitter Identification (SEI), a physical layer technique, as a means of augmenting bit-level security mechanism such as encryption. The work presented here integrates a Nelder-Mead based approach for estimating the Rayleigh fading channel coefficients prior to the SEI approach known as RF-DNA fingerprinting. The performance of this estimator is assessed for degrading signal-to-noise ratio and compared with least square and minimum mean squared error channel estimators. Additionally, this work presents classification results using RF-DNA fingerprints that were extracted from received signals that have undergone Rayleigh fading channel correction using Minimum Mean Squared Error (MMSE) equalization. This work also performs radio discrimination using RF-DNA fingerprints generated from the normalized magnitude-squared and phase response of Gabor coefficients as well as two classifiers. Discrimination of four 802.11a Wi-Fi radios achieves an average percent correct classification of 90% or better for signal-to-noise ratios of 18 and 21 dB or greater using a Rayleigh fading channel comprised of two and five paths, respectively.

Global Navigation Satellite System (GNSS) signals are subject to different kinds of events causing significant errors in positioning. This work explores the application of Machine Learning (ML) methods of anomaly detection applied to GNSS receiver signals. More specifically, our study focuses on multipath contamination, using samples of the correlator output signal. The GPS L1 C/A signal data is used and sourced directly from the correlator output. To extract the important features and patterns from such data, we use deep convolutional neural networks (CNN), which have proven to be efficient in image analysis in particular. To take advantage of CNN, the correlator output signal is mapped as a 2D input image and fed to the convolutional layers of a neural network. The network automatically extracts the relevant features from the input samples and proceeds with the multipath detection. We train the CNN using synthetic signals. To optimize the model architecture with respect to the GNSS correlator complexity, the evaluation of the CNN performance is done as a function of the number of correlator output points.

Predicting human behavior is a difficult and crucial task required for motion planning. It is challenging in large part due to the highly uncertain and multi-modal set of possible outcomes in real-world domains such as autonomous driving. Beyond single MAP trajectory prediction, obtaining an accurate probability distribution of the future is an area of active interest. We present MultiPath, which leverages a fixed set of future state-sequence anchors that correspond to modes of the trajectory distribution. At inference, our model predicts a discrete distribution over the anchors and, for each anchor, regresses offsets from anchor waypoints along with uncertainties, yielding a Gaussian mixture at each time step. Our model is efficient, requiring only one forward inference pass to obtain multi-modal future distributions, and the output is parametric, allowing compact communication and analytical probabilistic queries. We show on several datasets that our model achieves more accurate predictions, and compared to sampling baselines, does so with an order of magnitude fewer trajectories.

Romit Roy Choudhury is a professor and Jerry Sanders III AMD Inc. Scholar in the Department of ECE and CS at the University of Illinois at Urbana-Champaign, IL, USA. To view the accompanying paper, visit doi.acm.org/10.1145/3236621

Romit Roy Choudhury is a professor and Jerry Sanders III AMD Inc. Scholar in the Department of ECE and CS at the University of Illinois at Urbana-Champaign, IL, USA. To view the accompanying paper, visit doi.acm.org/10.1145/3236621

Multipath is among the major sources of errors in precise positioning using GPS and continues to be extensively studied. Two Fast Fourier Transform (FFT)-based detectors are presented in this paper as GPS multipath detection techniques. The detectors are formulated as binary hypothesis tests under the assumption that the multipath exists for a sufficient time frame that allows its detection based on the quadrature arm of the coherent Early-minus-Late discriminator (Q EmL) for a scalar tracking loop (STL) or on the quadrature (Q EmL) and/or in-phase arm (I EmL) for a vector tracking loop (VTL), using an observation window of N samples. Performance analysis of the suggested detectors is done on multipath signal data acquired from the multipath environment simulator developed by the German Aerospace Centre (DLR) as well as on multipath data from real GPS signals. Application of the detection tests to correlator outputs of scalar and vector tracking loops shows that they may be used to exclude multipath contaminated satellites from the navigation solution. These detection techniques can be extended to other Global Navigation Satellite Systems (GNSS) such as GLONASS, Galileo and Beidou.