Search Strategies for Multiple UAV Search and Destroy Missions

Multiple UAVs are deployed to carry out a search and destroy mission in a bounded region. The UAVs have limited sensor range and can carry limited resources which reduce with use. The UAVs perform a search task to detect targets. When a target is detected which requires different type and quantities of resources to completely destroy, then a team of UAVs called as a coalition is formed to attack the target. The coalition members have to modify their route to attack the target, in the process, the search task is affected, as search and destroy tasks are coupled. The performance of the mission is a function of the search and the task allocation strategies. Therefore, for a given task allocation strategy, we need to devise search strategies that are efficient. In this paper, we propose three different search strategies namely; random search strategy, lanes based search strategy and grid based search strategy and analyze their performance through Monte-Carlo simulations. The results show that the grid based search strategy performs the best but with high information overhead.

Continuity Metric for Unit Selection based Text-to-Speech Synthesis

A new method based on unit continuity metric (UCM) is proposed for optimal unit selection in text-to-speech (TTS) synthesis. UCM employs two features, namely, pitch continuity metric and spectral continuity metric. The methods have been implemented and tested on our test bed called MILE-TTS and it is available as web demo. After verification by a self selection test, the algorithms are evaluated on 8 paragraphs each for Kannada and Tamil by native users of the languages. Mean-opinion-score (MOS) shows that naturalness and comprehension are better with UCM based algorithm than the non-UCM based ones. The naturalness of the TTS output is further enhanced by a new rule based algorithm for pause prediction for Tamil language. The pauses between the words are predicted based on parts-of-speech information obtained from the input text.

MOSAICS: Multiplexed Optimal Signal Acquisition Involving Compressed Sensing

It is possible to sample signals at sub-Nyquist rate and still be able to reconstruct them with reasonable accuracy provided they exhibit local Fourier sparsity. Underdetermined systems of equations, which arise out of undersampling, have been solved to yield sparse solutions using compressed sensing algorithms. In this paper, we propose a framework for real time sampling of multiple analog channels with a single A/D converter achieving higher effective sampling rate. Signal reconstruction from noisy measurements on two different synthetic signals has been presented. A scheme of implementing the algorithm in hardware has also been suggested.

Frontier Based Multiple Goal Search in Unknown Environments

We present a frontier based algorithm for searching multiple goals in a fully unknown environment, with only information about the regions where the goals are most likely to be located. Our algorithm chooses an ``active goal'' from the ``active goal list'' generated by running a Traveling Salesman Problem (Tsp) routine with the given centroid locations of the goal regions. We use the concept of ``goal switching'' which helps not only in reaching more number of goals in given time, but also prevents unnecessary search around the goals that are not accessible (surrounded by walls). The simulation study shows that our algorithm outperforms Multi-Heuristic LRTA* (MELRTA*) which is a significant representative of multiple goal search approaches in an unknown environment, especially in environments with wall like obstacles.

Layered Tabu Search Algorithm for Large-MIMO Detection and a Lower Bound on ML Performance

In this paper, we are concerned with low-complexity detection in large multiple-input multiple-output (MIMO) systems with tens of transmit/receive antennas. Our new contributions in this paper are two-fold. First, we propose a low-complexity algorithm for large-MIMO detection based on a layered low-complexity local neighborhood search. Second, we obtain a lower bound on the maximum-likelihood (ML) bit error performance using the local neighborhood search. The advantages of the proposed ML lower bound are i) it is easily obtained for MIMO systems with large number of antennas because of the inherent low complexity of the search algorithm, ii) it is tight at moderate-to-high SNRs, and iii) it can be tightened at low SNRs by increasing the number of symbols in the neighborhood definition. Interestingly, the proposed detection algorithm based on the layered local search achieves bit error performances which are quite close to this lower bound for large number of antennas and higher-order QAM. For e. g., in a 32 x 32 V-BLAST MIMO system, the proposed detection algorithm performs close to within 1.7 dB of the proposed ML lower bound at 10(-3) BER for 16-QAM (128 bps/Hz), and close to within 4.5 dB of the bound for 64-QAM (192 bps/Hz).

Multiple UAV Coalitions for a Search and Prosecute Mission

