We consider sparse representations of signals from redundant dictionaries which are unions of several orthonormal bases. The spark introduced by Donoho and Elad plays an important role in sparse representations. However, numerical computations of spa
rks are generally combinatorial. For unions of several orthonormal bases, two lower bounds on the spark via the mutual coherence were established in previous work. We constructively prove that both of them are tight. Our main results give positive answers to Gribonval and Nielsens open problem on sparse representations in unions of orthonormal bases. Constructive proofs rely on a family of mutually unbiased bases which first appears in quantum information theory.
This paper addresses the fast replanning problem in dynamic environments with moving obstacles. Since for randomly moving obstacles the future states are unpredictable, the proposed method, called SMARRT, reacts to obstacle motions and revises the pa
th in real-time based on the current interfering obstacle state (i.e., position and velocity). SMARRT is fast and efficient and performs collision checking only on the partial path segment close to the robot within a feasibility checking horizon. If the path is infeasible, then tree parts associated with the path inside the horizon are pruned while maintaining the maximal tree structure of already-explored regions. Then, a multi-resolution utility map is created to capture the environmental information used to compute the replanning utility for each cell on the multi-scale tiling. A hierarchical searching method is applied on the map to find the sampling cell efficiently. Finally, uniform samples are drawn within the sampling cell for fast replanning. The SMARRT method is validated via simulation runs, and the results are evaluated in comparison to four existing methods. The SMARRT method yields significant improvements in travel time, replanning time, and success rate compared against the existing methods.
This paper presents a deep-learning based CPP algorithm, called Coverage Path Planning Network (CPPNet). CPPNet is built using a convolutional neural network (CNN) whose input is a graph-based representation of the occupancy grid map while its output
is an edge probability heat graph, where the value of each edge is the probability of belonging to the optimal TSP tour. Finally, a greedy search is used to select the final optimized tour. CPPNet is trained and comparatively evaluated against the TSP tour. It is shown that CPPNet provides near-optimal solutions while requiring significantly less computational time, thus enabling real-time coverage path planning in partially unknown and dynamic environments.
In this paper, we develop a non-uniform sampling approach for fast and efficient path planning of autonomous vehicles. The approach uses a novel non-uniform partitioning scheme that divides the area into obstacle-free convex cells. The partitioning r
esults in large cells in obstacle-free areas and small cells in obstacle-dense areas. Subsequently, the boundaries of these cells are used for sampling; thus significantly reducing the burden of uniform sampling. When compared with a standard uniform sampler, this smart sampler significantly 1) reduces the size of the sampling space while providing completeness and optimality guarantee, 2) provides sparse sampling in obstacle-free regions and dense sampling in obstacle-rich regions to facilitate faster exploration, and 3) eliminates the need for expensive collision-checking with obstacles due to the convexity of the cells. This sampling framework is incorporated into the RRT* path planner. The results show that RRT* with the non-uniform sampler gives a significantly better convergence rate and smaller memory footprint as compared to RRT* with a uniform sampler.
Measuring similarity between two images often requires performing complex reasoning along different axes (e.g., color, texture, or shape). Insights into what might be important for measuring similarity can can be provided by annotated attributes, but
prior work tends to view these annotations as complete, resulting in them using a simplistic approach of predicting attributes on single images, which are, in turn, used to measure similarity. However, it is impractical for a dataset to fully annotate every attribute that may be important. Thus, only representing images based on these incomplete annotations may miss out on key information. To address this issue, we propose the Pairwise Attribute-informed similarity Network (PAN), which breaks similarity learning into capturing similarity conditions and relevance scores from a joint representation of two images. This enables our model to identify that two images contain the same attribute, but can have it deemed irrelevant (e.g., due to fine-grained differences between them) and ignored for measuring similarity between the two images. Notably, while prior methods of using attribute annotations are often unable to outperform prior art, PAN obtains a 4-9% improvement on compatibility prediction between clothing items on Polyvore Outfits, a 5% gain on few shot classification of images using Caltech-UCSD Birds (CUB), and over 1% boost to Recall@1 on In-Shop Clothes Retrieval. Implementation available at https://github.com/samarth4149/PAN
We study a Rabi type Hamiltonian system in which a qubit and a d-level quantum system (qudit) are coupled through a common resonator. In the weak and strong coupling limits the spectrum is analysed through suitable perturbative schemes. The analysis
show that the presence of the multilevels of the qudit effectively enhance the qubit-qudit interaction. The ground state of the strongly coupled system is a found of Greenberger-Horne-Zeilinger (GHZ) type. Therefore, despite the qubit-qudit strong coupling, the nature of the specific tripartite entanglement of the GHZ state suppress the bipartite entanglement. We analyze the system dynamics under quenching and adiabatic switching of the qubit-resonator and qudit-resonator couplings. In the quench case, we found that the non-adiabatic generations of photons in the resonator is enhanced by the number of levels in the qudit. The adiabatic control represents a possible route for preparation of GHZ states. Our analysis provides relevant information for future studies on coherent state transfer in qubit-qudit systems.
This paper presents a novel algorithm, called MRRT, which uses multiple rapidly-exploring random trees for fast online replanning of autonomous vehicles in dynamic environments with moving obstacles. The proposed algorithm is built upon the RRT algor
ithm with a multi-tree structure. At the beginning, the RRT algorithm is applied to find the initial solution based on partial knowledge of the environment. Then, the robot starts to execute this path. At each iteration, the new obstacle configurations are collected by the robots sensor and used to replan the path. This new information can come from unknown static obstacles (e.g., seafloor layout) as well as moving obstacles. Then, to accommodate the environmental changes, two procedures are adopted: 1) edge pruning, and 2) tree regrowing. Specifically, the edge pruning procedure checks the collision status through the tree and only removes the invalid edges while maintaining the tree structure of already-explored regions. Due to removal of invalid edges, the tree could be broken into multiple disjoint trees. As such, the RRT algorithm is applied to regrow the trees. Specifically, a sample is created randomly and joined to all the disjoint trees in its local neighborhood by connecting to the nearest nodes. Finally, a new solution is found for the robot. The advantages of the proposed MRRT algorithm are as follows: i) retains the maximal tree structure by only pruning the edges which collide with the obstacles, ii) guarantees probabilistic completeness, and iii) is computational efficient for fast replanning since all disjoint trees are maintained for future connections and expanded simultaneously.
Effective human-vehicle collaboration requires an appropriate un-derstanding of vehicle behavior for safety and trust. Improvingon our prior work by adding a future prediction module, we in-troduce our framework, calledAutoPreview, to enable humans t
opreview autopilot behaviors prior to direct interaction with thevehicle. Previewing autopilot behavior can help to ensure smoothhuman-vehicle collaboration during the initial exploration stagewith the vehicle. To demonstrate its practicality, we conducted acase study on human-vehicle collaboration and built a prototypeof our framework with the CARLA simulator. Additionally, weconducted a between-subject control experiment (n=10) to studywhether ourAutoPreviewframework can provide a deeper under-standing of autopilot behavior compared to direct interaction. Ourresults suggest that theAutoPreviewframework does, in fact, helpusers understand autopilot behavior and develop appropriate men-tal models
The behavior of self driving cars may differ from people expectations, (e.g. an autopilot may unexpectedly relinquish control). This expectation mismatch can cause potential and existing users to distrust self driving technology and can increase the
likelihood of accidents. We propose a simple but effective framework, AutoPreview, to enable consumers to preview a target autopilot potential actions in the real world driving context before deployment. For a given target autopilot, we design a delegate policy that replicates the target autopilot behavior with explainable action representations, which can then be queried online for comparison and to build an accurate mental model. To demonstrate its practicality, we present a prototype of AutoPreview integrated with the CARLA simulator along with two potential use cases of the framework. We conduct a pilot study to investigate whether or not AutoPreview provides deeper understanding about autopilot behavior when experiencing a new autopilot policy for the first time. Our results suggest that the AutoPreview method helps users understand autopilot behavior in terms of driving style comprehension, deployment preference, and exact action timing prediction.
This paper provides a new avenue for exploiting deep neural networks to improve physics-based simulation. Specifically, we integrate the classic Lagrangian mechanics with a deep autoencoder to accelerate elastic simulation of deformable solids. Due t
o the inertia effect, the dynamic equilibrium cannot be established without evaluating the second-order derivatives of the deep autoencoder network. This is beyond the capability of off-the-shelf automatic differentiation packages and algorithms, which mainly focus on the gradient evaluation. Solving the nonlinear force equilibrium is even more challenging if the standard Newtons method is to be used. This is because we need to compute a third-order derivative of the network to obtain the variational Hessian. We attack those difficulties by exploiting complex-step finite difference, coupled with reverse automatic differentiation. This strategy allows us to enjoy the convenience and accuracy of complex-step finite difference and in the meantime, to deploy complex-value perturbations as collectively as possible to save excessive network passes. With a GPU-based implementation, we are able to wield deep autoencoders (e.g., $10+$ layers) with a relatively high-dimension latent space in real-time. Along this pipeline, we also design a sampling network and a weighting network to enable emph{weight-varying} Cubature integration in order to incorporate nonlinearity in the model reduction. We believe this work will inspire and benefit future research efforts in nonlinearly reduced physical simulation problems.
