Intel Serv Robotics DOI 10.1007/s11370-017-0223-z

ORIGINAL RESEARCH PAPER

Online complete coverage path planning using two-way proximity search Amna Khan1 · Iram Noreen1 · Hyejeong Ryu2 · Nakju Lett Doh3 · Zulfiqar Habib1

Received: 18 July 2016 / Accepted: 2 March 2017 © Springer-Verlag Berlin Heidelberg 2017

Abstract This paper presents an efficient online approach for complete coverage path planning of mobile robots in an unknown workspace based on online boustrophedon motion and an optimized backtracking mechanism. The presented approach first performs a single continuous boustrophedon motion until a critical point is reached. In order to completely cover the environment, next starting point is decided by using the accumulated knowledge of the environment map. An efficient backtracking technique based on proposed Two-way Proximity Search algorithm is used to plan a path from the critical point to the new starting point. Simulation results show the efficiency of proposed backtracking approach with improved total coverage time, coverage path length and memory requirements. Keywords Complete coverage path · Mobile robots · Boustrophedon motions · Two-way proximity search

B

Zulfiqar Habib [email protected] Amna Khan [email protected] Iram Noreen [email protected] Hyejeong Ryu [email protected] Nakju Lett Doh [email protected]

1

COMSATS Institute of Information Technology, Lahore, Pakistan

2

Division of Advanced Mechanical Engineering, Kangwon National University, Chuncheon, Korea

3

School of Electrical Engineering, Korea University, Seoul, Korea

1 Introduction Complete Coverage Path Planning (CCPP) algorithms have been applied to many real world robotic applications such as mine sweeping [1], agriculture [2], cleaning [3], surveillance [4] , underwater operations [5] and photogrammetric sensing of large areas [6]. In such applications mobile robot need to cover whole region while avoiding obstacles. The complete coverage algorithms are broadly categorized as offline and online algorithms [7]. The workspace is assumed to be fully known in advance while performing coverage with offline algorithms. Cellular decomposition based methods [8], spanning trees [9], spiral filling paths, neural networks [10], genetic algorithms [2,11], and ant colony methods [12] are popular candidates for the offline approach. On the contrary, online coverage approaches use real time measurements and decisions to cover the entire workspace. The complete workspace map is generated as a result of exploration and actions performed by robot. Sensor based approaches are good example of the online coverage algorithms [13]. A CCPP algorithm is complete if the robot covers the workplace such that union of all the sub-trajectories completely cover the workplace in finite time. The total operational time required for coverage and completeness determines the efficiency of a CCPP algorithm [14]. The two important criteria considered while performing CCPP are the environment decomposition technique, and the optimal backtracking mechanism. First, the environment decomposition technique determines the strategy to divide the workspace into smaller regions (cells) for effective coverage. Second, optimal backtracking mechanism finds an efficient path for motion planning of robot from one region (cell) to another. When there is no region left to backtrack, the coverage is said to be completed. The efficiency of a CCPP algorithm depends on environment decomposition technique and backtracking

123

Intel Serv Robotics

algorithm. An effective backtracking mechanism can significantly reduce total coverage time required for achieving complete coverage. One of the early approaches used for environment decomposition is cell based decomposition [15]. The free space within environment is decomposed into non overlapping regions called cells. The space within a cell can be easily filled using simple motions such as boustrophedon and square spiral motions. A complete CCPP algorithm of mobile robots using exact cell based decomposition is proposed in [16] which combines local coverage with global planning approach using boustrophedon motion. Exact cell based decomposition is simple and straightforward technique to implement, however, it could result in un-necessary small sub-regions. Exact cell based decomposition is further extended to trapezoidal [17,18] and boustrophedon [8] decomposition approaches. Such decomposition techniques are suitable for offline coverage. Random coverage path planning is used by several cleaning robots. Some mobile robots use spiral motion to cover area and follow random motion when obstacles are detected in path or the end of parameter (such as wall) is found. An online novel approach based on random path planning algorithm is discussed in [19]. The proposed approach is efficient, robust, and flexible for a small unknown environment. However, random path planning is not feasible for coverage in larger environments. Other techniques for environment decomposition includes grid based methods. Voronoi diagrams, distance maps, neural network based environment representation [20] and configuration space maps are few extensions that are derived from the grid based representation of the environment [13]. The limitation of such environment representation is exponential growth in memory requirement with the increase in map size. An online sensor based algorithm using spiral-STC by Gabriely and Rimon is presented in [9]. The robot follows a spiral path till it detects a critical point. A new point is searched along the covered path to start coverage. The robot returns to the start cell when coverage is completed. DFS based spanning tree for continuous coverage is proposed in [21]. The proposed algorithm used an improved STC based algorithm to optimize total number of U-turns within each sub-region. Senthilkumar and Bharadwaj [22,23] presented online decentralized multi-robot based coverage algorithm using multiple extended spanning trees. The proposed algorithm used ant-like robots for completing the coverage task. Although these approaches fulfill complete coverage tasks, they suffer from inefficient backtracking mechanism resulting in longer coverage paths. An optimal backtracking procedure results in reduced coverage time and minimum coverage path length. There are numerous procedures used in literature for this purpose.

