A new scheme for finding the biggest rectangle that doesn't have any obstacle
Jung‐Hwan Hwang, Heung-Seok Jeon · The KIPS Transactions PartA · 2011
Recently, many cleaning robots have been made with various algorithms for efficient cleaning. One of them is a DmaxCoverage algorithm which efficiently clean for the situation when the robot has a time limit. This algorithm uses Rectangle Tiling method for finding the biggest rectangle that doesn`t have any obstacle. When the robot uses grid map, Rectangle Tiling method can find the optimal value. Rectangle Tiling method is to find all of the rectangles in the grid map. But when the grid map is big, it has a problem that spends a lot of times because of the large numbers of rectangles. In this paper, we propose Four Direction Rectangle Scanning(FDRS) method that has similar accuracy but faster than Rectangle Tiling method. FDRS method is not to find all of the rectangle, but to search the obstacle`s all directions. We will show the FDRS method`s performance by comparing of FDRS and Rectangle Tiling methods.