• Efficient Topological Exploration


    Abstract

    We consider the robot exploration of a planar graph-like world. The robot's goal is to build a complete map of its environment. The environment is modeled as an arbitrary undirected planar graph which is initially unknown to the robot. The robot cannot distinguish vertices and edges that it has explored from the unexplored ones. The robot is assumed to be able to autonomously traverse graph edges, recognize when it has reached a vertex, and enumerate edges incident upon the current vertex. The robot cannot measure distances nor does it have a compass, but it is equipped with a single marker that it can leave at a vertex and sense if the marker is present at a newly visited vertex. The total number of edges traversed while constructing a map of a graph is used as a measure of performance. We present an efficient algorithm for learning an unknown, undirected planar graph by a robot equipped with one marker. One of the main results of this paper is to show that our strategy leads to performance that is typical linear in the size of the graph. Experimental results obtained by running a large collection of example worlds are also presented.
    (To Appear in ICRA 99)

    Bibtex entry

    @InProceedings{Rekleitis1999,
    author = {Ioannis M. Rekleitis, and Vida Dujmovi\'c and Gregory Dudek},
    title = {Efficient Topological Exploration},
    booktitle = {Proceedings of International Conference in Robotics and Automation},
    year = 1999
    address = {Detroit, USA},
    month = {May},
    pages = {}
    }

  • On Multiagent Exploration


    Abstract

    This paper describes a technique for multi-agent exploration of an unknown environment, that improves the quality of the map by reducing the inaccuracies that occur over time from dead reckoning errors. We present an algorithmic solution, simulation results, as well as a cost analysis and experimental data. The approach is based on using a pair of robots that observe one another's behaviour, thus greatly reducing odometry errors. We assume the robots can both directly sense nearby obstacles and see one another. We have implemented both these capabilities with actual robots in our lab. By exploiting the ability of the robots to see one another, we can detect opaque obstacles in the environment independent of their surface reflectance properties.

    Bibtex entry

    @InProceedings{Rekleitis1998,
    author = {Ioannis M. Rekleitis and Gregory Dudek and Evangelos E. Milios },
    title = {On Multiagent Exploration},
    booktitle = {Proceedings of Vision Interface 1998},
    year = 1998
    address = {Vancouver, Canada},
    month = {June},
    pages = {455-461}
    }

  • Multi-Robot Exploration of an Unknown Environment,
    Efficiently Reducing the Odometry Error


    Abstract

    This paper deals with the intelligent exploration of an unknown environment by autonomous robots. In particular, we present an algorithm and associated analysis for collaborative exploration using two mobile robots. Our approach is based on robots with range sensors limited by distance. By appropriate behavioural strategies, we show that odometry (motion) errors that would normally present problems for mapping can be severely reduced. Our analysis includes polynomial complexity bounds and a discussion of possible heuristics.
    (Appeared in IJCAI-97)

    Bibtex entry

    @InProceedings{Rekleitis:97b,
    author = {Ioannis Rekleitis, and Gregory Dudek, and Evangelos Milios},
    title = {Multi-Robot Exploration of an Unknown Environment, Efficiently Reducing the Odometry Error},
    booktitle = {International Joint Conference in Artificial Intelligence},
    editor = {IJCAI},
    volume = 2,
    year = 1997,
    publisher = {Morgan Kaufmann Publishers, Inc. },
    address = {Nagoya, Japan},
    month = {August},
    pages = {1340-1345}
    }

  • Optical Flow Recognition from the Power Spectrum of a Single Blurred Image


    Abstract

    In this paper a new technique for calculation of the optical flow is presented. When there is motion in the observed scene, an image taken will be motion blurred (to a degree depending on the exposure time). Up to now most of the algorithms for estimating the motion in a scene ignored motion blur and treated it as noise. On the contrary, motion blur is structured information and in certain cases can be used to infer the velocities locally. This new approach uses the information of the motion blur in the frequency domain to extract the orientation and the magnitude of the velocity - optical flow.

    Bibtex entry

    @InProceedings{Rekleitis:96b,
    author = "Ioannis M. Rekleitis",
    title = "Optical Flow Recognition from the Power Spectrum of a Single Blurred Image",
    booktitle = "International Conference in Image Processing",
    year = 1996,
    organization = {IEEE Signal Processing Society},
    address = "Lausanne, Switzerland",
    month = "Sep."
    }

  • Steerable Filters and Cepstral Analysis for Optical Flow Calculation from a Single Blurred Image


    Abstract

    This paper considers the explicit use of motion blur to compute the Optical Flow. In the past, many algorithms have been proposed for estimating the relative velocity from one or more images. The motion blur is generally considered an extra source of noise and is eliminated, or is assumed nonexistent. Unlike most of these approaches, it is feasible to estimate the Optical Flow map using only the information encoded in the motion blur. An algorithm that estimates the velocity vector of an image patch using the motion blur only is presented; all the required information comes from the frequency domain. The first step consists of using the response of a family of steerable filters applied on the log of the Power Spectrum in order to calculate the orientation of the velocity vector. The second step uses a technique called Cepstral Analysis. More precisely, the log power spectrum is treated as another signal and we examine the Inverse Fourier Transform of it in order to estimate the magnitude of the velocity vector. Experiments have been conducted on artificially blurred images and with real world data.
    (Appeared in Vi'96)

    Bibtex entry

    @InProceedings{Rekleitis:96,
    author = "Ioannis M. Rekleitis",
    title = "Steerable Filters and Cepstral Analysis for Optical Flow Calculation from a Single Blurred Image",
    pages = "159-166",
    booktitle = "Vision Interface",
    year = 1996,
    address = "Toronto",
    month = "May"
    }

  • Environment Exploration Using ``Just-in-Time'' Sensor Fusion


    Abstract

    This paper describes an approach to combining range data from both a set of sonar sensors as well as from a directional laser range finder to efficiently take advantage of the characteristics of both types of devices when exploring and mapping unknown worlds. We call our approach ``just in time sensing'' because it uses the more accurate but constrained laser range sensor only as needed, based upon a preliminary interpretation of sonar data. In this respect, it resembles ``just in time'' inventory control which attempts to judiciously obtain materials for industrial manufacturing only when and as needed. Experiments with a mobile robot equipped with sonar and a laser rangefinder demonstrate that by judiciously using the more accurate but more complex laser rangefinder to deal with the well-known ambiguity which arises in sonar data, we are able to obtain a much better map of an interior space at little additional cost (in terms of time and computational expense).
    (Appeared in Vi'96)

    Bibtex entry

    @InProceedings{Dudek:96b,
    author = "Gregory Dudek, and Paul Freedman and Ioannis M. Rekleitis",
    title = "Environment Exploration Using ``Just-in-Time'' Sensor Fusion",
    pages = "175-182",
    booktitle = "Vision Interface",
    year = 1996,
    address = "Toronto",
    month = "May"
    }

  • Just-in-time sensing: efficiently combining sonar and laser range data for exploring unknown worlds


    Abstract

    This paper describes an approach to combining range data from both a set of sonar sensors as well as from a directional laser range finder to efficiently take advantage of the characteristics of both types of devices when exploring and mapping unknown worlds. We call our approach ``just in time sensing'' because it uses the more accurate but constrained laser range sensor only as needed, based upon a preliminary interpretation of sonar data. In this respect, it resembles ``just in time'' inventory control which attempts to judiciously obtain materials for industrial manufacturing only when and as needed. Experiments with a mobile robot equipped with sonar and a laser rangefinder demonstrate that by judiciously using the more accurate but more complex laser rangefinder to deal with the well-known ambiguity which arises in sonar data, we are able to obtain a much better map of an interior space at little additional cost (in terms of time and computational expense).
    (Appeared in ICRA'96)

    Bibtex entry

    @InProceedings{Dudek:96a,
    author = "Gregory Dudek, and Paul Freedman and Ioannis M. Rekleitis",
    title = "Just-in-time sensing: efficiently combining sonar and laser range data for exploring unknown worlds",
    volume = "1",
    pages = "667-671",
    booktitle = "International Conference in Robotics and Automation",
    year = 1996,
    organization = "IEEE",
    month = "April"
    }

  • Visual Motion Estimation based on Motion Blur Interpretation


    Abstract

    When the relative velocity between the different objects in a scene and the camera is relative large -- compared with the camera's exposure time -- in the resulting image we have a distortion called motion blur. In the past, a lot of algorithms have been proposed for estimating the relative velocity from one or, most of the time, more images. The motion blur is generally considered an extra source of noise and is eliminated, or is assumed nonexistent. Unlike most of these approaches, it is feasible to estimate the Optical Flow map using only the information encoded in the motion blur. This thesis presents an algorithm that estimates the velocity vector of an image patch using the motion blur only, in two steps. The information used for the estimation of the velocity vectors is extracted from the frequency domain, and the most computationally expensive operation is the Fast Fourier Transform that transforms the image from the spatial to the frequency domain. Consequently, the complexity of the algorithm is bound by this operation into O(n log(n)). The first step consists of using the response of a family of steerable filters applied on the log of the Power Spectrum in order to calculate the orientation of the velocity vector. The second step uses a technique called Cepstral Analysis. More precisely, the log power spectrum is treated as another signal and we examine the Inverse Fourier Transform of it in order to estimate the magnitude of the velocity vector. Experiments have been conducted on artificially blurred images and with real world data, and an error analysis on these results is also presented.
    (M.Sc. Thesis)

    Bibtex entry

    @MastersThesis{Rekleitis:95,
    author = "Ioannis M. Rekleitis",
    title = "Visual Motion Estimation based on Motion Blur Interpretation",
    school = "School of Computer Science, McGill University",
    year = 1995,
    address = "Montreal, Quebec, Canada"
    }