Hilbert’s Space-filling Curve for Regions with Holes  Siddharth H. Nair 1 , Arpita Sinha 2   and Leena Vachhani 3  Abstract — The   paper   presents   a   systematic   strategy   for implementing Hilbert’s space filling curve for use in online exploration tasks and addresses its application in scenarios wherein the space to be searched obstacles (or holes) whose locations are not known a priori. Using the self-similarity and locality preserving properties of Hilbert’s space filling curve, a set of evasive maneuvers are prescribed and characterized for online implementation. Application of these maneuvers in the case of non-uniform coverage of spaces and for obstacles of varying sizes is also presented. The results are validated with representative simulations demonstrating the deployment of the approach.  I. INTRODUCTION Investigations   on   space   filling   curves   began   when George   Cantor   proved   that   there   exists   a   bijective   map between   any   two   finite-dimensional   manifolds.   The continuity   of   such   maps,   however,   was   a   mystery   until E. Netto demonstrated that a bijective map between two finite-dimensional   manifolds   of   different   dimensions   is necessarily   discontinuous.   All   was   not   lost   though-   in 1890, Peano relaxed the bijectivity condition of such maps and discovered a continuous surjective mapping from the unit interval   I   =   [0 ,   1]   to the unit square   Q   =   [0 ,   1] 2 . This paved the way to designing continuous maps to fill a higher dimensional space from a lower dimensional space[1]. Space filling curves are primarily used in applications that require visiting various regions in a space. Numerous works pertaining to use of various space filling curves for optimization exist in literature ([2], [3], [4]). The advantage of using Hilbert curve lies within the very nature of the map. The images of points in the domain of the map neighbour each other thereby lending a sense of “anticipation” during implementation. This inspires the use of the curve for robotic applications. In [5], a robot motion planning problem is introduced   and   uses   the   Hilbert   space-filling   curve   to uniformly cover a space with a single agent or multiple agents coordinating with each other. In [6], space filling curves   are   used   to   decompose   an   arbitrary   shape   using space filling curves and thus use the technique for planning a path for a tool to machine the desired shape. In [7], the strategy presented in [5] is implemented using an aerial  1 Siddharth   H.   Nair   is   with   Department   of   Aerospace Engineering,   Indian   Institute   of   Technology   Bombay,   400076   India.  siddharth.nair@iitb.ac.in  2 Arpita   Sinha   is   with   the   Faculty   of   Systems   and   Control   En- gineering,   Indian   Institute   of   Technology   Bombay,   400076   India.  arpita.sinha@iitb.ac.in  3 Leena   Vachhani   is   with   the   Faculty   of   Systems   and   Control Engineering,   Indian   Institute   of   Technology   Bombay,   400076   India.  leena.vachhani@iitb.ac.in  robot for search operations and also uses Moore’s space filling curve (a modification of the Hilbert curve). In [8], a tree is used to arrange nodes for uniformly covering the unit square. The nodes are numbered according to that of the Hilbert curve. In [9], a new approach is proposed to search this coverage tree to explore a space non-uniformly via an aerial agent by using the self-similarity of the Hilbert curve (which is a fractal curve) to define various levels for the tree. Literature pertaining to exploration for robots using space filling curves in spaces with holes/obstacles is sparse. A rigorous solution to search a space with holes is offered in [10] with applications in sensor networks by mapping any search domain canonically to a torus and design space-filling trajectories on this torus. However, the method requires knowledge of the structure of the search domain beforehand and   involves   complex   computations.   An   investigation of   a   technique   that   uses   feedback   and   traces   Hilbert’s curve would support sensor based autonomous strategies. Therefore, this paper addresses tracing the Hilbert curve when holes of fixed size in the space are present, but their locations are sensed online. A modification of the map of the Hilbert’s curve is also presented for robotic exploration applications. It shall be seen that a simplified approach can be derived by examining the properties of the Hilbert curve and its map. Furthermore, this is extended to the case of non-uniform coverage of spaces along the lines of [9] and for obstacles of varying sizes. The rest of the paper is divided into five sections. Section II introduces the map that defines the Hilbert curve. Section III highlights the underlying properties of the Hilbert curve and addresses the obstacle avoidance problem while Section IV extends the formulation for non-uniform coverage of spaces. Section V presents an algorithm for online imple- mentation of the prescribed strategy with simulation results followed by concluding remarks in Section VI. II. P RELIMINARY ON   H ILBERT ’ S   S PACE - FILLING   C URVE  Hilbert [1] was the first to propose a geometric generation principle for the construction of a space filling curve which can be encapsulated by the following procedure:  •   The   unit   interval   I   is   mapped   continuously   onto the   unit-square   Q .   I   is   partitioned   into   four   equal sub-intervals and   Q   is partitioned into four congruent sub-squares, so as to map the same continuously onto one of the sub-squares. This is repeated for the all the sub-intervals and sub-squares.  arXiv:1709.02938v1 [cs.RO] 9 Sep 2017
•   When repeating this procedure ad infinitum, the sub- squares are arranged in such a way that adjacent sub- squares correspond to adjacent sub-intervals hence pre- serving the overall continuity of the mapping. Hence, the   nth   order Hilbert curve divides the space   Q  and interval   I   into   4 n   subsets. Now, the map   f h   :   I   →   Q  is defined such that every   t   ∈   I   corresponds to a unique sequence of nested closed squares that shrink into a point of   Q , the image   f h ( t ) . Let us represent   t   ∈   I   in quaternary form as   t   = 0 . 4 q 1 q 2 q 3 q 4 ....   =   q 1  4   +   q 2  4 2   +   q 3  4 3   +   ...   where  q i   =   { 0 ,   1 ,   2 ,   3 } . The map   f h   :   I   →   Q   is called the Hilbert space-filling curve and is defined as a composition of transformations as   f h ( t ) = lim n →∞   T q 1   T q 2   ..T q n   Q   where the transformations   T q i   acting on   Q   are defined as  T 0  ([ x y  ])  = 1 2  [ 0   1 1   0  ] ︸   ︷︷   ︸  H 0  [ x y  ]  + 1 2  [ 0 0  ] ︸︷︷︸  h 0  T 1  ([ x y  ])  = 1 2  [ 1   0 0   1  ] ︸   ︷︷   ︸  H 1  [ x y  ]  + 1 2  [ 0 1  ] ︸︷︷︸  h 1  T 2  ([ x y  ])  = 1 2  [ 1   0 0   1  ] ︸   ︷︷   ︸  H 2  [ x y  ]  + 1 2  [ 1 1  ] ︸︷︷︸  h 2  T 3  ([ x y  ])  = 1 2  [   0   − 1  − 1   0  ] ︸   ︷︷   ︸  H 3  [ x y  ]  + 1 2  [ 2 1  ] ︸︷︷︸  h 3  For example, the image of the point   t   = 0 . 4 203   lies in the  (3 + 1) th   sub-square, of the   (0 + 1) th   sub-square, of the  (2 + 1) th   sub-square of   Q   (see Figure 1).  Fig. 1:   t   = 0 . 4 203   mapped into the unit square via Hilbert’s map Also note that any finite quaternary represents the starting of an interval and so,  f   (0 . 4 q 1 q 2 ..q n ) =   T q 1   ..T q n   ( lim  p →∞   T   p  0   ( Q )) =   T q 1   ..T q n  [ 0 0  ]  (1) Defining   e 0 j   =   N o. of times T 0   occurs bef ore T q j   ( mod 2)  and   e 3 j   =   N o. of times T 3   occurs bef ore T q j   ( mod 2) , Equation (1) simplifies (see [1]) to  f   (0 . 4 q 1 q 2 ..q n ) =  n ∑  j =1  1 2 j   H e 0 j  0   H e 3 j  3   h q j  The   implementation   of   a   Hilbert   curve   is   done   via   its approximating polygon which is obtained by mapping   4 n  nodes of the form   0 ,   1 4 n   ,   2 4 n   , ...   4 n − 1 4 n   to   Q   and joining the images using straight lines. Details of this analysis can be found in [1]. An implementation of a second order Hilbert curve is shown in Figure 2a.  (a)   (b)  Fig. 2: Figures 2a and 2b are Hilbert’s curves obtained using (1) and (2) respectively. For our application, we shift the nodes to the centres of the sub-squares and thus modify the map slightly as follows.  f   (0 . 4 q 1 q 2 ..q n ) =   T q 1   T q 2   ..F q n   = 1 2   H q 1   ..H q n − 1   F q n   +  n − 1 ∑  j =1  1 2 j   H e 0 j  0   H e 3 j  3   h q j  (2)  where   F 0   =  [   1 4 1 4  ]  ,   F 1   =  [   1 4 3 4  ]  ,   F 2   =  [   3 4 3 4  ]  and   F 3   =  [   3 4 1 4  ]  . An   implementation   of   the   modified   map   is   shown   in Figure 2b. This modification is motivated for exploration tasks where it would make sense to identify each node (sub-square) in the search space by its centre and not by its edges which could be shared with other nodes. This implementation of the Hilbert’s curve is restricted to all euclidean spaces that are homeomorphic to a unit square (polygons, circles etc.). The nodes obtained for the unit square can be mapped back into the actual space via the homeomorphism ([11]). III. E XTENSION OF   H ILBERT ’ S   S PACE - FILLING CURVE TO DOMAINS WITH BLOCKED NODES  Consider a problem wherein a searching agent traverses the space   Q   along the nodes of the   nth   order Hilbert curve and there is a single ”obstacle” node of the same resolution. The presence of the obstacle leaves that particular node unaccessible or blocked. The space is ”unknown” in the sense that the searching agent starts from a corner of the search space and only the boundary of the search space is known. It is also assumed that information about the occupancy of the neighbouring nodes (the sub-squares touching the sub-square occupied by the agent) is available to the agent. Before introducing the obstacle avoidance strategy, some definitions and properties of the Hilbert curve are presented.  Definition 1:   The nodes that enter or leave one of the   ( n −  1) th   order Hilbert curves in the   nth   order Hilbert curve are defined as corner nodes of the   nth   order Hilbert curve.
Fig. 3: Corner points for a third order Hilbert curve  Lemma 1:   The corner points of a Hilbert curve of order  n   are given by   t   = 0 . 4 q 1   00 ... 0 ︸ ︷︷ ︸  n − 1 0 s  or   t   = 0 . 4 q 1   33 ... 3 ︸ ︷︷ ︸  n − 1 3 s  .  Proof   By definition, intervals of the form   [   q 1  4   ,   q 1   +1 4   ]   map into one of the four   ( n   −   1) th   order Hilbert curves in the  nth   order Hilbert curve. Therefore, the corner node that enters the   ( n   −   1) th   order Hilbert curve is simply the first of the   4 n − 1   nodes within the same. Hence, it is given by  t   = 0 . 4 q 1 00 ... 0 . Similarly, the corner node that leaves the   ( n   −   1) th   order Hilbert curve is the last node of the same and is given by  t   = 0 . 4 q 1 33 ... 3 .     Note   that   each   lower   order   Hilbert   curve   within   the  nth   order Hilbert curve also contains corner nodes defined in a similar fashion. In general, each corner node (of every order) is given by   t   = 0 . 4 q 1 q 2 ..q n   where   q n   = 0   or   3 . Hence, all nodes that enter or leave the first order Hilbert curve are the corner nodes. Every other node lies between two corner nodes and due to the locality preserving property of the Hilbert curve, lie adjacent to each other. This is an important consequence which helps in devising a simple strategy to avoid an obstacle that is placed on a non-corner node as shown in Figure 4a which depicts a first order Hilbert curve. In essence, the locality preserving property ([12]) of the Hilbert curve helps us to skip the blocked node. However if the blocked node is a corner node, it may not be possible to simply skip it because the sub-square containing the next node may not intersect the sub-square containing the node preceding the obstacle node. Figure 4b illustrates the point in the case of a second order Hilbert curve where simply skipping the blocked node is not possible without disturbing the sequence of nodes dictated by map for the Hilbert curve. Now, we characterize the factors that come into play when deciding on a maneuver to avoid an obstacle node when placed on a corner node for a Hilbert curve of any order. Additionally, we also assume that the first node and the last  (a)   Evasive   maneuver   for when the obstacle lies on a non-corner node  (b) A case where skipping the blocked node is not pos- sible.  Fig. 4 node of the   nth   order Hilbert curve are unblocked.  Theorem 1:   For   the   nth   order   Hilbert   curve,   let  e n   =   n   ( mod   2)   and the entering and exiting corner nodes be given by   t   =   0 . 4 ( q 1   + 1)00 ... 0   and   t   =   0 . 4 q 1 33 ... 3  respectively where   q 1   = 0 ,   1 ,   2 . Then, the required evasive maneuver to avoid an obstacle on a corner node depends solely on the type of corner node (i.e, entering node or exiting node).  Proof   Consider the corner node which leaves the   ( q 1   + 1) th sub-square of the   n th order Hilbert curve. It is denoted by  t   = 0 . 4 q 1 33 ... 3 . The succeeding and preceding nodes are  t 1   = 0 . 4 ( q 1   + 1)00 ... 0   and   t 2   = 0 . 4 q 1 33 ... 2 . These points are mapped into   Q   as follows.  f h ( t 1 ) =   1 2 n − 1   H q 1 +1 H 0 H 0 ...F 0   + 1 2   h q 1 +1 + 1 2 2   H q 1 +1 ( h 0   + 1 2   H 0 h 0   + 1 2 2   h 0   +   ..   1 2 n − 1   H 1 − e n  0   h 0 )  Since   h 0   =  [ 0 0  ]  and   F 0   =  [   1 4 1 4  ]  , we have  f h ( t 1 ) =   1 2 n − 1   H q 1 +1 F 0   + 1 2   h q 1 +1  Now,  f h ( t 2 ) =   1 2 n − 1   H q 1   H 3 H 3 ...F 2   + 1 2   h q 1   + 1 2 2   H q 1   ( h 3   + 1 2   H 3 h 3   + 1 2 2   h 3   +   ..   1 2 n − 1   H 1 − e n  3   h 3 )  Again, since   H 3   =   − H 0   and   F 2   =  [   3 4 3 4  ]  , we have  f h ( t 2 ) =   −   1 2 n − 1   H q 1   F 2   + 1 2   h q 1   + 1 2 2   H q 1   ( h 3   −   1 2   H 0 h 3   + 1 2 2   h 3   +   ..   1 2 n − 1   ( − H 0 ) 1 − e n   h 3 )
⇒   f h ( t 2 ) =   −   1 2 n − 1   H q 1   F 2   + 1 2   h q 1   + 1 2 2   H q 1   ( h 3   −   1 2   H 0 h 3   + 1 2 2   h 3   +   ..   1 2 n − 1   ( − H 0 ) 1 − e n   h 3 )  The   evasive   maneuver   to   be   chosen   depends   on   the distance between the nodes preceding and succeeding the obstacle node. Hence, we find   f h ( t 1 )   −   f h ( t 2 ) .  f h ( t 1 ) − f h ( t 2 ) =   1 2 n − 1   ( H q 1 +1 F 0   +   H q 1   F 2 ) + 1 2 ( h q 1 +1   −   h q 1   )  −   1 2 2   H q 1  [ 2   −   1 2   +   1 2   −   1 4   +   1 4   ..   −   1 2 n − 3   (1   −   e n ) 1   −   1 +   1 4   −   1 4   +   1 8   −   1 8   −   1 2 n − 2   e n  ]  Defining   e q 1   =   q 1   ( mod 2) ,  ⇒   f h ( t 1 )   −   f h ( t 2 ) =  [  (   1 2 n   ) f loor (   q 1 2   )   +   e q 1  2 1 2 n   ) f loor (   q 1 2   )   +   1 − e q 1  2  ]  −   1 2 2   H q 1  [ 2   −   1 2 n − 3   (1   −   e n )  −   1 2 n − 2   e n  ]  Noting the fact that term   1 2 n   is merely a scaling factor, the distant between the nodes,   || f h ( t 1 )   −   f h ( t 2 ) || 2 , is primarily dependent on   q 1   and   e n . A similar analysis for the second type of corner node(entering a Hilbert curve of the same order) yields a similar result.     The   same   result   can   be   obtained   for   lower   order curves   within   the   given   Hilbert   curve   because   of   its self-similarity   property.   Consider   a   general   corner   node  t   = 0 . 4 q 1 q 2 ..q p mmm..m   where   m   is either 0 or 3. This node   enters   or   exits   an   ( n   −   p ) th   order   Hilbert   curve and   so,   the   ”effective”   order   of   the   Hilbert   curve   is  n ef f   =   n   −   p   + 1 . So, to decide on an evasive maneuver, we obtain   e n ef f   , q p ,   and   m   (which is known to the agent due to position feedback). Table I depicts the various evasive maneuvers that can be employed for various scenarios to avoid an obstacle placed on a corner node. By identifying the dependancy of the maneuver on   e n ,   q p ,   and   m , the various scenarios can be identified canonically and hence, presents the possibility of designing strategies for evasion that can be used online. Considering the assumption that the first node and the last node of the   nth   order Hilbert curve are unblocked, the number of combinations of   ( e n , q p , m )  is given by  2 ︸︷︷︸  e n  ×   4 ︸︷︷︸  q p  ×   2 ︸︷︷︸  m  −   4 ︸︷︷︸  Start and end points  = 12  The various combinations are categorized together based on the distance between the current node and the node succeeding the obstacle. The evasive strategies are presented in two forms :  •   in a discrete setting wherein the strategy prescribes the sequence of nodes to be traversed to evade the obstacle and not disturb the sequence of nodes as prescribed by Hilbert’s map.  •   in a continuous setting wherein the piecewise linear map that defines the approximating polygon for the Hilbert curve is modified. For example, for a third order Hilbert curve if the position of the obstacle is   t   = 0 . 4 110 , then   p   = 2   and   n ef f   = 3   −   2 + 1 = 2 . Therefore,   e n ef f   = 0 , q p   = 1 , m   = 0   and the prescribed maneuver is the last maneuver of the table. The paths described in Table I can be implemented using mobile robots by fitting splines along the nodes as is shown in [13]  Theorem 2:   Using the evasion strategies enlisted in Table I, a mobile agent traverses every available node of a Hilbert curve of any order in the space   Q   if an obstacle is placed on any node (barring the first and last node of the curve) of the same.  Proof   We proceed to prove the above statement using induction on the order of the Hilbert curve. Consider the first order Hilbert curve. Since the obstacle can’t be placed on the starting or ending node, it has to lie on a non-corner node as shown in figure 4a. Hence, the map is modified to just skip the blocked node and the rest of the nodes are visited. Hence, the proposed hypothesis holds true for   n   = 1 . Suppose   that   the   hypothesis   holds   true   for   n   =   k . Now, the Hilbert curve of order   n   =   k   + 1   is composed of 4 units of   kth   order Hilbert curves. There are two possible cases for the position of the obstacle node:  Case 1:   The obstacle node occupies a node which is neither the first nor the last node of one of the four   kth   order Hilbert curves. From definition 1, this would imply that obstacle doesn’t lie on the corner nodes of   ( k   + 1) th   order Hilbert curve and the solution for   n   =   k   is used for which the hypothesis holds true.  Case   2:   The   obstacle   node   occupies   a   corner   node   of the   ( k   + 1) th   order Hilbert curve that isn’t the starting or ending node of the same. In this case,   ( e n , p, m )   are obtained and the corresponding maneuver is performed. Note that the evasive maneuvers preserve the sequence of nodes everywhere except the first
( e n , q p , m )   Evasion Maneuver   Change in Path   Change in Map  f   ′   :   I   →   Q  (0,0,3) (0,3,0) (1,1,0) (1,2,3)  Node (: , n obs ) =   Node (: , n obs   + 1)   ( t   −   n obs   − 1 4 n   ) f h (   n obs   +1 4 n   )   −   ( t   −   n obs   +1 4 n   ) f h (   n obs   − 1 4 n   )  ∀ t   ∈   [   n obs   − 1 4 n   ,   n obs   +1 4 n   ]  (0,1,3) (0,2,0)  (1,0,3) (0,2,3)  Node (: , n obs ) =   Node (: , n obs   −   3) ( t   −   n obs   − 1 4 n   ) f h (   n obs   − 3 4 n   )   −   ( t   −   n obs  4 n   ) f h (   n obs   − 1 4 n   )  ∀ t   ∈   [   n obs   − 1 4 n   ,   n obs  4 n   ] ( t   −   n obs  4 n   ) f h (   n obs   +1 4 n   )   −   ( t   −   n obs   +1 4 n   ) f h (   n obs   − 3 4 n   )  ∀ t   ∈   [   n obs  4 n   ,   n obs   +1 4 n   ]  (1,1,3)  (0,1,0) (1,3,0)  Node (: , n obs ) =   Node (: , n obs   + 3)  Node (: , n obs   + 3) =   Node (: , n obs   + 4) ( t   −   n obs   − 1 4 n   ) f h (   n obs   +3 4 n   )   −   ( t   −   n obs  4 n   ) f h (   n obs   − 1 4 n   )  ∀ t   ∈   [   n obs   − 1 4 n   ,   n obs  4 n   ] ( t   −   n obs  4 n   ) f h (   n obs   +1 4 n   )   −   ( t   −   n obs   +1 4 n   ) f h (   n obs   − 3 4 n   )  ∀ t   ∈   [   n obs  4 n   ,   n obs   +1 4 n   ] ( t   −   n obs   +2 4 n   ) f h (   n obs   +4 4 n   )   −   ( t   −   n obs   +4 4 n   ) f h (   n obs   +2 4 n   )  ∀ t   ∈   [   n obs   +2 4 n   ,   n obs   +4 4 n   ] (1,2,0)  TABLE I: Evasive maneuvers for obstacle avoidance.
order Hilbert curve within which the obstacle node lies. However, every node in this first order Hilbert curve is visited prior to resorting back to the correct sequence of nodes and thus every available node in the   ( k   + 1) th   order Hilbert curve is visited. Since the hypothesis holds true for   n   =   k   + 1   as well, we conclude using the principle of mathematical induction that using the evasion strategies enlisted above, a mobile agent traverses every available node of a Hilbert curve of any order in the space   Q   if an obstacle is placed on any node (barring the first and last node of the curve) of the same.     Corollary 1:   The evasive strategies proposed in Table I can accommodate multiple obstacles nodes provided that no two obstacles share an edge of their respective sub-squares. This modification of Hilbert’s curve can be used online for exploration tasks by robotic agents. A specific example that could draw benefits from this algorithm is using ground bots for demining abandoned mine fields. After locating a search space, an array of ground bots can be left to explore the area and detonate the mines. Due to the modification of the map of the Hilbert’s curve to accommodate for obstacles, detonated bots act as blocked nodes and are accordingly avoided by the remaining bots. IV. N ON - UNIFORM   C OVERAGE  Non-uniform coverage using a Hilbert’s space filling curve has been studied in [9]. The region to be searched is divided into regions of varying “interest”. The “interesting” regions are to be searched with a higher resolution (more finely, using a higher order Hilbert’s curve). This is done by searching the space using coverage trees ([14]) where the root node is the centre of the square space and the subsequent levels are the nodes of Hilbert’s curves of increasing order. Such a tree structure requires the use of a self-similar, locality preserving curve because when zooming in or out, the successive nodes need to be close to each other([12]). This neccesitates the use of a space-filling fractal like the Hilbert’s curve. Moreover, it is shown in [9] that using the Hilbert’s curve for ordering of nodes in the coverage tree leads to more efficient coverage solutions. We extend their algorithm to accommodate for spaces with obstacles using the evasion strategy presented earlier (Table I) via a simple modification. For the Shortcut Heuristic proposed in [14], when the next node belongs to a Hilbert’s curve of different order, the we first go to the parent or child node of the current node to match the order of the next node. Then, we proceed to the next node unless if it is an obstacle node; in which case, the proposed obstacle avoidance strategy can be used because the current node (after ascending or descending accordingly) and the obstacle node are of the same order. This modified strategy can also be used to avoid multiple obstacle nodes of orders different from that of the nodes dictated by required search resolution. The implicit assumption is that the obstacles are nodes of Hilbert’s space-filling curve and it is also assumed that no two obstacles are adjacent.  Fig. 5: Using Hilbert’s curves for ordering of nodes in the Coverage Tree for non-uniform coverage V. I MPLEMENTATION AND   S IMULATIONS  The algorithm presented in the earlier sections can be used for online implementation because no apriori information about the location of the obstacle nodes is required. For non-uniform coverage, the resolutions with which particular sections of the space are to be searched can be relayed to a ground agent by an aerial agent working in tandem in real time. The prescribed strategies are deployed in various situations to demonstrate its effectiveness in figure 6. The various cases are tested for   n   = 2( e n   = 0)   and   n   = 3( e n   = 1)   for both types of corner nodes for the cases   p   = 0 ,   1 .  (a)   ( e n , p, m ) = (0 ,   0 ,   0)   (b)   ( e n , p, m ) = (1 ,   0 ,   0)  (c)   ( e n , p, m ) = (0 ,   0 ,   3)   (d)   ( e n , p, m ) = (1 ,   0 ,   3)  (e)   ( e n , p, m ) = (0 ,   1 ,   3)   (f)   ( e n , p, m ) = (1 ,   1 ,   3)  Fig. 6
Algorithm 1   Implementation of prescribed algorithm. Repeat for every node  Input   n ,   node is obstacle ,   obstacle size  Memory   t t   =   t   +   1 4 n   ; Node (:) =  [ 0 0  ]  ; %% Initializing vector of nodes  q (1 :   n ) = [00 .. 0] ; %%Vector to store digits  j   =   n ; %% Extracting digits  While { j   ≥   1 }{  q ( j ) = 4(4 j − 1 t   −   f loor (4 j − 1 t ))   −   4 j   t   +   f loor (4 j   t )  j   =   j   −   1 ; }  %% Mapping node via the Modified Hilbert Map  k   =   n ;  While { k   ≥   1 }{  if   { k   =   n }{  Node (:) =   F   ( q ( n )) ; }  else {  Node (:) =   T q ( k ) Node (:) ; }  k   =   k   −   1 ; }  %%Obstacle Avoidance  if   node is obstacle {  if   Node (:)   is a corner node {  n   =   obstacle size ; Calculate Node(:) at   t   −   3 4 n   ,   t ,   t   +   1 4 n   ,   t   +   2 4 n   ,   t   +   3 4 n   ,   t   +   4 4 n   ; Obtain   ( e n ef f   , p, m )   at   t   and perform evasion maneuver; }  else {  Not a corner node, so just skip the node; }}  else {  Make the robot go to the node; }  (a)   Employing   enlisted strategies   in   a   case   with multiple obstacles.  (b)   Non-uniform   coverage in a space with obstacles.  Fig. 7 If the obstacles are far enough, the prescribed evasive strategies yield good results as shown in Figure 7a. Cases like this could appear in real life situations like demining of mine fields as mentioned earlier. Furthermore, application of the algorithm for non-uniform coverage of a space with obstacles of varying sizes is presented in Figure 7b. VI. C ONCLUSION  The paper suggested a change in the map for plotting Hilbert’s curve via its approximating polygon for use in exploration tasks. In the following sections, the problem of using the Hilbert’s curve for exploring a space with an obstacle/a hole was considered and an inductive solution to the same was obtained using the locality preserving and self- similarity property of the Hilbert curve. The prescribed strat- egy is suitable for online implementation because location of the obstacle is not required apriori. The algorithm can be also used during non-uniform coverage operations. Future work entails consideration of arbitrary obstacles occupying a space to develop strategies for path planning and searching. R EFERENCES [1]   H. Sagan, “Space-filling curves.”   New York: Springer-Verlag, 1994. [2]   B. Goertzel, “Global optimization with space-filling curves,”   Applied Mathematics Letters , vol. 12, no. 8, pp. 133–135, 1999. [3]   D. Lera and Y. D. Sergeyev, “Lipschitz and holder global optimization using space-filling curves,”   Applied Numerical Mathematics , vol. 60, no. 1, pp. 115–129, 2010. [4]   A. R. Butz, “Space filling curves and mathematical programming,”  Information and Control , vol. 12, no. 4, pp. 314–330, 1968. [5]   S. V. Spires and S. Y. Goldsmith, “Exhaustive geographic search with mobile robots along space-filling curves,”   Collective Robotics , pp. 1– 12, 1998. [6]   M. Bertoldi, M. Yardimci, C. Pistor, and S. Guceri, “Domain decom- position and space filling curves in toolpath planning and generation,”  Solid Freeform Fabrication Proceedings , pp. 267–276, 1998. [7]   Z. Liu, Y. Chen, B. Liu, C. Cao, and X. Fu, “Hawk: An unmanned mini helicopter-based aerial wireless kit for localization,”   Proceedings of IEEE INFOCOM , 2012. [8]   J. Kuffner and S. M. LaValle, “Space-filling trees: A new perspective on motion planning via incremental search,”   Proceedings of IEEE International Conference on Intelligent Robots and Systems (IROS) , 2011. [9]   S. A. Sadat, J. Wawerla, and R. Vaughan, “Fractal trajectories for on- line non-uniform aerial coverage,”   Proceedings of IEEE International Conference on Robotics and Automation (ICRA) , 2015. [10]   X.   Ban,   M.   Goswami,   X.   G.   W.   Zeng,   and   J.   Gao,   “Topology dependent space filling curves for sensor networks and applications,”  Proceedings of IEEE INFOCOM , 2013. [11]   J. Munkres,   Topology , ser. Featured Titles for Topology Series.   Pren- tice Hall, Incorporated, 2000. [12]   H. Dai and H. Su, “On the locality properties of space-filling curves,”  Algorithms and Computation , vol. 2906, pp. 385–394, 2003. [13]   M. Gardner, “Mathematical games -in which ”monster” curves force redefinition of the word ”curve”,”   Scientific American , vol. 235, no. 6, pp. 124–133, 1976. [14]   S. A. Sadat, J. Wawerla, and R. Vaughan, “Recursive non-uniform cov- erage of unknown terrains for uavs,” in   2014 IEEE/RSJ International Conference on Intelligent Robots and Systems , 2014.