123

Depth First Search (DFS) based optimization of coverage sequence for agriculture robot is presented in [24,25]. The presented algorithms only work for planar fields with simple obstacles. Moreover, the models did not consider cost of turning between two edges. Waanders [3] proposed a CCPP algorithm for cleaning robots using a variation of boustrophedon decomposition combined with simple Dijkstra’s algorithm for backtracking optimization. Viet et al. [26] presented computationally low cost and efficient approach for online CCPP in unknown environment for cleaning robots based on boustrophedon motions and A*SP [27] algorithm. The approach was efficient with respect to total coverage time, coverage path length, and total number of boustrophedon cells formation. However, it was inadequate for dynamic environment because A* could deal with static obstacles only. On the contrary, D* algorithm [28], has the capability to deal with dynamic unknown environment due to continuous updating of environment map. An efficient CCPP approach named as Complete Coverage D* (CCD*) is presented in [29] which uses D* based backtracking technique CCD* algorithm considered model of cleaning robot to find the coverage path for both the static and dynamic obstacles. Dakulovic et al. [1] presented an approach for demining robots using CCD* algorithm. The presented algorithm performed well for unknown environments. However, this approach had limitation of leaving few regions unvisited due to imperfect path following and frequent changes in the path direction. Paratama et al. [36] presented an offline CCPP algorithm for an underwater mining robot using Morse decomposition and Depth-First Search (DFS) algorithm. The presented algorithm improved total operational time by reducing path overlapping and total number of turns. Another CCPP algorithm presented by Yu et al. [37] reduced total number of turns by using parallel line decomposition approach. The simulation experiments shows that the presented algorithm generated nearly optimal path efficiently for agriculture fields. This paper presents a computationally low cost and efficient online complete coverage path planning approach for an unknown environment. The coverage task is performed by following an online boustrophedon motion along with an efficient backtracking technique called Two-Way Proximity Search (TWPS) to reduce total coverage time. The proposed algorithm is a greedy strategy based variation of Witkowski’s algorithm [30] and generates the shortest possible path for backtracking. For the complete coverage path planning, it is assumed that the environment must be closed. Second, all the regions are connected so that any accessible position within environment is reachable by robot. Under these assumptions, computer simulations show that proposed coverage approach is efficient for the online coverage task for unknown environment in terms of total coverage time.

Intel Serv Robotics

The structure of this paper is organized as follows. Next section includes related work. Section 3 introduces our scheme of backtracking mechanism. Simulation results comparing our approach to others are presented in Sect. 4. Last section is concluded with future directions.

