Abstract

Polar codes, introduced by Arikan, achieve the capacity of arbitrary binary-input discrete memoryless channel W under successive cancellation decoding. Any such channel having capacity I(W) and for any coding scheme allowing transmission at rate R, scaling exponent is a parameter which characterizes how fast gap to capacity decreases as a function of code length N for a fixed probability of error. The relation between them is given by N ≥ α/(I(W)-R) μ . Scaling exponent for kernels of small size up to L=8 have been exhaustively found. In this paper, we consider product kernels TL obtained by taking Kronecker product of component kernels. We derive the properties of polarizing product kernels relating to number of product kernels, self duality and partial distances in terms of the respective properties of the smaller component kernels. Subsequently, polarization behavior of component kernel Tl is used to calculate scaling exponent of TL=T2⊗Tl. Using this method, we show that μ(T2⊗T5)= 3.942. Further, we employ a heuristic approach to construct good kernel of L=14 from kernel having size l=8 having best μ and find μ(T2⊗T7)=3.485.

Abstract

Distributed databases often suffer unequal distribution of data among storage nodes, which is known asdata skew'. Data skew arises from a number of causes such as removal of existing storage nodes and addition of new empty nodes to the database. Data skew leads to performance degradations and necessitatesrebalancing'at regular intervals to reduce the amount of skew. We define an -balanced distributed database as a distributed database in which the storage across the nodes has uniform size, and each bit of the data is replicated in distinct storage nodes. We consider the problem of designing such balanced databases along with associated rebalancing schemes which maintain the -balanced property under node removal and addition operations. We present a class of -balanced databases (parameterized by the number of storage nodes) which have the property of structural invariance, ie, the databases designed for different number of storage nodes have the same structure. For this class of -balanced databases, we present rebalancing schemes which use coded transmissions between storage nodes, and characterize their communication loads under node addition and removal. We show that the communication cost incurred to rebalance our distributed database for node addition and removal is optimal, ie, it achieves the minimum possible cost among all possible balanced distributed databases and rebalancing schemes.

Abstract

We consider the distributed computing framework of Map-Reduce, which consists of three phases, the Map phase, the Shuffle phase and the Reduce phase. For this framework, we propose the use of binary matrices (with entries) calledtextit {computing matrices} to describe the map phase and the shuffle phase. Similar binary matrices were recently proposed for the coded caching framework. The structure of ones and zeroes in the binary computing matrix captures the map phase of the Map-reduce framework. We present a new simple coded data shuffling scheme for this binary matrix model, based on atextit {identity submatrix cover} of the computing matrix. This new coded shuffling scheme has in general a larger communication load than existing schemes, but has the advantage of less complexity overhead than the well-known earlier schemes in literature in terms of the file-splitting and associated indexing and coordination required. We also show that there exists a binary matrix based distributed computing scheme with our new data-shuffling scheme which has strictly less than twice than the communication load of the known optimal scheme in literature. The structure of this new scheme enables it to be applied to the framework of Map-reduce with stragglers also, in a straightforward manner, borrowing its advantages and disadvantages from the no-straggler situation. Finally, using binary matrices derived from combinatorial designs, we show specific classes of computing schemes with very lowtextit {file complexity}(number of subfiles in the file), but with higher communication load compared to the optimal scheme for equivalent parameters.

Abstract

In this paper, we address the novel, highly challenging problem of estimating the layout of a complex urban driving scenario. Given a single color image captured from a driving platform, we aim to predict the bird’s eye view layout of the road and other traffic participants. The estimated layout should reason beyond what is visible in the image, and compensate for the loss of 3D information due to projection. We dub this problem amodal scene layout estimation, which involves hallucinating scene layout for even parts of the world that are occluded in the image. To this end, we present MonoLayout, a deep neural network for realtime amodal scene layout estimation from a single image. We represent scene layout as a multi-channel semantic occupancy grid, and leverage adversarial feature learning to “hallucinate" plausible completions for occluded image parts. We extend several state-of-the-art approaches for road-layout estimation and vehicle occupancy estimation in bird’s eye view to the amodal setup and thoroughly evaluate against them. By leveraging temporal sensor fusion to generate training labels, we significantly outperform current art over a number of datasets.

Abstract

This paper presents a new system to obtain dense object reconstructions along with 6-DoF poses from a single image. Geared towards high fidelity reconstruction, several recent approaches leverage implicit surface representations and deep neural networks to estimate a 3D mesh of an object, given a single image. However, all such approaches recover only the shape of an object; the reconstruction is often in a canonical frame, unsuitable for downstream robotics tasks. To this end, we leverage recent advances in differentiable rendering (in particular, rasterization) to close the loop with 3D reconstruction in camera frame. We demonstrate that our approach—dubbed reconstruct, rasterize and backprop (RRB)—achieves significantly lower pose estimation errors compared to prior art, and is able to recover dense object shapes and poses from imagery. We further extend our results to an (offline) setup, where we demonstrate a dense monocular object-centric egomotion estimation system.

Abstract

