Online publications of Lindsay Kleeman

INDEX:

Associate Professor Lindsay Kleeman 
kleeman[AT]eng[DOT]monash[DOT]edu[DOT]au
Intelligent Robotics Research Centre
Department Electrical & Computer Systems Engineering, 
Monash University, VIC 3800 AUSTRALIA 
Tel : +61 3 99053491  Fax : +61 3 99053454 
Keywords : robotics, sonar, ultrasonic, VLSI, sensing, localisation, logic, digital, self-timed, asynchronous.

© Copyright Notice
This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the authors and other copyright holders.

For IEEE publications, the following copyright notice applies. © 1992-2010 IEEE. Permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.

Selected Papers:

Most Cited Papers:

as judged by http://scholar.google.com/ Aug 2006: search now

Book

  • Geoffrey Taylor and Lindsay Kleeman, Visual Perception and Robotic Manipulation: 3D Object Recognition, Tracking and Hand-eye Coordination, Springer Tracts in Advanced Robotics (STAR), Vol 26 2006, ISBN: 3-540-33454-8, 218 pages + CD-ROM, buy it

Software

Videos:

  • DSP sonar tracking a moving plane: MPEGS: Low resolution (1 Mbyte) Medium (4 Mbyte)
  • Two DSP sonar sensors tracking the same wall on a moving robot - demonstration of interference rejection whilst classifying the wall as a plane. MPEGS: Low resolution (1 Mbyte) Medium (4 Mbyte)
  • Wiped sonar map building under joystick control. MPEGS: Low resolution (1 Mbyte) Medium (4 Mbyte)
  • Autonomous exploration and sonar mapping. MPEGS: Low resolution (1 Mbyte) Medium (4 Mbyte)
  • SLAM evolution of map building from sonar and laser: GIF: short (208 kbytes), long zoomed (2.2 Mbyte)
  • Interactive SLAM AVI: long (22 Mbytes) - for details see: A Diosi, G Taylor and L Kleeman, "Interactive SLAM using Laser and Advanced Sonar", Proceedings of the 2005 IEEE International Conference on Robotics and Automation Barcelona, Spain, April 2005, pp 1115-1120.
  • Robot manipulation and sensing videos from PhD student Geoff Taylor here

Online Theses:

Sonar SLAM (Simultaneous Localisation and Mapping) Map with Loops (jpg):

  • Map built using a robot running SLAM Extended Kalman Filtering from on-the-fly front and back sonar measurements during a wiping action. Yellow are features classified as a plane by the sonar, blue corners and green edges. Map with all measurements on 1 metre grid, final feature map. The robot path and error ellipses are shown in blue.

Seminars in powerpoint format:

Technical Reports Frequently Requested:

K S Chong and L. Kleeman "Precise odometry and statistical error modelling for a mobile robot", Technical report MECSE-96-6, Department of Electrical and Computer Systems Engg., Monash University 1996. Here is the conference presentation.

L. Kleeman "Odometry Error Covariance Estimation for Two Wheel Robot Vehicles", Technical report MECSE-95-1, Department of Electrical and Computer Systems Engg., Monash University 1995.

Other technical reports are available here: http://www.ds.eng.monash.edu.au/techrep/reports/

Archive of Zipped Postcript Papers:

