A common class of algorithms for informative path planning (IPP) follows boustrophedon ("as the ox turns") patterns, which aim to achieve uniform area coverage. However, IPP is often applied in scenarios where anomalies, such as plant diseases, pollution, or hurricane damage, appear in clusters. In such cases, prioritizing the exploration of anomalous regions over uniform coverage is beneficial. This work introduces a class of algorithms referred to as bounomōdes ("as the ox grazes"), which alternates between uniform boustrophedon sampling and targeted exploration of detected anomaly clusters. While uniform sampling can be designed using geometric principles, close exploration of clusters depends on the spatial distribution of anomalies and must be learned. In our implementation, the close exploration behavior is learned using deep reinforcement learning algorithms. Experimental evaluations demonstrate that the proposed approach outperforms several established baselines.

Gas distribution mapping (GDM) refers to the task of mapping the gas concentrations of an airborne chemical over a region of interest. A mobile robot equipped with a gas sensor can be used potentially autonomously to build such a distribution map. However, modern-day robots might not have enough battery power to cover the entire area of interest. Therefore, a group of n such collaborative mobile robots can be used for this purpose. The goal of the robots is to sample concentrations from a fraction of locations and infer the gas intensities in the rest of the area using a supervised machine learning technique, namely the Gaussian Process (GP). To this end, we propose a novel multi-robot gas distribution mapping framework, named GDM-Net++, which works in both 2D and 3D settings. Our proposed framework first divides the environment into n unique regions using Voronoi partitioning. Next, we employ a multi-agent deep Q-learning framework for the robots to learn a joint policy. As GP is a compute-intensive process, during testing, the learned policy is applied without re-training the GP model. The experiments are performed in simulation using Python on six types of Gaussian plumes to validate our proposed technique. Compared to two baselines – greedy and random walk, GDM-Net++ performs by 278% and 852% better in terms of earned rewards, while outperforming them by 34% and 155%, respectively, in terms of the precision of gas distribution modeling across unseen 2D test cases. Our approach can also gracefully handle 2D GDM scenarios where the distribution is consistently affected by wind.

The mathematics of genome rearrangements is significantly more complex compared to mutations. However, the study of genome rearrangements is of great interest to computational biologists, comparative genomicists, and phylogenists. Genome rearrangements are modeled using a variety of primitives, including block (strip) moves, block interchanges, reversals, and transpositions. The present study is an extension of previous work on a primitive known as the strip swap, a variant of the block interchange. A 2-approximation algorithm for sorting by strip swaps using cycle graphs previously reported in the literature fails under certain circumstances, and the current study provides a solution for those instances and improves upon the previous algorithm.

In a gas distribution mapping (GDM) task, the objective of a mobile robot is to map the gas concentrations of an airborne chemical over a region of interest using onboard sensing. Given the limited battery budget available to the robot, covering the entire area to measure gas concentrations at every location might be infeasible. Assuming that the robot only has a budget for b meters of travel, in the rest of the locations, gas concentrations can be inferred using a supervised machine learning technique, namely the Gaussian Process (GP). In this paper, we propose a novel technique that combines deep reinforcement learning and GP regression to find an effective policy for GDM. We have implemented the proposed technique in Python within a 16×16 4-connected plane. We have used six types of Gaussian plumes to validate our presented approach. Compared to two popular baselines, our approach outperforms greedy and random exploration by 62% and 151% in terms of earned rewards, while outperforming them by 47% and 345%, respectively, in terms of the precision of gas distribution modeling in all test cases without obstacles. Our approach also improves the coverage of the exploration while consequently reducing the uncertainty in the prediction.

In this paper, a modern multifactor authentication protocol is analyzed in order to perform cryptanalysis and improve its security. The protocol is a smart card based Multi-Server Two-Factor Authentication Scheme with Un-Traceability Using Elliptic Curve Cryptography (ECC) by Xu et al. We cryptanalyze this protocol and find that it is vulnerable to a type of denial of service (DoS) attack known as clogging attack. Next, we recommend enhancing the process to avoid the clogging attack. We note that all smart card-based authentication protocols preceding Xu et al. are vulnerable to the clogging attack, since they need the server to compute computationally intensive elliptic-curve algorithms. To stop the clogging attack, we propose an alternative protocol upgrade that also pertains to the Xu et al. protocol.

