Much of the focus of the research effort on mobile robots to date has centered on the problem of finding a path form a start location to a goal location while minimizing one of more parameters such as length of path, energy consumption or journey time. Essential motions of mobile robots can be classified into two categories: point-to-point and sweeping. The point-to-point is a motion for a set of points (0 dimension). The sweeping deals with an area (2 dimension).
Surface coverage or sweeping can defined as: a path of complete coverage is a planned path in which a robot sweeps all areas of free space in an environment in a systematic and efficient manner.
Surface coverage can be classified in two main groups.
1. Known environment
2. Unknown environment
For the known environment case, a path is generated for a given map of the environment. In the unknown environment case nothing is known about the environment a priori. There is not too much published research for the unknown environment case. However a couple papers exist for the known environment case.
First a survey for the known environment case will be given. Then the unknown environment case will be presented. Finally directions for future research will be given.
A rule based planing system which automatically generates the motion command sequence for an appropriate cleaning path according to robot geometry and kinematic restrictions is presented.
The existence of a 2D-map of a prior known walls, pillars, staircase or other fixed objects is assumed. These items are presented by closed 2D-object polygons.
Planning starts with operator-based identification of the borders of the cleaning area in a visualized 2D-map which is part of the planning system. Both, the borders and all object polygons inside the cleaning area are presented by contours.
Two basic changing maneuvers are used for connecting neighboring tracks. U-turn defined by the desired turning radius and turning angle of 180 degrees. Side shift defined by a concatenation of two circular arcs with different sign of curvature.
U turns maneuvers are preferred for path planning, because no change in motion direction is required and operating time as well as floor coverage redundancy can be reduced.
Once all the parameters of the robot and its environment are defined, the planning procedure automatically constructs a technologically feasible cleaning path based on basic path planing templates. 5 basic path planing templates are used. Automatic selection of basic path planing templates is made according to a logical sequence of rules.
This algorithm works efficiently if the area covered does not include any obstacles. An intelligent behavior of the robot should be added to handle with the situations having obstacles.
In this paper complete coverage based upon an extension to the distance transform path planing methodology is presented.
In this approach, instead of propagating a distance from the goal wave front through free space, a new wave front is propagated which was a weighted sum of the distance from the goal together with a measure of the discomfort of moving too close to obstacles. The distance transform can be regarded as a numeric potential field.
The algorithm for the complete coverage of an environment is as follows:
Set Start cell to current cell
This strategy does not guarantee the "complete coverage path" will be an optimum path i.e. the shortest possible and not unnecessarily visiting any cell more than once, the complete coverage produces a reasonable path with minimal secondary visits to grid cells.
A disadvantage of the distance transformation is that only minimize the distance to a goal. However the safety of the robot is important particularly if the robot is operating in an unknown environment since there are uncertainties in the unknown environment i.e the exact shape and position of obstacles.
In this paper an off-line planning algorithm for cooperative sweeping tasks of multiple robots is presented. The algorithm used introduce both edges of the configuration space and Voronoi diagram so as to compute paths in the whole area. Then a tour generated for traversing all the paths by applying the algorithm of the Chinese Postman problem.
According to the cost evaluation, appropriate paths of the tour are assigned to each robot. A robot sweeps an area either in contour-parallel or direction-parallel. A robot sweeps an area along its contour by contour-parallel sweeping. By the direction parallel sweeping a robot sweeps in parallel direction all the way. The direction -parallel method often fails in a concave shape area also direction parallel sweeping goes across other paths which can cause collisions of robots in a multiple mobile robot system. Paths are calculated from Voronoi diagram for parts of the work area where c-space can not be created.
The algorithm is not tested for concave and convex obstacles.
In this paper the problem of sweeping solved by using an algorithm called Autonomous Robot Architecture which is mainly a behavior based architecture. The basic action units "Motor Schemas "in Autonomous Robot architecture are used. Primitive sensorimotor behaviors are used in the construction of the reactive control for the vacuuming robot.
Some examples of the primitive sensorimotor behaviors are Detect-dirt, Over-Dirt, Find Obstacle and Detect-current-heading.
To complete a task the team of robots must move over a specified area while simultaneously collecting small objects which have been uniformly scattered about the environment. Robots able to perform this generic task could easily perform specific tasks such as mowing lawns, or vacuuming a house.
Not really related to surface coverage. It is an application of autonomous robot architecture.
In this paper cellular decomposition is used. Cellular decomposition is a motion planning technique in which the free space is decomposed into cells such that union of the cells is the original free space.
Typically in these methods an adjacency graph, reflecting the connectivity of the individual cells, is formed. Motion planning between two points is achieved via a graph search of this adjacency graph.
A useful cellular decomposition technique is the trapezoidal decomposition in which the robot's free space is decomposed into trapezoidal regions. This approach assumes that vertical line, termed a slice, sweeps left to right through a bounded environment which is populated with polygonal obstacles.Cells are formed via sequence of open and close operations which occur when the slice encounters an event, an instance in which a slice intersects a vertex of a polygon.
By covering each of the cells of a trapezoidal decomposition, a robot is guaranteed to cover an entire free space. By using boustrophedon decomposition a fewer number of cells can be obtained which decreases the number of back and forth motions. With the boustrophedon decomposition approach, two cells are merged into one cell to form bigger cells.
With the decomposition and adjacency graph, the robot can now plan a path that covers the environment. this is done in two steps: a path is found in the adjacency graph that visits each node, and then the explicit robot motions are computed within each cell.
The determination of an optimal path that visits each node in a generic graph is the classical traveling salesman problem
The problem of covering a terrain whose model is not a prior known by a mobile robot is considered in this paper. The proposed solution consists of several subtasks: following the outer boundary of room(s), planning a path for terrain coverage, controlling the robot along the planned path, and adapting the path when obstacles are encountered.
The wall-following module, path planing module, and path execution module was designed and tested in rooms with rectilinear walls. The path adaptation module was only completed for the case of a single obstacle of arbitrary size and shape.
Some what near a wall and away from obstacles and that a start button be pushed. The robot will learn the necessary parameters of the room on its own accord.
By adapting the methods for terrain model acquisition, in particular using trapezoidal decomposition, terrain coverage was shown in a formal framework to be attainable, yet this usually rests on the assumption of an ideal robot with ideal sensors.
In this method robot first discovers the environment, in a sense it is generating the map of the environment. The rest of the coverage algorithm is similar to the rest of the known environment algorithms.
Main attention must be focused on cellular decomposition and Voronoi diagrams which can be both extended to the unknown environments.
For the cellular decomposition algorithms larger polygonal cells means higher efficiency for sweeping. So new algorithms or modified version of algorithms should be further investigated.
Voronoi diagrams now already being used for exploration. Its one of the best sensor -based motion planning method. This approach can be extended for surface coverage assuming a limited sensor range.