Safety considerations call for deployment of autonomous ground vehicles in defense and high risk zones for transport of goods from one point to another. Such vehicles face the threat of an intelligent autonomous adversary that may disrupt the transfer of material. This article investigates the challenges involved in autonomous protection of a delivery agent, via a land-based rescue agent, before interception of the delivery agent by the adversary occurs. In particular, we study how effectively an adversary equipped with a vision sensor can be handled by an autonomous rescue agent operating without vision support and relying only on wireless communication with the delivery agent. Taking capabilities and weights of the three vehicles into account, the delivery agent is assumed to be the slowest while the adversary operates at the highest speed among the three vehicles. A geometric framework based on Apollonius circles is proposed to analyze the interaction between the delivery and rescue agents. The adversary's speed and its moves (based on the direction of the delivery agent) are taken into account, along with the Apollonius circles for the rescue-delivery agent pair, to determine the possibility of capture. Regions in the plane where the delivery and rescue agents can meet, prior to a capture by the adversary, are obtained to compute safe regions for the delivery agent. Algorithms adopted by the delivery agent, rescue agent, and the adversary are described. We, then, explore the challenges in rescue of multiple delivery agents from a vision-guided adversary by introducing additional rescue agents. In particular, we study protection of k delivery agents (from an adversary) via k rescue agents. Algorithms to compute 1) multiple meeting points, one each for a delivery agent-rescue agent pair and 2) the strategy of the adversary to capture any one of the k delivery agents are presented. Experiments with multiple agents show that the delivery and rescue agents can execute their strategies using simply low-end microcontrollers without external memory.

Multiple autonomous agents working cooperatively have contributed to the development of robust large-scale systems. While substantial work has been done in manufacturing and domestic environments, a key consideration for small hardware agents engaged in collaborative factory automation and welfare support systems is limited area and power on-board. When the agents attempt to meet for performing a task, it is natural for them to encounter obstacles and it is desirable for each agent to optimize its resources during its navigation. In this paper, we develop efficient geometric algorithms to find a point, termed as the gathering point (and denoted by PG), for the agents that minimizes the maximum of path lengths. In particular, we present an O(n log2n) time algorithm for calculation of PGfor an environment with two agents and n static polygonal obstacles. We then use the notion of a weighted minimax point to derive an efficient algorithm (with complexity of O(k2+ kn log2n)) for computing PGfor an environment with k agents and n obstacles. An enhancement to a dynamic environment is then presented. We also present details of an efficient hardware realization of the algorithms. Each agent, equipped with only an ATmega328P microcontroller and no external memory, executes the algorithms. Experiments with multiple agents navigating amidst static as well as dynamic obstacles are reported.

Dynamic obstacles present a challenge for navigation of mobile robots. Estimation of the velocity of dynamic obstacles helps in collision avoidance. In this paper, we propose a hardware-efficient approach for velocity estimation that is appropriate for FPGA-driven mobile robots. The proposed approach is based on a novel approximate radix-4 CORDIC algorithm with low latency. The new CORDIC requires at most four iterations for convergence and has very low area requirement. Using the proposed CORDIC, we present an iterative method for velocity estimation. The velocity estimation scheme achieves roughly 87% reduction in slice-delay product compared to a direct algebraic approach (that uses multipliers). Experiments with an FPGA-based robot are reported.

Rendezvous of multiple autonomous agents has been of active interest in the last decade. Considerable work has been done on this problem with constraints on sensing and shape of the environment. However, not much is known on rendezvous amidst obstacles. When obstacles are introduced into the setting, it becomes natural to explore strategies for rendezvous that optimize some parameter (such as distance, time etc.). Our objective in this paper is to compute a location (which we refer to as the Time Optimal Rendezvous Point (TORP)) that minimizes the time for rendezvous amidst obstacles. We discuss challenges in finding TORP and develop efficient algorithms to compute TORP for r agents moving amidst m static polygonal obstacles. We then extend the analysis to handle dynamic obstacles. Experimental results are presented to validate the theory.

