Mobile Robots | Algorithms & Applications Group

Algorithms & Applications Group
Mobile Robots

Feature-Based Mobile Robot Localization and Navigation
supported by NSF
Jinsuck Kim, Roger Pearce, Nancy Amato
Project Alumni: Sooyong Lee

Personal robotics applications require autonomous mobile robot navigation methods that are robust and inexpensive. We are researching on a method for navigation in a known indoor environment, such as a home or office, that requires only inexpensive range sensors such as sonar sensors. Our framework includes a high-level planner which integrates and coordinates path planning and localization modules with the aid of a module for computing regions which are expected, with high probability, to contain the robot at any given time. The localization method is based on simple geometric properties of the environment which are computed during a preprocessing stage. The roadmap-based path planner enables one to select routes, and sub-goals along those routes, that will facilitate localization and other optimization criteria. In addition, our framework enables one to quickly plan new routes, dynamically, based on the current position as computed by intermediate localization operations.

We assume that
1. Partially known environment (map is given).
2. Initial position and orientation of the robot is known.
3. Sonar sensors have range (min/max) and incidence angle limitations.

Trilobot is scanning the environment using three sonar range sensors attached to the rotating head.
Simulation of scanning using ideal range sensors.

Left is the picture of hardware experiment using TriRobot. To improve signal/noise ratio, a dedicated signal processing board was used. Command is generated in a host computer, and transmitted through wireless modem. Right figure shows the simulation of scanning the environment shown above. From the scanning, we extract characteristic points (m,M,D,c) and use that information to localize within a visibility sector.

First iteration of high-level planning. Obstacles (inside and outside), a roadmap (dotted line segments), a path (arrow), uncertainty ellipses are shown.
The robot reaches the goal in the second iteration.

Simulation of navigation is shown above. We use uncertainty ellipses to predict collision and decide where to localize. The path in the first iteration is from start to node g (left figure), and after localization, the second path from node g to the goal (right figure) is used. The movie showing path replanning is presented, in avi format (4Mb) (includes explanatory texts) or animated gif format (80Kb).

Two visibility polygons (a thick rectangle from the wall feature, a portion of annulus from the corner feature) are highlighted. Scannable sectors are shown in gray lines.
Visibility numbers (number of features visible from each scannable sector).

We improved the visibility sectors to scannable sectors based methods. The left figure above shows two visibility polygons, and scannable sectors are obtained by intersecting all the polygons. For each sector, visibility numbers are computed as shown in the right figure. Using one feature, which provides one dimensional information, the uncertainty ellipse is reduced to a thin ellipse (or a line segment if the sensor is noise-free). Two or more features enable reducing the ellipse to a small circle (or a point) after localization.

The problem of minimizing the path cost. Our method extracts such path from the roadmap.
AmigoBot was used in our lab environment to experiment the localization based on scannable sectors and the optimal path planning.

Our navigator extracts an optimal path among all the paths existing in the roadmap using an augmented Dijkstra's shortest path algorithm. It combines the mathematical flexibility of general optimization techniques and computational efficiency of roadmap-based methods. Optimization values include kinematic/dynamic constraints, minimum clearance, and feature visibility for localization. The movie animates searching for the path with maximum clearance, in avi format (6.7Mb) ;5Aor in animated GIF format (30Kb) (green edges are the roadmap, blue arrows are the edges explored durinig the execution of Dijkstra's algorithm, and black lines are the obstacles).

Papers

A Framework for Roadmap-Based Navigation and Sector-Based Localization of Mobile Robots, Jinsuck Kim, Ph.D. Thesis, Parasol Laboratory, Department of Computer Science, Texas A&M University, Aug 2004.
Ph.D. Thesis(ps, pdf, abstract)

Complexity Analysis and Approximate Solutions for Two Multiple-Robot Localization Problems, Jinsuck Kim, Nancy M. Amato, In Proc. IEEE Int. Conf. Robot. Autom. (ICRA), pp. 1052--1057, New Orleans, LA, Apr 2004.
Proceedings(abstract)

Extracting Optimal Paths from Roadmaps for Motion Planning, Jinsuck Kim, Roger A. Pearce, Nancy M. Amato, In Proc. IEEE Int. Conf. Robot. Autom. (ICRA), pp. 2424-2429, vol 2, Sep 2003.
Proceedings(ps, pdf)

Feature-Based Localization using Scannable Visibility Sectors, Jinsuck Kim, Roger A. Pearce, Nancy M. Amato, In Proc. IEEE Int. Conf. Robot. Autom. (ICRA), pp. 2854-2859, vol 2, Sep 2003.
Proceedings(ps, pdf)

Robust Geometric-Based Localization in Indoor Environments Using Sonar Sensors, Jinsuck Kim, Roger A. Pearce, Nancy M. Amato, In Proc. IEEE Int. Conf. Intel. Rob. Syst. (IROS), pp. 421-426, Oct 2002.
Proceedings(ps, pdf)

Multiple Robot Navigation and Localization Using Sonar Sensors in an Indoor Environment, Jinsuck Kim, Roger A. Pearce, Nancy M. Amato, Technical Report, TR01-004, Parasol Laboratory, Department of Computer Science, Texas A&M University, Oct 2001.
Technical Report(ps, pdf)

An Integrated Mobile Robot Path (Re)Planner and Localizer for Personal Robots, Jinsuck Kim, Nancy M. Amato, Sooyong Lee, In Proc. IEEE Int. Conf. Robot. Autom. (ICRA), pp. 3789-3794, May 2001. Also, Technical Report, TR00-028, Parasol Laboratory, Department of Computer Science, Texas A&M University, Nov 2000.
Proceedings(ps, pdf)

Localization based on Visibility Sectors using Range Sensors, Sooyong Lee, Nancy M. Amato, James Fellers, In Proc. IEEE Int. Conf. Robot. Autom. (ICRA), pp. 3505-3511, Jan 2000. Also, Technical Report, TR00-002, Department of Computer Science, Texas A&M University, Jan 2000.
Proceedings(ps, pdf)

Dissertations and Theses

Department of Computer Science | Dwight Look College of Engineering | Texas A&M University
Privacy statement: Computer Science Engineering TAMU