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. ©2010 IEEE.

Krishnamurthy Sridharan

Department of Electrical Engineering

Efficient architecture

Floating point operations

Indoor environment

Novel algorithm

Processing hardware

Robotic mapping

Voronoi diagrams

Algorithms

Computational geometry

Computer vision

Field programmable gate arrays (FPGA)

Graphic methods

Mobile robots

Robotics

IIT Madras is a public technical and research university located in Chennai, Tamil Nadu. Founded in 1959, it is recognised as an Institute of National Importance.

IIT Madras has been ranked as the top engineering institute in India for four years in a row by the National Institutional Ranking Framework of the MHRD

It currently offers undergraduate, postgraduate and research degrees across 16 disciplines in Engineering, Sciences, Humanities and Management. About 596 faculty belonging to science and engineering departments and centres of the Institute are engaged in teaching, research and industrial consultancy.

IIT Madras

Robotic mapping with simple sensing and processing hardware — Algorithm and architecture

11th International Conference on Control, Automation, Robotics and Vision, ICARCV 2010

Sensor-based construction of different geometric structures has been an important development in the domain of autonomous robot navigation. This paper presents a hardware-efficient scheme to construct one such geometric structure, namely, the generalized Voronoi diagram (GVD), using a prediction-and-correction strategy. In this paper, an architecture to construct the GVD for an indoor environment with multiple obstacles whose geometry and location are not known beforehand is presented. A feature of the proposed approach is that it does not involve operations that are expensive in hardware. Furthermore, no explicit angle computation circuitry is needed. An efficient architecture based on hardware reuse is presented. The design is shown to be space efficient and fits in a low-end field-programmable gate-array (FPGA) device (with a small number of system gates). Detailed experiments with a mobile robot fabricated locally with a Xilinx XC2S200E FPGA and eight ultrasonic sensors onboard validate the efficacy of the proposed approach for static as well as dynamic environments. © 2008 IEEE.

IEEE Transactions on Industrial Electronics

Hardware-efficient prediction-correction-based generalized-voronoi-diagram construction and FPGA implementation

The International Journal of Robotics Research

Sensor-Based Exploration: The Hierarchical Generalized Voronoi Graph

IEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans

Constructing the generalized local Voronoi diagram from laser range scanner data

The Journal of VLSI Signal Processing

10.1023/a:1008145506415

IEEE Transactions on Robotics and Automation

Collision-free path planning for a diamond-shaped robot using two-dimensional cellular automata

Robotic mapping with simple sensing and processing hardware - Algorithm and architecture

Journal	11th International Conference on Control, Automation, Robotics and Vision, ICARCV 2010
Open Access	No