Disease control is paramount in modern agriculture to ensure optimal yield. Monitoring the spread of crop diseases is crucial for effective control measures. Traditional methods involve uniform pesticide spraying across entire fields, which can be inefficient and environmentally harmful. In this paper, we propose an intelligent solution employing mobile robots equipped with predictive AI techniques for disease monitoring and targeted intervention. These robots strategically visit select locations within the field, guided by a convolutional and recurrent neural network model trained on limited data to predict disease spread. We introduce a novel weighted path planning algorithm to optimize robot movement within the field considering disease risk and battery constraints. Our approach is implemented in the WaterBerry benchmark, an open-source platform for agricultural robotics. Experimental results demonstrate the efficacy of our technique, showcasing improved prediction accuracy and operational efficiency compared to baseline methods.

Locating the source of harmful, flammable, or polluting gas leaks is an important task in many practical scenarios. A recently proposed localization approach is to use a mobile robot equipped with a chemical sensor. The localization algorithm guides the movement of the robot based on the previous observations, with the objective of reaching the source as quickly as possible. In this paper, we propose an approach where the robot policy is represented by a neural network combining convolutional and LSTM layers. The approach relies on a gas dispersion model that takes into account obstacles, wind direction, and molecular movement. We found that the trained model provides a 47.34% higher success rate in finding the gas source than an existing greedy approach on test cases with unseen gas plumes and random obstacles.

In today's era of automation, mobile robots are being used for collecting meaningful information about an ambient phenomenon such as temperature or moisture distribution in an agricultural field. Most of the studies in the literature assume that the underlying information field is Gaussian, and therefore, Gaussian Process (GP)-based models are extremely popular. Furthermore, we have found that due to the inherent computational complexity of such naive GP-based techniques, most studies in the literature do not scale well beyond small-size environments, i.e., where the number of informative points$n < 1000$. These render such a predictive model more or less useless in many practical applications. In this paper, we posit that a different technique, Generative Adversarial Network-based inpainting, for robotic information gathering can be useful. The state-of-art inpainting techniques 1) do not assume that the underlying data is Gaussian, and 2) easily scale to$n\gg 1000$. Thus, they eliminate the two bottlenecks posed by the GP-based solutions. We have tested our hypothesis on a synthetic and a real-world crop dataset. Results show that while the inpainting technique easily scales to$1024\times 1024$, GP-based predictions cannot. On the other hand, their solution qualities are shown to be comparable.

Multi-robot teams are becoming an increasingly popular approach for information gathering in large geographic areas, with applications in precision agriculture, surveying the aftermath of natural disasters or tracking pollution. These robot teams are often assembled from untrusted devices not owned by the user, making the maintenance of the integrity of the collected samples an important challenge. Furthermore, such robots often operate under conditions of opportunistic, or periodic connectivity and are limited in their energy budget and computational power. In this paper, we propose algorithms that build on blockchain technology to address the data integrity problem, but also take into account the limitations of the robots' resources and communication. We evaluate the proposed algorithms along the perspective of the tradeoffs between data integrity, model accuracy, and time consumption.

Blockchain-powered smart systems deployed in different industrial applications promise operational efficiencies and improved yields, while significantly mitigating cybersecurity risks. Tradeoffs between availability and security arise at implementation, however, triggered by the additional resources (e.g., memory and computation) required by blockchain-enabled hosts. This paper applies an energy-reducing algorithmic engineering technique for Merkle Tree (MT) root calculations and the Proof of Work (PoW) algorithm, two principal elements of blockchain computations, as a means to preserve the promised security benefits but with less compromise to system availability. Using pyRAPL, a python library to measure the energy consumption of a computation, we experiment with both the standard and energy-reduced implementations of both algorithms for different input sizes. Our results show that up to 98% reduction in energy consumption is possible within the blockchain’s MT construction module, with the benefits typically increasing with larger input sizes. For the PoW algorithm, our results show up to 20% reduction in energy consumption, with the benefits being lower for higher difficulty levels. The proposed energy-reducing technique is also applicable to other key elements of blockchain computations, potentially affording even “greener” blockchain-powered systems than implied by only the results obtained thus far on the MT and PoW algorithms.

We study the problem of information sampling of an ambient phenomenon using a group of mobile robots. Autonomous robots are being deployed for various applications such as precision agriculture, search-and-rescue, among others. These robots are usually equipped with sensors and tasked with collecting maximal information for further data processing and decision making. The studied problem is proved to be NP-Hard in the literature. To solve the stated problem approximately, we employ a multi-agent deep reinforcement learning framework and use the concepts of mean field games to potentially scale the solution to larger multi-robot systems. Simulation results show that our presented technique easily scales to 10 robots in a 19 × 19 grid environment, while consistently sampling useful information.

