Tackling Area Coverage Problems in a Reconfigurable Floor Cleaning Robot Based on Polyomino Tiling Theory

Abstract

Whilst Polyomino tiling theory has been extensively studied as a branch of research in mathematics, its application has been largely confined to multimedia, graphics and gaming domains. In this paper, we present a novel application of Tromino tiling theory, a class of Polyomino with three cells in the context of a reconfigurable floor cleaning robot, hTromo. The developed robot platform is able to automatically generate a global tiling set required to cover a defined space while leveraging on the Tromino tiling theory. Specifically, we validated the application of five Tromino tiling theorems with our hTromo robot. Experiments performed clearly demonstrate the efficacy of the proposed approach resulting in very high levels of area coverage performance in all considered experimental cases. This paper also presents the system architecture of our hTromo robot and a detailed description of the five tiling theorems applied in this study.

1. Introduction

Floor cleaning, be it commercial or domestic, is commonly considered to be boring, repetitive, and tiresome. Over the course of the last two decades, considerable work has been conducted in seeking to develop automated cleaning robots. Such work has led to a new generation of robot cleaners, and subsequent improvements in quality of life and personal productivity. Robotic cleaners are predicted to become commonplace in the years to come, with estimated sales of such devices forecast to reach $2.5 billion by 2020 [1]. Currently, market leaders include Samsung, Neato, iRobot, and Dyson, with their floor-cleaning devices commonly adopting a circular, or half-circular shape. Such devices use a network of internal sensors to navigate a specific floorspace independently. A significant amount of robotics research has studied cleaning robots and their human interaction, functionality, design, independence, benchmarking, and mechanics. Such literature has led to the production of multiple new robotic devices. Gao et al., for example, proposed an innovative robot cleaner for busy locations, such as transport hubs, that utilized Swedish wheel technology to navigate such floorspaces effectively [2]. Another example of such innovation can be seen in the work of Jason Yan, who created a wheelset mechanism to allow robotic devices to navigate irregular floorspaces, safe from grounding or flooring damage [3]. In terms of autonomous operation, the work presented in [4] outlined a Simultaneous Localization And Mapping (SLAM)-based methodology for floor cleaning, blending magnetism and odometry to navigate set areas, and ensure optimum coverage independently. In another work presented in [5] proposes a neural-network-based architecture for robotic floor-cleaning, allowing autonomous devices to plan routes and circumnavigate obstacles in unpredictable surroundings.

With a concentration on the relationship between human users and their robotic devices, Fink et al. [6] conducted a six-month ethnographic investigation into aspects of the social activity, user perception, and usage analysis. The work presented in [7] proposes a specific gesture-reliant technology, utilizing ceiling-mounted cameras, whereby users could interact with, and operate, a cleaning device. In another work, Panagiota Tsarouch et al., conducted a study on Human–Robot Collaboration (HRC) framework for the execution of the collaborative task in hybrid assembly cell [8]. In this study, the proposed framework facilitates the placement of sequential task appointed to robots and humans in a distinct workspace. Sotiris Makris et al., proposed a similar human–robot collaborative work, wherein they demonstrated flexible assembly task between a dual arm robot and humans in an automotive industry case [9]. Much study has also been conducted into cleaning robots in a multi-robot environment. Luo and Yang, for example, created a neural-network approach for a community of cleaning robots [10]. Further to this, Janchiv et al., proposed a cellular decomposition approach, employing two internal cleaning robots for optimum surface-area coverage [11]. In terms of benchmarking for floor coverage, critical performance indicators of independent movement, noise, and dust collection were highlighted by Rhim et al. [12]. Further work, by Wong et al., proposed computer vision methodology for benchmarking a cleaning robot’s floor coverage [13].