2 Related work Coverage path planning algorithm decompose environment into small regions for coverage. After performing coverage task in a sub-region, backtracking points list is accumulated. Backtracking points are the candidate starting points for the new coverage task. The most suitable backtracking point is selected from the backtracking point list for coverage. Coverage is said to be completed when no backtracking points are detected within an environment. Complete coverage path planning algorithm proposed in this paper is based on the online boustrophedon motion and two-way proximity search algorithm. This section gives a brief discussion about online boustrophedon motion and detection of backtracking points for coverage by Viet et al. [26]. 2.1 Online Boustrophedon motion(BM) Viet et al. [26] presented an online boustrophedon motion (BM) for complete coverage of the workspace W . BM incrementally constructs non-overlapping regions for complete coverage of cleaning robot. Similar to cell based decomposition techniques online boustrophedon motion divides free space into small boustrophedon regions for coverage. However, the number of region formation is sufficiently reduced and it works for unknown environment as well. Algorithm 1: Online Boustrophedon Motion(BM) [26] Inputs: Robot’s configurations and the initial coverage model M of the workspace. Outputs: Updated coverage model M , new configuration for robot. Step 1. Find first direction for movement in the priority order of north-south-east-west. If critical point is reached, break the loop. Step 2. Move one step along the direction. Step 3. Create a tile according to the size of the robot (size = 2 ∗ radiuso f robot). Step 4. Add the tile to the coverage model M. Go to Step 1.

In order to construct an incremental complete coverage region, the robot moves to one of the four available sweep directions (north–south–east–west) at each time step depending on priority. Robot only moves in one direction at each iteration. For mimicking basic boustrophedon motion, if robot is moving in north direction it will continue moving in the same direction until a blocked position is encountered.

Fig. 1 Conditions for backtracking point detection [26]