Unmanned aerial vehicles (UAVs) have the potential to carry resources in support of search and prosecute operations. Often to completely prosecute a target, UAVs may have to simultaneously attack the target with various resources with different capacities. However, the UAVs are capable of carrying only limited resources in small quantities, hence, a group of UAVs (coalition) needs to be assigned that satisfies the target resource requirement. The assigned coalition must be such that it minimizes the target prosecution delay and the size of the coalition. The problem of forming coalitions is computationally intensive due to the combinatorial nature of the problem, but for real-time applications computationally cheap solutions are required. In this paper, we propose decentralized sub-optimal (polynomial time) and decentralized optimal coalition formation algorithms that generate coalitions for a single target with low computational complexity. We compare the performance of the proposed algorithms to that of a global optimal solution for which we need to solve a centralized combinatorial optimization problem. This problem is computationally intensive because the solution has to (a) provide a coalition for each target, (b) design a sequence in which targets need to be prosecuted, and (c) take into account reduction of UAV resources with usage. To solve this problem we use the Particle Swarm Optimization (PSO) technique. Through simulations, we study the performance of the proposed algorithms in terms of mission performance, complexity of the algorithms and the time taken to form the coalition. The simulation results show that the solution provided by the proposed algorithms is close to the global optimal solution and requires far less computational resources.

Automated Multi-Agent Search Using Centroidal Voronoi Configuration

This paper addresses the problem of automated multiagent search in an unknown environment. Autonomous agents equipped with sensors carry out a search operation in a search space, where the uncertainty, or lack of information about the environment, is known a priori as an uncertainty density distribution function. The agents are deployed in the search space to maximize single step search effectiveness. The centroidal Voronoi configuration, which achieves a locally optimal deployment, forms the basis for the proposed sequential deploy and search strategy. It is shown that with the proposed control law the agent trajectories converge in a globally asymptotic manner to the centroidal Voronoi configuration. Simulation experiments are provided to validate the strategy. Note to Practitioners-In this paper, searching an unknown region to gather information about it is modeled as a problem of using search as a means of reducing information uncertainty about the region. Moreover, multiple automated searchers or agents are used to carry out this operation optimally. This problem has many applications in search and surveillance operations using several autonomous UAVs or mobile robots. The concept of agents converging to the centroid of their Voronoi cells, weighted with the uncertainty density, is used to design a search strategy named as sequential deploy and search. Finally, the performance of the strategy is validated using simulations.

Genetic search: Analysis using fitness moments

Genetic Algorithms are efficient and robust search methods that are being employed in a plethora of applications with extremely large search spaces. The directed search mechanism employed in Genetic Algorithms performs a simultaneous and balanced, exploration of new regions in the search space and exploitation of already discovered regions.This paper introduces the notion of fitness moments for analyzing the working of Genetic Algorithms (GAs). We show that the fitness moments in any generation may be predicted from those of the initial population. Since a knowledge of the fitness moments allows us to estimate the fitness distribution of strings, this approach provides for a method of characterizing the dynamics of GAs. In particular the average fitness and fitness variance of the population in any generation may be predicted. We introduce the technique of fitness-based disruption of solutions for improving the performance of GAs. Using fitness moments, we demonstrate the advantages of using fitness-based disruption. We also present experimental results comparing the performance of a standard GA and GAs (CDGA and AGA) that incorporate the principle of fitness-based disruption. The experimental evidence clearly demonstrates the power of fitness based disruption.

Unwinding of heterologous DNA by RecA protein during the search for homologous sequences

The search for homologous sequences promoted by RecA protein in vitro involves a presynaptic filament and naked duplex DNA, the multiple contacts of which produce nucleoprotein networks or coaggregates. The single-stranded DNA within the presynaptic filaments, however, is extended to an axial spacing 1.5 times that of B-form DNA. To investigate this paradoxical difference between the spacing of bases in the RecA presynaptic filament versus the target duplex DNA, we explored the effect of heterologous contacts on the conformation of DNA, and vice versa. In the presence of wheat germ topoisomerase I, RecA presynaptic filaments induced a rapid, limited reduction in the linking number of heterologous circular duplex DNA. This limited unwinding of heterologous duplex DNA, termed heterologous unwinding, was detected within 30 seconds and reached a steady state within a few minutes. Presynaptic filaments that were formed in the presence of ATP?S and separated from free RecA protein by gel filtration also generated a ladder of topoisomers upon incubation with relaxed duplex DNA and topoisomerase. The inhibition of heterologous contacts by 60 mImage -NaCl or 5 mImage -ADP resulted in a corresponding decrease in heterologous unwinding. In reciprocal fashion, the stability or number of heterologous contacts with presynaptic filaments was inversely related to the linking number of circular duplex DNA. These observations show that heterologous contacts with the presynaptic filament cause a limited unwinding of the duplex DNA, and conversely that the ability of the DNA to unwind stabilizes transient heterologous contacts.