Despite their advantages being repeatedly underlined by existing literature, traditional technologies in the cleaning robot field are still limited, and their performance is often unreliable. Coverage presents a common issue, owing to the fixed morphologies of existing devices. There is a significant gap in the market for cleaning robots with reconfigurable morphologies, reacting to their surroundings to provide optimum floor coverage. Over the past thirty years, significant interest has been paid to the field of reconfigurable robotics. Robotic devices are commonly split into three primary groups [14]: inter-reconfigurable, nested reconfigurable, and intra-reconfigurable. For devices in the intra-reconfigurable group, they can adapt their own morphologies. Scorpio, for example, was a robot developed by Tan et al. [15] that, with an intra-reconfigurable code, could utilize separate morphologies, by climbing, crawling, or rolling across surfaces. Further examples of such intra-reconfigurable devices are an anthropomorphic robot hand developed by [16] that altered its palm to create different topologies and a reconfigurable under-actuated legged platform [17] that could create unique movement gaits. Jason Spiliotopoulos et al., presented their version of intra-reconfigurable robots wherein they developed a high-speed multi-fingered reconfigurable gripper. In this work, they have performed preliminary grasping experiments highlight its potential in robotic handling applications [18]. Generally, inter-reconfigurable devices combine various technologies to create an overarching morphology, combining and separating to take on alternative ones. Sambot [19] provided an example of this, with its ability to swarm with, and separate from, other robots, in order to adopt new morphologies, along with a sub-aqueous platform that can dissect itself into separate modules, and move in an eel-like fashion through water [20]. Nested reconfigurable robots involve platforms that are capable of both intra-reconfigurable and inter-reconfigurable abilities. Tan et al., presented a nested reconfigurable robot, Hinged-Tetro [21] that is capable of transforming between morphologies as a single unit as well as assemble and disassemble with a set of other fellow robots to generate global morphologies. In our earlier work, we put forward and validated a Tetris-inspired intra-reconfigurable floor cleaning robot, hTetro capable of changing its morphology to any of the seven one-sided tetromino forms towards maximizing floor coverage area [22]. We also benchmarked the area coverage performance of our hTetro robot with a commercially available fixed morphology robot. The experimental design involved a human user reactively switching the morphology of the hTetro robot in relation to the perceived set of obstacles in the environment towards maximizing coverage performance with no global planning involved. In this paper, we significantly extend our earlier work by leveraging on the Tromino tiling theory to automatically generate a global tiling set that would enable our hTromo robot to cover a given area. Especially, we demonstrate the application of five Tromino tiling theorems in the context of area coverage task with hTromo robot.

Polyomino tiling theory concerns the use of pre-determined polyomino types, in order to cover a surface, and has been the subject of much academic study Since the 1950s. Craig S. Kaplan [23] used the polyomino tiling theory to develop a mathematical and algorithmic methodology for computer graphics software, and Ostromoukhov et al. [24] used it to propose a method for fast hierarchical importance sampling with blue noise properties. This development was then applied to a high-quality graphical video, providing rapid sampling and greater visual quality. A similar algorithm was applied by Takefuji and Lee to tile polyominoes [25], with it being subsequently verified as a method for the insertion of components or cells in Very Large Scale Integration (VLSI)-design, creating printed circuitry and tackling 2D and 3D packaging challenges.

The employment of polyomino tiling theory in gaming software has been widely detailed in the literature. In [26] for example, Jho and Lee created a new polyomino re-tiling system whereby a combination of polyomino pieces was interchanged with another set. The suggested algorithm was applied to a puzzle containing various polyomino copies. By using this algorithm, new game stages could be created, without the need for added system memory. Further examples of its employment are shown by the authors of [27], creating a unique 3D tiling method for a 3D puzzle, and a photominoes synthesizer, detailed in study [28], which applied digital images to the creation of polyomino pieces for a jigsaw. Although numerous research work has been done towards development and application of Polyomino tiling theories, they are largely limited to gaming and graphics domains. Besides, none of the previous works involving tiling theory has been applied to a robotic system towards solving area coverage problem, which opens much opportunity for research and development.

