Howie Choset

Contact Information

Carnegie Mellon University
choset@cs.cmu.edu
http://voronoi.sbp.ri.cmu.edu

Interest in Motion Planning:

Title of Talk

Coverage Path Planning and Applications

Abstract

Part 1: Overview

Whereas conventional path planning determines a path between two points, coverage specifically emphasizes the volume swept along the path by the robot, its detector range, and other effectors. The approach we take to coverage uses a cellular decomposition, which divides the environment into cells and forms a graph encoding the adjacent relationships (topology) among cells. Complete coverage of a target region is achieved by visiting each cell in the decomposition, i.e., finding a walk through the adjacency graph. Coverage of an unknown space reduces to dynamically covering each cell while simultaneously determining the adjacency graph; this enables floor cleaning and inspection of unknown floor spaces. Our current research involves extending our work in planar mobile robot coverage to robotic painting. The challenges here include lifting coverage into three dimensions and ensuring uniform coverage of a target region, which is imperative for high quality and low cost operations.

In many situations, such as robotic de-mining, time may not permit covering a target environment completely. However, if the planner has access to a probabilistic map of mine locations, it can opportunistically guide the robot. For mine fields that have been set down in a pattern, current work involves developing a Bayesian method a Bayesian method for efficiently decoding the parameters that describe the field. Once these are known, the robot can cover a small fraction of the target region and locate most of the mines.

Part 2: Key research issues

For coverage path planning with mobile robots, there are three key research issues: completeness, optimality, and localization. Completeness ensures that the robot has indeed passed over all points in the target environment. Consider the application de-mining. Using non-complete approaches is a kin to using a faulty mine detector. Optimality is important for applications such as painting where the robot must cover the car as quickly as possible, while ensuring uniform thickness. The two challenges here are: covering a non-Euclidean surface and covering it with a complex deformation pattern. Finally, localization or positioning is perhaps the greatest challenge to any mobile robot applications, including de-mining and floor scrubbing. Even if the planner is complete, if the robot does not go where the planner directs it to go because of positioning errors, then there are problems. Conventional mobile robotics has used a learning/optimization approach to localization. In our work, we use a motion planning approach that exploits geometries encoded in the target environment to perform localization by reducing the positioning problem to a graph matching one.

Part 3: Scenarios and benchmarks

  • Benchmark 1: Time to complete: This is simple. Does the use of a motion planning algorithm decrease the time to complete a job.
  • Benchmark 2: Time-Cost to complete. Perhaps, the time to completion is improved by the algorithm, but what cost? Another metric could be time-to-completion multiplied by cost-of-completion.
  • Benchmark 3: Time/Danger. The use of robots could increase the time to completion, but at the savings of reduction in danger. This metric is time-to-completion divided by danger. How to measure danger is a difficult task however.
  • Scenario 1: Robotic Search for Land mines

    The crucial first step of de-mining and UXO hunting is finding the mines and UXO's. Searching for mines and UXO's is a dangerous and expensive task. The use of robots immediately bypasses the danger, reduces the cost, and potentially speeds the process. In de-mining, a robot must pass a mine-detecting sensor over all points in the region that might conceal a mine. To do this, the robot must traverse a carefully planned path through the target region. Can the robot do a faster job? Cheaper? Even if it is cheaper, would people want to give up their de-mining job?
  • Scenario 2: Robotic Painting

    In robot painting, the system implementer does not use any standard path planning technique, but instead ``manually programs'' the robot in an attempt to ensure full coverage of the car-body. This process requires the programmer to position (possibly in an off-line simulation programming environment) the robot at a large number (hundreds) of points along its path over the car-body, trying to maintain both a fixed distance between the car-body and atomizer, and an atomizer orientation that is normal to the surface of the car body. Naturally, regions near complex geometric features require more way points to ensure uniform coverage and thus increases the programming effort. This results in an undesirable trade-off between the cost of programming an automated painting system and both its environmental impact and overall performance. The manual programming approach is a tedious process that can take in excess of three months, according to a specialist who ``teaches'' different car bodies to robot systems. In addition to this long set-up time, the resulting program lacks any flexibility or control over the many process variables, such as applicator distance to the car and paint applicator operating conditions (paint flow-rate, air pressure, etc.). Furthermore, modifying the resulting program to accommodate a seemingly small change can be as difficult as re-programming the entire car-body to the robot from scratch. A coverage path planner may be able to reduce the five month time down to five hours, while at the same time improving performance.
Florent Lamiraux
Last modified: Mon Jun 5 13:41:20 MET DST 2000