Turn Minimizing Multirobot Coverage - adigoswami/MiniProject1 GitHub Wiki

By Isaac Vandermeulen, Roderich Groß, and Andreas Kolling

Coverage is an essential primitive for path planning, a crucial fundamental for autonomous mobile robots that let robots find the shortest - or otherwise optimal - paths between two points. Coverage is an open-ended problem in the field of robotics pertaining to path planning which can range from as simple as a paintbrush and a lawnmower to as complex as a land rover in human rescue or even a mars rover. The aim is to cover the maximum of the target area in the minimum time while respecting the constraints of the problem. The majority of past work, tried to minimize time by minimizing distance. That however, implies that speed remains constant throught the route. In reality though speed varies and particularly it decreases when a robot needs to make a turn. That is why this work tries to minimize time by minimizing the number of turns.

This paper presented a new multi-robot coverage planner that explicitly considers turn minimization and works for most of the polygonal environment. The goal which is minimization of mission time is defined as

where t_total is total time (mission time), l_path is path length, v_robot is the robot's linear velocity, n_turn is number of turns, and t_turn is the time taken for one turn. The total number of turns equals the number of straight line segments (ranks) directly covered by the robot. Therefore, minimizing time is equivalent to partitioning the target area into a minimum number of ranks that cover the largest possible area.

Partitioning the environment can broadly be divided into five steps.

1. Perimeter following: In a given perimeter, if a robot can move outside of the boundary then only complete coverage of the area will be done. But usually, that’s not the case and the robot has to move inside the perimeter. In doing so, it leaves some areas while parsing each rank. So to overcome this, the robot should follow the ranks along the perimeter and then follow horizontal ranks. This way, near-perfect coverage, is achieved (four corners still can be left depending on the shape of the robot).
2. A unit length grid is overlaid on the polygonal environment such that the maximum length of the perimeter aligns with the grid. This gives an integer rectilinear polygon.
3. Now that a rectilinear polygon has been obtained, it is divided into a smaller rectangle using a checkerboard partition.
4. After the partition, rectangles are oriented using a heuristic which creates locally optimal assignment which can not be improved by changing the orientation of a single rectangle. This is done using an algorithm that finds local optimum and runs in constant time. So the algorithm is very fast and can be repeated to increase the probability of finding the global optimum.
5. Final step involves merging same-sized and similarly oriented rectangles and then creating ranks by adding endpoints and midpoints.

The paper is indeed able to address the problem of coverage by providing a novel algorithm to minimizing the number of turns and thus the total number of time taken to cover the area. The experimental results attest to the success of this algorithm.

Still, there are certainly grey areas. They seem to assume that each robot can start at any point on the map, which usually is not the case. Most buildings have one main entrance and that's where all robots should start. Additionally, this technique works well only in rectangular areas where all the lines of the perimeter are either horizontal of vertical. The efficacy in circular and triangular areas is questionable.

Return to main page.