 |
Robot Coverage |
        |
The Coverage problemThere are many applications where we want a mobile robot to sweep a sensor or actuator over all points in a region: lawn mowing, spray painting, inspection, demining, etc. We want to guarantee that the robot will in fact cover all points, and we'd like the robot to do it as efficiently as possible!There are actually several different versions of this problem. First, there are "online" and "offline" versions. In the offline version, the robot is given a map of the region ahead of time and can precompute the path it will take. In the online version, the robot must explore and map the area at the same time it performs the coverage operation. Secondly, there are single-robot and a multiple-robot versions. For the single robot version, we know that the robot will have to cover the entire region itself. For the multiple robot version, the robots must decide how to split the work among themselves. Some technical detailsWe consider solutions of the offline version where we decompose the given region into subregions that the robot can cover using back-and-forth motion (i.e. driving in parallel rows). We have assumed that the region is much larger than the robot and that turning around at the end of a row is the most important factor in finding a good solution.Under these assumptions, we have devised the Minimal Sum of Altitudes (MSA) decomposition which provides an optimal solution to this problem. This algorithm has been implemented and we are currently testing it. We will also be doing experiments using the mobile robots in our lab. Our research papers on this topic will be appearing online in the near future (next month or so). |