In this paper, we present a novel application of Tromino tiling theory, a class of Polyomino with three cells in the context of a reconfigurable floor cleaning robot, hTromo. The developed robot platform is able to automatically generate a global tiling set required to cover a defined space while leveraging on the Tromino tiling theory. The main challenges in the proposed approach include the design of the reconfiguring mechanism, the inclusion of cleaning features and the non-trivial process of implementing theoretical Tromino tiling designs generated analytically into physical mechanisms. All these aspects are detailed in this paper, concluding with experimental results using the prototype hTromo robot that validates the proposed approach. The application of Tromino tiling theory herein presented is a critical effort towards designing a self-reconfigurable robot that is capable of autonomously generating global tiling set for any given space, identifying associated local and global optimal trajectories and generating appropriate motor primitives based on inverse kinematics and dynamics model.

Rest of this article is organized as follows: Section “Polyomino Tiling Theory” introduces the concept of polyominoes and the specific Tromino tiling theorems implemented in this paper. Section “hTromo: Robot Architecture” presents a discussion on the realization of a Tromino inspired floor cleaning robot. This Section covers details on the core component modules of the developed robot namely the reconfigurable base, mobility unit, cleaning module and Android application interface. Section “Experiments and Results” details the experimental design involving our hTromo robot and application of Tromino tiling theory, test setup, and analysis of the results. Finally, the Section “Conclusion” concludes this study and discusses future work.

2. Polyomino Tiling Theory

Polyominoes are plain geometrical structures formed by endwise coupling of congruent squares [29]. Based on spatial orientation, geometrical transformation and chirality, each polyomino can be categorized into free polyominoes, one-sided Polyominoes, and fixed Polyominoes. For instance, the set domino, formed by the combination of two congruent square, can have single one-sided, single free and two fixed dominoes as its subsets. Correspondingly, triominoes (3-omino) can exist as two free, two one-sided, and six fixed triominoes [29]. In the case of tetromino that contains four constituent squares can form five free, seven one-sided, and nineteen fixed tetrominoes. In this paper, we used a Tromino inspired reconfigurable robot, hTromo capable of switching between one of the three forms.

Polyominoes Tiling Theory

The Polyominoes tiling theory deals with the problem of partitioning or filling of a geometrical region using same or multiple sub-regions. Literature offers numerous work that discusses tiling theorems with proof for distinct polyomino set. With Tromino forming the inspiration for our hTromo robot, this paper presents our first attempt at applying Tromino tiling theory to coverage problem for a floor cleaning robot. Specifically, we apply five theorems proposed in [30,31,32].

Theorem 1.

An a × b rectangle can be tiled with L- and I-trominoes if and only if the area of that rectangle is divisible by 3.

Figure 1 shows tiles τ2 and τ4 a right-oriented L-tromino piece, and tiles τ1 to τ3, a left-oriented L-tromino piece. In the experiments performed, we either used pre-defined testbed space that was either a complete rectangle or modified rectangle based on the theorem considered where the concerned robot was able to achieve complete coverage. Figure 2 presents a sample case for Theorem 1 involving tiling using I- and L-tromino configurations.

Theorem 2.

Let a, b be the integers such that 2 ≤ a ≤ b. An a × b rectangle can be tiled with set ‘T’ trominoes if and only if one of the following conditions holds:

1. 

a = 3 and b is even;

2. 

a ≠ 3 and ab is divisible by 3.

‘T’ is a set of four L-trominoes. Since the tromino has three constituent squares with unit area, any rectangle with an area that is a multiple of 3 can be covered using any of the trominoes pieces. This notion leads to the formulation of Condition 2 of Theorem 2. Let a and b be the dimensions of the rectangle to be tiled. Since the area of the rectangle has to be a multiple of 3, (a × b) = 3n, where n $\in$ {1, 2, 3……}. This implies that either a or b must be divisible by 3. However according to condition 2, a cannot be 3. For example, the rectangles that have a dimension of 6 × 5, 4 × 9, 12 × 6 can be tiled using the set of ‘T’ trominoes. Condition 1 of Theorem 2 excludes certain rectangles that cannot be tiled using ‘T’ trominoes. Specifically, according to this theorem, it is impossible to tile rectangles that have a dimension of 3 × 5, 3 × 7, 3 × 9 using any arrangements of ‘T’ trominoes. The Lemmas 1 and 2 detailed below validates Theorem 2.