This paper introduces the Omnidirectional Tractable Three Module Robot for traversing inside complex pipe networks. The robot consists of three omnidirectional modules fixed 120 apart circumferentially which can rotate about their axis allowing holonomic motion of the robot. Holonomic motion enables the robot to overcome motion singularity when negotiating T-junctions and further allows the robot to arrive in a preferred orientation while taking turns inside a pipe. The singularity region while negotiating T-junctions is analyzed to formulate the geometry of the region. The design and motion capabilities are validated by conducting simulations in MSC ADAMS on a simplified lumped-model of the robot

Abstract

In this paper, we tackle the problem of multibody SLAM from a monocular camera. The term multibody, implies that we track the motion of the camera, as well as that of other dynamic participants in the scene. The quintessential challenge in dynamic scenes is unobservability: it is not possible to unambiguously triangulate a moving object from a moving monocular camera. Existing approaches solve restricted variants of the problem, but the solutions suffer relative scale ambiguity (i.e., a family of infinitely many solutions exist for each pair of motions in the scene). We solve this rather intractable problem by leveraging single-view metrology, advances in deep learning, and category-level shape estimation. We propose a multi posegraph optimization formulation, to resolve the relative and absolute scale factor ambiguities involved. This optimization helps us reduce the average error in trajectories of multiple bodies over real-world datasets, such as KITTI [1]. To the best of our knowledge, our method is the first practical monocular multi-body SLAM system to perform dynamic multi-object and ego localization in a unified framework in metric scale.

Abstract

The probabilistic velocity obstacle (PVO) extends the concept of velocity obstacle (VO) to work in uncertain dynamic environments. In this paper, we show how a robust model predictive control (MPC) with PVO constraints under non-parametric uncertainty can be made computationally tractable. At the core of our formulation is a novel yet simple interpretation of our robust MPC as a problem of matching the distribution of PVO with a certain desired distribution. To this end, we propose two methods. Our first baseline method is based on approximating the distribution of PVO with a Gaussian Mixture Model (GMM) and subsequently performing distribution matching using Kullback Leibler (KL) divergence metric. Our second formulation is based on the possibility of representing arbitrary distributions as functions in Reproducing Kernel Hilbert Space (RKHS). We use this foundation to interpret our robust MPC as a problem of minimizing the distance between the desired distribution and the distribution of the PVO in the RKHS. Both the RKHS and GMM based formulation can work with any uncertainty distribution and thus allowing us to relax the prevalent Gaussian assumption in the existing works. We validate our formulation by taking an example of 2D navigation of quadrotors with a realistic noise model for perception and ego-motion uncertainty. In particular, we present a systematic comparison between the GMM and the RKHS approach and show that while both approaches can produce safe trajectories, the former is highly conservative and leads to poor tracking and control costs. Furthermore, RKHS based approach gives better computational times that are up to one order of magnitude lesser than the computation time of the GMM based approach.

Abstract

Existing deep learning based visual servoing approaches regress the relative camera pose between a pair of images. Therefore, they require a huge amount of training data and sometimes fine-tuning for adaptation to a novel scene. Furthermore, current approaches do not consider underlying geometry of the scene and rely on direct estimation of camera pose. Thus, inaccuracies in prediction of the camera pose, especially for distant goals, lead to a degradation in the servoing performance. In this paper, we propose a two-fold solution: (i) We consider optical flow as our visual features, which are predicted using a deep neural network. (ii) These flow features are then systematically integrated with depth estimates provided by another neural network using interaction matrix. We further present an extensive benchmark in a photo-realistic 3D simulation across diverse scenes to study the convergence and generalisation of visual servoing approaches. We show convergence for over 3m and 40 degrees while maintaining precise positioning of under 2cm and 1 degree on our challenging benchmark where the existing approaches that are unable to converge for majority of scenarios for over 1.5m and 20 degrees. Furthermore, we also evaluate our approach for a real scenario on an aerial robot. Our approach generalizes to novel scenarios producing precise and robust servoing performance for 6 degrees of freedom positioning tasks with even large camera transformations without any retraining or fine-tuning.

Abstract

Autonomous cars and fixed-wing aerial vehicles have the so-called non-holonomic kinematics which non-linearly maps control input to states. As a result, trajectory optimization with such a motion model becomes highly non-linear and nonconvex. In this paper, we improve the computational tractability of non-holonomic trajectory optimization by reformulating it in terms of a set of bi-convex cost and constraint functions along with a non-linear penalty. The bi-convex part acts as a relaxation for the non-holonomic trajectory optimization while the residual of the penalty dictates how well its output obeys the non-holonomic behavior. We adopt an alternating minimization approach for solving the reformulated problem and show that it naturally leads to the replacement of the challenging nonlinear penalty with a globally valid convex surrogate. Along with the common cost functions modeling goal-reaching, trajectory smoothness, etc., the proposed optimizer can also accommodate a class of non-linear costs for modeling goal-sets, while retaining the bi-convex structure. We benchmark the proposed optimizer against off-the-shelf solvers implementing sequential quadratic programming and interior-point methods and show that it produces solutions with similar or better cost as the former while significantly outperforming the latter. Furthermore, as compared to both off-the-shelf solvers, the proposed optimizer achieves more than 20x reduction in computation time.