The robot then checks for east or west directions for availability of change in direction. In next iteration the sweep direction is determined while considering north–south–east– west priority until a critical point is reached. A critical point is the position where all possible neighbors of robot are either blocked or covered. The coverage model M is created incrementally as the robot moves along the workspace. At each iteration M gives partial map of the workspace and is used for planning backtracking path. Algorithm 1 explains online BM [26] for performing coverage of an unknown environment. 2.2 Backtracking mechanism A partial environment map is generated as a consequence of single continuous boustrophedon motion (no-obstacle environment is not considered). After critical point is reached, robot accumulate list of backtracking points from the partially originated environment map. The most suitable backtracking point along the covered path for starting a new coverage motion is selected from the backtracking list. Viet et al. [26] presented a criteria for determining the backtracking list comprising of candidate backtracking points using partial environment map built so far by movement of robot. Generally, every single point lying on the covered path with at least one neighbor un-covered is a candidate starting point. However, selecting any point randomly from these candidate points could result in forming unnecessary large number of boustrophedon regions thus, resulting in increased path length and total execution time. Therefore, un-covered points present at the corners of the initial coverage map are identified as candidates for backtracking points. Fig.1 shows six conditions for identifying candidate backtracking points using Eqs. (1) and (2). The neighbors in black color are blocked positions (either an obstacle or already covered regions. The white neighbors indicate free position and blue neighbors specifies “don’t-care” positions. Let Vn (v) = {v1 , v2 , v3 , v4 , v5 , v6 , v7 , v8 } represents the set of

123

Intel Serv Robotics

all eight neighboring vertices of a tile v. For any two cells, vi ∈ Vn and v j ∈ Vn where (i, j = 1, 2, . . . , 8) we can formulate mathematical function for all the six conditions shown in Fig. 1 as  1, if(vi is free) and (v j is blocked); (1) τ (vi , v j ) = 0, Otherwise and the sum function τ (vi , v j ) = τ (v1 , v8 ) + τ (v1 , v2 ) + τ (v5 , v4 ) + τ (v5 , v6 ) + τ (v7 , v6 ) + τ (v7 , v8 ),

(2)

An un-covered region v along the initial covered path is selected as a backtracking point only if τ (v) ≥ 1 and stored in a list B L of backtracking points as B L = {v|v ∈ M and τ (v) ≥ 1},

(3)

Determining backtracking point during coverage is difficult due to insufficient information about all the corners neighbors. Moreover, as workspace is initially unknown, map is built online as a consequence of robot’s motion. Therefore, backtracking points are calculated from the partial workspace map built by the robot’s motion only if it reaches a critical point. The backtracking list B L built at the end of each iteration is then used to determine the best starting point of the next boustrophedon motion. In this paper, backtracking point v with the minimum Euclidean distance from the critical point represented as vcp is selected as the next starting point. v = min v BL (euclid(v, vcp )).

(4)

After selection of next starting point, a smooth A* algorithm for tiling is used to generate a collision free trajectory from critical point to the new starting point.

3 Proposed approach This section presents proposed backtracking point detection and two-way proximity search (TWPS) path planning approaches for an efficient complete coverage mechanism. A simple online boustrophedon motion is used for coverage with in a region. The mechanism for determining backtracking points list and planning an efficient collision free path from critical point to new starting point is discussed as follows. 3.1 Backtracking points detection For detection of backtracking points Eqs. (1) and (2) highlight all points present at the corners of coverage path. However, criteria mentioned in (1) and (2) for detecting suitable back-

123

(a)

(b) Fig. 2 Detecting backtracking points. a Using sum function in [26] b using proposed sum function

tracking points present at the corners of the initial covered path are not sufficient. Fig. 2a shows the partial map of the environment build after completion of first boustrophedon motion and red dots indicate candidate starting points in the current backtracking list found using (1) and (2). Points 1, 2 and 3 lies closest to critical point. As greedy strategy using (4) is used for selection of next starting point, point 3 is selected. As mentioned earlier, robot has to plan a backtracking path from partially build map during coverage, resulting in a longer path. The upper left corner of obstacle remains undetected using criteria mentioned above. Therefore, four new criteria as shown in Fig. 3 are added to Eq. (2) resulting in Eq. (5). Fig. 2b shows the result of using Eq. (5) to the partial map after first boustrophedon motion. Point 1 is selected as a new starting point using Eq. (4) resulting in comparatively shorter path as compared to the previous attempt. The respective sum function is shown in Eq. (5).

Intel Serv Robotics

hand, Theeta* [34] integrates smoothing with the searching process, consequently increasing total computational cost and complexity. Our proposed backtracking path planner is a simple heuristic based proximity search to enhance time efficiency for coverage based on Witkowski’s algorithm [30] and a distance based heuristic function. In order to determine a collision free path, our algorithm uses two queues of vertices sour ceList and goal List. sour ceList contains vertices to be expanded from source towards goal and goal List contains vertices to be expanded from goal towards source using a simple heuristic function mentioned in Eq. (6). h cost (n i , vg ) =

Fig. 3 New conditions for backtracking points detection

τ (vi , v j ) = τ (v1 , v8 ) + τ (v5 , v6 ) + τ (v1 , v2 ) + τ (v5 , v4 )



(vgx − n i x )2 + (vgy − n i y )2

(6)

where i = 1, 2, 3, . . . , 8 and n = neighbors of the current vertex. At each iteration, neighbor with the minimum Euclidean distance is selected for expansion from sour ceList greedily until goal is found. This simple strategy is fast and enhances time efficiency however, this greedy best-first selection could get trap in local minima. When expansion of sour ceList is

+ τ (v7 , v6 ) + τ (v7 , v8 ) + τ (v5 , v7 ) + τ (v5 , v3 ) + τ (v1 , v7 ) + τ (v1 , v3 )

(5)

3.2 Planning backtracking path This section discusses our proposed approach for efficient online complete coverage in unknown workspace. At present, we assume that robot and obstacles are projected as a twodimensional object in workspace W = R 2 . After detecting suitable backtracking point from the backtracking list B L , next task of robot is to find an efficient collision free path from  criticalpoint  to the backtracking point. In this section an efficient collision free backtracking path planning algorithm known as Two-way Proximity Search (TWPS) is presented for traversing from critical point to the next nearest starting point. The proposed approach uses neighboring tiles for searching path instead of neighboring vertices resulting in an efficient backtracking path. Each tile is equal to the size of the robot. Several path planning algorithms such as Wavefront planner [31], Dijkstra’s [32], A* [26], or D* [28] can be used to plan a backtracking path for the robot. However, as these algorithms work on grids and parent of a vertex must be an adjacent vertex, the resulting path is an unnecessary long and jagged. Consequently, the robot must continuously reorient while following the planned path from source to the goal vertex. Other variations of A* such as A*SP [33] and Theeta* [34] try to overcome this limitation by using smoothing process. A*SP [33] generates shorter paths than A* search by applying smoothing as a post processing step. On the other

Algorithm 2: Two Way Proximity Search Data: star t , goal Result: Backtracking Path ∀ n ∈ N , h(n) ← ∞, g(n) ← ∞, f (n) ← ∞, sour ceList = φ, goal List = φ, h(star t) = 0 push(sour ceList, sour ce) push(goal List, goal) begin while sour ceList = φ and local Minima == f alse do o = pop(sour ceList) for ∀ n ∈ N such that {o, n} ∈ M do calculate h cost (n i , vg ) for all neighbors min N eighbor = minimum(h cost (n i , vg )) if islocalMinima then f or war d Pass = f ail break else push(sour ceList, min N eighbor ) return path Found if forwardPass == fail then localMinima = false while goal List = φ and local Minima == f alse do o = pop(goal List) for ∀ n ∈ N such that {o, n} ∈ M do calculate h cost (n i , vs ) for all neighbors min N eighbor = minimum(h cost (n i , vs )) if islocalMinima then r ever se Pass = f ail break else push(goal List, min N eighbor ) return path Found if forwardPass == fail and reversePass == fail then path = optimizeBreadthFirstSearch (sour ce, goal) return path Found

123

Intel Serv Robotics

restricted by local minima, reverse pass is generated from goal to source until a common meeting point or source is reached. goal List is expanded using (6) and path is formulated using both lists. If both, forward and reverse passes for expansions gets trap in local minima, then path is constructed by using an optimized breadth-first-search algorithm. The algorithm for the proposed backtracking path planning is presented in Algorithm 2. The generated path given by TWPS is not the shortest path because, parent of each tile during expansion is constrained to a neighbor tile with minimum Euclidean cost. Therefore, the generated path can be improved by using simple line of sight path smoothing algorithms such as A*SP [33] or global path pruning strategy [35]. However, the width of the line of sight is considered to be equal to the size of the robot so that the robot might not collide with corners of obstacles. Figure 4 shows an example of finding the collision free shortest path from the starting point S to the goal G using A*SPT and TWPS. Expansion grid for A*SPT indicates the algorithm has to cover a large area before finding path to the goal. Thus, efficiency for A*SPT decreases as the distance between starting point S and goal G increases. Meanwhile, Two-way Proximity Search expands only in direction determined by the greedy heuristic function as mentioned in (6) while generating the shortest collision free path to a goal.

(a)

3.3 Proposed complete coverage path planning algorithm using online boustrophedon motion and TWPS An online complete coverage algorithm for completely unknown environment based on proposed backtracking strategy is presented in this section. Algorithm 3 presents the proposed complete coverage approach. Initially, robot has no prior knowledge about environment. The robot performs coverage from the initial starting point based on Algorithm 1 until a critical point is reached. The partial environment map  M  is constructed incrementally during coverage task of robot. The environment map  M  is further used to generate candidate backtracking points list using the criteria mention in Eq. 5. The nearest critical point is selected for starting the next online boustrophedon motion for coverage. The coverage task continues until no backtracking point is detected.

4 Simulation results In this section simulation results for the proposed algorithm TWPS are compared with BA*SPT [26] using online boustrophedon motion. Matlab 2015 software is used for implementing simulations on core i3-3110M CPU 2.4 GHz with a 4-GB RAM computer. To evaluate the successful coverage and efficient backtracking mechanism eight different

123

(b) Fig. 4 Expansion grid for a A*SPT b Proposed Approach

Algorithm 3: Complete Coverage Path Planning using TWPS Result: Complete Coverage Path M =φ; critical Point = 0 ; f lag = tr ue ; while f lag == true do [M, critical Point] = perform BM in algorithm 1 ; B L = identifyBPs( M , critical Point ) ; if B L == φ then Coverage is Complete ; f lag = false ; else f lag = true ; star t Point = findPoint(B L , critical Point) ; backtracking Path = TWPS( critical Point, star t Point);

Intel Serv Robotics Table 1 Total coverage distance for performing coverage

Table 3 Total cells required for performing coverage

Maps

Maps

Total coverage distance (Euclidean) using A*

D*

A*SPT

TWPS

Map1

3865.56

3865.56

3824.55

3819.83

Map2

3497.27

3497.27

3421.83

3417.06

Map3

3458.99

3458.99

3449.65

Map4

3833.13

3833.13

Map5

3750.71

3750.71

Map6

3412.42

Map7 Map8

A*

D*

A*SPT

TWPS

Map1

435

435

473

382

Map2

427

427

469

348

3426.34

Map3

350

350

394

343

3740.30

3692.23

Map4

947

947

1028

387

3491.48

3462.49

Map5

883

883

953

345

3412.42

3406.56

3375.08

Map6

745

745

791

386

3450.00

3450.00

3450.00

3424.14

Map7

398

398

418

345

3460.41

3460.41

3373.99

3342.55

Map8

1260

1260

1375

327

Table 2 Total time required for performing coverage Maps

Total number of cells

Total time required for coverage in seconds A*

D*

A*SPT

TWPS 4.10

Map1

61.81

61.81

67.89

Map2

68.35

68.35

76.03

5.78

Map3

164.68

164.68

209.41

20.78

Map4

159.09

159.09

223.93

6.87

Map5

175.62

175.62

190.68

6.23

Map6

69.76

69.76

73.29

42.11

Map7

63.32

63.32

77.82

5.36

Map8

350

350

389.80

9.78

environment maps are generated. For simulation purpose, robot is modeled by the circle with the radius of r = 5 pixels. The size of each tile formed by robot is equal to 2 ∗ r and is indicated by light gray squares in maps. Moreover, Si represents set of all starting points and Ei represents the set of all the critical points, such that i = (1, 2, 3, . . . , br ) where br represents total number of boustrophedon regions formed during coverage. A slightly modified versions of A* and D* algorithms along with A*SPT are compared with the proposed method. The A* and D* algorithms are modified to perform path planning on the tiling model M, constructed incrementally by boustrophedon motion. The total coverage length and execution time for A* and D* remains same in all the cases. The main reason behind this phenomenon is that currently unknown environment with static obstacles is considered. The summary of total coverage distance in robot’s diameter and total execution time required for coverage by using A*, D*, A*SPT and the proposed algorithm is presented in Table 1 and in Table 2 respectively. The proposed approach not only generates shorter coverage path efficiently but is also memory efficient. Table 3 shows a comparison of total number of cells required to gen-

erate the coverage path by B-A*SPT [26] and the proposed strategy. Figure 5 summarizes average execution time and average coverage path length of the proposed approach, A*, D* and B-A*SPT for 20 trials. The average number of cells required by A*, D*, A*SPT and the proposed approach is summarized in Fig. 5b. Analysis of total coverage execution time clearly indicates that the proposed methodology is efficient than A*, D* and B-A*SPT. Figure 6 shows the simulation results for online complete coverage using A*SPT and TWPS as the backtracking technique for different environment maps. Coverage region is formed by performing online boustrophedon motion therefore, the total number of coverage cells formed by robot model are same in both algorithms. Total coverage path length and total number of cells used by proposed approach for coverage (including backtracking mechanism) is sufficiently less than the previous B-A*SPT approach. Moreover, the proposed approach is time efficient as well. Complete coverage path planning for two different maps of complex corridor like environment is shown in Fig. 7. The start point is selected at the upper right corner for these simulations. The total coverage distance covered by BA*SPT for Fig. 7a, c is 3740.3095 and 3491.489 respectively. Whereas, the total coverage distance covered by proposed BTWPS approach for Fig. 7b, d is 3692.2362 and 3462.4956 respectively. Similarly, for an unstructured environment the simulation results are shown in Fig. 8. The proposed algorithm works well in the unstructured environment as well. The total coverage regions formed by both the previous algorithm B-A*SPT and B-TWPS are same. However, the proposed approach is efficient in terms of time and memory requirements. Moreover, the total coverage path length of the proposed approach is less than the previous approach. The following observations are summarized from the simulation results of our proposed B-TWPS, and and B-A*SPT approach. The coverage path obtained by the proposed

123

Intel Serv Robotics Fig. 5 Complete coverage path planning a Total execution time b total number of cells used c total coverage path length

(a)

(b)

(c)

123

Intel Serv Robotics

(a)

B-A*SPT (Map1)

(b)

B-TWPS (Map1)

(a)

B-A*SPT (Map2)

(b)

B-TWPS (Map2)

(a)

B-A*SPT (Map3)

(b)

B-TWPS (Map3)

Fig. 6 Complete coverage path planning for different maps

123

Intel Serv Robotics

(a) B-A*SPT (Map4)

(b) B-TWPS (Map4)

(c) B-A*SPT(Map5)

(d) B-TWPS (Map5)

Fig. 7 Complete coverage using for complex corridor environments

(a)

B-A*SPT

Fig. 8 Complete coverage path planning for less structured environment map

123

(b)

B-TWPS

Intel Serv Robotics

approach B-TWPS is shorter than the B-A*SPT approach. The coverage rate achieved by both the approaches is same because both of them use the similar online boustrophedon motion strategy to perform coverage task. Furthermore, both approaches leave small area around obstacle boundaries during coverage task. However, the backtracking strategy for the proposed approach is much more time and memory efficient than the B-A*SPT technique.

5 Conclusion and future directions Coverage time of CCPP algorithm is mainly influenced by environment decomposition methodology, and backtracking mechanism. Backtracking includes backtracking point detection and backtracking path planning. The focus of this paper is to improve total coverage time by using an efficient backtracking algorithm. The proposed algorithm is based on the online boustrophedon motion and an efficient backtracking path planning mechanism called two-way proximity search. Computer simulations show that proposed backtracking algorithm works properly in an unknown environment with static obstacles. Simulation results further concludes that the proposed algorithm performs better to A*, D* and B-A*SPT algorithm in terms of total coverage time, path length and memory requirements. However, currently the proposed approach is tested in simulation environment only. Future directions include testing of the proposed algorithm on real robot for cleaning task such as i Robot Cr eate. Moreover, the proposed approach can only consider static obstacles while generating a backtracking path. The extension of the proposed algorithm to address dynamic obstacle avoidance is another future direction. Acknowledgements This study is supported by the research grant of Higher Education Commission (HEC) of Pakistan (No. 20-2359/NRPU/ R&D/HEC/12-6779) and partly supported by a project of Korean government (No. 10073166).

References 1. Dakulovic M, Petrovic I (2012) Complete coverage path planning of mobile robots for humanitarian demining. Ind Robot: Int J 39(5):484–493 2. Hameed AI, Bochtis D, Sorensen CA (2013) An optimized field coverage path planning approach for navigation of agricultural robots in fields involving obstacles. Int J Adv Robot Syst 10:1– 9 3. Waanders M (2011) Coverage path planning for mobile cleaning robots. In: 15th twente student conference on IT, Enschede 4. Perezimaz HIA, Rezeck PAF, Macharet DG, Campos MFM (2016) Multi-robot 3D coverage path planning for First Responders teams. In: IEEE international conference on automation science and engineering (CASE), pp 1374–1379

5. Galceran E, Carreras M (2012) Efficient Seabed Coverage Path Planning for ASVs and AUVs. In: IEEE/RSJ international conference on intelligent robots and systems, Vilamoura, Portugal 6. Franco CD, Buttazzo G (2016) Energy-aware coverage path planning of UAVs. In: IEEE international conference on autonomous robot systems and competitions, pp 111–117 7. Choset H (2001) Coverage for robotics—a survey for recent results. Ann Math Artif Intell 31:13–126 8. Choset H, Pignon P (1998) Coverage path planning: the boustrophedon cellular decomposition. In: Zelinsky A (ed) Field and service robotics. Springer, London, pp 203–209 9. Gabriely Y, Rimon E (2002) Spiral-STC : an on-line coverage algorithm of grid environments by a mobile robot. In: International conference on robotics and automation, pp 954–960 10. Qiu X, Liu S , Yang SX (2004) A rolling method for complete coverage path planning in uncertain environments. In: International conference on robotics and biometric, pp 146–151 11. Hameed IA, Bochtis DD, Sorensen CG (2011) Driving angle and track sequence optimization for operational path planning using genetic algorithms. Appl Eng Agric ASABE 27(6):1077–1086 12. Chibin Z, Xingsong W, Yong D (2008) Complete coverage path Planning based on ant colony algorithm. In: 15th international conference on mechatronics and machine vision in practice, pp 357–361 13. Galceran E, Carreras M (2013) A survey on coverage path planning for robotics. Robots Auton Syst 61:1258–1276 14. Janchiv A, Batsaikhan D, Kim B, Lee W, Lee S (2013) Timeefficient and complete coverage path planning based on flow networks for multi-robots. Int J Control Autom Syst 11(2):369– 376 15. Huang W H (2001) Optimal line-sweep-based decompositions for coverage algorithm. In: Proceedings of the 2001 IEEE international conference on robotics and automation, pp 27–32 16. Zhou P, Wang Z , Li Z , Li Y (2012) Complete coverage path planning of mobile robot based on dynamic programming algorithm. In: 2nd international conference on electronic and mechanical engineering and information technology, pp 1837–1841 17. Choset H, Lynch K, Hutchinson S, Kantor G, Burgard W, Kavraki I, Thrun S (2005) Principals of robot motion: theory, algorithms and implementations. MIT Press, Cambridge 18. Kim DH, Hoang G, Bae MJ, Kim JW, Yoon SM, Yeo TK, Sup H, Kim SB (2014) Path tracking control coverage of a mining robot based on exhaustive path planning with exact cell decomposition. In: International conference on control, automation and systems, pp 730–735 19. Liu Y, Lin X, Zho S (2008) Combined coverage path planning for autonomous cleaning robots in unstructured environments. In: Proceedings of the 7th world congress on intelligent control and automation, pp 8271–8276 20. Qiu X, Liu S , Yang S (2004) A rolling method for complete coverage path planning in uncertain environments. In: International conference on robotics and biometrics, pp 146–151 21. Weiss-Cohen M, Sirotin I, Rave E (2008) Lawn mowing system for known areas. In: International conference on computational intelligence for modeling control and automation, pp 539–544 22. Senthilkumar KS, Bharadwaj KK (2008) Spanning tree based terrain coverage by multi robots in an unknown environment. In: INDICON, pp 120–125 23. Senthilkumar KS, Bharadwaj KK (2012) Multi-robot exploration and terrain coverage in an unknown environment. Robot Auton Syst 60:123–132 24. Zuo G, Zhang P , Qiao J (2010) Path planning algorithm based on sub-region for agricultural robot. In: International Asia conference on informatics in control, automation and robotics, pp 197–200 25. Jin J, Tang L (2010) Optimal coverage path planning for arable farming on 2D surfaces. Trans ASABE 53(1):283–295

123

Intel Serv Robotics 26. Viet HH, Dang VH, Laskar MNU, Chung TC (2013) BA* : an online complete coverage algorithm for cleaning robots. Int J Appl Intell Neural Netw Complex Probl Solving Technol 39:217235 27. Hart PE, Nilsson NJ, Raphael B (1968) A formal basis for the heuristic determination of minimum cost paths. IEEE Trans Syst Sci Cybern 4(2):100–107 28. Stentz A (1994) Optimal and efficient path planning for partiallyknown environments. In: Proceedings IEEE conference on robotics and automation 29. Dakulovic M, Horvatic S, Petrovic I (2011) Complete coverage D* algorithm for path planning of a floor-cleaning mobile robot. In: 18th international federation of automatic control (IFAC) world congress, pp 5950–5955 30. Witkowsky C (1983) A parallel processor algorithm for robot route planning. In: International joint conference on artificial intelligence, pp 827–829 31. Zelinsky A , Jarvis RA , Byrne JC , Yuta S (1993) Planning paths of complete coverage of an unstructured environment by a mobilerobot. In: Proceedings of international conference on advanced robotics

123

32. Dijkstra E (1958) A note on two problems in connexion with graphs. Numerische Mathematik 1(1):269–271 33. Botean A, Müller M, Schaeffer J (2004) Near optimal hierarchical path-finding. J Game Dev 1:7–28 34. Nash A, Daniel K, Koenig S, Felner A (2010) Theta*: any angle path planning on grids. J Artif Intell Res 39(1):533–579 35. Yang K ,Sukkareih S (2008) 3D Smooth path planning for a UAV in cluttered natural environment. In International conference on intelligent robots and systems, pp 794–800 36. Pratama PS, Kim JW, Kim HK, Yoon SM, Yeu TK, Hong S, Oh SJ, Kim SB (2015) Path planning algorithm to minimize an overlapped path and turning number for an underwater mining robot. In:15th international conference on control, automation and systems, pp 499–504 37. Yu X, Hung JY (2015) Coverage path planning based on a multiple sweep line decomposition. In: 41st annual conference of the IEEE industrial electronics society pp 4052–4458