Blockchain-powered smart systems deployed in different industrial applications promise operational efficiencies and improved yields, while mitigating significant cybersecurity risks pertaining to the main application. Associated tradeoffs between availability and security arise at implementation, however, triggered by the additional resources (e.g., memory, computation) required by each blockchain-enabled host. This paper applies an energy-reducing algorithmic engineering technique for Merkle Tree root calculations, a principal element of blockchain computations, as a means to preserve the promised security benefits but with less compromise to system availability. Using pyRAPL, a python library to measure computational energy, we experiment with both the standard and energy-reduced implementations of the Merkle Tree for different input sizes (in bytes). Our results show up to 98% reduction in energy consumption is possible within the blockchain's Merkle Tree construction module, such reductions typically increasing with larger input sizes. The proposed energy-reducing technique is similarly applicable to other key elements of blockchain computations, potentially affording even “greener” blockchain-powered systems than implied by only the Merkle Tree results obtained thus far.

BLOCK SORTING is an APX-hard combinatorial optimization problem motivated by applications in genome rearrangements. While previous works on block sorting have mainly focused on theoretical analyses of approximation algorithms, work we had previously developed an implementation framework for block sorting in the Java programming language in one of our earlier works [1]. We proposed a greedy heuristic for block sorting in that work. In this work, we use this framework to implement and experimentally evaluate five different algorithms for block sorting: 1) each block move guarantees a reduction of at least one block; 2) block moves are performed only on those blocks which are not members of the longest increasing subsequence (of blocks) in the original permutation; 3) each block move either reduces the number of blocks by two or three blocks, or reduces the number of reversals or inversions in the original permutation; 4) a previously designed algorithm for block sorting based on another problem, block merging; and 5) a theoretically conjectured more efficient version of the previous algorithm called efficient block merging. We analyze and compare these algorithms for their performance as the order of permutations is varied, using the measures of number of block moves and approximation ratios when sorting kernelized permutations of a given order. We also compare execution time of each algorithm over same set of inputs. Our experiments validate the efficiency of the greedy algorithm for block sorting presented in a companion paper [1], and brings out many practical insights of the problem. To the best of our knowledge this is the first work that is focused on implementation and experimental performance analysis of any existing algorithms for block sorting (e.g. block merging). We believe our results will be useful for researchers and practitioners working in this area.

Network security is an ongoing major problem in today's Internet world. Even though there have been simulation studies related to denial of service and cache attacks, studies of attacks on real networks are still lacking in the research. In this work, the effects of cache attacks in real information-centric networking systems were investigated. Cache attacks were implemented in real networks with different cache sizes and with Least Recently Used, random and First In First Out algorithms to fill the caches in each node. The attacker hits the cache with unpopular content, making the user request that the results be fetched from web servers. The cache hit, time taken to get the result and number of hops to serve the request were calculated with real network traffic. The results of the implementation are provided with the consideration of different topologies and are compared with existing simulation results.

Block Sorting is an APX-hard combinatorial optimization problem motivated by applications in genome rearrangements. While previous works on block sorting have mainly focused on theoretical analyses of approximation algorithms, in this work we develop an implementation framework for block sorting in the Java programming language. Our framework uses a simple data structure for a block and includes methods to: manipulate blocks; extract useful information about blocks at various stages in a block sorting algorithm; and perform block moves. We use this framework to implement algorithms for block sorting, based on three different heuristics: 1) each block move guarantees a reduction of at least one block; 2) block moves are performed only on those blocks which are not members of the longest increasing subsequence (of blocks) in the original permutation; and 3) each block move either reduces the number of blocks by two or three blocks, or reduces the number of reversals or inversions in the original permutation. We analyze and compare these algorithms for their performance as the order of permutations is varied, using the measures of number of block moves and approximation ratios when sorting kernelized permutations of a given order. To the best of our knowledge this is the first work that is focused on implementation and experimental performance analysis of any algorithm for block sorting. We believe our results will be useful for researchers and practitioners working in this area.

In this work we propose to design and implement a secure one-time password (OTP) system to provide a better method of enforcing a stricter set of policies, that bypass natural human habits of choosing passwords that do not abide by the policies of an organization, leaving systems vulnerable to security threats. We would then perform static and dynamic analysis of our OTP system to ensure it is not vulnerable to different kinds of security threats and other risks.

In this paper, we study a genome rearrangement primitive called block moves. This primitive as a special case of another well studied primitive transposition. We revisit the problem of BLOCK SORTING, which is a sorting problem under the primitive block moves in this work. BLOCK SORTING has been shown to be NP-Complete, and a couple of results have designed factor 2 approximation algorithms for the problem - the best known till date. However whether the problem is APX-Hard, or an improvement over the factor 2 approximation algorithms have been interesting open problems. We design a new factor 2 approximation algorithm for BLOCK SORTING. Our algorithm is equal to the best known in terms of approximation ratio, however, our approach is much simpler and is linear time (O (n)) as compared to the cubic (O (n3)) and quadratic (O (n2)) run-times of the existing algorithms for the problem.