Tidally compressed gas in centers of early-type and ultraluminous galaxies

In this paper we propose that the compressive tidal held in the centers of flat-core early-type galaxies and ultraluminous galaxies compresses molecular clouds producing dense gas observed in the centers of these galaxies. The effect of galactic tidal fields is usually considered disruptive in the literature. However, for some galaxies, the mass profile flattens toward the center and the resulting galactic tidal field is not disruptive, but instead it is compressive within the flat-core region. We have used the virial theorem to determine the minimum density of a molecular cloud to be stable and gravitationally bound within the tidally compressive region of a galaxy. We have applied the mechanism to determine the mean molecular cloud densities in the centers of a sample of flat-core, early-type galaxies and ultraluminous galaxies. For early-type galaxies with a core-type luminosity profile, the tidal held of the galaxy is compressive within half the core radius. We have calculated the mean gas densities for molecular gas in a sample of early-type galaxies which have already been detected in CO emission, and we obtain mean densities of [n] similar to 10(3)-10(6) cm(-3) within the central 100 pc radius. We also use our model to calculate the molecular cloud densities in the inner few hundred parsecs of a sample of ultraluminous galaxies. From the observed rotation curves of these galaxies we show that they have a compressive core within their nuclear region. Our model predicts minimum molecular gas densities in the range 10(2)-10(4) cm(-3) in the nuclear gas disks; the smaller values are applicable typically for galaxies with larger core radii. The resulting density values agree well with the observed range. Also, for large core radii, even fairly low-density gas (similar to 10(2) cm(-3)) can remain bound and stable close to the galactic center.

An Online Kannada Text Transliteration System for Mobile Phones

Transliteration system for mobile phone is an area that is always in demand given the difficulties and constraints we face in its implementation. In this paper we deal with automatic transliteration system for Kannada which has a non-uniform geometry and inter-character spacing unlike non-oriental language text like English. So it is even more a challenging problem. Working model consists of part of the process taking place on a mobile with remaining on a server. Good results are achieved.

Machine recognition of printed Kannada text

This paper presents the design of a full fledged OCR system for printed Kannada text. The machine recognition of Kannada characters is difficult due to similarity in the shapes of different characters, script complexity and non-uniqueness in the representation of diacritics. The document image is subject to line segmentation, word segmentation and zone detection. From the zonal information, base characters, vowel modifiers and consonant conjucts are separated. Knowledge based approach is employed for recognizing the base characters. Various features are employed for recognising the characters. These include the coefficients of the Discrete Cosine Transform, Discrete Wavelet Transform and Karhunen-Louve Transform. These features are fed to different classifiers. Structural features are used in the subsequent levels to discriminate confused characters. Use of structural features, increases recognition rate from 93% to 98%. Apart from the classical pattern classification technique of nearest neighbour, Artificial Neural Network (ANN) based classifiers like Back Propogation and Radial Basis Function (RBF) Networks have also been studied. The ANN classifiers are trained in supervised mode using the transform features. Highest recognition rate of 99% is obtained with RBF using second level approximation coefficients of Haar wavelets as the features on presegmented base characters.

Search for sub-mm, mm and radio continuum emission from extremely red objects

We present the results of sub-mm, mm (850 mum, 450 mum and 1250 mum) and radio (1.4 and 4.8 GHz) continuum observations of a sample of 27 K-selected Extremely Red Objects, or EROs, (14 of which form a complete sample with K < 20 and I - K > 5) aimed at detecting dusty starbursts, deriving the fraction of UltraLuminous Infrared Galaxies (ULIGs) in ERO samples, and constraining their redshifts using the radio-FIR correlation. One ERO was tentatively detected at 1250 mum and two were detected at 1.4 GHz, one of which has a less secure identification as an ERO counterpart. Limits on their redshifts and their star forming properties are derived and discussed. We stacked the observations of the undetected objects at 850 mum, 1250 mum and 4.8 GHz in order to search for possible statistical emission from the ERO population as a whole, but no significant detections were derived either for the whole sample or as a function of the average NIR colours. These results strongly suggest that the dominant population of EROs with K < 20 is not comprised of ULIGs like HR 10, but is probably made of radio-quiet ellipticals and weaker starburst galaxies with L < 10(12) L . and SFR < few hundred M. yr(-1).