Lemma 1.

Let a = 3 and b ∈ {2, 4, 6} then a 3 × b rectangle can be tiled using the arrangement of ‘T’ trominoes shown in Figure 3a. Hence it is proved that the smallest rectangle that satisfies condition 1 Theorem 2 is (3 × 2). Let b > 6, even numbers, and c ∈ {2, 4, 6}, then b = 3n + c, where n can have a positive even integer value. As such, it allows for splitting of a (3 × b) rectangle into n (3 × 2) rectangles and one (3 × c) rectangle, as in Figure 3b. This implies, if b ≥ 2, even numbers, then a (4 × b) rectangle can be tiled using a set of ‘T’ trominoes.

Lemma 2.

According to condition 2 of Theorem 2, the smallest rectangle that can be tiled using ‘T’ trominoes is (2 × 3). Let a = 4; then according to condition 2, the possible b values must be divisible by 3. Let’s assume the dimension of the rectangle is 4 × 6, Figure 4a; then it is possible to decompose it to a 4 (2 × 3) rectangles. Hence, a rectangle with a dimension was a > 3, and b is a multiple of 3, then the rectangle could be decomposed to n(2 × 3) rectangles as in Figure 4b, which can be tillable with ‘T’ trominoes. However, the rectangle with dimensions of 5 × 3, 7 × 3, and 9 × 3 cannot be tiled using any arrangement of ‘T’ trominoes.

Theorem 3.

A deficient n X n rectangle board can be tiled with the set of ‘T’ trominoes, if, and only if, either:

1. 

n is odd, and >5, and n² − 1 is divisible by 3.

2. 

n is even, and >1, and n² − 1 is divisible by 3.

Also with Theorem 3, we are utilizing set ‘T’ tromino pieces in order to tile the given area. The term deficient in the theorem describes a square grid of side a and b with a single cell truncated. According to Theorem 3, if the sides of the squares are odd, it should be greater than 5, and to the square of that sides subtracted by 1 must be divisible by 3 to tile the space using ‘T’ trominoes. In order to tile an even-sided deficient square with ‘T’ trominoes, the value must be greater than 1 and, to the square of that value subtracted by 1 must be divisible by 3. The above notion regarding tiling the deficient square points to Conditions 1 and 2 of Theorem 3. Lemmas 3 and 4 validate Theorem 3 by proving Conditions 1 and 2.

Lemma 3.

Let M (a, b) be the modified rectangle and segmented into an (i, j) grids. Let’s consider an M (7 × 7) rectangle grid with a single (1, 1) square is removed Figure 5a Left. As shown in Figure 5a Right, the considered rectangle can be decomposed to a 2 × 3, 3 × 2, 5 × 5, and three separate L-trominoes. According to Lemma 1, a 2 × 3, and 3 × 2, a rectangle can be easily tillable with ‘T’ tromino set. When it comes to a 5 × 5 square, it is tileable with ‘T’ trominoes only if the corner cells are removed as shown is Figure 5b. Hence, the results show that an M (7 × 7) rectangle with single cell removed is tillable with ‘T’ trominoes. It is also possible to tile an M (7 × 7) rectangle when we delete (1, 4), (2, 3), (2, 4), or (4, 4) cells.

Lemma 4.

Similarly, with condition 2 Theorem 3, we are considering an M (10 × 10) rectangle. The considered rectangle can be split into a 7 × 7, 6 × 3, 3 × 6, and 4 × 4 sub-rectangles shown in Figure 6b. According to Lemma 3 a 7 × 7 rectangle with one square removed can be tiled with ‘T’ tromioes. Similarly, with the help of Lemmas 1 & 2, we know that 6 × 3, and 3 × 6 can also be tiled with ‘T’ trominoes. For a 4 × 4 square, it is proven that a $2^k\times 2^k$ when k $\ge 1$ can be tiled with ‘T’ tominoes as shown in Figure 6a. Hence, it is proved that a rectangle with even sided can be tiled using set of ‘T’ tromino pieces.

