Collaborative intelligence is a new paradigm for efficient deployment of deep neural networks across the mobile-cloud infrastructure. By dividing the network between the mobile and the cloud, it is possible to distribute the computational workload such that the overall energy and/or latency of the system is minimized. However, this necessitates sending deep feature data from the mobile to the cloud in order to perform inference. In this work, we examine the differences between the deep feature data and natural image data, and propose a simple and effective near-lossless deep feature compressor. The proposed method achieves up to 5% bit rate reduction compared to HEVC-Intra and even more against other popular image codecs. Finally, we suggest an approach for reconstructing the input image from compressed deep features in the cloud, that could serve to supplement the inference performed by the deep model.
Apr 11 2018 cs.GT
In practical crowdsourcing systems such as Amazon Mechanical Turk, posted pricing is widely used due to its simplicity, where a task requester publishes a pricing rule a priori, on which workers decide whether to accept and perform the task or not, and are often paid according to the quality of their effort. One of the key ingredients of a good posted pricing lies in how to recruit more high-quality workers with less budget, for which the following two schemes are considered: (i) personalized pricing by profiling users in terms of their quality and cost, and (ii) additional bonus payment offered for more qualified task completion. Despite their potential benefits in crowdsourced pricing, it has been under-explored how much gain each or both of personalization and bonus payment actually provides to the requester. In this paper, we study four possible combinations of posted pricing made by pricing with/without personalization and bonus. We aim at analytically quantifying when and how much such two ideas contribute to the requester's utility. To this end, we first derive the optimal personalized and common pricing schemes and analyze their computational tractability. Next, we quantify the gap in the utility between with and without bonus payment in both pricing schemes. We analytically prove that the impact of bonus is negligible significantly marginal in personalized pricing, whereas crucial in common pricing. Finally, we study the notion of Price of Agnosticity that quantifies the utility gap between personalized and common pricing policies. This implies that a complex personalized pricing with privacy concerns can be replaced by a simple common pricing with bonus. We validate our analytical findings through extensive simulations and real experiments done in Amazon Mechanical Turk, and provide additional implications that are useful in designing a pricing policy.
Apr 02 2018 cs.CL
Neural machine translation (NMT) has been a new paradigm in machine translation, and the attention mechanism has become the dominant approach with the state-of-the-art records in many language pairs. While there are variants of the attention mechanism, all of them use only temporal attention where one scalar value is assigned to one context vector corresponding to a source word. In this paper, we propose a fine-grained (or 2D) attention mechanism where each dimension of a context vector will receive a separate attention score. In experiments with the task of En-De and En-Fi translation, the fine-grained attention method improves the translation quality in terms of BLEU score. In addition, our alignment analysis reveals how the fine-grained attention mechanism exploits the internal structure of context vectors.
We consider a scenario consisting of a set of heterogeneous mobile agents located at a depot, and a set of tasks dispersed over a geographic area. The agents are partitioned into different types. The tasks are partitioned into specialized tasks that can only be done by agents of a certain type, and generic tasks that can be done by any agent. The distances between each pair of tasks are specified, and satisfy the triangle inequality. Given this scenario, we address the problem of allocating these tasks among the available agents (subject to type compatibility constraints) while minimizing the maximum cost to tour the allocation by any agent and return to the depot. This problem is NP-hard, and we give a three phase algorithm to solve this problem that provides 5-factor approximation, regardless of the total number of agents and the number of agents of each type. We also show that in the special case where there is only one agent of each type, the algorithm has an approximation factor of 4.
Mar 05 2018 cs.ET
Devices in a beacon-enabled network use slotted CSMA/CA to contend for channel usage. Each node in the network competes for the channels when ready to transmit data. The slotted CSMA/CA mechanism based on the super-frame structure fairly provides communication chance for each node and makes a reasonable usage of the available energy in beacon-enabled Zigbee networks. When wireless nano-sensor nodes are implanted into the target human body area for detecting disease symptoms or virus existence, each node also requires a similar characteristic in channel sharing and in the transmission of event-driven data with a short length. In this paper, we suggest a wireless network model with nano-sensor nodes for the in-body application. We propose a novel MAC protocol derived from an existing Zigbee MAC protocol scheme and analyze the performance of energy usage with variable super-frame durations and packet sizes.
Feb 13 2018 cs.CV
Recent studies have shown that the efficiency of deep neural networks in mobile applications can be significantly improved by distributing the computational workload between the mobile device and the cloud. This paradigm, termed collaborative intelligence, involves communicating feature data between the mobile and the cloud. The efficiency of such approach can be further improved by lossy compression of feature data, which has not been examined to date. In this work we focus on collaborative object detection and study the impact of both near-lossless and lossy compression of feature data on its accuracy. We also propose a strategy for improving the accuracy under lossy feature compression. Experiments indicate that using this strategy, the communication overhead can be reduced by up to 70% without sacrificing accuracy.
We propose a variant of Ising model, called the Seeded Ising Model, to model probabilistic nature of human iris templates. This model is an Ising model in which the values at certain lattice points are held fixed throughout Ising model evolution. Using this we show how to reconstruct the full iris template from partial information, and we show that about 1/6 of the given template is needed to recover almost all information content of the original one in the sense that the resulting Hamming distance is well within the range to assert correctly the identity of the subject. This leads us to propose the concept of effective statistical degree of freedom of iris templates and show it is about 1/6 of the total number of bits. In particular, for a template of $2048$ bits, its effective statistical degree of freedom is about $342$ bits, which coincides very well with the degree of freedom computed by the completely different method proposed by Daugman.
This paper proposes the continuous semantic topic embedding model (CSTEM) which finds latent topic variables in documents using continuous semantic distance function between the topics and the words by means of the variational autoencoder(VAE). The semantic distance could be represented by any symmetric bell-shaped geometric distance function on the Euclidean space, for which the Mahalanobis distance is used in this paper. In order for the semantic distance to perform more properly, we newly introduce an additional model parameter for each word to take out the global factor from this distance indicating how likely it occurs regardless of its topic. It certainly improves the problem that the Gaussian distribution which is used in previous topic model with continuous word embedding could not explain the semantic relation correctly and helps to obtain the higher topic coherence. Through the experiments with the dataset of 20 Newsgroup, NIPS papers and CNN/Dailymail corpus, the performance of the recent state-of-the-art models is accomplished by our model as well as generating topic embedding vectors which makes possible to observe where the topic vectors are embedded with the word vectors in the real Euclidean space and how the topics are related each other semantically.
In this work, we present an efficient framework to generate a motion trajectory of a robot that has a high degree of freedom (e.g., a humanoid robot). High-dimensionality of the robot configuration space often leads to difficulties in utilizing the widely-used motion planning algorithms because the volume of the decision space increases exponentially with the number of dimensions. To handle complications arising from the large decision space, and to solve a corresponding motion planning problem efficiently, two key concepts were adopted. First, the Gaussian process latent variable model (GP-LVM) was utilized for low-dimensional representation of the original configuration space. Second, an approximate inference algorithm was used, exploiting through the duality between control and estimation, to explore the decision space and to compute a high-quality motion trajectory of the robot. Utilizing the GP-LVM and the duality between control and estimation, we construct a fully probabilistic generative model with which we transform a high-dimensional motion planning problem into a tractable inference problem. Finally, we compute the optimal motion trajectory via an approximate inference algorithm based on a variant of the particle filter. Numerical experiments are presented to demonstrate the applicability and validity of the proposed approach. The resulting motions can be viewed in the supplemental video. ( https://youtu.be/DsZ1afN6pTY )
Image and video compression has traditionally been tailored to human vision. However, modern applications such as visual analytics and surveillance rely on computers seeing and analyzing the images before (or instead of) humans. For these applications, it is important to adjust compression to computer vision. In this paper we present a bit allocation and rate control strategy that is tailored to object detection. Using the initial convolutional layers of a state-of-the-art object detector, we create an importance map that can guide bit allocation to areas that are important for object detection. The proposed method enables bit rate savings of 7% or more compared to default HEVC, at the equivalent object detection rate.
Oct 31 2017 cs.CV
Finding faces in images is one of the most important tasks in computer vision, with applications in biometrics, surveillance, human-computer interaction, and other areas. In our earlier work, we demonstrated that it is possible to tell whether or not an image contains a face by only examining the HEVC syntax, without fully reconstructing the image. In the present work we move further in this direction by showing how to localize faces in HEVC-coded images, without full reconstruction. We also demonstrate the benefits that such approach can have in privacy-friendly face localization.
In Crowdfunding platforms, people turn their prototype ideas into real products by raising money from the crowd, or invest in someone else's projects. In reward-based crowdfunding platforms such as Kickstarter and Indiegogo, selecting accurate reward delivery duration becomes crucial for creators, backers, and platform providers to keep the trust between the creators and the backers, and the trust between the platform providers and users. According to Kickstarter, 35% backers did not receive rewards on time. Unfortunately, little is known about on-time and late reward delivery projects, and there is no prior work to estimate reward delivery duration. To fill the gap, in this paper, we (i) extract novel features that reveal latent difficulty levels of project rewards; (ii) build predictive models to identify whether a creator will deliver all rewards in a project on time or not; and (iii) build a regression model to estimate accurate reward delivery duration (i.e., how long it will take to produce and deliver all the rewards). Experimental results show that our models achieve good performance -- 82.5% accuracy, 78.1 RMSE, and 0.108 NRMSE at the first 5% of the longest reward delivery duration.
Sep 18 2017 cs.CV
Millions of surveillance cameras operate at 24x7 generating huge amount of visual data for processing. However, retrieval of important activities from such a large data can be time consuming. Thus, researchers are working on finding solutions to present hours of visual data in a compressed, but meaningful way. Video synopsis is one of the ways to represent activities using relatively shorter duration clips. So far, two main approaches have been used by researchers to address this problem, namely synopsis by tracking moving objects and synopsis by clustering moving objects. Synopses outputs, mainly depend on tracking, segmenting, and shifting of moving objects temporally as well as spatially. In many situations, tracking fails, thus produces multiple trajectories of the same object. Due to this, the object may appear and disappear multiple times within the same synopsis output, which is misleading. This also leads to discontinuity and often can be confusing to the viewer of the synopsis. In this paper, we present a new approach for generating compressed video synopsis by grouping tracklets of moving objects. Grouping helps to generate a synopsis where chronologically related objects appear together with meaningful spatio-temporal relation. Our proposed method produces continuous, but a less confusing synopses when tested on publicly available dataset videos as well as in-house dataset videos.
Sep 12 2017 cs.CV
Image and video analytics are being increasingly used on a massive scale. Not only is the amount of data growing, but the complexity of the data processing pipelines is also increasing, thereby exacerbating the problem. It is becoming increasingly important to save computational resources wherever possible. We focus on one of the poster problems of visual analytics -- face detection -- and approach the issue of reducing the computation by asking: Is it possible to detect a face without full image reconstruction from the High Efficiency Video Coding (HEVC) bitstream? We demonstrate that this is indeed possible, with accuracy comparable to conventional face detection, by training a Convolutional Neural Network on the output of the HEVC entropy decoder.
Autism spectrum disorder (ASD) is regarded as a brain disease with globally disrupted neuronal networks. Even though fMRI studies have revealed abnormal functional connectivity in ASD, they have not reached a consensus of the disrupted patterns. Here, a deep learning-based feature extraction method identifies multivariate and nonlinear functional connectivity patterns of ASD. Resting-state fMRI data of 972 subjects (465 ASD 507 normal controls) acquired from the Autism Brain Imaging Data Exchange were used. A functional connectivity matrix of each subject was generated using 90 predefined brain regions. As a data-driven feature extraction method without prior knowledge such as subjects diagnosis, variational autoencoder (VAE) summarized the functional connectivity matrix into 2 features. Those feature values of ASD patients were statistically compared with those of controls. A feature was significantly different between ASD and normal controls. The extracted features were visualized by VAE-based generator which can produce virtual functional connectivity matrices. The ASD-related feature was associated with frontoparietal connections, interconnections of the dorsal medial frontal cortex and corticostriatal connections. It also showed a trend of negative correlation with full-scale IQ. A data-driven feature extraction based on deep learning could identify complex patterns of functional connectivity of ASD. This approach will help discover complex patterns of abnormalities in brain connectivity in various brain disorders.
Jul 05 2017 cs.GT
This paper addresses information-based sensing point selection from a set of possible sensing locations, which determines a set of measurement points maximizing the mutual information between the sensor measurements and the variables of interest. A potential game approach has been applied to addressing distributed implementation of decision making for cooperative sensor planning. When a sensor network involves a large number of sensing agents, the local utility function for a sensing agent is hard to compute, because the local utility function depends on the other agents' decisions while each sensing agent is inherently faced with limitations in both its communication and computational capabilities. Accordingly, a local utility function for each agent should be approximated to accommodate limitations in information gathering and processing. We propose an approximation method for a local utility function using only a portion of the decisions of other agents. The part of the decisions that each agent considers is called the neighboring set for the agent. The error induced by the approximation is also analyzed, and to keep the error small we propose a neighbor selection algorithm that chooses the neighbor set for each agent in a greedy way. The selection algorithm is based on the correlation information between one agent's measurement selection and the other agents' selections. Futhermore, we show that a game with an approximate local utility function has an $\epsilon$-equilibrium and the set of the equilibria include the Nash equilibrium of the original potential game. We demonstrate the validity of our approximation method through two numerical examples on simplified weather forecasting and multi-target tracking.
Jun 21 2017 cs.CL
Electronic health records (EHRs) contain important clinical information about patients. Efficient and effective use of this information could supplement or even replace manual chart review as a means of studying and improving the quality and safety of healthcare delivery. However, some of these clinical data are in the form of free text and require pre-processing before use in automated systems. A common free text data source is radiology reports, typically dictated by radiologists to explain their interpretations. We sought to demonstrate machine learning classification of computed tomography (CT) imaging reports into binary outcomes, i.e. positive and negative for fracture, using regular text classification and classifiers based on topic modeling. Topic modeling provides interpretable themes (topic distributions) in reports, a representation that is more compact than the commonly used bag-of-words representation and can be processed faster than raw text in subsequent automated processes. We demonstrate new classifiers based on this topic modeling representation of the reports. Aggregate topic classifier (ATC) and confidence-based topic classifier (CTC) use a single topic that is determined from the training dataset based on different measures to classify the reports on the test dataset. Alternatively, similarity-based topic classifier (STC) measures the similarity between the reports' topic distributions to determine the predicted class. Our proposed topic modeling-based classifier systems are shown to be competitive with existing text classification techniques and provides an efficient and interpretable representation.
Jun 20 2017 cs.DL
Precision medicine and health requires the characterization and phenotyping of biological systems and patient datasets using a variety of data formats. This scenario mandates the centralization of various tools and resources in a unified platform to render them Findable, Accessible, Interoperable, and Reusable (FAIR Principles). Leveraging these principles, Aztec provides the scientific community with a new platform that promotes a long-term, sustainable ecosystem of biomedical research software. Aztec is available at https://aztec.bio and its source code is hosted at https://github.com/BD2K-Aztec.
Apr 26 2017 cs.GR
To watch 360\deg videos on normal 2D displays, we need to project the selected part of the 360\deg image onto the 2D display plane. In this paper, we propose a fully-automated framework for generating content-aware 2D normal-view perspective videos from 360\deg videos. Especially, we focus on the projection step preserving important image contents and reducing image distortion. Basically, our projection method is based on Pannini projection model. At first, the salient contents such as linear structures and salient regions in the image are preserved by optimizing the single Panini projection model. Then, the multiple Panini projection models at salient regions are interpolated to suppress image distortion globally. Finally, the temporal consistency for image projection is enforced for producing temporally stable normal-view videos. Our proposed projection method does not require any user-interaction and is much faster than previous content-preserving methods. It can be applied to not only images but also videos taking the temporal consistency of projection into account. Experiments on various 360\deg videos show the superiority of the proposed projection method quantitatively and qualitatively.
For effective treatment of Alzheimer disease (AD), it is important to identify subjects who are most likely to exhibit rapid cognitive decline. Herein, we developed a novel framework based on a deep convolutional neural network which can predict future cognitive decline in mild cognitive impairment (MCI) patients using flurodeoxyglucose and florbetapir positron emission tomography (PET). The architecture of the network only relies on baseline PET studies of AD and normal subjects as the training dataset. Feature extraction and complicated image preprocessing including nonlinear warping are unnecessary for our approach. Accuracy of prediction (84.2%) for conversion to AD in MCI patients outperformed conventional feature-based quantification approaches. ROC analyses revealed that performance of CNN-based approach was significantly higher than that of the conventional quantification methods (p < 0.05). Output scores of the network were strongly correlated with the longitudinal change in cognitive measurements. These results show the feasibility of deep learning as a tool for predicting disease outcome using brain images.
Jan 24 2017 cs.SY
In this paper, cyber attack detection and isolation is studied on a network of UAVs in a formation flying setup. As the UAVs communicate to reach consensus on their states while making the formation, the communication network among the UAVs makes them vulnerable to a potential attack from malicious adversaries. Two types of attacks pertinent to a network of UAVs have been considered: a node attack on the UAVs and a deception attack on the communication between the UAVs. UAVs formation control presented using a consensus algorithm to reach a pre-specified formation. A node and a communication path deception cyber attacks on the UAV's network are considered with their respective models in the formation setup. For these cyber attacks detection, a bank of Unknown Input Observer (UIO) based distributed fault detection scheme proposed to detect and identify the compromised UAV in the formation. A rule based on the residuals generated using the bank of UIOs are used to detect attacks and identify the compromised UAV in the formation. Further, an algorithm developed to remove the faulty UAV from the network once an attack detected and the compromised UAV isolated while maintaining the formation flight with a missing UAV node.
This paper addresses path planning of an unmanned aerial vehicle (UAV) with remote sensing capabilities (or wireless communication capabilities). The goal of the path planning is to find a minimum-flight-time closed tour of the UAV visiting all executable areas of given remote sensing and communication tasks; in order to incorporate the nonlinear vehicle dynamics, this problem is regarded as a dynamically-constrained traveling salesman problem with neighborhoods. To obtain a close-to-optimal solution for the path planning in a tractable manner, a sampling-based roadmap algorithm that embeds an optimal control-based path generation process is proposed. The algorithm improves the computational efficiency by reducing numerical computations required for optimizing inefficient local paths, and by extracting additional information from a roadmap of a fixed number of samples. Comparative numerical simulations validate the efficiency of the presented algorithm in reducing computation time and improving the solution quality compared to previous roadmap-based planning methods.
This work presents a multiscale framework to solve an inverse reinforcement learning (IRL) problem for continuous-time/state stochastic systems. We take advantage of a diffusion wavelet representation of the associated Markov chain to abstract the state space. This not only allows for effectively handling the large (and geometrically complex) decision space but also provides more interpretable representations of the demonstrated state trajectories and also of the resulting policy of IRL. In the proposed framework, the problem is divided into the global and local IRL, where the global approximation of the optimal value functions are obtained using coarse features and the local details are quantified using fine local features. An illustrative numerical example on robot path control in a complex environment is presented to verify the proposed method.
This work presents a multiscale framework to solve a class of stochastic optimal control problems in the context of robot motion planning and control in a complex environment. In order to handle complications resulting from a large decision space and complex environmental geometry, two key concepts are adopted: (a) a diffusion wavelet representation of the Markov chain for hierarchical abstraction of the state space; and (b) a desirability function-based representation of the Markov decision process (MDP) to efficiently calculate the optimal policy. In the proposed framework, a global plan that compressively takes into account the long time/length-scale state transition is first obtained by approximately solving an MDP whose desirability function is represented by coarse scale bases in the hierarchical abstraction. Then, a detailed local plan is computed by solving an MDP that considers wavelet bases associated with a focused region of the state space, guided by the global plan. The resulting multiscale plan is utilized to finally compute a continuous-time optimal control policy within a receding horizon implementation. Two numerical examples are presented to demonstrate the applicability and validity of the proposed approach.
Oct 06 2016 cs.RO
Informative path planning (IPP) is used to design paths for robotic sensor platforms to extract the best/maximum possible information about a quantity of interest while operating under a set of constraints, such as the dynamic feasibility of vehicles. The key challenges of IPP are the strong coupling in multiple layers of decisions: the selection of locations to visit, the allocation of sensor platforms to those locations; and the processing of the gathered information along the paths. This paper presents a systematic procedure for IPP and environmental mapping using multiple UAV sensor platforms. It (a) selects the best locations to observe, (b) calculates the cost and finds the best paths for each UAV, and (c) estimates the measurement value within a given region using the Gaussian process (GP) regression framework. An illustrative example of RF intensity field mapping is presented to demonstrate the validity and applicability of the proposed approach.
Current language models have a significant limitation in the ability to encode and decode factual knowledge. This is mainly because they acquire such knowledge from statistical co-occurrences although most of the knowledge words are rarely observed. In this paper, we propose a Neural Knowledge Language Model (NKLM) which combines symbolic knowledge provided by the knowledge graph with the RNN language model. By predicting whether the word to generate has an underlying fact or not, the model can generate such knowledge-related words by copying from the description of the predicted fact. In experiments, we show that the NKLM significantly improves the performance while generating a much smaller number of unknown words.
A homogeneous set of a graph $G$ is a set $X$ of vertices such that $2\le \lvert X\rvert <\lvert V(G)\rvert$ and no vertex in $V(G)-X$ has both a neighbor and a non-neighbor in $X$. A graph is prime if it has no homogeneous set. We present an algorithm to decide whether a class of graphs given by a finite set of forbidden induced subgraphs contains infinitely many non-isomorphic prime graphs.
Jul 05 2016 cs.CL
We first observe a potential weakness of continuous vector representations of symbols in neural machine translation. That is, the continuous vector representation, or a word embedding vector, of a symbol encodes multiple dimensions of similarity, equivalent to encoding more than one meaning of the word. This has the consequence that the encoder and decoder recurrent networks in neural machine translation need to spend substantial amount of their capacity in disambiguating source and target words based on the context which is defined by a source sentence. Based on this observation, in this paper we propose to contextualize the word embedding vectors using a nonlinear bag-of-words representation of the source sentence. Additionally, we propose to represent special tokens (such as numbers, proper nouns and acronyms) with typed symbols to facilitate translating those words that are not well-suited to be translated via continuous vectors. The experiments on En-Fr and En-De reveal that the proposed approaches of contextualization and symbolization improves the translation quality of neural machine translation systems significantly.
This paper studies the problem of parameter learning in probabilistic graphical models having latent variables, where the standard approach is the expectation maximization algorithm alternating expectation (E) and maximization (M) steps. However, both E and M steps are computationally intractable for high dimensional data, while the substitution of one step to a faster surrogate for combating against intractability can often cause failure in convergence. We propose a new learning algorithm which is computationally efficient and provably ensures convergence to a correct optimum. Its key idea is to run only a few cycles of Markov Chains (MC) in both E and M steps. Such an idea of running incomplete MC has been well studied only for M step in the literature, called Contrastive Divergence (CD) learning. While such known CD-based schemes find approximated gradients of the log-likelihood via the mean-field approach in E step, our proposed algorithm does exact ones via MC algorithms in both steps due to the multi-time-scale stochastic approximation theory. Despite its theoretical guarantee in convergence, the proposed scheme might suffer from the slow mixing of MC in E step. To tackle it, we also propose a hybrid approach applying both mean-field and MC approximation in E step, where the hybrid approach outperforms the bare mean-field CD scheme in our experiments on real-world datasets.
May 03 2016 cs.LG
Since microRNAs (miRNAs) play a crucial role in post-transcriptional gene regulation, miRNA identification is one of the most essential problems in computational biology. miRNAs are usually short in length ranging between 20 and 23 base pairs. It is thus often difficult to distinguish miRNA-encoding sequences from other non-coding RNAs and pseudo miRNAs that have a similar length, and most previous studies have recommended using precursor miRNAs instead of mature miRNAs for robust detection. A great number of conventional machine-learning-based classification methods have been proposed, but they often have the serious disadvantage of requiring manual feature engineering, and their performance is limited as well. In this paper, we propose a novel miRNA precursor prediction algorithm, deepMiRGene, based on recurrent neural networks, specifically long short-term memory networks. deepMiRGene automatically learns suitable features from the data themselves without manual feature engineering and constructs a model that can successfully reflect structural characteristics of precursor miRNAs. For the performance evaluation of our approach, we have employed several widely used evaluation metrics on three recent benchmark datasets and verified that deepMiRGene delivered comparable performance among the current state-of-the-art tools.
Mar 17 2016 cs.RO
Topological motion planning is a planning problem embedding topological concept of trajectories. In this work, we propose two asymptotically optimal sampling-based algorithms for topological motion planning: (a) a batch processing-based planner, termed Fast Marching Homology-embedded Tree star (FMHT*); and (b) an incremental anytime algorithm, termed Rapidly-exploring Random Homology-embedded Tree star (RRHT*). The methods commonly expand a graph directly in the configuration space and project the associated tree onto the topological concept-augmented space; the computational cost in edge computation and collision checking is significantly reduced by allowing trajectories with different topology to share the edge and collision information. Illustrative numerical examples are presented to demonstrate the validity and applicability of the proposed approach.
Mar 15 2016 cs.RO
This paper extends the RRT* algorithm, a recently developed but widely-used sampling-based optimal motion planner, in order to effectively handle nonlinear kinodynamic constraints. Nonlinearity in kinodynamic differential constraints often leads to difficulties in choosing appropriate distance metric and in computing optimized trajectory segments in tree construction. To tackle these two difficulties, this work adopts the affine quadratic regulator-based pseudo metric as the distance measure and utilizes iterative two-point boundary value problem solvers for computing the optimized segments. The proposed extension then preserves the inherent asymptotic optimality of the RRT* framework, while efficiently handling a variety of kinodynamic constraints. Three numerical case studies validate the applicability of the proposed method.
Oct 21 2015 cs.LG
We present an efficient method for training slack-rescaled structural SVM. Although finding the most violating label in a margin-rescaled formulation is often easy since the target function decomposes with respect to the structure, this is not the case for a slack-rescaled formulation, and finding the most violated label might be very difficult. Our core contribution is an efficient method for finding the most-violating-label in a slack-rescaled formulation, given an oracle that returns the most-violating-label in a (slightly modified) margin-rescaled formulation. We show that our method enables accurate and scalable training for slack-rescaled SVMs, reducing runtime by an order of magnitude compared to previous approaches to slack-rescaled SVMs.
This work presents an efficient method to solve a class of continuous-time, continuous-space stochastic optimal control problems of robot motion in a cluttered environment. The method builds upon a path integral representation of the stochastic optimal control problem that allows computation of the optimal solution through sampling and estimation process. As this sampling process often leads to a local minimum especially when the state space is highly non-convex due to the obstacle field, we present an efficient method to alleviate this issue by devising a proposed topological motion planning algorithm. Combined with a receding-horizon scheme in execution of the optimal control solution, the proposed method can generate a dynamically feasible and collision-free trajectory while reducing concern about local optima. Illustrative numerical examples are presented to demonstrate the applicability and validity of the proposed approach.
Aug 12 2015 cs.LG
We present improved methods of using structured SVMs in a large-scale hierarchical classification problem, that is when labels are leaves, or sets of leaves, in a tree or a DAG. We examine the need to normalize both the regularization and the margin and show how doing so significantly improves performance, including allowing achieving state-of-the-art results where unnormalized structured SVMs do not perform better than flat models. We also describe a further extension of hierarchical SVMs that highlight the connection between hierarchical SVMs and matrix factorization models.
As the number of electronic components in the car increases, the requirement for the higher data transmission scheme among them is on the sharp rise. Controller area network (CAN) has been widely adopted to support the in-car communications needs but the data rate is far below what other schemes such as Ethernet and optical fibers can offer. A new scheme for enhancing the speed of CAN network has been proposed, where carrier modulated signal is introduced on top of the existing CAN signal whereby the data rate can be enhanced over 100Mbps. The proposed scheme is compatible with the existing CAN network and accordingly enables seamless upgrade of the existing network to support high speed demand using CAN protocol.
We consider discretization of the 'geometric cover problem' in the plane: Given a set $P$ of $n$ points in the plane and a compact planar object $T_0$, find a minimum cardinality collection of planar translates of $T_0$ such that the union of the translates in the collection contains all the points in $P$. We show that the geometric cover problem can be converted to a form of the geometric set cover, which has a given finite-size collection of translates rather than the infinite continuous solution space of the former. We propose a reduced finite solution space that consists of distinct canonical translates and present polynomial algorithms to find the reduce solution space for disks, convex/non-convex polygons (including holes), and planar objects consisting of finite Jordan curves.
This paper presents a potential game approach for distributed cooperative selection of informative sensors, when the goal is to maximize the mutual information between the measurement variables and the quantities of interest. It is proved that a local utility function defined by the conditional mutual information of an agent conditioned on the other agents' sensing decisions leads to a potential game with the global potential being the original mutual information of the cooperative planning problem. The joint strategy fictitious play method is then applied to obtain a distributed solution that provably converges to a pure strategy Nash equilibrium. Two numerical examples on simplified weather forecasting and range-only target tracking verify convergence and performance characteristics of the proposed game-theoretic approach.
Jan 20 2014 cs.SY
This paper presents heuristic algorithms for interleaved pulse scheduling problems on multi-target tracking in pulse Doppler phased array radars that can process multiple simultaneous received beams. The interleaved pulse scheduling problems for element and subarray level digital beamforming architectures are formulated as the same integer program and the asymptotic time complexities of the algorithms are analyzed.
This paper presents a solution procedure of search parameter optimization for minimum load ensuring desired one-off and cumulative probabilities of detection in a multifunction phased array radar. The key approach is to convert this nonlinear optimization on four search parameters into a scalar optimization on signal-to-noise ratio by a semi-analytic process based on subproblem decomposition. The efficacy of the proposed solution approach is verified with theoretical analysis and numerical case studies.
This paper presents expression of mutual information that defines the information gain in planning of sensing resources, when the goal is to reduce the forecast uncertainty of some quantities of interest and the system dynamics is described as a continuous-time linear system. The method extends the smoother approach in  to handle more general notion of verification entity - continuous sequence of variables over some finite time window in the future. The expression of mutual information for this windowed forecasting case is derived and quantified, taking advantage of underlying conditional independence structure and utilizing the fixed-interval smoothing formula with correlated noises. Two numerical examples on (a) simplified weather forecasting with moving verification paths, and (b) sensor network scheduling for tracking of multiple moving targets are considered for validation of the proposed approach.