In this work we compute the energy generated by modular exponentiation, a widely used powerful tool in password authentication protocols for cyber physical systems. We observe modular exponentiation to be an expensive operation in terms of energy consumption in addition to be known to be computationally intensive. We then analyze the security and energy consumption an advanced smart card based password authentication protocol for cyber physical systems, that use modular exponentiation. We devise a generic cryptanalysis method on the protocol, in which the attacker exploits the energy and computational intensive nature of modular exponentiation to a perform denial of service (DoS) attack. We also show other similar protocols to be vulnerable to this attack. We then suggest methods to prevent this attack.

In this work, we argue that energy management should be a guiding principle for design and implementation of algorithms. Traditional complexity models for algorithms are simple and do not aid in design of energy-efficient algorithms. In this work, we conducted a large number of experiments to understand energy consumption for algorithms. We study the energy consumption for popular vector operations, matrix operations, sorting, and graph algorithms. We observed that the energy consumption for any given algorithm depends on the memory parallelism the algorithm can exhibit for a given data layout in the RAM with variations up to 100% for many popular algorithms. Our experiments validate the asymptotic energy complexity model presented in a companion paper [1] and brings out many practical insights. We show that reads can be more expensive in terms of energy than writes, and different data types can lead to different energy consumption. Our most important result is a theoretical and experimental quantification of the impact of parallel data sequences on energy consumption. We also observe that high memory parallelism can also increase energy consumption with multiple concurrent access sequences. We use insights from our experiments to propose algorithmic engineering techniques for practical energy efficient software.

Energy consumption has emerged as a first class computing resource for both server systems and personal computing devices. The growing importance of energy has led to rethink in hardware design, hypervisors, operating systems and compilers. Algorithm design is still relatively untouched by the importance of energy and algorithmic complexity models do not capture the energy consumed by an algorithm. In this paper, we propose a new complexity model to account for the energy used by an algorithm. Based on an abstract memory model (which was inspired by the popular DDR3 memory model and is similar to the parallel disk I/O model of Vitter and Shriver), we present a simple energy model that is a (weighted) sum of the time complexity of the algorithm and the number of 'parallel' I/O accesses made by the algorithm. We derive this simple model from a more complicated model that better models the ground truth and present some experimental justification for our model. We believe that the simplicity (and applicability) of this energy model is the main contribution of the paper. We present some sufficient conditions on algorithm behavior that allows us to bound the energy complexity of the algorithm in terms of its time complexity (in the RAM model) and its I/O complexity (in the I/O model). As corollaries, we obtain energy optimal algorithms for sorting (and its special cases like permutation), matrix transpose and (sparse) matrix vector multiplication.

In this work we consider two protocols for performing cryptanalysis and security enhancement. The first one by Song, is a password authentication scheme based on smart cards. We note that this scheme has already been shown vulnerable to the off-line password guessing attack by Tapiador et al. We perform a further cryptanalysis on this protocol and observe that it is prone to the clogging attack, a kind of denial of service (DOS) attack. We observe that all smart card based authentication protocols which precede the one by Song, and require the server to compute the computationally intensive modular exponentiation, like the one by Xu et al., or Lee et al., are prone to the clogging attack. Further, some recent protocols by Li, and Wang et al. are also vulnerable to the clogging attack. We then suggest an improvement on the protocol to prevent the clogging attack. The other protocol we consider is a two-party identity-based authenticated key agreement protocol by Hölbl et al. They have devised two such protocols in their work. They call them Protocol 1 and Protocol 2. Both the protocols have already been shown vulnerable to the insider attack in a recent work by Chen et al. Here we consider Protocol 2 and show its vulnerability to a simple man-in-the-middle attack where the adversary does not know or calculate either party's private key, or the session key. Protocol 2 by Hölbl et al is an improvement over a previous work by Tseng. This makes the Tseng's protocol vulnerable to the attack we illustrate. We further suggest an additional step for these protocols to make them immune against the man-in-the-middle attack.

Genome and other syntenic blocks rearrangements have become a topic of intensive study by phylogenists, comparative genomicists, and computational biologists: they are a feature of many cancers, must be taken into account to align highly divergent sequences, and constitute a phylogenetic marker of great interest. The mathematics of rearrangements is far more complex than for indels and mutations in sequences. Genome rearrangements have been modeled by a variety of primitives such as reversals, transpositions , block moves and block interchanges. In this paper, we study a genome rearrangement primitive called strip exchanges. We formulate the primitive as a special case of another primitive, the block interchanges, identify a new lower bound for the sorting by strip exchanges problem. We then design a 2 approximation algorithm for the problem.