Theorem 4.

An Aztec Diamond, AZ(n) can be tiled using ‘T’ set of tromino tiling pieces if, and only if n (n + 1) ≡ 0 mod 3, where n can be a positive integer.

Theorem 5.

A deficient Aztec Diamond, AZ(k) can be tiled using ‘T’ set of tromino tiling pieces if, and only if k = (3n − 2), where n can be a positive integer.

An Aztec diamond of order n is the region obtained from staircase shapes of height n by gluing them together along the straight edges. According to Theorem 4, a non-deficient Aztec diamond can be tiled using the ‘T’ set of tromino pieces if and only if n (n + 1) ≡ 0 mod 3. Hence, it is clear that the tabbed $n{\mathrm{th}}^{}$ order must be divisible by 3 after applying it to n (n + 1), were n can be any integer. Similarly, with Theorem 5, it is clear that, we can tile a defected Aztec diamond (with one square removed) using ‘T’ tromino set only if the $n{\mathrm{th}}^{}$ order is equivalent to 3n − 2, where n can be any integer. Below mentioned Lemma 5 and 6 supports the conditions of Theorems 4 and 5.

Lemma 5.

Note that the only values for which n (n + 1) ≡ 0 (mod 3) holds are n = 3 k or n = 3k − 1 for some unique positive integer k. Thus, the statement is equivalent to say that for all positive integers k there is a tiling for AZ (3k) and AZ (3k − 1) as shown in Figure 7 but there is no tiling for AZ (3k − 2). The tiling of Aztech diamond can be achieved by tiling the edges of considered space. We used stairs concept in order to tile the edges of the Aztec diamond. A stair is a polyomino made-up of tromino pieces wherein their 180° rotations are connected as steps shown in Figure 8. The height of the stair was computed under the formulation of 3k + 2, for any positive integer k. The height of the stair is equal to the order of Aztec diamond. If the order of Aztec diamond is n ≤ 4, then AZ (n) can be tiled using ‘T’ trominoes through tiling partial or half stairs as shown in Figure 7 (Top Right & Left). If the order n ≥ 5, then the AZ (n) can be tiled using K-stair of ‘T’ tromino pieces. The image argument for order n = 5 is shown in Figure 7 (bottom), green colored tromino pieces tiled the edges using 1-stair.

Lemma 6.

To tile AZ (3k − 2) with one defect a fringe appearing has been used as shown in Figure 9 left. It is easy to check that if a fringe has exactly one defect, then it can be covered with ‘T’ trominoes. In particular, a possible rectangle with a fringe that can be tiled by ‘T’ tromino is 2 × 2 square. Similarly, as lemma 5, the stair patterns were used to tile the edges of the concern defected Aztec diamond. The space with fringe placed is considered as a 2 × 2 square plot and can be tiled using ‘T’ trominoes Figure 9 left. The other space of defected Aztec diamond was tiled similarly to Lemma 5. In another approach, tiling pattern of Figure 8 was used wherein the k-stairs laid above and below the fringe in order to tile the Aztec diamond with ‘T’ trominoes, as shown in Figure 9 Right.

3. hTromo: Robot Architecture

The experiments presented in this paper involves a novel area coverage technique with Tromino tiling theory as a basis. The proposed approach was validated on the hTromo; a Tromino inspired reconfigurable floor cleaning robot that was developed based on the theory of “hinged dissection of polyominoes”. Hinged dissection is a geometric analysis wherein a planar structure dissected into finite pieces connected by “hinged” points, such that the formation of one structure to another can be accomplished by continuously swinging the hinged points without breaking the chain [33]. Several studies targeting the concept of hinged dissection have been reported. Pertinent efforts in this field have included the remodeling of an equilateral triangle into a polygon [34], combining several rigid duplicates of the same polyhedron [35], the creation of unique patterns through rearrangement of shapes from one to another [36], and 3D hinged dissection being used for the formation of 3D polyhedra. In robotics, the work presented in [21] studies the hinged dissection principle, with a view to creating a nested re-configurable robot module named ‘hinged-tetro’, and to demonstrating that Left Left Right (LLR) or Left Left Left (LLL) hinged dissection applies to the creation of all one-sided tetromino forms. The LLR hinged dissection method was utilized in the creation of the hTetro cleaning device [22], in order to achieve the transformational capability. Since hTromo robot only consists of three blocks and requires only two hinged points; we utilized Left Left (LL) hinged dissection configuration to achieve the shape-shifting ability outlined in