Abstracts and Papers in Zipped Postscript for Download

  • Chong, K.S. and Kleeman, L. "Indoor Exploration using a Sonar Sensor Array: A Dual Representation Strategy", Proceedings 1997 IEEE/RSJ International Conference on Intelligent Robots and Systems.


    This paper presents an environmental acquisition strategy for a mobile robot using an advanced sonar sensor to achieve mapping navigation in an a priori unknown, imperfectly structured indoor environment. Most existing feature based strategies rely on unrealistic assumptions about the environment, while their grid based counterparts hinder localisation which leads to rapid degradation of map quality. A dual representation strategy is proposed here which exploits the strength of both a feature map and a grid map. With the advanced sensor, the environment is scanned and the obtained features are classified into planes, corners, edges and unknowns. The feature map is only updated with the first three types of features. Being sharper and more realistic than other representations such as uncertainty/bayesian maps, continual localisation is made possible. The grid map is updated with all measurements, including the unknowns resulting from complicated objects, to enable obstacle avoidance. On the grid map, Distance Transform based exploratory path planning is implemented. Adaptation has been made so that an explore-local-first behaviour is exhibited. Processing efficiency is improved with a simple dynamic memory allocation scheme. The paths generated by the Distance Transform are validated with a new local path validator that accounts for the limitation of sonar perception.

  • Chong, K.S. and Kleeman, L. "Sonar Feature Map Building for a Mobile Robot", Proceedings 1997 IEEE International Conference on Robotics and Automation.


    This report/paper describes a mobile robot equipped with a sonar sensor array, Werrimbi, in a guided feature based map building task in an indoor environment. Common indoor landmarks such as planes, corners and edges are located and classified with a multiple transducer sensor array. Accurate odometry information is derived from a pair of narrow unloaded encoder wheels. Discrete sonar observations are incrementally merged into partial planes to produce a realistic representation of environment. Collinearity constraints among features are exploited to enhance state estimation. The map update utilises Julier-Uhlmann Kalman Filter (JUKF) which improves the accuracy of covariance propagation through nonlinear equations and eliminates the need to derive Jacobian matrices. Correlation among map features and robot location are explicitly represented. Partial planes are also used to eliminate phantom targets caused by sonar specular reflection.

  • Chong, K.S. and Kleeman, L. "Accurate Odometry and Error Modelling for a Mobile Robot", Proceedings 1997 IEEE International Conference on Robotics and Automation.


    This report/paper presents a low cost novel odometry design capable of achieving high accuracy dead-reckoning. It also develops a statistical error model for estimating position and orientation errors of a mobile robot using odometry. Previous work on propagating odometry error covariance relies on incrementally updating the covariance matrix in small time steps. The approach taken here sums the noise theoretically over the entire path length to produce simple closed form expressions, allowing efficient covariance matrix updating after the completion of path segments. Closed form error covariance matrix is developed for a general circular arc and two special cases: (I) straight line and (II) turning about the centre of axle of the robot. Other paths can be composed of short segments of constant curvature arcs without great loss of accuracy. The model assumes that wheel distance measurement errors are exclusively random zero mean white noise. Systematic errors due to wheel radius and wheel base measurement were first calibrated with UMBmark [BorFen94]. Experimental results show that, despite its low cost, our system's performance, with regard to dead- reckoning accuracy, is comparable to some of the best, award-winning vehicles around. The statistical error model, on the other hand, needs to be improved in light of new insights.

  • L Kleeman, "Scanned monocular sonar and the doorway problem", accepted to IEEE/RSJ International Conference on Intelligent Robots and Systems 1996. (recommended for best paper award by a referee)


    A sonar system is presented that relies on scanning a single ultrasonic transducer and measuring echo amplitude and arrival times. Bearing angles to targets are estimated far more accurately than the transducer beamwidth as obtained with conventional sonar rings based on the Polaroid ranging module. A Gaussian beam characteristic is fitted using least squares to the amplitudes of corresponding echoes in the scan to obtain an estimate of the bearing to specular targets. As an illustration of the information gain over conventional sonar rings, the sensor approach is used on a mobile robot to find, traverse and map doorways reliably and with minimal algorithmic effort. This is compared with other work that claims the problem is difficult to solve using a conventional sonar ring of 24 Polaroid ranging modules

  • H. Akbarally and L. Kleeman, "3D robot sensing from sonar and vision", accepted to IEEE International Conference on Robotics and Automation 1996, Minneapolis - recommended for best student paper prize by a referee. see PDF version above.


    We describe a sensor that fuses sonar and visual data to create a three dimensional (3D) model of the environment with application to robot navigation. The environment is characterized by a set of connected horizontal and vertical lines. 3D sonar data is augmented by making deductions concerning the connection and definition of lines in 2D visual data. Any errors that may result from incorrect interpretation of the 2D camera data, such as false connections between lines, can be detected by moving the robot. Experimental results from the sensor are presented.

  • L. Kleeman and R. Kuc, "Mobile robot sonar for target localization and classification", International Journal of Robotics Research, Volume 14, Number 4, August 1995, pp 295-318.


    A novel sonar array is presented that has applications in mobile robotics for localization and mapping of indoor environments. The ultrasonic sensor localizes and classifies multiple targets in two dimensions to ranges of up to 8 meters. By accounting for effects of temperature and humidity, the system is accurate to within a millimeter and 0.1 degrees in still air. Targets separated by 10 mm in range can be discriminated. The error covariance matrix for these measurements is derived to allow fusion with other sensors. Targets are statistically classified into four reflector types: planes, corners, edges and unknown. The paper establishes that two transmitters and two receivers are necessary and sufficient to distinguish planes, corners and edges. A sensor array is presented with this minimum number of transmitters and receivers. A novel design approach is that the receivers are closely spaced so as to minimize the correspondence problem of associating different receiver echoes from multiple targets. A linear filter model for pulse transmission, reception, air absorption and dispersion is used to generate a set of templates for the echo as a function of range and bearing angle. The optimal echo arrival time is estimated from the maximum cross-correlation of the echo with the templates. The use of templates also allows overlapping echoes and disturbances to be rejected. Noise characteristics are modeled for use in the maximum likelihood estimates of target range and bearing. Experimental results are presented to verify assumptions and characterize the sensor.

  • C. Y. Chung and L. Kleeman, "Avoiding hazards in self-timed digital circuits derived from signal transition graphs", Australian Telecommunications Review, Vol. 29, No. 1, pp. 25-38, 1995.


    Since the introduction of Signal Transition Graphs (STGs) in the mid 1980s [1, 2], a number of techniques for the synthesis of self-timed circuits using STGs have been proposed. To achieve a hazard-free implementation, restrictions on the structure of the STG have been employed. Also, hazard-free design techniques have been incorporated into the synthesis procedure. Despite these, implementations derived using these techniques are not always hazard-free. Hazards are shown in this paper to be intrinsic to the function being implemented and cannot be eliminated. To avoid these hazards, certain timing conditions must be preserved. Previous attempts [3, 4, 5] to eliminate hazards are shown to have important limitations. A new procedure is proposed in this paper for the detection of hazards and timing constraints to avoid these hazards. The procedure is compared with previous attempts at hazard detection, and examples presented to show the limitations of other approaches.

  • L. Kleeman, "A three dimensional localiser for autonomous robot vehicles", Robotica, Vol 13, No 1 pp 87-94, 1995.


    A novel design of a three dimensional localiser intended for autonomous robot vehicles is presented. A prototype is implemented in air using ultrasonic beacons at known positions, and can be adapted to underwater environments where it has important applications, such as deep sea maintenance, data collection and reconnaissance tasks. The paper presents the hardware design, algorithms for position and orientation determination (six degrees of freedom), and performance results of a laboratory prototype. Two approaches are discussed for position and orientation determination - (i) fast single measurement set techniques and (ii) computationally slower Kalman filter based techniques. The Kalman filter approach allows the incorporation of robot motion information, more accurate beacon modelling and the capability of processing data from more than four beacons, the minimum number required for localisation.

  • H. Akbarally and L. Kleeman, "Sensor data fusion of sonar and visual data", Australian Robot Association conference "Robots for Australian Industries" Melbourne July 1995, pp. 288-305.


    In this paper we describe a technique that fuses sonar and visual data to create a three dimensional (3D) environmental model intended for robotic navigation. The model characterizes the environment as a set of connected horizontal and vertical lines. Starting with a measurement cycle from a new 3D sonar sensor, the environmental model is expanded successively to include lines from a camera view. The 3D sonar data is augmented by making deductions concerning the connection and definition of lines in the 2D visual data. Any errors that may result from incorrect interpretation of the 2D camera data, such as false connections between lines, can be detected by moving the robot to a second location. We illustrate the performance of this system by presenting experimental results from sensing a 3D structure.

  • H. Akbarally and L. Kleeman, "A sonar sensor for accurate 3D target localisation and classification", IEEE International Conference on Robotics and Automation 1995, Nagoya, Japan, May 1995 pp. 3003-3008. See PDF version above.


    This paper presents a novel sonar sensor consisting of three transmitters and three receivers that can localise and classify 3D targets into 16 different naturally occurring indoor classes. The sensor produces sub-millimeter range and sub-degree bearing accuracies using an optimal matched filter time of flight estimator up to a range of 6 meters. The sensor configuration, hardware and processing are described. Experimental results from the sensor are presented.

  • M.L.Hong and L. Kleeman, "A low sample rate 3D sonar sensor for mobile robots", IEEE International Conference on Robotics and Automation 1995, Nagoya, Japan, May 1995 pp. 3015-3020.


    This paper describes an ultrasonic sensor which uses the times of flight from three Polaroid ultrasonic transducers arranged in an equilateral triangle to identify and localise planes, 2D and 3D corners. The sensor employs a Maximum Likelihood Estimator and a data acquisition system with a low sampling rate of about 59kHz. The hardware and processing requirements are modest and fast due to the simple identification algorithms and sensor structure. Localisation of the objects can be achieved with range error of about 2mm and bearing error of less than 1°. The sensor has been applied to localising a robot in a known indoor environment using 3D natural features and has achieved accuracies of 1cm in position and 2° in bearing.

  • L.Kleeman and R.Kuc, "An optimal sonar array for target localization and classification", IEEE International Conference on Robotics and Automation, San Diego USA, May 1994 pp 3130-3135.


    A novel sonar array for mobile robots is presented with applications to localization and mapping of indoor environments. The ultrasonic sensor localizes and classifies multiple targets in two dimensions to ranges of up to 8 meters. By accounting for effects of temperature and humidity, the system is accurate to within 1 mm and 0.1 degrees in still air. Targets separated by 10 mm can be discriminated. Targets are classified into planes, corners, edges and unknown, with the minimum of two transmitters and two receivers. A novel approach is that receivers are closely spaced to minimize the correspondence problem of associating echoes from multiple targets. A set of templates is generated for echoes to allow the optimal arrival time to be estimated, and overlapping echoes and disturbances to be rejected.

  • C. Y. Chung and L. Kleeman, "An optimal approach to implementing self-timed logic circuits from signal transition graphs", Australian Telecommunications Review, Vol 27, No. 2, pp. 41-56, 1993.


    Scaling of integrated circuits in recent years has resulted in improvements in speed and density of VLSI circuits. However scaling has also aggravated clock skew problems due to increasing wire delays. Consequently, to exploit the speed improvements of scaling and to avoid synchronisation failure in synchronous systems, designers are now turning towards self-timed system design for solutions. Amongst the techniques for the synthesis of self-timed circuits, an approach using Signal Transition Graphs was introduced by Chu [1, 2, 3]. In an attempt to simplify his method and to achieve efficient results, he uses a procedure called net contraction to decompose a Signal Transition Graph into simpler subgraphs known as contracted STGs. With the possibility of state assignment problems in the contracted STGs, net contraction introduces complications and inefficiencies. The cause of these deficiencies can be shown to be the criterion upon which a signal is retained during net contraction. To avoid these deficiencies, a new approach is presented that derives circuit implementations from uncontracted state graphs using Quine-McCluskey tabular Karnaugh mapping and Prime Implicant tables. This approach is shown to produce hazard free implementations with a minimum number of gates in contrast to Chu's sub-optimal method.

  • L.Kleeman, "Optimal estimation of position and heading for mobile robots using ultrasonic beacons and dead-reckoning", IEEE International Conference on Robotics and Automation, Nice, France, pp 2582-2587, May 10-15 1992.


    An active beacon localisation system is described that estimates position and heading for a mobile robot. An Iterated Extended Kalman Filter is applied to the beacon and dead-reckoning data to estimate optimal values of position and heading, given a model for the localiser and robot motion. This paper describes the implementation and experimental results of the localisation system. Position and heading angle updates are calculated in real time every 150 milliseconds with a measured standard deviation of path error of 40 mm in a 12 metre square workspace.

Department of Electrical and Computer Systems Engineering | Faculty of Engineering | Monash University
Last updated : 2006