K Sridharan

Map-making is a challenging task when the environment is unknown and the collected information is local. This paper presents the design of a hardware architecture for sensor-based map construction in a planar environment. In particular, the map is a Voronoi diagram of the environment. The Voronoi construction is based on a control law. Features of the proposed architecture are absence of arithmetic operations expensive in digital hardware and a planning algorithm for completing the map. Also, the implementation of control-law uses look-up tables and reuse of CORDIC module to avoid matrix multiplications. A highly area-efficient FPGA implementation of the architecture is also reported. Experiments with an FPGA-based robot confirm the effectiveness of the proposed approach.

Tangent graph based data structure has been readily used in motion planning for mobile robots and robot manipulators. The complexity of the tangent graph grows exponentially as the robot's configuration space increases in dimension. The ability to construct larger number of tangents at high speed thus becomes crucial to facilitate dynamic motion planning where on-line avoidance is necessary. In this paper, we present efficient schemes for construction of tangent graphs for an environment consisting of both non-convex and convex obstacles. The proposed technique for tangent graph construction is based on a gradient computation approach that encompasses binary search, logarithmic approximation, and half-plane computation modules. The modules were ported to Very Large Scale Integration (VLSI) using commercial tools. Synthesis results show that each module has a latency of only 7.2 ns and a total chip area of about 7K NAND gates, thus demonstrating that the proposed techniques are highly appropriate for tangent graph computations in real-time applications. © 2005 Elsevier B.V. All rights reserved.

An important geometric structure used in robotic path planning and computer graphics is the visibility graph. In this paper, we present a new parallel algorithm to construct the reduced visibility graph that is appropriate for finding shortest paths in a convex polygonal environment. A key feature of the algorithm is that it supports easy mapping to hardware. The computational complexity is O(p 2+log((n/p) 2)) where p is the number of objects and n is the total number of vertices. An efficient FPGA implementation of the algorithm is presented. The design operates at approximately 48 Mhz. Further, the implementation for an environment with roughly 60 vertices requires 90% of an XCV3200E.

The Euclidean Distance Transform (EDT) is an important tool in image analysis and machine vision. It is compute-intensive and real-time applications call for highly parallel solutions. A new linear-time parallel algorithm for EDT is proposed in this paper. The algorithm readily maps to hardware. A pipelined cellular architecture is presented. The architecture is modular and cascadable. Preliminary results of FPGA implementation indicate that the proposed architecture can compute EDT at speeds much higher than the video rate using only a small percentage of the chip (components) for fairly large image sizes.

There is an increasing interest in e-governance for better reachability of government services to citizens. This paper is on our efforts to automate a key activity of the science and technology department of the government of India. In particular, we present the design and development of a comprehensive Web-based system for inviting and processing research proposals. The architecture presented is generic in that extensions to multiple applications such as conference and event management are straightforward. We present the challenges in the automation process, discuss prior work, and then present novel aspects of our system. The system is based on PHP and MySQL. © Copyright 2007 Inderscience Enterprises Ltd.

The reduced visibility graph (RVG) is an important structure for computation of shortest paths for mobile robots. An efficient bit representation is proposed to construct segments that are part of the RVG. Based on the bit representation, a hardware-efficient scheme is presented whose computational complexity is O(k2 log(n/k)), where k is the number of objects and n is the total number of vertices. An architecture that accomplishes the construction of the RVG without division or explicit intersection point calculations is proposed. An efficient field-programmable gate array implementation using block random access memory on an XCV3200E device is presented. © 2007 IEEE.

Computing the shortest path between a pair of points is an important problem in robotics and intelligent transportation systems. The ability to compute this path in real time is valuable in a number of situations. These include an automaton attempting to reach its destination minimizing chances of collision with obstacles. Previous work on shortest path is limited to sequential algorithms and parallel algorithms (for some versions of the problem) on general-purpose architectures. The authors develop a new hardware-efficient algorithm and present an FPGA implementation for shortest path calculation between an automaton's start point and its destination. Results of implementation in Xilinx Virtex FPGA are promising: the solution operates at approximately 68 MHz and the implementation for a graph with 58 nodes and 82 edges fits in one XC2V6000 device. © 2006 Elsevier B.V. All rights reserved.

We present a hardware-directed robotic exploration algorithm for an indoor environment in this paper. The robot is equipped with eight ultrasonic sensors. The algorithm has optimal (linear) time complexity. An important feature of the algorithm is the acquisition of distance information by the eight sensors in parallel. A novel architecture based on Content Addressable Memory (CAM) has been developed. An FPGA implementation has also been developed. Experiments with an FPGA-based robot have been successfully conducted for exploration of static as well as dynamic environments. © 2008 IEEE.

Year 2009 marks the completion of 50 years of the invention of CORDIC (COordinate Rotation DIgital Computer) by Jack E. Volder. The beauty of CORDIC lies in the fact that by simple shift-add operations, it can perform several computing tasks such as the calculation of trigonometric, hyperbolic and logarithmic functions, real and complex multiplications, division, square-root, solution of linear systems, eigenvalue estimation, singular value decomposition, QR factorization and many others. As a consequence, CORDIC has been utilized for applications in diverse areas such as signal and image processing, communication systems, robotics and 3-D graphics apart from general scientific and technical computation. In this article, we present a brief overview of the key developments in the CORDIC algorithms and architectures along with their potential and upcoming applications. © 2009 IEEE.

The computation of shortest path for a mobile robot to get to a destination is considered in this paper. An architecturally-efficient solution is presented for this problem. Results of implementation in Xilinx Virtex FPGA are promising: the solution operates at approximately 72 MHz and the implementation for a graph with 40 nodes and 52 edges fits in one XCV3200E-FG1156 device. © 2009 IEEE.