Table 1. LL hinged points of hTromo robot. LL: Left Left.

.

Mechanism Design

The hTromo robot comprises three squares, and two (LL) hinged points, to facilitate transformation. Figure 10 shows the intermediate form of the hTromo robot while transforming from one configuration to another. Figure 11 shows the detailed component list for the device. Block 1 contains the requisite components for movement, block 2 the electronic peripherals, and blocks 3 the cleaning components and functionality. A single hTromo block measures 140 × 140 × 75 mm, with 4 mm thick honeycomb walls, formed from PLA for minimum tensile strength. The device houses six DC motors, with four mounted on block 1 and controlled fundamental mobility. Two further DC motors sit on block 3, optimizing smooth mobility for the robot. For ease of navigation within an area, the robot has omnidirectional movement capabilities. Furthermore, caster wheels were attached to blocks 2 and 3 to maintain the position of the blocks. Blocks 3 also house a tailor-made vacuum module, for cleaning functionality, and the collection of dirt. The suction chamber and duct were specifically created to minimize loss of suction and dust spillage during operation. For the creation of the three available one-sided Tromino shapes, the robot houses two smart servos that sit on hinged points. Both the servos attached to, and anchoring, block 2 and driving blocks 1 and 3. Every motor fixes its position with its stall torque, allowing it to continually support robot morphology for the duration of its operation.

For a low-level controller, block 2 houses an Arduino Mega 16-bit microcontroller to manage movement and transformation gait performance. Action commands are sent by Raspberry PI which is also mounted on block 2, with the microcontroller executing these commands, sending Pulse Width Modulation (PWM) motor primitives to the driver unit. Integrated electronics are powered by a LiPo battery, providing 7.4 v through a toggle switch. In block 2, a DC step-down controller maintains a 5 v input voltage for the Raspberry PI. The vacuum module is operated through activation of a relay switch. For user commands to reach the Raspberry PI, a wireless Bluetooth interface is used. Figure 12 shows an intuitive Android App that was developed for the control of the hTromo robot. To maneuver and transform the robot, and operate its cleaning functions, users select commands from a list of pre-set options. The app provides arrow buttons for directional commands, seven Tetris buttons for shape reconfiguring, pause and play buttons to freeze or commence actions, and on and off buttons for vacuuming operations.

4. Experiments and Results

In this paper, we present the application of Tromino tiling theory, a class of Polyomino with three cells in the context of a reconfigurable floor cleaning robot, hTromo. The developed robot platform is able to automatically generate a global tiling set required to cover a defined space while leveraging on the Tromino tiling theory. There are five set of theorems that this work sought to validate, as denoted in Section 2. The first set of experiments validated the application of Theorem 1 using a rectangular surface of 140 × 126 cm, split into 10 × 9 squares. Figure 13a presents the universal tiling set that was auto-generated by our path planning algorithm to cover the given area using only L- and T-trominoes. In order to validate the application of Theorem 2, Lemma 1, a rectangular area measuring 126 cm × 112 cm was utilized and further sub-divided into 9 × 8 square grids. Figure 13b illustrates the corresponding universal tiling set auto-generated by our path planning algorithm using which tiles the second test area with only T-set trominoes. The third set of experiments validates Theorem 2, Lemma 2. This was done in a rectangular area of 154 cm × 126 cm, split into 11 × 9 square grids.

