Posts Tagged ‘mapping’

August 31st, 2011

Building topological maps to get around - article


Autonomous topological modeling of a home environment and topological localization using a sonar grid map
Jinwoo Choi, Minyong Choi, Sang Yep Nam, Wan Kyun Chung

Service robots entering our homes will need to map their environment and figure out their location as they move around. Previous articles discussed Self-Localization And Mapping (SLAM) approaches that give accurate measurements regarding the location of the robot and objects in the environment. Such so called “metric” approaches can be useful for robot tasks that require high accuracy, such as placing a cup in an exact location.

Instead, the “topological” approach represents the environment as places (nodes) and paths between places as edges. Robots can localize by finding the node where they are currently positioned. The advantage of this approach is that large amounts of data can be stored as nodes and edges and noisy sensors can be used to grossly map the environment. Furthermore, for human robot interactions it is sometimes more useful for the robot to know in what room it is (e.g. kitchen node) rather than a cartesian coordinate.

Following this idea, Choi et al. present a method for autonomous topological modeling and localization in home environments using only low-cost sonar sensors. Experiments were conducted using a Pioneer 3-DX differential drive robot (see picture below) equipped with 12 Murata MA40B8 sonar sensors in a 11.4 m × 8.7 m home environment of several rooms containing items of furniture.

As a first step, the robot was manually guided along an arbitrary path at an average speed of about 0.15 m/s while acquiring sensor data at a rate of 4 Hz. Based on the sonar data, the robot marks a grid map with regions that have obstacles and those that don’t. The grid map is then partitioned into several convex subregions that represent the nodes in the environment. The result is a topological map as can be seen below. As a second experiment, the robot is again guided through the environment and asked to identify its node location, even in situations where furniture has been moved around. Results show that the proposed method provides reliable modeling and localization using sparse and noisy sonar data.

Experimental results of the autonomous topological modeling process: autonomous subregion extractions (each subregion is a different color) and the corresponding topological models.

Although the proposed method was developed for sonar sensors, it can also be applied to any type of sensor that generates grid maps (e.g., laser range finders or stereo vision sensors).

| More

Related posts

No Comments »

May 13th, 2011

Underwater 3D mapping - article


Spectral registration of noisy sonar data for underwater 3D mapping
Heiko Bülow, Andreas Birk

We saw the need for good underwater robots during the Deepwater spill last summer. In such scenarios, a remote operator controls a robot equipped with a camera and means to build a 2D map of the environment. However, if you want your robot to inspect non-trivial structures such as oil- and gas- production and transport equipment, or if you want it to be more autonomous in challenging environments, 3D mapping is essential.

As seen in previous posts, to make a 3D map for a ground robot you might use a laser-range finder. However, similar sensors are not available in underwater environments and the researchers are left coping with low-resolution and noisy measurement systems. To solve this problem, Bülow et al. propose a new method to combine sensory information from noisy 3D sonar scans that partially overlap. The general idea is that the robot scans the environment, moves a little, and then scans the environment again such that the scans overlap. By comparing them, the researchers are able to figure out how the robot moved and can use that to infer where each scan was taken from. This means that there is no need to add expensive motion sensors typically required by other state-of-the-art strategies (Inertial Navigation Systems, and Doppler Velocity Logs).

The approach was first tested in simulation on virtual images with controllable levels of noise. Results show that the method is not computationally expensive, can deal with large spatial distances between scans, and that it is very robust to noise. The authors then plunged a Tritech Eclipse sonar in a river in Germany to generate 18 scans of the Lesumer Sperrwerk, a river flood gate. Results from that experiment shown in the video below compared well to other approaches described in the literature.



In the future, Bülow et al. hope to combine this approach with SLAM to avoid the accumulation of relative localization errors.

| More

Related posts

No Comments »

October 2nd, 2010

SLAM with aerial images - article


Large scale graph-based SLAM using aerial images as prior information
Rainer Kümmerle, Bastian Steder, Christian Dornhege, Alexander Kleiner, Giorgio Grisetti, Wolfram Burgard

Imagine arriving in a new city without a map. Starting from the train station, you might take a walk around the block before returning to your starting point. As you go you’ll probably start building a mental map with the interesting shops, restaurants and streets. Since you don’t want to get lost, you also have to place yourself in this map (localization). This problem of simultaneously mapping while localizing is one of the main challenges in robotics to allow robots to deploy in new environments.

Simultaneous localization and mapping (SLAM) problems often assume robots have no information concerning their environment. This means they can only count on their own sensing and odometry, which often results in an accumulation of mapping errors.

However, with the advent of tools such as Google Earth, there is a huge amount of information that can help robots figure out where they are. Building on this idea, Kümmerle et al. propose to localize a robot by matching data from its sensors to aerial images of the environment. This strategy prevents mapping errors from accumulating.

More precisely, the robot combines information from a 3D laser range finder and from a stereo camera with global constraints extracted from aerial images. The video below shows a MobileRobots Powerbot navigating indoors and outdoors while SLAMing.

Results demonstrate that the maps acquired with this method are closer to reality than those generated using state-of-the art SLAM algorithms or GPS.

| More

Related posts

No Comments »

September 21st, 2010

Exploration using Voronoi diagrams - article


A provably complete exploration strategy by constructing Voronoi diagrams
Jonghoek Kim, Fumin Zhang, Magnus Egerstedt

How can a robot explore and make maps of new environments while avoiding obstacles?

One way is to let the robot remain at equal distance from its two nearest obstacles, thereby navigating exactly in between them (Voronoi edge). If you follow the trajectory performed by the robot, it might look something like the blue line in the figure below.

The Voronoi diagram is shown in blue, intersections are in green and obstacles are in red.

However, challenges arise when the robot is at equal distance from more than two obstacles (intersection). In those cases, the robot needs to decide between which two obstacles it should navigate next. Ideally, you would want the robot to choose its way so that it eventually explores the entire environment.

For this purpose, Kim et al. propose two algorithms that allow the robot to track visited edges and subsequently decide on new edges to explore. By the end of the exploration, the robot will have constructed a topological map of its entire environment based on Voronoi edges (i.e. a Voronoi diagram).

Experiments shown below were conducted with a Khepera III robot equipped with Infrared (IR) sensors for distance measurement and capable of localizing based on odometry. Results show the correct exploration and mapping of the environment.

Voronoi diagram built by a Khepera III robot.

| More

Related posts

No Comments »

July 29th, 2010

Contour extraction for mapping - article


Representing and evaluating ultrasonic maps using active snake contours and Kohonen’s self-organizing feature maps
Kerem Altun, Billur Barshan

To map their environment, robots typically collect large amounts of range and bearing measurements to walls around them. However, when using noisy sensors, additional efforts need to be done to extract a map from the recorded data points.

For this purpose, Altun et al. propose two algorithms for extracting smooth closed curves that compactly represent the environment without gaps. These curves are easier to use and store than the raw data points.

The first method fits active snake contours to the data as can be seen in the image below (left) while the second technique uses a neural network to generate a self-organized feature map of the environment (right). Particle swarm optimization is used to automatically tune the parameters of both algorithms.

In the bottom images, black dots represent the processed ultrasonic data, the blue curve is the curve fitted to this data using active snake contours or self-organized maps and the red curve is ground truth.

Experiments were conducted using the Nomad 200 robot equipped with three front ultrasonic sensors and a structured-light system. The robot was programmed to follow the walls of a small room while mapping the environment.

Results show that active snake contours perform better because they are able to discard outliers in the data and match angles and edges more precisely than the self-organized map.

| More

Related posts

No Comments »