The design of high-performance adders has experienced a renewed interest in the last few years; among high performance schemes, parallel prefix adders constitute an important class. They require a logarithmic number of stages and are typically realized using AND-OR logic; moreover with the emergence of new device technologies based on majority logic, new and improved adder designs are possible. However, the best existing majority gate-based prefix adder incurs a delay of 2log2(n) - 1 (due to the nth carry); this is only marginally better than a design using only AND-OR gates (the latter design has a 2log2(n) + 1 gate delay). This paper initially shows that this delay is caused by the output carry equation in majority gate-based adders that is still largely defined in terms of AND-OR gates. In this paper, two new majority gate-based recursive techniques are proposed. The first technique relies on a novel formulation of the majority gate-based equations in the used group generate and group propagate hardware; this results in a new definition for the output carry, thus reducing the delay. The second contribution of this manuscript utilizes recursive properties of majority gates (through a novel operator) to reduce the circuit complexity of prefix adder designs. Overall, the proposed techniques result in the calculation of the output carry of an n-bit adder with only a majority gate delay of log2(n) + 1. This leads to a reduction of 40percent in delay and 30percent in circuit complexity (in terms of the number of majority gates) for multi-bit addition in comparison to the best existing designs found in the technical literature.

Several field-effect transistor (FET)-based device technologies are emerging as powerful alternatives to the classical metal oxide semiconductor FET (mosfet) for computing applications. The focus of this paper is on the analysis of reliability of combinational logic circuits at the transistor level with the goal of application to these technologies. To this end, we present an approach for the calculation of the output probabilities for basic logic primitives that comprise a combinational circuit. Using the output probabilities, a computationally efficient algorithm (based on Hadamard product) is presented to calculate the reliability. As an application of the proposed algorithm, we analyze the reliability of adder circuits composed of carbon nanotube FETs considering fabrication-level parameters. We then investigate adder characteristics that lead to high reliability independent of the technology. In particular, we propose a new multibit adder termed hybrid adder offering high reliability with low area requirement for various transistor-based emerging technologies. Detailed simulation results are presented to support the analysis.

Autonomous vehicles engaged in terrain exploration are typically equipped with a camera. The camera is subjected to vibration as the vehicle moves so that the videos captured require stabilisation to facilitate accurate interpretation by remote operators. Dedicated architectures for video stabilisation that offer high performance while consuming low area and power are desirable for this application. This study presents a pipelined very large‐scale integration architecture. It is based on exploiting the separability property of the two‐dimensional (2‐D) Sobel matrix and the 2‐D Gaussian filtering matrix to obtain an efficient corner point detection architecture. It also employs the coordinate rotation digital computer architecture for global motion vector calculation. The proposed architecture has been coded in Verilog and synthesised for a field programmable gate array (FPGA), which offers massive parallelism at fairly low power. The proposed architecture is shown to be highly area efficient. An FPGA‐based autonomous vehicle has been fabricated, and experiments with a camera mounted on the vehicle are presented and analysed.

In this brief, we consider quantum-dot cellular automata (QCA) realization of the discrete Hadamard transform (DHT). An analysis of a full-parallel solution based on efficient multibit addition in QCA is first presented. We show that this leads to large area as well as delay. We then propose a bit-serial pipelined architecture for QCA-based DHT. The proposed architecture is based on a new one-bit adder-subtractor requiring only six majority gates and a feedback latch that requires only one majority gate and limited wiring. The approach leads to a reduction in area-delay-cycle product of 74% and 91% (over a full-parallel solution) for wordlengths of 4 and 8, respectively. Results of simulations in QCADesigner are also presented.

This paper first presents an efficient quantum-dot cellular automata (QCA) design for the Ladner-Fischer prefix adder. We then present an efficient QCA design of a hybrid adder that combines the Ladner-Fischer adder with a ripple carry adder. We show that the hybrid adder has better performance (in terms of latency) in QCA than a Ladner-Fischer or a ripple carry adder. We also show that the hybrid adder has a smaller area-delay product than existing adder designs in QCA. Results of simulation in QCADesigner are also given and they support the theory presented.