Figure 13c, shows the corresponding tiling set generated based on Theorem 2, Lemma 2. In the fourth set of experiments, obstacles were inserted within the test area in order to modify the area based on Theorem 3, Lemma 3. We utilized a square area of 154 cm × 154 cm, subdivided into 11 × 11 square grids. According to the assertion of Lemma 3, this modified area can be tiled using a ‘T’-set of tetromino pieces. Figure 13d illustrates the universal tiling set that was auto-generated based on Theorem 3, Lemma 3. The fifth set of experiments focused on validation of Theorem 3, Lemma 4. The test was performed within a square area of 140 cm × 140 cm, further subdivided into 10 × 10 square grids. To meet the requirements of Lemma 4 towards realizing a modified rectangle, obstacles were inserted into the middle of the test area. The global tiling set that was auto-generated based on Lemma 4 can be seen in Figure 13e.

With Lemma 5 of Theorem 4, we used a square plot as a test arena with a dimension of 168 cm × 168 cm and segmented it into 12 × 12 square grids. Since the concern theorem deals with Aztec diamond space, we modified the defined area into a 6th order diamond space by placing obstacles. Figure 13f shows the tiling set generated with ‘T’ trominoes according to the lemma 5 and the orange shaded areas are filled with obstacles. Similarly, for Lemma 6, we used a 112 cm × 112 cm square plot which was segmented to an 8 × 8 square grids. The considered area was filled with obstacles in order to convert the square area to a 4th order Aztec diamond. Also, we placed a separate obstacle in the 4,4 cell to modify area as a deficient diamond. Figure 13g shows the tiling set generated with ‘T’ trominoes according to the lemma 6.

4.1. Experimental Testbed

When establishing the test environment, a pre-determined floor area was split into squares, congruent with the hTromo robot blocks, and an overhead support frame mechanism erected, to accommodate a camera. Image data captured by this camera was post-processed, to evaluate the percentage of the test area covered by hTromo during each experiment. The complete area used for all experiments measured 196 × 196 cm. The limits of the specified test area were adapted using an extendable metal framework, according to the assertions of each theory. The test area was further split, using white tape, into a 14 × 14 square grid. As shown in Figure 14, every square within this grid mirrored the measurements of a single hTromo robot block.

A shake-resistant parallelepiped was created using an aluminum extrusion profile, with a camera then attached in the center, at the top of the structure. Furthermore, the image plane was verified as being horizontal to the floor, to avoid perspective projection complications for area calculation. As such, when the camera was attached to the structure, a spirit level was used to ensure it sat parallel to the ground. The camera set-up and corresponding test area can be seen in Figure 15. Auto-focus was turned off, and a set focal length employed when recording robot tiling. The raw video recordings were subsequently post-processed, in order to assess robot performance.

To generate a tracking map for the hTromo movement, an image-processing calculation was employed, which comprised three key stages. The first of these stages concerned the storage of a reference image, from which a track map would be created. Secondly, the location and form of the robot were identified in each frame. After multichannel color thresholding, the algorithm recognized the robot as three spots. The center of these spots corresponds to the center of each red color. Finally, a track map was created, by marking the green squares in accordance with spots detected on the reference image. When a track map was ready, a percentage calculation was conducted using the following formula, to assess the total area coverage achieved.

$$\%Coverage Area=\frac{\mathrm{Pixels}\mathrm{area}\mathrm{of}\mathrm{the}\mathrm{robot}}{\mathrm{Total}\mathrm{pixels}\mathrm{area}\mathrm{of}\mathrm{the}\mathrm{testing}\mathrm{field}}\times 100$$

(1)

$$\%CoverageArea=\frac{\mathrm{Pixel}\mathrm{area}\mathrm{of}\mathrm{the}\mathrm{robot}}{\mathrm{Total}\mathrm{pixel}\mathrm{area}\mathrm{of}\mathrm{the}\mathrm{testing}\mathrm{field}-\mathrm{Total}\mathrm{pixel}\mathrm{area}\mathrm{of}\mathrm{the}\mathrm{obtacles}}\times 100$$

(2)

4.2. Results and Analysis

