The mobile robotics and shape recognition group is an informal
grouping of people and projects at the centre.
The group has at least three
mobile robots sporting a collection of sensors including sonar, video,
BIRIS, and infra-red reflectance, depending on the current experiments
in progress. The primary computing resources are SGI Indigos
and INDYs, some SUN sparc's, and a few other computing
devices integrated into the
general CIM computing environment.
Last update: October 1996.
This group is involved in issues of form representation and discovery.
This relates specifically to the
exploration and representation of
unknown environments using mobile robots,
and the representation and
recognition of objects.
Key technical foci are the abstraction of shape models across scale,
the relationship between signals and symbolic descriptions.
Some of the problems we are
interested in include the following.
How can a moving observer such as a robot recognize
where it is? How can it build but a virtual reality model
of its world for use by a human operator (this is important for
tasks such as remote inspection)? How can a robot learn efficiently
about where it is? How can a group of robots collaboate efficiently?
A typical prosaic objective create a robot than
can learn your office over the weekend:
It is delivered on Friday, you open the box, leave it on the floor, and
go home. By Monday morning the robot would have explored the
office and would be able to carry out delivery and search tasks (``Get
my mail and find Mary and escort her to the conference room'').
A two minute
demo movie is
available in
quicktime format (7.4 Meg binhex encoded)
or in
MPEG format (3.1 Meg).
The quicktime version is a compressed MacBinary file. The
MPEG version has no audio track; a major disadvantage.
Be warned that to keep the size down, the movie has been severly
compressed and the quality isn't great (image size is 160x120 but it
should be played a double size on most machines).
Newton books
Much is this information is also available in the form of a Newton Book
for perusal using an Apple Newton device.
Click
here to obtain a "stuffit" archive of this book. (Note:
some of the terms above may be tradmarked by their respective owners.)
A brief abstract of some of our work on position estimation in different
contexts is also
available for download as a Newton book.
More information sources are mentioned at the end of this page.
Graduate students
If you want to apply to be a grad student working in this group, you can
get
further information from the school of computer science.
Note that CIM is not an "academic unit" and different faculty are
officially associated with different departments.
A Distributed, device independent mobile robot controller and simulator.
It supports
distributed computation and visualization and can control one or more
real Nomad or RWI robots.
Some additional details and a picture are available.
This project deals with the inference of environmental structure from
shadow information.
Click here for an abstract
Multi-Robot Exploration and Rendezvous
N. Roy, I, Rekleitis, G. Dudek.
This project deals with the exploration of an unknown
environment using two or more robots working together.
Key aspects of the problems coordination, and particularly
rendezvous, between the robots, and efficient decomposition
of the exploration task.
Object description and recognition
W. Alami, G. Dudek, Nigel Ayoung-Chee, Frank Ferrie
This research investigates the combined use of a sonar range finder and a laser range
finder (QUADRIS or BIRIS) for exploring a structured indoor environment.
The methodology is called "just-in-time" sensing.
A longer abstract is also available.
Reliable Vehicle Trajectory Planning
G. Dudek, Chi Zhang
We are using a hybrid method for vehicle path planning that guarantees
globally acceptable solutions yet has limit time and space complexity.
This depends on a combination of variational methods with other
approaches.
Localizing a Robot with Minimum Travel
Gregory Dudek (dudek@cim.mcgill.ca),
Kathleen Romanik (romanik@dimacs.rutgers.edu),
Sue Whitesides (sue@cs.mcgill.ca)
G. Dudek in collaboration with Professors
E. Milios and
M. Jenkin
of York U. and
D. Wilkes at Ontario Hydro
We are interested in elaborating a taxonomy for systems
of multiple mobile robots. The specific issues we are foc
using on are the relationships between inter-robot
communication, sensing, and coordination of behaviour in the
context of position estimation and exploration.
A short paper describing a trial experiment in this context
is
available in postscript form.
Mapping using weak information
G. Dudek in collaboration with Professors
E. Milios and
M. Jenkin
of York U. and
D. Wilkes at Ontario Hydro
Autonomous navigation using sensory information often depends
on a usable map of the environment. This work deals with the
automatic creation of such a maps by an autonomous agent
and the
minimal requirements such a map must satisfy in order to be useful.
One aspect of this work
is the analysis of how uncertainty either in the map or in
sensing devices relates to the reliability and cost of navigation and
and path planning. Another aspect is the development of sensing
strategies and behaviours
that facilitate reliable self-location and map construction.
Probabilistic sonar understanding
Simon Lacroix, Grogory Dudek
Pose Estimation From Image Data
Without Explicit Object Models
G. Dudek, Chi Zhang
We consider the problem of locating a robot in an initially-unfamiliar
environment from visual input. The robot is not given a map of the
environment, but it does have access to a limited set of training
examples each of which specifies the video image observed when the
robot is at a particular location and orientation. Such data might
be acquired using dead reckoning the first time the robot entered an
unfamiliar region (using some simple mechanism such as sonar to avoid
collisions). In this paper, we address a specific variant of this
problem for experimental and expository purposes: how to estimate a
robot's orientation(pan and tilt) from sensor data.
Performing the requisite scene reconstruction needed to construct a
metric map of the environment using only video images is difficult.
We avoid this by using an approach in which the robot learns to
convert a set of image measurements into a representation of its pose
(position and orientation). This provides a {\em local} metric
description of the robot's relationship to a portion of a larger
environment. A large-scale map might then be constructed from a
collection of such local maps. In the case of our experiment, these
maps express the statistical
relationship between the image measurements and camera pose. The
conversion from visual data to camera pose is implemented using
multi-layer neural network that is trained using backpropagation.
For extended environments, a separate network can be trained for
each local region. The experimental data reported in this paper
for orientation information (pan and tilt) suggests the accuracy
of the technique is good while the on-line computational cost is very
low.
Spatial abstraction and mapping
P. Mackenzie, G. Dudek
This project involves the development of a formalism and
methodology for making the transition from raw noisy
sensor data collected by a roving robot to a map composed
of object models and finally to a simple abstract map
described in terms of discrete places of interest. An important early stage
of such processing the the ability to select, represent and
find a discrete set of places of interest or landmarks that will make
up a map. Associated problems are those of using an map to accurately localize
a mobile robot and generating intelligent exploration plans to
verify and elaborate a map.
Click here for a compressed postscript copy of a recent paper on this work.
As a sensor-based mobile robot explores an unknown environment it
collects percepts about the world it is in. These percepts
may be ambiguous individually but as a collection they
provide strong constraints on the topology of the environment.
Appropriate exploration strategies and representations allow
a limited set of possible world models to be considered as
maps of the environment. The structure of the real world and the
exploration method used specify the reliability
the final map and the computational and perceptual complexity
of constructing it. Computational tools being used to construct a
map from uncertain data range from graph-theoretic to
connectionist.
Human object recognition and shape integration
Gregory Dudek,
Daniel Bub: Neurolinguistics, Montreal Neurological Inst.,
Martin Arguin: Phychology Dept., University of Montreal
Computational vision is defined, to a large extent, with reference to
the visual abilities of humans. In this project we are examining the
relationship between the characteristics of object shape and the
abilities of humans to recognize these shapes.
This includes
the modelling of subjects with object recognition deficits due
to brain damage as well as normal subjects.
Click here for a compressed postscript copy of a recent paper on this work.
Dynamic reasoning, navigation and sensing for mobile robots
Martin D. Levine, Peter Caines, Renato DeMori, Gregory Dudek,
Paul Freedman (CRIM), Geoffrey Hinton (University of Toronto)
The goal of this project is to develop both the theoretical basis
and practical instantiation of a mobile robotic system
will be able to reason about tasks, recognize objects in its environment,
map its environment, understand voice commands, and navigate through the
environment and perform the specified search tasks. This will be achieved
in a dynamic environment, in that knowledge of a (possibly changing) world
may be updated, and the tasks themselves may be radically altered during
the system's operation. Core research areas involved include
perceptual modelling, control theory, neural networks, graph theory,
attentive control of processing and speech understanding.
Among the key capabilities indended as outcomes of this
project are:
Integrated low (eg, points and lines) and high level (eg. places and
rooms) descriptions of the environment.
Ability to deal with a changing environment.
Ability to reason about multiple tasks and the changing environment.
Ability to learn about the environment and the sensor characteristics.
Ability to accept high level verbal commands (with a limited lexicon and
syntax) similar to those employed by humans (based on psychological data)
and translate them into control actions for the robot and sensors.
Enhanced reality for mobile robotics
Kadima Lonji, G. Dudek
This project involves the use of a synthetic scene model for
teleoperation or pose estimation. Live video and synthetic model
information is fused to produce a composite image.
Natural language referring expressions in a
person/machine dialogue.
A FLEXIBLE BEHAVIORAL ARCHITECTURE
FOR MOBILE ROBOT NAVIGATION
J. Zelek, M. D. Levine
The intention of this study is to design an architecture that
allows the behavioral control strategy that is flexible, generalizable, and
extendable. The component dedicated to behavioral activities should be able
to
attempt tasks with or without a reasoning module. We are investigating 2D
navigational tasks for a mobile robot possessing sonar sensors and a
controllable TV camera mounted on a pan-tilt head.
The major aspects of our proposed behavioral architecture are as follows:
- A natural language lexicon is used to represent spatial information
and for defining task commands. The lexicon is used as a language for
internal communications and user-specified commands. The task is to go to
a location in space, either known or determined by locating a specific object.
- An extension of a formalism, referred to as teleo-reactive (T-R) programs
(Nilsson:94), is used for specifying behavioral control.
The extensions of this approach involve dealing with real-time resource
limitations and constraints.
This document is Copyright (c) Gregory Dudek, 1996.
You are granted permission for the non-commercial use,
reproduction, distribution or
display of this document in any format under the following restrictions.
Appropriate credit is given as to
its source and authorship.
This permission is valid for a period of 45 (forty-five) days
from the time this document was obtained from McGill University.
All other rights reserved by the author(s).