This paper considers the problem of generating a map of an indoor environment by a mobile robot when constraints are placed on sensing and processing hardware. In particular, we present an algorithm for Voronoi diagram generation by a mobile robot equipped merely with inexpensive ultrasonic sensors and a low-end Field Programmable Gate Array (FPGA) device. The algorithm is based on the definition of the Voronoi diagram in terms of the perpendicular-bisector. Deviations from the Voronoi diagram of the (reference) point on the robot are corrected by a novel algorithm that is devoid of division and floating-point operations. An efficient architecture and experiments with an FPGA-based robot are also presented.

This paper presents a new VLSI-efficient algorithm for robotic exploration in a dynamic environment where the geometry of the objects or their motion trajectories are not known a priori. The input to the proposed algorithm is a list of G nodes obtained using the robot's step size and the dimensions of the environment. P nodes accessible to the robot are identified. The time complexity of the proposed algorithm is O(G). Special features of the algorithm include parallel processing of data from multiple ultrasonic sensors and the use of associative memory to efficiently keep track of the visited terrain nodes. A novel architecture based on selective shutdown of hardware modules for reducing energy consumption is proposed. Detailed experiments with a mobile robot fabricated locally with a Xilinx XC2S200E field programmable gate array and eight ultrasonic sensors on-board validate the efficacy of the proposed approach

In this paper, we present a new algorithm to construct a discrete Voronoi diagram based on the Euclidean distance metric in a binary image. The algorithm has linear time complexity and is suited to very large-scale integration (VLSI) implementation due to the use of local neighborhood calculations on reduced bit-width data. A cellular architecture for construction of the diagram is proposed. The proposed architecture has been implemented in VLSI using 0.35 micron 2-poly 3-metal layer complementary metal-oxide-semiconductor technology, and the dimensions of the chip are 3.16 mm/spl times/3.16 mm, with the maximum frequency of operation being 50 MHz.

This paper presents a parallel algorithm for computing the Voronoi diagram for collision-free path planning of robots. The algorithm constructs the Voronoi diagram on a binary image of the workspace and is based on the Euclidean distance function. It has been implemented in ANSI-C on an HP workstation. The algorithm is suitable for VLSI implementation in a cellular architecture. Such an architecture is described. Comparisons with an existing algorithm are also presented.

Algorithms to compute measures of penetration between convex polygonal objects in /spl Rfr//sup 2/ and convex polyhedral objects in /spl Rfr//sup 3/ are presented. The algorithms are analyzed for their asymptotic complexity. Details of implementation on a single processor machine are given. Parallelization of the algorithms is discussed.

This paper presents efficient algorithms for computing new types of distance measures. One of the measures denoted by d/sub rho//sup +/ (A, B) characterizes proximity of non-intersecting objects A and B taking into account their shapes. The second measure denoted by /spl delta/(/spl sigma/; A, B) characterizes the penetration between two intersecting objects. The main contributions include: 1) O(m log n+n log m) algorithms to compute d/sub rho//sup +/ (A, B) and /spl delta/(/spl sigma/; A, B) between convex polyhedra in /spl Rfr//sup 3/ having m and n vertices respectively; and 2) an efficient procedure to compute /spl delta/(/spl sigma/; A, B) between non-polygonal objects described algebraically. We point out the utility of the measures for collision detection between a pair of objects.>

The problem of planning motions offline for a robot in the presence of obstacles via an algorithm that does not proceed by a discretization of the search space involves defining good heuristics to characterize the proximal relationships between two rigid bodies and the development of algorithms for their computation. Several measures are presented, and schemes for their computation are developed. The performances of the algorithms are determined in terms of their running time. The advantage of the fuzzy model is that it lends itself easily to numerical computation involving manipulation of the coordinates of the extreme points.>