Each experiment was started after placing the hTromo robot in a predefined position inside the area. We recorded the robot in action from the beginning to the end of the experiments. Once the tests were completed, the recorded videos were post-processed using the image processing algorithm detailed in Section 4 in order to generate the track map. Figure 16 presents the track map images of the hTromo robot that were generated following the first set of experiments that sought to validate the application of Theorem 1. The green colored shading represents the area covered by our hTromo robot. The percentage of area covered was computed using Equation (1) and is displayed on top of the tracked images. Figure 17 presents the tiled area during different stages of our first set of experiment. The figure indicates the actual position of the robot at a specific time point, and the associated track map at that instance overlaid with the completed tiling set. The robot path was executed according to the global tiling set specified in basic tromino theory. The results clearly show that our hTromo robot covered more than 95% of the test area in the first set of experiment validating the underline theory of tromino tiling. In the second set of an experiment involving Lemma 1 of Theorem 2, the area covered by our hTromo robot was found to be over 95%. Figure 16 presents the tiled area during different stages of our second set of experiment. We extended the testing area by adjusting the metal frames as mentioned in Section 4, in order to validate Lemma 2 of Theorem 2. The same process has been followed to generate the track map in order to compute total area covered. The results show that the htromo covered more than 91% of the defined testing area thereby validating the application of Lemma 2 shown in Figure 18.

In the fourth and fifth set of experiments, obstacles were placed inside the testing area as a means of modifying the test space as required by the Lemma. The boundaries of the testing area were adjusted according to the arguments in Lemma 3 and 4 of Theorem 3. We computed the total area covered by excluding the pixels associated with the obstacles by utilizing Equation (2). Figure 19 depicts the area coverage process while validating the application of Lemma 3. Results clearly show that hTromo robot covered an area in excess of 97% of the total test area, thereby validating the application of the Lemma 3 of Theorem 3. Similarly, with experiments involving Lemma 4, the hTromo robot covered an area of over 95% of the total test area. Figure 20, presents the tiled area during the different stages of a fifth and final set of experiments.

Furthermore, with the sixth set of experiments, we changed the test bed size to 168 × 168 cm by adjusting the metal frames. We placed obstacles inside the test area in order to make the square space into an Aztec diamond. We again followed the same experimental procedure to generate the tack maps to compute the total area covered. Since we placed obstacles inside the test arena; we used Equation (2) to compute the total area covered. Figure 21 shows the area coverage process during the validation of Lemma 5. The results show that the hTromo robot covers more than 97% of the defined area, thereby validating the application of the Lemma 5 of Theorem 4. The experiments that involve Lemma 6 of Theorem 5 was tested in a 112 cm × 112 cm area. The area coverage of hTromo robot under this experiment was computed using the Equation (2). Figure 22 shows the coverage process of the hTromo robot during the validation Lemma 6. The results show that hTromo robot can achieve a coverage area of more than 92%, through validating the application of Lemma 6 of Theorem 5. The experimental results clearly indicate that there are significant untapped research and development opportunity related to the application of the polyomino tiling theory within the area coverage problem.

5. Conclusions

In this paper, we proposed a novel area coverage approach for a reconfigurable floor cleaning robot, hTromo using Tromino tiling theory. Specifically, we validated the application of five tromino tiling theorems with our hTromo robot. Experiments performed clearly demonstrate the efficacy of the proposed approach resulting in very high levels of area coverage performance in all considered experimental cases. By automating the process of generating a global tiling set for tackling area coverage in our hTromo robot, we hope to simplify the path planning problem greatly. This paper also introduced the system architecture of our hTromo robot and details of experimental design and testbed. Future research will focus on: (1) integration of infrared, ultrasonic, and bump sensors for obstacle avoidance functions; (2) Optimizing robot’s path planning by implementing the Decision Making Framework for Human–Robot Collaborative Workplace Generation framework proposed by Panagiota Tsarouchi et al. [37] (3) Experimenting the proposed approach in a larger space by increasing the floor area and computing the total area covered within a given time period and (4) exploring global and local path planning by utilizing the images captured from the overhead camera.