-
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"
}