.
The Optimal Obstacle Placement With Disambiguation Problem by Polat Charyyev A Dissertation Submitted to the Graduate School of Sciences and Engineering in Partial Fulfillment of the Requirements for the Degree of Doctor of Philosophy in Mathematics 2017 The Optimal Obstacle Placement With Disambiguation Problem Koç University Graduate School of Sciences and Engineering This is to certify that I have examined this copy of a doctoral dissertation by Polat Charyyev and have found that it is complete and satisfactory in all respects, and that any and all revisions required by the final examining committee have been made. Committee Members: Assoc. Prof. Atilla Yılmaz Assoc. Prof. Mine Çaglar Assoc. Prof. Elvan Ceyhan Asst. Prof. Özgür Asar Asst. Prof. Ümit Islak Date: This thesis is dedicated to my parents. iii ABSTRACT In the optimal obstacle placement with disambiguation (OPD) problem, we investigate how traversal length depends on the spatial pattern of the obstacles. In the OPD problem an obstacle placing agent (OPA) wishes to insert (diskshaped) obstacles of two types as true or false obstacles in an environment so as to maximize the traversal length of a navigating agent (NAVA). NAVA is equipped with a sensor that can only assign probabilities to each obstacle as being a true obstacle, but does not know the actual status of the obstacle until it reaches the boundary of the obstacle. When NAVA comes by the obstacle, it disambiguates the status of the obstacle with a cost added to the traversal length. We first investigate the case when OPA equips the overall working window with false and/or true obstacles together where the whole obstacle pattern changing from uniformness to regularity and from uniformness to clustering, then on the average, the mean traversal length tends to increase (decrease) as the obstacle pattern changes from uniformness to regularity (clustering). Secondly, we introduce M2k algorithm which is the modified version of RD algorithm and mainly based on the effective choice of a subset of possible disambiguations. We observed that the trends for mean traversal length estimated by M2k algorithm is similar to RD algorithm except for reducing the complexity time and keeping relative error less than 2:5%. Moreover, we study the case when obstacles are distributed inside various obstacle window types such as linear strips, Vshaped, semicircular, and elliptical where we change the parameters such as location, orientation and curvature of these obstacle window forms. We also consider the case where the true obstacles are placed randomly proportional to the areas of Voronoi polygons or Delaunay triangles based on the allocation of the clutter points. On the average, the elliptical window type (a continuous version of Vshaped) reveals to be the best iv performing in maximizing the traversal length of NAVA and as for tessellations, the mean traversal length is essentially the same as the mean traversal length when obstacles are distributed uniformly. On the other hand, we provide extensions of the existing suboptimal algorithms in the OPD problem, and introduce new ones for NAVA. The goal is to find an algorithm to minimize the expected traversal length of NAVA. We generalize the penaltybased functions used within the existing heuristic algorithms, and combine possibly related algorithms in a single family. We provide a guidance for choosing the algorithm from the defined family when the performance of NAVA’s sensor varies from poor to almost perfect detection (of true obstacles). Our results are supported by extensive Monte Carlo simulations and theoretical results for some special types of graph structures are also provided. ÖZETÇE Belirsizligi giderme özellikli optimal engel yerlestirme (OPD) probleminde, yol uzunlugunun uzaysal desen türlerine göre nasıl etkilendigini arastırıyoruz. OPD probleminde, navigasyon aracının (NAVA) gidecegi yolu mümkün oldugunca uzun tutmak için yüzeye engel yerlestirme aracı (OPA) tarafından gerçek veya sahte engeller yerlestirilmektedir. NAVA her diskin gerçek engel olma ihtimalini belirleyen sensör ile donatılmıs olup, disklerin gerçek veya sahte oldugunu diskin sınırlarına gelene kadar bilmemektedir. Fakat NAVA diskin sınırlarında iken belirli bir maliyetin toplam süreye/uzunluga eklenmesi karsılıgında disklerin gerçek veya sahte oldugunu ögrenebilmektedir. ?lk olarak, OPA’nın çalısma bölgesine sahte ve/veya gerçek engelleri tüm engel desenin tekdüzelikten düzenlilige ve tekdüzelikten kümelenmeye göre yerlestirilmesi sonucunda toplam geçis uzunlugunun engel desenin tekdüzelikten düzenlilige göre artmakta ve tekdüzelikten kümelenmeye göre ise azalmaktadır. Ikinci olarak, RD algoritmasının degistirilmis versiyonu olan ve temel olarak disk basına düsen belirsizlik nokta sayısının akıllıca seçilmesine baglı olan M2k algoritmasını tanıtmaktayız. M2k algoritması tarafından hesaplanan yol uzunlugunun RD algoritması tarafından hesaplanan yol uzunlugu ile benzer egilimler gösterdigini gözlemledik ve dahası hesaplama süresi azaltılmıs olup, toplam geçis uzunlugu en fazla %2:5 sapmaktadır. Buna ek olarak, engellerin lineer, Vseklinde, yarı çembersel, ve eliptik gibi degisik sekil içinde dagılımları engel sekillerin lokasyon, oryantasyon, ve kurvatür gibi parametrelerine göre incelenmistir. Ayrıca, sahte engellerin yerlesimine baglı olarak Voronoi çokgen veya Delaunay üçgen alanlarına orantılı olacak sekilde gerçek engellerin yerlestirilme durumu ele alınmıstır. Ortalama olarak, NAVA’nın toplam geçis uzunlugunu maksimuma çıkarmak için engel sekillerin arasından eliptik engel sekli (Vseklinin sürekli versiyonu) en optimal degeri vermektedir ve Dirichlet vi mozaigi gibi düzenlemeler için ise geçis uzunlugu engellerin tekdüze dagılımındakine yakın degeri vermektedir. Diger taraftan, OPD problemindeki NAVA için mevcut optimal olmayan algoritmaları genisletmekteyiz ve yenilerini ortaya koymaktayız. Buradaki asıl amaç, NAVA’nın beklenen geçis uzunlugunu minimuma indiren algoritma gelistirmektir. Mevcut sezgisel algoritmalarda kullanılan agırlıga dayalı fonksiyonları genellestiriyoruz, ve benzer algoritmaları tek çatı altında birlestiriyoruz. NAVA’nın sensör algılama (gerçek engel olma ihtimali) performans gücünün en zayıftan mükemmel dereceye kadar durumlarda birlestirilen algoritma kümesinden en optimal olanı seçmeyi gösteriyoruz. Bizim sonuçlarımız kapsamlı Monte Carlo simülasyonları ile desteklenmekle beraber, bazı özel graf biçimleri için teorik sonuçlar göstermekteyiz. ACKNOWLEDGMENTS I would like to express my sincere gratitude to my advisors Assoc. Prof. Elvan Ceyhan and Assoc. Prof. Atilla Yılmaz for the continuous support of my Ph.D study and related research, for their patience, motivation, and immense knowledge. Their guidance helped me in all the time of research and writing of this thesis. Besides my advisor, I would like to thank Assoc. Prof. Vural Aksakallı for his guidance and help on designing and understanding the related algorithms. I thank my thesis committee members Assoc. Prof. Atilla Yılmaz and Assoc. Prof. Mine Çaglar for their insightful comments and encouragement. I also thank thesis jury members Asst. Prof. Özgür Asar and Asst. Prof. Ümit Islak for accepting and participating my thesis defense. I thank my Ph.d colleagues, especially Artür Manukyan for the stimulating discussions and for all the fun we have had in the last five years. I thank Mathematics department Professors for creating academic environment and all GSSE staff, especially Emine Büyükdurmus and Elif Tüysüz for their continual support and guidance. I would like to thank Koç University and TUBITAK for providing me with financial support which made this study possible. I would like to thank my family: my parents, my brother and sisters, my wife and beloved son for supporting me spiritually throughout writing this thesis and my life in general. viii TABLE OF CONTENTS List of Tables xii List of Figures xv Nomenclature xxv Chapter 1: Introduction 1 1.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2 Continuous SOS and OPD Problems . . . . . . . . . . . . . . . . . . 5 1.3 Discretized SOS and OPD Problems . . . . . . . . . . . . . . . . . . 6 1.4 Organization of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . 7 Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent 8 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2 Experimental Setting . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.3 Obstacle Pattern Ranging from Uniformness to Regularity . . . . . . 11 2.3.1 Clutter Only Case . . . . . . . . . . . . . . . . . . . . . . . . 12 2.3.2 True Obstacles Only Case . . . . . . . . . . . . . . . . . . . . 19 2.3.3 True and False Obstacles Together . . . . . . . . . . . . . . . 22 2.4 Obstacle Pattern Ranging from Uniformness to Clustering . . . . . . 24 2.5 Stochastic Ordering of Traversal Lengths . . . . . . . . . . . . . . . . 27 2.6 Mean Traversal Length Versus Ratio of Number of True to False Obstacles 31 2.6.1 Obstacle Pattern Ranging from Uniformness to Regularity . . 32 2.6.2 Obstacle Pattern Ranging from Uniformness to Clustering . . 38 ix 2.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 Chapter 3: M2k Algorithm for the OPD Problem 45 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 3.2 Experimental Setting . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 3.2.1 Background Clutter Generation . . . . . . . . . . . . . . . . . 45 3.3 M2k Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 3.4 Repeated Measures ANOVA . . . . . . . . . . . . . . . . . . . . . . . 51 3.4.1 Overall Comparison of Traversal Lengths . . . . . . . . . . . . 52 3.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 Chapter 4: Dependence of Traversal Length on Obstacle Window Types and Tessellations 62 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 4.2 Obstacle Window Types . . . . . . . . . . . . . . . . . . . . . . . . . 63 4.2.1 Linear Strip Window . . . . . . . . . . . . . . . . . . . . . . . 63 4.2.2 VShaped Window . . . . . . . . . . . . . . . . . . . . . . . . 66 4.2.3 Semicircular Window . . . . . . . . . . . . . . . . . . . . . . . 71 4.3 Placing True Obstacles in a Regular Fashion . . . . . . . . . . . . . . 74 4.4 Voronoi and Delaunay Tessellations . . . . . . . . . . . . . . . . . . . 80 4.4.1 Results and Analysis . . . . . . . . . . . . . . . . . . . . . . . 81 4.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 Chapter 5: Heuristic Algorithms for the OPD Problem 87 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 5.2 Algorithms for NAVA . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 5.3 A Unifying Framework for FRD, FP , and FDT . . . . . . . . . . . . . 91 5.4 Experimental Setting . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 5.5 ALG(k) Algorithm and Sensor Precision . . . . . . . . . . . . . . . . 101 x 5.6 ALG(k) Algorithm and the Disambiguation Cost . . . . . . . . . . . 107 5.7 Convergence of Traversal Length Under ALG(k) Algorithm . . . . . . 109 5.8 MT(~k) Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 5.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 Chapter 6: Theoretical Results 123 6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 6.2 RD Algorithm for the Discrete SOSP . . . . . . . . . . . . . . . . . . 124 6.3 Graphs with Two Nodes . . . . . . . . . . . . . . . . . . . . . . . . . 125 6.3.1 Empirical Results . . . . . . . . . . . . . . . . . . . . . . . . . 131 6.4 Generalization of OPD Problem . . . . . . . . . . . . . . . . . . . . . 131 6.4.1 Higher Dimensional Discretization . . . . . . . . . . . . . . . . 133 6.5 Future Research . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 Chapter 7: Conclusions and Discussion 137 xi LIST OF TABLES 2.1 Intercept and slope values of regression lines for each categorical group nc. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.2 Significant level of differences (pvalues) in intercept (a) and slope (b) for each pair of groups. . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.3 Coefficients of quadratic polynomial fitted to the data at each clutter number level. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.4 Significant level of differences (pvalues) of coefficient c (intercept) (a), coefficient b (linear term) (b), and coefficient a (quadratic term) (c) at each pair of clutter level. . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.5 Intercept and slope values of regression lines for each categorical group no. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.6 Significant level of differences (pvalues) in intercept (a) and slope (b) for each pair of groups. . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.7 Intercept and slope values of regression lines for each categorical group . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 3.1 The comparisons of the models in Equation (1) when the traversal length is estimated by RD algorithm. . . . . . . . . . . . . . . . . . 53 3.2 The shortest and longest traversal lengths and the corresponding treatment types for overall comparisons, and comparisons at specific clutter types, obstacle types, and obstacle numbers when the traversal length is computed by RD algorithm. . . . . . . . . . . . . . . . . . . . . . 59 xii 3.3 The shortest and longest traversal lengths and the corresponding treatment types for overall comparisons, and comparisons at specific clutter types, obstacle types, and obstacle numbers when the traversal length is computed by M8 algorithm. . . . . . . . . . . . . . . . . . . . . . 60 4.1 Comparison of mean traversal lengths for obstacle number levels no = 40 and no = 50. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 4.2 Comparison of mean traversal lengths for obstacle number levels no = 50 and no = 60. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 4.3 Mean traversal length versus d2 values for no = 20 inside L10 obstacle form with background clutter type Hardcore(nc = 100; d) where d = 5; 6; 7; 8. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 4.4 Mean traversal length versus d2 values for no = 30 inside V90 obstacle form with background clutter type Hardcore(nc = 100; d) where d = 5; 6; 7; 8. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 4.5 Mean traversal length versus d2 values for no = 30 inside SC90 obstacle form with background clutter type Hardcore(nc = 100; d) where d = 5; 6; 7; 8. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 5.1 Comparison of mean traversal lengths estimated by the RD (shown in bold) and ALG(2) algorithms for various pairs of (nc; no) with percentage error less than 2%. . . . . . . . . . . . . . . . . . . . . . . . . . 98 5.2 Comparison of mean traversal lengths computed by the P (shown in bold) and ALG(3) algorithms for various pairs of (nc; no) with percentage error less than 0:5% . . . . . . . . . . . . . . . . . . . . . . . . . 98 5.3 Comparison of mean traversal lengths computed by the DT (shown in bold) and ALG(5) algorithms for various pairs of (nc; no) with percentage error less than 1%. . . . . . . . . . . . . . . . . . . . . . . . . . 100 xiii 6.1 For any fixed values of a and n, there are 100 realizations of values of p selected randomly from uniform (0; 1) distribution. And, we exhibit the corresponding mean values. . . . . . . . . . . . . . . . . . . . . . 132 6.2 Some values of k in ddimensional case . . . . . . . . . . . . . . . . . 135 xiv LIST OF FIGURES 2.1 A realization of clutter disks (dashed circles) with nc = 40 from the Strauss(nc = 40; d = 9; = 0) process. . . . . . . . . . . . . . . . . . 12 2.2 Mean traversal length versus values for groups nc = 25; 50; 75; 100 together with overall plot (i.e., the average of all groups combined). . 13 2.3 Mean traversal length versus d values for groups nc = 25; 50; 75; 100 with overall plot (i.e., the average of all groups combined). . . . . . . 15 2.4 Mean traversal length versus d values for nc = 25; 50; 75; 100 together with quadratic polynomial fit and (nonparametric) smoothing spline with smoothing parameter p = 0:9863 . Notice that vertical axes are differently scaled. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.5 Contour plots of mean traversal length versus and d values for nc = 25; 50; 75; 100. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.6 Mean traversal length versus values for groups no = 25; 50; 75; 100 together with overall plot (i.e., the average of all groups combined). . 21 2.7 Contour plots of mean traversal length versus and d values for no = 75; 100. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.8 The pattern is from the Strauss(nc + no = 50; d = 9; = 0) process where dashed circles (nc = 25 with centers in XC) are the 25 false obstacles and solid circles (no = 25 with centers in XO) are the 25 true obstacles. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.9 Contour plots of the mean traversal length versus and d values when (a) (nc; no) = (25; 50), (b) (nc; no) = (25; 75). . . . . . . . . . . . . . . 24 xv 2.10 (a) A realisation of clutter disks from the Matérn( = 2; r0 = 15; = 10) process shown in dashed circles. (b) The pattern is from the Matérn(8,15,10) process where dashed circles indicate the false obstacles (nc = 60) and solid circles indicate the true obstacles (no = 20). . 26 2.11 Mean traversal length versus cluster radius values when there are (a) only clutter disks with nc = 20; 40; 60; 80 together with overall plot (i.e., the average of all groups combined), (b) only true obstacles with no = 20; 40; 60; 80 together with overall plot (i.e., the average of all groups combined). Notice that vertical axes are differently scaled. . . 27 2.12 Mean traversal length versus values for groups (a) = 0; 1=4; 1=2; 1 together with overall plot (the average of all 7 distinct groups), (b) = 1; 2; 4;1 together with overall plot (the average of all 7 distinct groups). Notice that vertical axes are differently scaled. . . . . . . . . 33 2.13 (a) Mean traversal length versus values for groups = 0; 0:4; 0:6; 1, (b) average contour plot of mean traversal length versus and values. 34 2.14 Mean traversal length versus d values for groups (a) = 0; 1=4; 1=2; 1 together with overall plot (the average of all 7 distinct groups), (b) = 1; 2; 4;1 together with overall plot (the average of all 7 distinct groups). Notice that vertical axes are differently scaled. . . . . . . . . 35 2.15 (a) Mean traversal length versus values for groups d = 1; 4; 6; 10, (b) average contour plot of mean traversal length versus d and values. 36 2.16 Overall average contour plots of the mean traversal length versus and d values for (a) = 0, (b) = 1=4, (c) = 1=2, and (d) = 1. . . . . 37 2.17 Overall average contour plots of the mean traversal length versus and d values for (a) = 2, (b) = 4, (c) = 1, and (d) overall (the average of all levels). . . . . . . . . . . . . . . . . . . . . . . . . . . 38 xvi 2.18 Mean traversal length versus r0 values for groups (a) = 0; 1=4; 1=2; 1 together with overall plot (the average of all 7 distinct groups), (b) = 1; 2; 4;1 together with overall plot (the average of all 7 distinct groups). Notice that vertical axes are differently scaled. . . . . . . . . 39 2.19 Mean traversal length versus values for groups (a) = 0; 1=4; 1=2; 1 together with overall plot (the average of all levels), (b) = 1; 2; 4;1 with overall plot (the average of all levels). Notice that vertical axes are differently scaled. . . . . . . . . . . . . . . . . . . . . . . . . . . 40 2.20 (a) Mean traversal length versus values for groups r0 = 5; 15; 30; 50, (b) average contour plot of mean traversal length versus r0 and values. 41 2.21 (a) Mean traversal length versus values for groups = 1; 3; 6; 10, (b) average contour plot of mean traversal length versus and values. 41 2.22 Overall average contour plots of the mean traversal length versus no and nc values when (a) (d; ) = (6; 0), (b) (d; ) = (7; 0), and (c) (d; ) = (8; 0). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 3.1 Sample realizations from homogeneous and inhomogeneous point processes. The parameters are: (a) CSR(100) and (b) IP 0:037e(10y)=40 . Indeed, on the average 100 points are generated by using these distribution parameters, but by using the rejection sampling we fix them to exactly 100 points. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 3.2 Sample realizations from Matérn and Thomas point processes. The parameters are: (a) M(10; 10; 10) and (b) T(10; 10; 5). Indeed, on the average 100 points are generated by using these distribution parameters, but by using the rejection sampling we fix them to exactly 100 points. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 xvii 3.3 Sample realizations from Hardcore and Strauss point processes. The parameters are: (a) HC(100; 5) and (b) S(100; 5; 0:5). Indeed, on the average 100 points are generated by using these distribution parameters, but by using the rejection sampling we fix them to exactly 100 points. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 3.4 A total of 8 disambiguation points are labeled in each diskshaped obstacle. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 3.5 The interaction plots for each pair of treatment factors (obstacle type/form, clutter type, and obstacle number) when the other factor is ignored. The traversal length is estimated by RD algorithm. . . . . . . . . . . 57 3.6 The interaction plots for each pair of treatment factors (obstacle type/form, clutter type, and obstacle number) when the other factor is ignored. The traversal length is estimated by M8 algorithm. . . . . . . . . . . 58 3.7 The plots of mean traversal length versus obstacle window type, clutter type, and obstacle number level when computed by RD, M16, M8, and M4 algorithms, respectively. . . . . . . . . . . . . . . . . . . . . . . . 58 4.1 The background clutter pattern is from the Hardcore(100; 5) (dashed circles) process and no = 20 true obstacles are uniformly distributed inside the linear strip of width ` = 10 (solid circles). . . . . . . . . . . 64 4.2 Mean traversal length versus (a) width ` of linear strip and (b) location of linear strip for no = 20; 30; 40; 50; 60 provided that background clutter type is Hardcore(100; 5). Notice that vertical axes are differently scaled. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 4.3 Mean traversal length versus (a) width ` of linear strip and (b) location of linear strip for no = 20; 30; 40; 50; 60 provided that background clutter type is Hardcore(100; 6). Notice that vertical axes are differently scaled. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 xviii 4.4 Mean traversal length versus (a) width ` of linear strip and (b) location of linear strip for no = 20; 30; 40; 50; 60 provided that background clutter type is Hardcore(100; 7). Notice that vertical axes are differently scaled. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 4.5 Mean traversal length versus (a) width ` of linear strip and (b) location of linear strip for no = 20; 30; 40; 50; 60 provided that background clutter type is Hardcore(100; 8). Notice that vertical axes are differently scaled. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 4.6 The background clutter pattern is from the Hardcore(100; 5) (dashed circles) process and no = 20 true obstacles are uniformly distributed inside the Vshaped obstacle window with distance v = 80 between two upper lips (solid circles). . . . . . . . . . . . . . . . . . . . . . . . 68 4.7 Mean traversal length versus (a) v value and (b) location of Vshaped window for no = 20; 30; 40; 50; 60 together with v = 80 provided that the background clutter type is Hardcore(100; 5). Notice that vertical axes are differently scaled. . . . . . . . . . . . . . . . . . . . . . . . . 69 4.8 Mean traversal length versus (a) v value and (b) location of Vshaped window for no = 20; 30; 40; 50; 60 with v = 80 provided that background clutter type is Hardcore(100; 8). Notice that vertical axes are differently scaled. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 4.9 The background clutter pattern is from the Hardcore(100; 5) (dashed circles) process and no = 20 true obstacles (solid circles) are uniformly distributed inside the Vshaped obstacle window with distance w = 10 between the vertex of the obstacle from and the point (50; 10). . . . 70 4.10 Overall mean traversal length versus w values for no = 20; 30; 40; 50; 60. 71 4.11 The background clutter pattern is from the Hardcore(100; 5) (dashed circles) process and no = 20 true obstacles are uniformly distributed inside the semicircular obstacle window form (solid circles). . . . . . . 72 xix 4.12 Mean traversal length versus location of semicircular obstacle window form for no = 20; 30; 40; 50; 60 provided that the background clutter type is (a) Hardcore(100; 5) and (b) Hardcore(100; 8). . . . . . . . . 73 4.13 The background clutter pattern is from the Hardcore(100; 5) (dashed circles) process and no = 20 true obstacles (solid circles) are uniformly distributed inside the elliptical obstacle with distance u = 20 between the vertex of the obstacle from and the point (50; 10). . . . . . . . . 74 4.14 Overall mean traversal length versus u values for no = 20; 30; 40; 50; 60. 75 4.15 Mean traversal length versus d2 values (regularity parameter for no) for no = 20; 30; 40 provided that the background clutter type is Hardcore (overall average of Hardcore(nc = 100; d) with d = 5; 6; 7; 8). . . . . . 75 4.16 Mean traversal length versus d2 values (regularity parameter for no) for no = 20; 30; 40 provided that the background clutter type is Hardcore (overall average of Hardcore(nc = 100; d) with d = 5; 6; 7; 8). . . . . . 77 4.17 Mean traversal length versus d2 values (regularity parameter for no) for no = 20; 30; 40 provided that the background clutter type is Hardcore (overall average of Hardcore(nc = 100; d) with d = 5; 6; 7; 8). . . . . . 78 4.18 Mean traversal length versus d2 values (regularity parameter for no) for no = 20; 30; 40 provided that the background clutter type is Hardcore (overall average of Hardcore(nc = 100; d) with d = 5; 6; 7; 8). . . . . . 79 4.19 Mean traversal length versus d2 values (regularity parameter for no) for no = 20; 30; 40 provided that the background clutter type is Hardcore (overall average of Hardcore(nc = 100; d) with d = 5; 6; 7; 8). . . . . . 80 4.20 (a) Voronoi diagram and (b) Delaunay triangulation of 100 sample points. 82 4.21 For the CSR background clutter type, the mean traversal length (a) when true obstacles are placed around vertices and centroids of tessellations, and (b) when true obstacles are placed proportional to tile areas of tessellations. . . . . . . . . . . . . . . . . . . . . . . . . . . 82 xx 4.22 For the Hardcore(nc = 100; d) background clutter type (combined all d = 5; 6; 7; 8 cases), the mean traversal length (a) when true obstacles are placed around vertices and centroids of tessellations, and (b) when true obstacles are placed proportional to tile areas of tessellations. . 83 5.1 Pairwise comparison of the penalty functions FRD, FP , FDT with the penalty function Fk for k = 2; 3; 5. Note that both vertical and horizontal values are differently scaled. . . . . . . . . . . . . . . . . . . . 93 5.2 Disambiguation cost c versus k(c) values when p 2 (0; 1) (when the penalty function FRD approximated by the penalty function Fk). . . . 95 5.3 Comparison of mean traversal lengths computed by the RD and ALG(2) algorithms, (a) when there are only clutter disks with nc 2 f50; 75; : : : ; 200g, (b) and when there are only true obstacles with nc =2 f50; 75; : : : ; 200g with 95% confidence intervals for the mean traversal length computed by the RD and ALG(2) algorithms, respectively. . . . . . . . . . . . 96 5.4 Comparison of mean traversal lengths estimated by the P and ALG(3) algorithms, (a) when there are only clutter disks with nc 2 f50; 75; : : : ; 200g, (b) and when there are only true obstacles with nc =2 f50; 75; : : : ; 200g with 95% confidence intervals for the mean traversal length computed by the P and ALG(3) algorithms, respectively. . . . . . . . . . . . . 99 5.5 Comparison of mean traversal lengths estimated by the DT and ALG(5) algorithms, (a) when there are only clutter disks with nc 2 f50; 75; : : : ; 200g, (b) and when there are only true obstacles with no 2 f50; 75; : : : ; 200g with 95% confidence intervals for the mean traversal length computed by the DT and ALG(5) algorithms, respectively. . . . . . . . . . . . 100 xxi 5.6 Comparison of average number of disambiguations when the mean traversal length is estimated by the RD, P, and DT algorithms, (a) when there are only clutter disks with nc 2 f50; 75; : : : ; 200g, (b) and when there are only true obstacles with no 2 f50; 75; : : : ; 200g. Note that vertical axes are differently scaled. . . . . . . . . . . . . . . . . 102 5.7 Comparison of mean traversal lengths estimated by the ALG(k) algorithms, (a) when there are only clutter disks with nc = 50; 75; 100; 125, (b) and when there are only true obstacles with nc = 50; 75; 100; 125. Notice that vertical axes are differently scaled. Note that vertical axes are differently scaled. . . . . . . . . . . . . . . . . . . . . . . . . . . 103 5.8 Comparison of mean traversal lengths estimated by the ALG(k) algorithms when there are total nc + no number of obstacles uniformly generated with nc = 25; 50; 75; 100 and no = 25; 50; 75; 100. . . . . . . 105 5.9 Comparison of mean traversal lengths estimated by the ALG(k) algorithms, (a) for (nc; no) = (25; 75), (b) for (nc; no) = (50; 50), (c) and for (nc; no) = (75; 25). Notice that vertical axes are differently scaled. 106 5.10 Comparison of mean traversal lengths estimated by the ALG(k) algorithms when there are total nc + no number of obstacles (combination of all (nc; no) pairs) uniformly generated with nc; no 2 f25; 50; 75; 100g. 108 5.11 Comparison of mean traversal lengths estimated by the ALG(k) algorithms, (a) for (nc; no) = (25; 75), (b) for (nc; no) = (50; 50), (c) and for (nc; no) = (75; 25). Notice that vertical axes are differently scaled. 109 5.12 (a) Mean traversal length estimated by benchmark, ALG(1), ALG(2) algorithms versus nc with nc 2 f50; 75; : : : ; 325g. (b) Mean traversal length estimated by the benchmark, ALG(4), ALG(5) algorithms versus no with no 2 f50; 75; : : : ; 250g . Notice that horizontal axes are differently scaled. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 xxii 5.13 (a) Mean traversal length versus nc computed by the B, ALG(2), T(0:5) algorithms with nc 2 f50; 75; : : : ; 325g. (b) Mean traversal length versus no computed by the B, ALG(5), T(0:5) algorithms with no 2 f50; 75; : : : ; 250g . Note that horizontal axes are differently scaled. 113 5.14 (a) Mean traversal length versus nc estimated by the B, DT, MT(7) algorithms with nc 2 f50; 75; : : : ; 325g. (b) Mean traversal length versus no computed by the B, DT, MT(7) algorithms with no 2 f50; 75; : : : ; 250g with 95% confidence intervals for the benchmark value. Notice that horizontal axes are differently scaled. . . . . . . . . . . . . . . . . . . 114 5.15 Comparison of mean traversal lengths estimated by the B, DT, MT(7) algorithms, (a) for nc = 25 with no 2 f25; 50; : : : ; 200g, (b) and for nc = 75 with no 2 f25; : : : ; 200g with 95% confidence intervals for the benchmark value. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 5.16 Comparison of mean traversal lengths estimated by the B and MT(~k) algorithms, (a) for nc = 25 with no = 25; 50; 75; 100, (b) and for nc = 50 with no = 25; 50; 75; 100 with 95% confidence intervals for the benchmark value. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 5.17 Comparison of mean traversal lengths estimated by the B and MT(~k) algorithms, (a) for nc = 75 with no 2 f25; 50; : : : ; 100g, (b) and for nc = 100 with no 2 f25; 50; : : : ; 100g with 95% confidence intervals for the benchmark value. . . . . . . . . . . . . . . . . . . . . . . . . . . 116 5.18 Comparison of mean traversal lengths estimated by the B and ALG(k) algorithms, (a) for nc = 25 with no = 25; 50; 75; 100, (b) and for nc = 50 with no = 25; 50; 75; 100 with 95% confidence intervals for the benchmark value. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 xxiii 5.19 Comparison of mean traversal lengths estimated by the B and ALG(k) algorithms, (a) for nc = 75 with no = 25; 50; 75; 100, (b) and for nc = 100 with no = 25; 50; 75; 100 with 95% confidence intervals for the benchmark value. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 xxiv NOMENCLATURE Abbreviations CTP Canadian Traveler’s Problem DSOS Discretized Stochastic Obstacle Scene DTA Distance to Termination Algorithm NAVA Navigating Agent OPD Obstacle Placement with Disambiguation OPA Obstacle Placing Agent RDA Reset Disambiguation Algorithm SOS Stochastic Obstacle Scene SRA Simulated Risk Algorithm xxv Chapter 1 INTRODUCTION The optimal obstacle placement with disambiguation (OPD) problem was first introduced by Aksakalli and Ceyhan (2012). The OPD problem is the dual of the stochastic obstacle scene (SOS) problem (Papadimitriou and Yannakakis, 1991), where the discrete version is called the Canadian traveler’s problem (CTP) (BarNoy and Schieber, 1991). In the SOS problem, the main goal is finding the shortest path through an unknown environment wherein a navigating agent (NAVA) plans the route from a given starting point to a designated target point through randomly positioned disk shaped regions that represent obstacles. In the version of the OPD problem of Aksakalli and Ceyhan (2012), the navigation environment already contained clutter, i.e., false natural obstacles, and an obstacle placing agent (OPA) placed true obstacles in the same environment. In practice this setting may arise in various situations, for example, OPA can represent a naval warfare vehicle placing mines (i.e., true obstacles) on the surface of a water body (such as a sea or ocean) which already has natural or artificial obstacles (like rocks or debris). And, NAVA could be a battleship (from the opponent forces to OPA) and wants to traverse from a source point to a target point which might be located at the coast defended by OPA and its affiliates. Prior to NAVA’s traversal, NAVA obtains the respective probabilities of the obstacle disks being true obstacles by using its sensor. Throughout the traversal, when NAVA reaches a disk’s boundary, it can disambiguate the disk and learn the actual status of it, i.e., whether it is a true or false obstacle. The cost of the disambiguation for each disk is added to the total traversal length (which contributes to the total cost in our optimization problem). If the disambiguated disk is a false obstacle, then NAVA can pass through 2 Chapter 1: Introduction or over it; otherwise NAVA has to replan its route from the current location avoiding the true obstacles until it reaches the target. From NAVA’s perspective, the task is then finding the optimal path for reaching from the source point to the target, i.e., the path with minimum expected traversal length. Conversely, the OPA’s goal is placing the obstacles in a such a way that NAVA’s traversal length is maximized. Here, we assume that NAVA uses a greedy algorithm called the RD algorithm (Aksakalli et al., 2011) in choosing the optimal path. Hence, NAVA disambiguates any obstacle it runs into and then always seeks a better policy and updates the algorithm accordingly. On the other hand, OPA will search for a better placement of obstacles. We also consider the version of the OPD problem where OPA has the capability of inserting both true and false obstacles in the navigation environment. Although these optimization problems have gained considerable attention in literature, few theoretical and efficient optimal results have been found. In particular, Papadimitriou and Yannakakis (1991) showed that the SOS problem is NPhard, and as for the CTP with its variants, one can find many heuristics for special cases wherein the optimal solution is attained in some special graph structures (Nikolova and Karger, 2008; Xu et al., 2009; Bnaya et al., 2009; Fried, 2013). Among these references, the work of Bnaya et al. (2009) is the closest to ours. They introduce the sensing cost of an edge in the CTP problem which is equivalent to the disambiguation cost of an obstacle in the SOS problem. In this variant of CTP, additional actions, called remote sensing, are allowed where each such action reveals the status of a nonincident edge for a certain cost. Indeed, allowing remotesensing makes CTP NPhard even on disjointpath graphs (Fried et al., 2013). Regarding the suboptimal algorithms for SOS problem, the BAO* algorithm of Aksakalli (2007a), the simulated risk disambiguation (SRA) of Fishkind et al. (2007) and the reset disambiguation algorithm (RDA) of Aksakalli et al. (2011) are among the examples. Indeed, the RD algorithm is an efficient algorithm for discretized SOS problem and yields an optimal value for graphs with two nodes (called parallel graphs G = (V;E) with jV j = 2), and for disjointpath graphs. In general, the discrete SOS Chapter 1: Introduction 3 problem for parallel graphs can be solved in O(jEj!) time complexity, but using the policy dictated by the RD algorithm the complexity of solving the same problem reduces to O(jEj log jEj). Successful adaptations of all these heuristics to the discretized SOS problem and the generalizations of both SRA and RDA were given in Aksakalli and Ari (2014), which in turn is called the "distance to termination" (DT) algorithm. The DT algorithm exploits the distance from current position of any obstacle to the target point together with the corresponding probabilities of obstacles being true obstacles. As for CTP, several variants of it have been introduced and effective heuristic algorithms are proposed. For example, in BarNoy and Schieber (1991) the recoverable CTP was introduced where a blocked edge does not remain blocked forever, and each vertex v has a recovery time `(v) 2 [0;1) for edges adjacent to v. They also introduced the kCTP, in which an upper bound of k blocked edges is given. Nikolova and Karger (2008) studied another variant of the CTP where the cost of edges comes from independent and identical distributions. Bnaya et al. (2008) introduced the sensing cost in CTP which is closely related to our work. In the original CTP, the status of an edge (i.e., whether it is blocked or not) can only be revealed upon reaching a vertex incident to that edge. This kind of sensing is called the local sensing, and the remote sensing refers to revealing the status of an edge from a distant location (Bnaya et al., 2009). The sensing cost in the CTP is equivalent to the disambiguation cost in SOS problem. Bnaya et al. (2015) studied the repeatedtask CTP where a number of navigating agents need to travel with the same goal, minimizing their combined travel cost. Moreover, recently Aksakalli et al. (2016) developed an AO* based exact algorithm, called the CAO* algorithm, for the CTP and they showed that the empirical performance is better than other exact algorithms. 4 Chapter 1: Introduction 1.1 Preliminaries The most common notion of comparison of random variables is the stochastic order. For any real valued random variable X, let FX(x) = P(X x) be the cumulative distribution function of X. Definition 1.1.1 If X and Y are random variables defined on the same sample space , then X is stochastically smaller than Y (X st Y ) if FX(!) FY (!) for each ! 2 . Similar definition holds for ‘ st’. There are many equivalent definitions describing the stochastic ordering of random variables. The following is the most common way of characterizing the stochastic ordering. Definition 1.1.2 If X and Y are random variables defined on the same sample space , then X st Y () Ef(X) Ef(Y ) for all nondecreasing functions f. Where Ef(X) represents the expected value of f(X) with respect to the density function of random variable X. Analogous definition holds for ‘ st’. Definition 1.1.3 Let Xn be a sequence of random variables defined on a sample space . We say that Xn is convergent in probability to a random variable X defined on if and only if lim n!1 P(jXn Xj > ) = 0 for any > 0. X is called the probability limit of the sequence and the convergence in probability is denoted by Xn P ! X: Chapter 1: Introduction 5 1.2 Continuous SOS and OPD Problems The continuous SOS problem is formally defined as follows: Consider a bounded obstacle field R2. False obstacles (such as rocks, debris, fake mines) are assumed to be located at points, XC, from a spatial point process C. Then, an Obstacle Placing Agent (OPA) places true obstacles at the points, XO, where centers are from another spatial point process O, possibly different from C. All false obstacles (respectively true obstacles) are assumed to be disk shaped and centered at the points in XC (respectively XO). A Navigating Agent (NAVA) wishes to traverse from a given starting point, s 2 , to a target point, t 2 , and is equipped with a sensor that assigns random probabilities pC : XC ! [0; 1] and pO : XO ! [0; 1] prior to NAVA’s traversal. When observing a realization of these processes, the NAVA only sees X := XC [ XO as obstacles, some of which maybe true obstacles. Let p(x) be the probability that x 2 XO, that is, x is a true obstacle for all x 2 X. Then NAVA’s detector assigns p(x) = pO for x 2 XO and p(x) = pC for x 2 XC. For every disk center x, the obstacle disk Dx is an open region with a fixed radius r > 0. The NAVA seeks to traverse a continuous (s; t) curve without hitting any true obstacle at shortest achievable arc length (i.e., in shortest traversal length). We further suppose that there is a dynamic disambiguation capability. Specifically, for all x 2 X, when the traversal curve is on the boundary of the disk, denoted as @Dx, (i.e., NAVA comes right at the boundary of the obstacle), it has an option to disambiguate x, that is, to learn x 2 XO or not, but at a cost c > 0 added to the length of the traversal curve. The NAVA can pass through disks that have been disambiguated and found to be clutter (i.e., false obstacle), but has to avoid ambiguous disks as well as disks that have been disambiguated and found to be true obstacles. How the NAVA should route the continuous (s; t) traversal curve  and where and when the disambiguations should be performed  in order to minimize the expected length (including the disambiguation cost) of this curve is called the continuous SOS problem (Papadimitriou and Yannakakis, 1991). On the other hand, the problem of placing the obstacles so as to maximize the 6 Chapter 1: Introduction NAVA’s traversal length in the SOS problem, namely the optimal obstacle placement with disambiguations (OPD) problem was introduced by Aksakalli and Ceyhan (2012). Indeed, the OPD problem can be formulated as max XO E[L(XO [ XC)] such that XO \Wc = ;; jXOj = n; where L(X) is the traversal length of NAVA given a set of hindrance (obstacle or clutter) points of X and W is the window where obstacles are placed by the OPA. 1.3 Discretized SOS and OPD Problems For computational efficiency and convenience, we consider a discrete approximation of the continuous setting on the 8adjacency integer lattice as in Aksakalli et al. (2011). Specifically, this discretization is stored as a graph G whose vertices are all of the pairs of integers i; j such that 1 i imax and 1 j jmax where imax and jmax are given integers. The obstacle field is partitioned by an imax jmax grid consisting of unit squares and the vertices of the squares in the grid constitute the vertices of G. The edges of G are determined by the adjacency of the vertices in the grid. That is, there are edges between all pairs of the following four types of vertices: (1) (i; j) and (i+1; j) with unit length, (2) (i; j) and (i; j + 1) with unit length, (3) (i; j) and (i + 1; j + 1) with length p 2, and (4) (i + 1; j) and (i; j + 1) with length p 2 for i; j = 0; 1; : : : ; 99. Also, we add corner edges of unit length with pairs of vertices connecting (100; j) and (100; j + 1), and vertices connecting (i; 100) and (i + 1; 100) for i; j = 0; 1; : : : ; 99. This discretization is called the 8adjacency integer discretization of . One vertex in G is designated as the starting point, s, and another vertex in G is designated as the target point, t (starting and target points are totally arbitrary). The NAVA wishes to traverse from s to t in G, using only the edges that do not intersect any true obstacle or ambiguous disks in the environment. If an edge intersects any ambiguous disk, then a disambiguation of the disk may be performed from either endpoint of the edge that are outside of the disk. The goal is to devise an algorithm (to be implemented Chapter 1: Introduction 7 by NAVA) that minimizes its expected traversal length by effecient exploitation of the disambiguation capability and the information on the locations of the disks. We call this discretization as the discretized SOS problem (DSOSP), which in effect, is a special case of the Canadian traveler’s problem. 1.4 Organization of the Thesis The rest of this thesis is organized as follows: In Chapter 2 we discuss choosing the optimal obstacle pattern against a disambiguating navigating agent. In Chapter 3 we introduce M2k algorithm for the OPD problem and investigate the trends for mean traversal length by statistical analysis tools such as repeated measures ANOVA. In Chapter 4 we investigate how the traversal length depends on obstacle window types and tessellations. In Chapter 5 we consider heuristic algorithms for the OPD problem and provide a guidance for choosing the best performing algorithm given the problem setting. In Chapter 6 we present some theoretical results in the discrete SOS problem for some special graphs and present directions for future research. In Chapter 7 presents conclusions and discussion. Chapter 2 CHOOSING THE OPTIMAL OBSTACLE PATTERN AGAINST A DISAMBIGUATING NAVIGATION AGENT 2.1 Introduction In Aksakalli and Ceyhan (2012), NAVA uses the RD algorithm (Aksakalli et al., 2011) to find the shortest path and authors mainly focus on two problems. First, given a background clutter pattern, what would be the optimal number of obstacles and the obstacle pattern to use so as to maximize the NAVA’s total traversal length. Second, if OPA is given a certain number of obstacles, then what would be the optimal way to place these obstacles among the given clutter locations. OPA places the true obstacles uniformly inside various obstacle windows such as linear strips, Vshaped and Wshaped windows together with the possibly natural pattern scenarios of false obstacles with different pattern types such as uniform (homogeneous Poisson process), clustered (Thomas and Matérn) and regular (hardcore and Strauss point process) patterns (Baddeley et al., 2008). Aksakalli and Ceyhan (2012) provided same evidence that on the average the traversal length of NAVA increases as the level of regularity increases and decreases as the level of clustering increases. In overall comparison, the mean traversal length of NAVA attains its maximum value when the background clutter type is hardcore, and the obstacle form is Vshaped with 50 uniformly sampled obstacles. In this section, we investigate how traversal length depends on obstacle pattern changing from uniformness to regularity and from uniformness to clustering in a more detailed fashion. For regularity, the effects of two parameters, the pairwise distance between disk shaped obstacles and the number of such obstacles (i.e., its Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent 9 density) are investigated. As for clustering, the effects of the radius in which obstacles accumulate around one or more cluster centers and the number of such cluster centers are investigated. In Aksakalli and Ceyhan (2012) a few clutter types were considered, but here we address more types of obstacle patterns and also study the case where OPA can insert both false and true obstacles. 2.2 Experimental Setting For simplicity, we take the study window (i.e., the navigation environment) to be = [0; 100] [0; 100] and we insert a grid of unit squares on the study window, so that we partition the window with 104 such squares. In each square we also insert the diagonal line segments connecting nonadjacent vertices. We represent this square grid partition (together with diagonals) as a graph G = (V;E) such that V is comprised of vertices of the squares in the grid and edges are the edges of the squares together with diagonals. Hence, we have edges between all pairs of the following four types of vertices : (1) (i; j) and (i + 1; j) with unit length, (2) (i; j) and (i; j + 1) with unit length, (3) (i; j) and (i + 1; j + 1) with length p 2, and (4) (i + 1; j) and (i; j + 1) with length p 2 for i; j = 0; 1; : : : ; 99. Also, we add corner edges of unit length with pairs of vertices connecting (100; j) and (100; j + 1), and vertices connecting (i; 100) and (i + 1; 100) for i; j = 0; 1; : : : ; 99. This discretization is called the 8adjacency integer discretization of . Without loss of generality, we take a starting point s on the upper boundary of the study window, say s = (50; 100). And, for the target we take a point on the opposite side of rectangular window, say t = (50; 1). In practice, we can think of as a section of sea near the coast which is going to be defended by OPA, where NAVA could be a ship trying to navigate over the sea to reach the target at the coast. Here, OPA inserts disk shaped obstacles whose centers are generated from a random point process. In this version, OPA determines only the distribution of the obstacles, but not their exact locations. Each disk is either traversable (i.e., false or clutter obstacle) or nontraversable (i.e., true obstacle) with their respective proba 10 Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent bilities of being a true obstacle. In the OPD problem an obstacle is traversable if it is of clutter type and nontraversable if it is a true obstacle. The traversable (respectively, nontraversable) obstacles, i.e., clutter (respectively, true) obstacles, are denoted with a set of circles whose centers are the set of points denoted by XC (respectively, XO). NAVA wishes to traverse from the given starting point s to the target point t inserted with a sensor assigning (random) probabilities pc : XC ! [0; 1] and po : XO ! [0; 1] prior to its traversal. That is, the sensor assigns the status of disks with the probability function f(x), f(x) = 8>>>>>< >>>>>: pc; x 2 XC po; x 2 XO 0; otherwise where pc and po are also random variables with density functions FC and FO, respectively. The sensor would (preferably) attach high probabilities for true obstacles compared to clutter. NAVA knows the exact locations of X = XC [ XO, but not the actual status of disks, i.e., whether a disk is traversable or not, but only have a probability which is suggestive of the actual status of the disks. Also suppose that when the NAVA is located on the boundary of a disk, it disambiguates a disk at a cost c > 0 added to the traversal length; i.e., NAVA can learn the actual status of the disk with the specific cost c. NAVA disambiguates the obstacle and if the obstacle is of clutter type, NAVA is able to traverse through it and can not traverse otherwise. Each disk has a fixed radius of r = 4:5 units and the disk centers are sampled inside [10; 90] [10; 90] ensuring that there always exists a (possibly very long ) s; t walk. The existence of such a long traversable path is based on the assumption that NAVA must reach the target, but in an untimely manner (i.e., traversal length being larger than a threshold) and for larger traversal times/lengths NAVA’s arrival at the target (is assumed to) pose no threat to defending entities (including OPA). That is, NAVA’s arrival on time to the target could make a difference for the state of affairs and if arrival is sufficiently late, then we assume it is irrelevant from OPA’s perspective. The disambiguation cost of a disk is taken to be c = 5, and in each part clutter proba Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent 11 bilities pc are from Beta(2; 6) distribution, whereas true obstacle probabilities po are from Beta(6; 2) distribution. From NAVA’s perspective, small probabilities indicate that it is more likely to be traversable, whereas high probabilities show that it is less likely to be traversable. The means of random variables sampled from Beta(2; 6) and Beta(6; 2) are 0:25 and 0:75, respectively, which resonates with the idea that the sensor assigning high probabilities to true obstacles. So, it is reasonable to work with these skewed distributions for sensor’s capability of obstacle detection. These choices (of the cost c and sensor probability distributions) are made in line with those of Aksakalli and Ceyhan (2012) and Priebe et al. (2005). However, if one wants to increase the sensor’s sensitivity, one might pick Beta( ; ) with < 2; > 6 for false obstacles and Beta( ; ) with > 6; < 2 for true obstacles. 2.3 Obstacle Pattern Ranging from Uniformness to Regularity In the OPD problem, we investigate how the traversal length varies as the obstacle pattern changes. First, we equip the whole window with only false or only true obstacles whose pattern changes from uniformness to regularity. We denote the number of clutter (false obstacles) by nc and the number of true obstacles by no. We compute the traversal lengths for nc = 25; 50; 75; 100 and no = 25; 50; 75; 100. For inserting obstacles conforming to regularity, the points that constitute the centers of disk shaped obstacles are chosen from the Strauss process (Baddeley et al., 2008), denoted as Strauss(n; d; ), where n stands for the number of points, is the intensity of the number of pairs of distinct points lying closer than d units; i.e., the parameter controls ‘strength’ of interaction between points. For any fixed value of d, if = 1 the density reduces to a uniform point process (i.e., the pattern becomes uniformness), and if = 0 the density is a hard core process (i.e., completely regular pattern). For values 0 < < 1, the process exhibits negative association (i.e., inhibition) between points. Thus, in our simulations we choose the values from 0 to 1 with an increment size of 0:1 units and we also consider various values of d varying from 0:5 to 11 with an increment size of 0:5 units. Moreover, the whole window is inserted with both 12 Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent false and true obstacles together where the whole pattern changes from uniformness to regularity for nc = 25; 50; 75 and no = 25; 50; 75 such that nc + no = 50; 75; 100. In our data set , d and the number of obstacles (hence implicitly obstacle density) are the main factors that influence the traversal length. In Aksakalli and Ceyhan (2012), in the regularity pattern Strauss(nc; d; ), the number of clutter was fixed to be nc = 100, d was taken to be 5 and values were 0, 0.5, and 1. And, the number of true obstacles no was taken to be 20, 30, 40, 50, and 60. They observed that the NAVA tends to have higher traversal lengths for smaller values. In the current study, we want to address how the traversal length changes when both d and change under regularity by considering various values of d and simultaneously. Based on our Monte Carlo simulations, on the average the traversal lengths tend to increase as the obstacle pattern changes from uniformness to regularity. 2.3.1 Clutter Only Case In this section, we consider the case of only clutter type obstacles being inserted into the study window where obstacle pattern ranges from uniformness to regularity. Since 0 20 40 60 80 100 0 20 40 60 80 100 s t Figure 2.1: A realization of clutter disks (dashed circles) with nc = 40 from the Strauss(nc = 40; d = 9; = 0) process. Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent 13 there are 11 different values of , 22 different values of d and together with 100 Monte Carlo replication for each clutter number level nc, we have 11 22 100 = 24200 measurements. For each realization, the traversal length is computed by using RD algorithm described in Aksakalli et al. (2011). An example for the realization of this setting is given in Figure 2.1. We investigate the trends in the mean traversal length of NAVA as a function of the level of regularity of clutter points. First, we only consider the influence of values (ignore d values) on the traversal length for each clutter number level. We model the traversal length in this scenario as follows, Yij = j + jXij + ij (2.1) where i = 1; 2; :::; 24200 and j = 1; 2; 3; 4; Yij (i.e., the dependent variable) is the ith traversal length of NAVA at jth clutter level, j is the mean for clutter number level j, j is the rate of change in mean traversal length in clutter number level j, Xij (continuous covariate) is the corresponding gamma value of ith observation at jth categorical group, and ij is the associated error term. Since nc takes a few values, CSR 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 Regular . 100 105 110 115 120 125 130 mean traversal length n c =25 n c =50 n c =75 n c =100 overall Figure 2.2: Mean traversal length versus values for groups nc = 25; 50; 75; 100 together with overall plot (i.e., the average of all groups combined). we take the number of clutter levels as a categorical variable rather than a numerical 14 Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent variable. Recall that for any fixed d, when = 1 the point pattern is uniform and when = 0 the point pattern becomes completely regular. In Figure 2.2, we provide interaction plots for different clutter number levels versus values and also overall plot of the average of all groups versus values. In Figure 2.2, when the point pattern changes from uniformness to regularity the average traversal lengths seem to remain unchanged or increase slightly for all clutter number levels. We record the intercept and slope values of regression lines for each clutter number level nc (see Table 2.1). So, using ANCOVA (Seltman, 2012) with model given in Equation (2.1), we find nc = 25 nc = 50 nc = 75 nc = 100 intercept 103.84 108.36 113.79 119.96 slope 0 0.03 0.12 0.26 Table 2.1: Intercept and slope values of regression lines for each categorical group nc. out that there is a significant interaction between clutter number levels and values (pvalue<0.001). Hence, not all j’s are equal, i.e., the lines in Figure 2.2 are not all parallel to each other although the lines in the plot suggest otherwise. The next intercept nc = 50 nc = 75 nc = 100 nc = 25 <0.001 <0.001 <0.001 nc = 50 <0.001 <0.001 nc = 75 <0.001 (a) slope nc = 50 nc = 75 nc = 100 nc = 25 0.003 <0.001 <0.001 nc = 50 <0.001 <0.001 nc = 75 <0.001 (b) Table 2.2: Significant level of differences (pvalues) in intercept (a) and slope (b) for each pair of groups. natural question would be which clutter number levels have significantly different Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent 15 trends than other(s). To explain this, we repeat the model in Equation (2.1) for each pair of groups to get the pairwise significance level of differences in intercept and slope (see Table 2.2). From Table 2.2 it follows that both intercepts and slopes for clutter number levels 25, 50, 75 and 100 are significantly different from each other. Thus, the lines in Figure 2.2 have significantly different slopes except for nc = 25; 50. So far, we have not taken into consideration the influence of the d values. Figure 2.3 shows the plots of the average traversal length versus d values. Observe that the 0 2 4 6 8 10 d 100 105 110 115 120 125 130 mean traversal length n c =25 n c =50 n c =75 n c =100 overall Figure 2.3: Mean traversal length versus d values for groups nc = 25; 50; 75; 100 with overall plot (i.e., the average of all groups combined). change in d values influences the traversal lengths considerably for larger nc values. The Figure 2.3 also suggest choosing nc 75 and d 6 for larger traversal length. We fit the data set into the best quadratic polynomial because the curves in Figure 2.3 suggest that there is a concave down trend at least for nc = 75 and 100. In Figure 2.4, we provide graphs separately for each clutter number level and show corresponding fitted quadratic polynomial. Clearly, the concave down trend gets more emphasized as the number of clutter increases. Also, for any fixed value of and when d ranges from 0 to 8 the obstacle pattern gets more regular and hence yields higher traversal length. But, when d is larger than 9 units the average traversal length decreases sharply because the obstacle pattern leaves obstaclefree spaces in the region through 16 Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent which NAVA can quickly traverse without encountering any obstacle. These specific 0 2 4 6 8 10 12 d 103.4 103.5 103.6 103.7 103.8 103.9 104 104.1 mean traversal length n c =25 smoothingspline quadratic fit (a) 0 2 4 6 8 10 12 d 107.2 107.4 107.6 107.8 108 108.2 108.4 108.6 108.8 109 109.2 mean traversal length n c =50 smoothingspline quadratic fit (b) 0 2 4 6 8 10 12 d 111 112 113 114 115 116 117 mean traversal length n c =75 smoothingspline quadratic fit (c) 0 2 4 6 8 10 12 d 115 116 117 118 119 120 121 122 123 124 125 mean traversal length n c =100 smoothingspline quadratic fit (d) Figure 2.4: Mean traversal length versus d values for nc = 25; 50; 75; 100 together with quadratic polynomial fit and (nonparametric) smoothing spline with smoothing parameter p = 0:9863 . Notice that vertical axes are differently scaled. threshold values of d are closely related to the radius of disk shaped obstacle (i.e., r = 4:5 units). When d = 9, recalling that r = 4:5, the diskshaped obstacles become tangent to each other. Thus, for values of d larger than 9 the obstacles are no longer tangent and, so distances between obstacles increase resulting in a shorter path. Regarding the plots in Figure 2.4, we consider the following model for the traversal Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent 17 coefficients n groups nc = 25 nc = 50 nc = 75 nc = 100 overall 103.73 108.73 112.75 117.95 110.65 0.12 0.39 1.20 2.20 0.98 0.01 0.04 0.12 0.21 0.10 Table 2.3: Coefficients of quadratic polynomial fitted to the data at each clutter number level. intercept nc = 50 nc = 75 nc = 100 nc = 25 <0.001 <0.001 <0.001 nc = 50 <0.001 <0.001 nc = 75 <0.001 (a) linear term nc = 50 nc = 75 nc = 100 nc = 25 0.17 <0.001 <0.001 nc = 50 <0.001 <0.001 nc = 75 <0.001 (b) quadratic term nc = 50 nc = 75 nc = 100 nc = 25 0.07 <0.001 <0.001 nc = 50 <0.001 <0.001 nc = 75 <0.001 (c) Table 2.4: Significant level of differences (pvalues) of coefficient c (intercept) (a), coefficient b (linear term) (b), and coefficient a (quadratic term) (c) at each pair of clutter level. length of NAVA, Yij = j + jXij + jX2 ij + ij (2.2) where i = 1; 2; : : : ; 24200 and j = 1; 2; 3; 4 standing for nc = 25; 50; 75; 100, respec 18 Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent tively; Yij is the ith traversal length of NAVA at jth group, Xij is the value of d at ith treatment within jth group, and ij is an error term. The index j denotes the group membership (i.e., clutter level). The coefficient estimates in Model (2.2) are presented in Table 2.3. Table 2.4 suggests that the intercept values of all fitted polynomials in Figure 2.4 are statistically different from each other. The linear and quadratic trends for mean traversal length of clutter levels 25 and 50 are quite similar (see Table 2.4(b) and Table 2.4(c)), whereas the other pairs significantly different. nc = 25 1 2 3 4 5 6 7 8 9 10 11 d 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 . 103 103.2 103.4 103.6 103.8 104 104.2 104.4 104.6 (a) nc = 50 1 2 3 4 5 6 7 8 9 10 11 d 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 . 106.5 107 107.5 108 108.5 109 109.5 110 110.5 (b) nc = 75 1 2 3 4 5 6 7 8 9 10 11 d 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 . 110 111 112 113 114 115 116 117 118 119 120 (c) nc = 100 1 2 3 4 5 6 7 8 9 10 11 d 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 . 115 120 125 130 (d) Figure 2.5: Contour plots of mean traversal length versus and d values for nc = 25; 50; 75; 100. Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent 19 We also consider the contour plot of the mean traversal lengths where the impacts of both the and d values can be seen simultaneously (see Figure 2.5). The traversal lengths are within a small range, especially for nc = 25; 50 (see Figures 2.5(ab)). However, for nc = 75; 100, there is much wider range for traversal length and also a trend can be observed in these cases (see Figures 2.5(cd)). Empirically the mean traversal length is maximized when is less than 0.1 and when d is around 7 (from 6 to 8). On the average, for moderate values of d and the smaller values of we obtain longer traversal lengths. Also observe that for large values of d, values have almost no influence on the traversal length. In summary, if the whole window is going to be inserted only with the false obstacles with capability of varying the parameters of regularity (i.e., d and values), then on the average, traversal lengths tend to increase as the clutter pattern changes from uniformness to regularity. The values (esp. 0.11.0) have only mild influence on the traversal length, while d (that is especially large for d values between 68) has a substantial influence. Considering them together, from OPA’s perspective we recommend choosing moderate values of d (within 6 to 8) and smaller values ( < 0:1) in this setting so as to maximize the total traversal length of NAVA. We also observe that the value d is closely related with the radius r of diskshaped obstacle. From OPA’s perspective the case d > 2r is not desirable since for d > 2r obstacles become too sparse in the environment, whereas the optimal value of d takes place when the ratio d=r is within the interval (1:33; 1:77) together with = 0. 2.3.2 True Obstacles Only Case The simulation setting is as in the false obstacle only case in Section 2.3.1, with nc being replaced by no. We repeat the same analysis done in Section 2.3.1, but emphasize on the main differences here. For the same levels of number of obstacles, and d values, the mean traversal lengths with the true obstacles tend to be longer compared to the false obstacles. Using the model as in the Equation (2.1), we observe that on the average the traversal length tends to increase as the true obstacle pattern 20 Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent changes from uniformness to regularity provided that d < 2r. The trends in traversal length as increases is similar to the clutter only case (Figure 2.2), and the slopes and intercept estimates (Table 2.5) are significantly different from each other (Tables 2.6). no = 25 no = 50 no = 75 no = 100 intercept 104.06 111.78 137.63 204.21 slope 0 0.03 2.06 0.93 Table 2.5: Intercept and slope values of regression lines for each categorical group no. intercept no = 50 no = 75 no = 100 no = 25 <0.001 <0.001 <0.001 no = 50 <0.001 <0.001 no = 75 <0.001 (a) slope no = 50 no = 75 no = 100 no = 25 0.812 <0.001 <0.001 no = 50 <0.001 <0.001 no = 75 <0.001 (b) Table 2.6: Significant level of differences (pvalues) in intercept (a) and slope (b) for each pair of groups. When no equals 25 or 50, there still remains some obstaclefree spaces in the environment where NAVA can traverse even without any disambiguation. So, the values have almost no effect on the traversal length. When no = 75, the small values of becomes more important. When obstacles are distributed more regularly, NAVA starts to take risks (due to the greedy nature of the RD algorithm) rather than circumnavigate the zero risk route. When no = 100, then the value again loses its importance because we already have 100 obstacles which saturates the area regardless of values. The mean traversal lengths versus d values are presented in Figure 2.6. Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent 21 Note that the trends are concave down and similar to the clutter only case (see Figure 2.3). By using a model as in Equation (2.2) we observe that fitted polynomials for 0 2 4 6 8 10 d 100 120 140 160 180 200 240 260 100 mean traversal length n c =25 n c =50 n c =75 n c =100 overall Figure 2.6: Mean traversal length versus values for groups no = 25; 50; 75; 100 together with overall plot (i.e., the average of all groups combined). true obstacle levels 25 and 50 are similar (hence have similar trends), but the others are significantly different from each other. We also present the contour plot of the mean traversal lengths versus and d values in Figure 2.7 for no = 75; 100 only since for no = 25; 50 traversal length weakly depends on d and values (hence are omitted). But, when no = 75 mean traversal length is maximized for d values around 7 together with = 0. As for obstacle number level no = 100, mean traversal length tends to have higher value for values between 0.1 and 0.4, and for d values from 6 to 8. In summary, if the whole window is to be inserted only with true obstacles with capability of varying the regularity parameters (i.e., d and values), then on the average traversal length tends to increase as true obstacle pattern changes from uniformness to regularity. From OPA’s perspective, considering and d values together, we recommend choosing moderate values of d (around 6 to 8) and smaller values (especially, 0.1< < 0:4). 22 Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent no = 75 1 2 3 4 5 6 7 8 9 10 11 d 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 . 120 140 160 180 200 220 240 (a) no = 100 1 2 3 4 5 6 7 8 9 10 11 d 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 . 120 140 160 180 200 220 240 260 280 (b) Figure 2.7: Contour plots of mean traversal length versus and d values for no = 75; 100. 2.3.3 True and False Obstacles Together In this section we consider the setting in which OPA has the capability of inserting both true and false obstacles simultaneously. The obstacle pattern changes from uniformness to regularity for nc = 25; 50; 75 and no = 25; 50; 75 such that nc + no = 50; 75; 100. An example for the realization of this setting is given in Figure 2.8. From our simulations (see Sections 2.3.1 and 2.3.2), we observe that true obstacles make the traversal length much longer compared to false obstacles when the number of true and false obstacles are same. Hence, from OPA’s perspective it is more desirable to insert true obstacles rather than false obstacles (assuming OPA has sufficient amount of both true and false obstacles). For the sake of simplicity, we only present the case where nc = 25 and no = 25; 50; 75 such that nc + no = 50; 75; 100. The trend for traversal length versus values for no = 25; 50; 75 with fixed nc = 25 false obstacles is similar to the one in Figure 2.2. When the whole pattern is uniform (i.e., = 1) the average traversal lengths are smaller and when the pattern is completely regular (i.e., = 0) the average traversal lengths are larger. Based on our analysis, we Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent 23 0 20 40 60 80 100 0 20 40 60 80 100 s t Figure 2.8: The pattern is from the Strauss(nc +no = 50; d = 9; = 0) process where dashed circles (nc = 25 with centers in XC) are the 25 false obstacles and solid circles (no = 25 with centers in XO) are the 25 true obstacles. find no significant difference between the true obstacle number levels 25 and 50 (p value=0.190), but the trend for true obstacle number level 75 is totally different from the others. Regarding the influence of d, for obstacle number levels 25, 50, and 75 we still have a concave down trend similar to Figure 2.3 for mean traversal length as d values increase. The mean traversal length is maximized when d is from 5:5 to 6:5. We also present the contour plot of the mean traversal length versus and d values in Figure 2.9 for (nc; no) = (25; 50) and (nc; no) = (25; 75). In the case (nc; no) = (25; 25), traversal length seems to be not affected by d and values (hence not presented). Notice that on the average the traversal lengths tend to have larger values when values are less than 0:1 and when d values are from 6 to 8 units. For the cases when the number of false obstacles are fixed 50 and 75, we obtain very similar results as the case when the false obstacle number level is fixed to 25. Hence, the plots for nc = 50 with no = 25; 50; 75 and nc = 75 with no = 25; 50; 75 cases are not presented. 24 Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent 1 2 3 4 5 6 7 8 9 10 11 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 110 115 120 125 130 135 140 (a) 1 2 3 4 5 6 7 8 9 10 11 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 120 140 160 180 200 220 240 (b) Figure 2.9: Contour plots of the mean traversal length versus and d values when (a) (nc; no) = (25; 50), (b) (nc; no) = (25; 75). In summary, if the whole window is to be inserted with both false and true obstacles together where the overall pattern changes from uniformness to regularity, then on the average traversal lengths tend to increase. Based on our observation, in order to maximize NAVA’s traversal length, we suggest choosing small values (less than 0.1) and moderate d values (from 6 to 8) for OPA to insert obstacles in the environment. If feasible, we also recommend OPA insert more true obstacles than false obstacles, and mix them so as to trick NAVA to run into more true obstacles and hence do more disambiguations and replan its route to a longer path. 2.4 Obstacle Pattern Ranging from Uniformness to Clustering In this section, we consider the case that OPA inserts obstacles from patterns changing from uniformness to clustering. To investigate this scenario we use the Matérn clustering point process denoted Matérn( ; r0; ) wherein a given window, , first we uniformly generate ‘parent points’, and then for each parent point we generate ‘offspring points’, independently and uniformly distributed in a ball of radius r0 cen Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent 25 tered around the parent. In the Matérn( ; r0; ) process, is the intensity of ‘parent’ points from Poisson process, each parent has a Poisson( ) number of offsprings independently and uniformly distributed in a disc of radius r0 centered around the parent (Baddeley et al., 2008). Then parents are discarded from the region, and only offspring points are kept. Throughout this section the average number of points (i.e., offsprings ) per parent point is taken to be 10, and the radius of a ball (r0) around the parent varies from 5 to 50 with an increment size of 5 units. Notice that as the radius gets larger, the pattern gets closer to uniformness. In Aksakalli and Ceyhan (2012), the clustering pattern Matérn( ; r0; ), was employed with parameters = 10; r0 = 10, and = 10 so that on the average there are = 100 clutter points. And, the number of true obstacles no was taken to be 20, 30, 40, 50, and 60. They observed that NAVA tends to have lower traversal length for clustered point pattern. In the current study, we want to address how the traversal length changes when both (hence ) and r0 change under clustering by considering various values of and r0 simultaneously. We investigate three different cases. In line with Section 2.1, the whole window is inserted with clutter disks (i.e., false obstacles) only or true obstacles only, then the whole window is inserted with both true and false obstacles together (see Figure 2.10). The number of parent points is chosen to be 2, 4, 6 and 8 and for each parent there are on the average = 10 offsprings. We present the mean traversal length versus clustering radius for the false obstacle only and true obstacle only cases in Figure 2.11. If there are only false obstacles, then as the pattern changes from uniformness to clustering, the average traversal length decreases, especially for small values of cluster radius. For large values of cluster radius the trend is almost same as in the uniformness pattern. Similarly, if there are only true obstacles, as the pattern changes from uniformness to clustering, the average traversal length decreases as the clustering radius decreases; and the rate of decrease is remarkably sharp for smaller radius values. For the case when there are both false and true obstacles, we investigate the situations where the number of false 26 Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent 0 20 40 60 80 100 0 20 40 60 80 100 s t (a) 0 20 40 60 80 100 0 20 40 60 80 100 s t (b) Figure 2.10: (a) A realisation of clutter disks from the Matérn( = 2; r0 = 15; = 10) process shown in dashed circles. (b) The pattern is from the Matérn(8,15,10) process where dashed circles indicate the false obstacles (nc = 60) and solid circles indicate the true obstacles (no = 20). obstacles is fixed to nc = 20 and the number of true obstacles no takes values 20; 40, and 60. That is to say, we consider the pairs (nc; no) = (20; 20); (20; 40), and (20; 60). The trend is similar to the cases in Figure 2.11 (hence not presented). Based on our Monte Carlo simulation results, we observe that on the average traversal length tends to decrease for true obstacles, false obstacle and both as the clustering radius decreases and at a sharper rate for smaller radius values. When the pattern gets more clustered, obstacles accumulate around one or multiple points (i.e., cluster centers) and as a result it is more likely to have more empty spaces inside the window with a shorter length from s to t and this enables NAVA to attain a quick traversal with encountering few or no obstacles. Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent 27 CSR 50 45 40 35 30 25 20 15 10 Clust cluster radius (r0) 100 102 104 106 108 110 112 114 116 118 120 mean traversal length n c =20 n c =40 n c =60 n c =80 overall (a) CSR 50 45 40 35 30 25 20 15 10 Clust cluster cadius (r0) 100 110 120 130 140 150 160 170 mean traversal length n o =20 n o =40 n o =60 n o =80 overall (b) Figure 2.11: Mean traversal length versus cluster radius values when there are (a) only clutter disks with nc = 20; 40; 60; 80 together with overall plot (i.e., the average of all groups combined), (b) only true obstacles with no = 20; 40; 60; 80 together with overall plot (i.e., the average of all groups combined). Notice that vertical axes are differently scaled. 2.5 Stochastic Ordering of Traversal Lengths We next consider the stochastic ordering of traversal lengths under various obstacle patterns. Recall that NAVA is designed to traverse from source s to target t on an (s; t) walk, with each edge weighted by the Euclidean distance and the disambiguation cost of an obstacle. Given n (i.e., no+nc), let = no=nc be the ratio of true obstacles to false obstacles. Then, for any fixed value, suppose that there are m many distinct distances (avoiding loops) with ith distance occurring ki times. So, denote such an (s; t) path as ij , i = 1; 2; : : : ;m and j = 1; 2; : : : ; ki so that there are in total M = Pm i=1 ki many (s; t) paths on the usual integer grid. When there are no obstacles (n = 0) in the environment, let `ij be the corresponding Euclidean length for path ij and without loss of generality we can assume that `1j < `2j < : : : < `mj. Notice that for any fixed i, there are ki paths of equal length, i.e., `ij = `ij0 for any 28 Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent j; j0 = 1; 2; : : : ; ki. Now, let Lij be the traversal length for path ij in the presence of true or false obstacles. In the absence of obstacles (n = 0) we have the equality Lij = `ij for all i; j. When there are only false obstacles (n > 0 and = 0, i.e., no = 0), then we need to update the value of Lij by using the weight function defined by the RD algorithm. Recall that, when there are only clutter disks the set X = XC where XC is the set of points of centers of disk shaped obstacles Dr(x) (a disc of radius r centered at a point x) for x 2 XC with fixed radius r > 0. And, for x 2 X, p(x) is the probability that Dr(x) is a true obstacle with c(x) being the disambiguation cost of Dr(x). In our case, the disambiguation cost c(x) = c > 0 is fixed. If we ignore the probabilities, we have Lij = `ij + wij c with wij = X x2XC 1Dr(x)\ ij 6=; where wij gives the number of obstacles intersecting the edges of path ij . On the other hand, if we do consider the probabilities of disk shaped obstacle being true obstacle, then we update each edge of path ij . Namely, if e 2 ij then, w(e) = `(e) + 1 2 F(e) with F(e) = X x2XC 1fDr(x)\e6=;g c 1 p(x) So that Lij = P e2 ij w(e). Notice that in the updated version for any fixed i, Lij 6= Lij0 in general, because the number of obstacles intersecting the paths of same Euclidean length ij and ij0 may not be equal. If we consider all Lij values in the clutter only case in an array (1 by M) with M many entries so that L(k) is the kth smallest length, then RD algorithm choses L(k) over L(k0) for k < k0. Let LS ij and LU ij be the traversal lengths of path ij under regularity ( = 0) and uniformness ( = 1), respectively. Under regularity, the path ij is more likely to intersect an obstacle compared to uniformness. So, it is more likely that LU ij st LS ij , i.e., the traversal length is stochastically smaller under the uniformness compared to that under regularity. Indeed, one can extend the above argument to the case Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent 29 that at fixed d, let L ij denote the traversal length for Strauss(n; d; ) pattern. Then, L ij st L 0 ij whenever < 0. Similarly, Lr0 ij be the traversal length for Matérn( ; r0; ) pattern and let LM ij denote the traversal length of path ij under clustering (r0 0) for fixed ; . Then for r0 < r00 , Lr0 ij st Lr00 ij since under Matérn( ; r0; ) pattern any ij is less likely to hit an obstacle compared to that under Matérn( ; r00 ; ) whenever r0 < r00 . So, we have proved the following: Proposition 2.5.1 : Whenever X = XC (i:e:;OPA only inserts false obstacles to our standard window [0; 100] [0; 100]), we have (i) LM ij st LU ij st LS ij (defined as above). (ii) L ij st L 0 ij for < 0. (iii) Lr0 ij st Lr00 ij for r0 < r00 . In the true obstacle only case (n > 0 and = 1, i.e., nc = 0), if an obstacle intersects a path then it renders that path nontraversable. So, if a shorter path hits a true obstacle, RD resets the algorithm whenever NAVA hits the obstacle and then picks another longer path. That is to say, when we have true obstacles the total number of distinct traversable paths reduces compared to the clutter only case. Hence, traversal length in the true obstacle case tends to be larger compared to that in the false obstacle only case. Furthermore, by the same reason as above the same stochastic orderings occur under regularity, clustering and uniformness patterns. Proposition 2.5.2 : Whenever X = XO (i:e:;OPA only inserts true obstacles to our standard window [0; 100] [0; 100]), we have (i) LM ij st LU ij st LS ij (ii) L ij st L 0 ij for < 0. (iii) Lr0 ij st Lr00 ij for r0 < r00 . 30 Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent One can also write stochastic ordering for clutter only and true obstacle only cases as follows. Let LC ij be the traversal length of path ij under the clutter only case and LO ij be the traversal length of path ij under the true obstacle only case. Then with the same obstacle pattern of nc = n in the clutter only case and no = n in the true obstacle only case we have, Proposition 2.5.3 : With the same obstacle pattern and the same number of obstacles, LC ij st LO ij : This holds because if true obstacles were also clutter, then we would have LC ij d=LO ij . But, when NAVA runs into a true obstacle, then it has to stop and choose a longer traversable path while if the obstacle was false NAVA would traverse through it. Since the cost of disambiguation is same, we have a reduction in the number of traversable paths under true obstacle only case with LC ij values being more likely to be smaller than LO ij values. Let LC;O ij be the traversal length of path ij under the clutter & true obstacle cases. Corollary 2.5.3.1 : With the same obstacle pattern and the same number of obstacles, LC ij st LC;O ij st LO ij : The result also extends to the mixed obstacle case. One can also show that with everything else being same, and = no=nc and keeping the number of clutter equal, we have L ij st L 0 ij whenever < 0 (but, notice that this result does not extend if the number of clutter values are different). Indeed, this case can be generalized whenever total number of obstacles is fixed (we will be studied in detail in Section 2.6). Proposition 2.5.4 : Whenever X = XC [ XO, and nc is fixed, then for < 0 (i) LM ij st LU ij st LS ij Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent 31 (ii) L ij st L 0 ij for < 0. (iii) Lr0 ij st Lr00 ij for r0 < r00 . To conclude, at any path ij , the cost under regularity would tend to be higher compared to uniformness. The main reason for this is that under regularity, it is more likely for an obstacle to be placed on an edge on ij compared to uniformness, since under regularity obstacles will be more evenly distributed compared to uniformness. On the other hand, for any path ij the cost under clustering would tend to be lower compared to uniformness. Because, under clustering the obstacle is less likely to hit an edge on ij compared to uniformness. Since, under clustering obstacles will be accumulated around parents or hotspots and thus form clumps so that ij has more chance of not falling inside these clumps compared to uniformness. Thus, if the obstacle pattern is regular then the probability of maximizing the mean traversal length of NAVA is higher than any other cases. 2.6 Mean Traversal Length Versus Ratio of Number of True to False Obstacles So far we denote the number of clutter (false obstacles) by nc and the number of true obstacles by no, and n = nc +no and we compute the traversal lengths for each nc; no combinations. In this section, we investigate the trends for mean traversal length with respect to the ratio = no=nc when the sum no + nc is fixed. In our experimental setting the total number of obstacles to be inserted into the study window is equal to 100. So, the case no = 0 corresponds to deploying the study window only with clutter, and nc = 0 means inserting only true obstacles. To measure the traversal length for intermediate values of pairs of (no; nc), we introduce a new variable = no=nc taking the values f0; 1=4; 1=2; 1; 2; 4;1g. Thus, extreme cases of = 0 is equivalent to the case no = 0 and = 1 is equivalent to the case nc = 0. In the following subsections, we investigate the case where the obstacle pattern changes from the complete spatial uniformness (uniformness) to regularity. We 32 Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent use 11 11 partition of ( ; d) 2 (0; 1) (1; 11) (i.e., and d are parameters of Strauss(n; d; )), so our current investigation is much more detailed for compared to Aksakalli and Ceyhan (2012), and investigation for d is different from that in Aksakalli and Ceyhan (2012). We also investigate the case where the obstacle pattern changes from the uniformness to clustering. In our experimental setting, we choose the values f1; 2; 3; :::; 10; 11g and the radius r0 around the parent varies from 5 to 50 units with an increment size of 5 units (i.e., and r0 are parameters of Matérn( ; r0; )). As the radius gets larger, the pattern formed is getting closer to uniformness. In Aksakalli and Ceyhan (2012), the cluster radius r0 and the average offspring per parent were both taken to be 10. In our study, we increase the range of r0 and values. 2.6.1 Obstacle Pattern Ranging from Uniformness to Regularity Our goal is to determine the trend for the mean traversal length of NAVA as a function of the level of regularity. In our experimental setting, there are 11 different values of d (1; 2; :::; 10; 11), 11 different values of (0; 0:1; :::; 0:9; 1), 7 different values of (0, 1/4, 1/2, 1, 2, 4, inf), and 100 Monte Carlo simulations for each of these combinations. First, we only consider the influence of values, and then we will discuss the effect of d values. We model the traversal length as in Equation (2.1) where the categorical level will be . Since there are 7 categorical groups, for simplicity we split the corresponding interaction plots into two parts. In Figure 2.12(a) we show the interaction plot of mean traversal length versus values for groups = 0; 1=4; 1=2; 1 and the overall plot (i.e., the average of all 7 distinct groups). And, in Figure 2.12(b) we show the interaction plot of mean traversal length versus values for groups = 1; 2; 4;1 and the overall plot. We observe that the intercept values for = 1=4; 1=2 are not significantly different from = 0 (pvalues 0.4071, 0.0524, respectively). And, the slopes of regression lines for = 1=4; 1=2; 1 are not significantly different than the slope of group = 0 (p values 0.9817, 0.7207, 0.1984, respectively). Moreover, the slope values for all groups Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent 33 CSR 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 Regular . 120 125 130 135 140 145 150 155 160 mean traversal length ;=0 ;=1/4 ;=1/2 ;=1 overall (a) CSR 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 Regular . 120 130 140 150 160 170 180 190 200 210 220 230 mean traversal length ;=1 ;=2 ;=4 ;=Inf overall (b) Figure 2.12: Mean traversal length versus values for groups (a) = 0; 1=4; 1=2; 1 together with overall plot (the average of all 7 distinct groups), (b) = 1; 2; 4;1 together with overall plot (the average of all 7 distinct groups). Notice that vertical axes are differently scaled. are positive (Table 2.7), which means that the mean traversal length tends to increase as the gamma ( ) values decrease. In all groups, the average traversal length is maximized when = 0 (i.e., when the pattern is completely regular) and the mean traversal length tends to increase as gets larger (i.e., intercept value increases as increases). It is also interesting that the overall trend of mean traversal length is almost the same as the case = 2 (see Figure 2.12(b)). Moreover, in Figure 2.13 we show the plot of mean traversal length versus values for various choices of and the contour plot of mean traversal length versus and values. In Figure 2.13(a), the mean traversal length tends to be higher (and thus maximized) when = 0 for each values. And, in Figure 2.13(b) layers of color are formed for each different values of implying that the mean traversal length tends to be larger as value increases. For fixed value, the trend when = 0 is different from other values of showing that the traversal length is maximized when = 0. Figure 2.13(b) also summarizes the plots given in Figure 2.12. 34 Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent 0 1/4 1/2 1 2 4 Inf ; 120 140 160 180 200 220 mean traversal length .=0 .=0.4 .=0.6 .=1.0 (a) 0 1/4 1/2 1 2 4 Inf ; 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 . 120 130 140 150 160 170 180 190 200 210 (b) Figure 2.13: (a) Mean traversal length versus values for groups = 0; 0:4; 0:6; 1, (b) average contour plot of mean traversal length versus and values. = 0 = 1=4 = 1=2 = 1 = 2 = 4 = 1 intercept 119.50 120.69 122.29 126.73 137.52 154.55 201.07 slope 0.29 0.29 0.36 0.56 1.15 2.33 1.14 Table 2.7: Intercept and slope values of regression lines for each categorical group . We also record the intercept and slope values of regression lines for each categorical group (see Table 2.7). If we repeat the model as in Equation (2.1) for each pair of groups, then we will get the pairwise significance levels of differences in intercept and slope similar to Table 2.2. Thus, we have more information about how exactly each categorical group differs from one another. For instance, Table 2.7 and Figure 2.12 shows that although the intercepts are different for = 2 and = 1 groups, the trend for mean traversal length of NAVA is similar since their slopes (1:15 and 1:15, respectively) are not significantly different (pvalue=0:974). Next, we consider the effect of d values on mean traversal length of NAVA for different groups. Similar to Figure 2.3, we will fit the data set into the best quadratic Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent 35 1 2 3 4 5 6 7 8 9 10 11 d 115 120 125 130 135 140 145 150 155 160 165 mean traversal length ;=0 ;=1/4 ;=1/2 ;=1 overall (a) 1 2 3 4 5 6 7 8 9 10 11 d 120 140 160 180 200 220 240 260 mean traversal length ;=1 ;=2 ;=4 ;=Inf overall (b) Figure 2.14: Mean traversal length versus d values for groups (a) = 0; 1=4; 1=2; 1 together with overall plot (the average of all 7 distinct groups), (b) = 1; 2; 4;1 together with overall plot (the average of all 7 distinct groups). Notice that vertical axes are differently scaled. polynomial and record the corresponding coefficients because the curves in Figure 2.14 suggest a concave down trend. In Figure 2.14, we provide graphs separately for levels = 0; 1=4; 1=2; 1 and = 1; 2; 4;1 together with overall plot (the average of all 7 distinct groups) in order to observe the general trend. Clearly, mean traversal length gets higher, reaches a peak and then decreases as d values increase. And, concave down trend gets more emphasized as the increases. Moreover, in Figure 2.15 we show the plot of mean traversal length versus values for various choices of d and the contour plot of mean traversal length versus d and values. In Figure 2.15(a), the mean traversal length tends to be higher when d = 6 (and similarly between 5 and 8) for each values. Observe that when d gets smaller values (less than 3) or larger values (greater than 9), then the mean traversal length tends to be smaller than the case d is between 5 and 8. In Figure 2.15(b) layers of color are formed for each different values of implying that the mean traversal length tends to be larger as value increases. Figure 2.15(b) also summarizes the 36 Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent 0 1/4 1/2 1 2 4 Inf ; 100 150 200 250 mean traversal length d=1 d=4 d=6 d=10 (a) 0 1/4 1/2 1 2 4 Inf ; 1 2 3 4 5 6 7 8 9 10 11 d 120 140 160 180 200 220 (b) Figure 2.15: (a) Mean traversal length versus values for groups d = 1; 4; 6; 10, (b) average contour plot of mean traversal length versus d and values. plots (concave down trend) given in Figure 2.14. We also present the contour plot of the mean traversal lengths versus and d values in Figures 2.16 and 2.17. Notice that on the average the traversal length tends to have larger values when values are less than 0.1 and when d values are concentrated around 7 for levels = 0; 1=4; 1=2; 2. As the values increases, the contour plots get more emphasized and for = 1 level the mean traversal length is maximized when is less than 0.1 and d is around 5 and 7. In Figure 2.17, for = 4 the average traversal length is maximized when is less than 0.1 and d is around 5 and 8. Unlike previous cases, for = inf the mean traversal length tends to have higher values when is between 0.1 and 0.4 together with d values between 6 and 8. Based on the overall contour plot of levels (see Figure 2.17(d)), we observe that the NAVA tends to have higher mean traversal length for smaller values (i.e., smaller than 0.1) and moderate d values around 7. As a consequence, for fixed number of obstacles n = no+nc the ratio = no=nc is also important in maximizing the traversal length of NAVA. So, Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent 37 ; = 0 1 2 3 4 5 6 7 8 9 10 11 d 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 . 110 115 120 125 130 (a) ; = 1=4 1 2 3 4 5 6 7 8 9 10 11 d 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 . 110 115 120 125 130 135 (b) ; = 1=2 1 2 3 4 5 6 7 8 9 10 11 d 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 . 110 115 120 125 130 135 140 (c) ; = 1 1 2 3 4 5 6 7 8 9 10 11 d 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 . 110 120 130 140 150 160 (d) Figure 2.16: Overall average contour plots of the mean traversal length versus and d values for (a) = 0, (b) = 1=4, (c) = 1=2, and (d) = 1. Proposition 2.6.1 : Whenever X = XC [ XO, and n = nc + no is fixed, then L ij st L 0 ij for < 0. Thus, from OPA’s perspective considering and d values together, we recommend choosing moderate values of d (around 7) and smaller values (less than 0:1). And, given the total number of obstacles (n = nc + no is fixed), we recommend to choose value as large as possible so as to maximize the total traversal length of NAVA. 38 Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent ; = 2 1 2 3 4 5 6 7 8 9 10 11 d 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 . 120 130 140 150 160 170 180 190 200 210 220 (a) ; = 4 1 2 3 4 5 6 7 8 9 10 11 d 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 . 120 140 160 180 200 220 240 (b) ; = 1 1 2 3 4 5 6 7 8 9 10 11 d 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 . 120 140 160 180 200 220 240 260 (c) Overall (the average of all ; levels) 1 2 3 4 5 6 7 8 9 10 11 d 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 . 120 130 140 150 160 170 (d) Figure 2.17: Overall average contour plots of the mean traversal length versus and d values for (a) = 2, (b) = 4, (c) = 1, and (d) overall (the average of all levels). 2.6.2 Obstacle Pattern Ranging from Uniformness to Clustering In this Section, we investigate the trend for mean traversal length of NAVA as a function of the level of clustering. To generate the clustering point pattern we use Matérn( ; r0; ) as in Section 2.4. In our experimental setting, there are 11 different values of (i.e., 1; 2; : : : ; 11), 11 different values of cluster radius r0 (i.e., 5; 10; : : : ; 50), Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent 39 7 different values of (i.e., 0; 1=4; 1=2; 1; 2; 4;1), and 100 Monte Carlo simulations for each these combinations. Since the total number of obstacle is fixed to n = 100, so on the average the value automatically equals to n= . Ignoring , in Figure 2.18 we observe that the mean traversal length tends to decrease as the cluster radius r0 decreases for each level (concave down decrease trend). That is to say, the mean traversal length tends to decrease as the obstacle pattern changes from uniform to clustering. In all groups, the average mean traversal length is maximized when the obstacle pattern is uniform and minimized when the obstacle pattern is clustered. The trends is concave down, and as the value increases the decrease for mean traversal length gets more emphasized. CSR 50 45 40 35 30 25 20 15 10 Clust r0 100 105 110 115 120 125 130 135 140 145 150 mean traversal length ;=0 ;=1/4 ;=1/2 ;=1 overall (a) CSR 50 45 40 35 30 25 20 15 10 Clust r0 100 120 140 160 180 200 220 mean traversal length ;=1 ;=2 ;=4 ;=Inf overall (b) Figure 2.18: Mean traversal length versus r0 values for groups (a) = 0; 1=4; 1=2; 1 together with overall plot (the average of all 7 distinct groups), (b) = 1; 2; 4;1 together with overall plot (the average of all 7 distinct groups). Notice that vertical axes are differently scaled. Ignoring r0, in Figure 2.19 the mean traversal length tends to increase as the number of parent points increases for each level (concave down increase trend). But, the increase in trend slows down after = 5 because as the number of parent points increases the obstacles pattern gets less clustered. In both Figures 2.18 and 40 Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent 1 2 3 4 5 6 7 8 9 10 11 5 100 115 120 125 130 135 140 mean traversal length ;=0 ;=1/4 ;=1/2 ;=1 overall (a) 1 2 3 4 5 6 7 8 9 10 11 5 110 120 130 140 150 160 170 180 mean traversal length ;=1 ;=2 ;=4 ;=Inf overall (b) Figure 2.19: Mean traversal length versus values for groups (a) = 0; 1=4; 1=2; 1 together with overall plot (the average of all levels), (b) = 1; 2; 4;1 with overall plot (the average of all levels). Notice that vertical axes are differently scaled. 2.19, the overall plot is similar to the group level = 2. Moreover, in Figure 2.20 we show the plot of mean traversal length versus values for various choices of r0 and the contour plot of mean traversal length versus r0 and values. In Figure 2.20 (a), the mean traversal length tends to be higher when r0 = 50 (i.e., eventually CSR) for each values. In Figure 2.20 (b) layers of color are formed for each different values of implying that the mean traversal length tends to be larger as value increases. Figure 2.20 (b) also summarizes the plots (concave down trend) given in Figure 2.18. Similarly, in Figure 2.21 (a) as the number of parent points ( ) decreases (i.e., eventually clustering) the mean traversal length tends to be smaller for each value. And, in Figure 2.21 (b) the mean traversal length increases as the value increases. In summary, we observe that from uniformness to clustering, traversal length tends to decrease. Hence, clustering obstacle patterns are not preferable in OPA’s perspective. That is, OPA should avoid clustering obstacle patterns as much as possible and simply choose uniformness if uniformness and various clustering schemes Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent 41 0 1/4 1/2 1 2 4 Inf ; 100 120 140 160 180 200 220 mean traversal length r0=5 r0=15 r0=30 r0=50 (a) 0 1/4 1/2 1 2 4 Inf ; 5 10 15 20 25 30 35 40 45 50 CSR r0 110 120 130 140 150 160 170 180 190 200 (b) Figure 2.20: (a) Mean traversal length versus values for groups r0 = 5; 15; 30; 50, (b) average contour plot of mean traversal length versus r0 and values. 0 1/4 1/2 1 2 4 Inf ; 110 120 130 140 150 160 170 mean traversal length 5=1 5=3 5=6 5=10 (a) 0 1/4 1/2 1 2 4 Inf ; 1 2 3 4 5 6 7 8 9 10 11 5 115 120 125 130 135 140 145 150 155 160 165 (b) Figure 2.21: (a) Mean traversal length versus values for groups = 1; 3; 6; 10, (b) average contour plot of mean traversal length versus and values. are the only available options. So far, we have observed that the mean traversal length is maximized for moderate values of d (from 6 to 8) together with small values of (less than 0.1). We also observed that to maximize the traversal length of navigating 42 Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent agent (NAVA), obstacle placing agent (OPA) should insert more true obstacles than false obstacles. Under these circumstances, we can also decide in what proportion of true obstacles to false obstacles should be used so as to maximize the traversal length of NAVA. We plot the mean traversal length versus no and nc values for pairs (d; ) = (6; 0), (d; ) = (7; 0), and (d; ) = (8; 0). In Figure 2.22, we see that on the average the mean traversal length is maximized when no is around 80 together with nc less than 20. Mean Traversal Length 10 20 30 40 50 60 70 80 90 100 nc 10 20 30 40 50 60 70 80 90 100 no 120 140 160 180 200 220 240 (a) Mean Traversal Length 10 20 30 40 50 60 70 80 90 100 nc 10 20 30 40 50 60 70 80 90 100 no 120 140 160 180 200 220 240 (b) Mean Traversal Length 10 20 30 40 50 60 70 80 90 100 nc 10 20 30 40 50 60 70 80 90 100 no 120 140 160 180 200 220 240 260 (c) Figure 2.22: Overall average contour plots of the mean traversal length versus no and nc values when (a) (d; ) = (6; 0), (b) (d; ) = (7; 0), and (c) (d; ) = (8; 0). Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent 43 2.7 Summary We investigate how the traversal length of NAVA changes as the obstacle pattern changes from uniformness to regularity, and from uniformness to clustering for various pairs of numbers of clutter and true obstacles nc; no. In our experimental setting, we simulated various combinations of both false and true obstacle number levels. Based on our investigation with extensive Monte Carlo simulations, we found that traversal lengths are higher under regularity than those under uniformness which tend to be higher that those under clustering. Under regularity, we investigate the influence of the two parameters d and . Given the number of obstacles, the is the intensity of the number of pairs of distinct points lying closer than d units. In all cases, clutter only, true obstacle only and mixture of false and true obstacle, we recommend choosing moderate values of d (around 7) together with small values of (between 0 and 0:1). Moreover, given the total number of obstacles, the ratio of true versus false obstacles is another important factor for the traversal length. Taking all of these into consideration, to achieve optimal value we recommend choosing moderate values of d (around 7) and smaller values (less than 0:1). And, given the total number of obstacles (i.e., n = nc + no is fixed), we also recommend choosing value as large as possible in order to maximize the total traversal length of NAVA. Under clustering obstacle pattern, the cluster radius r0 and the number of parent points are found to be important. Here, the stands for the number of accumulation points and r0 stands for the radius at which obstacles accumulate around the accumulation point. We do not recommend choosing clustering point pattern since it is not feasible. The number of true obstacles clearly dominates the number of false obstacles, again the parameter plays an important role in determining the trend of traversal length when the total number of given obstacles is fixed. Hence, all things considered for optimal values we do not recommend using the clustering obstacle pattern in order to maximize the total traversal length of NAVA. When the obstacle pattern and the number of obstacles kept same, then the traver 44 Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent sal length under cluttering pattern is stochastically less than or equal to the traversal length under uniformness, and which is also stochastically less than or equal to the traversal length under regularity. Thus, mean traversal length is maximized then the obstacle pattern is regular. Moreover, the traversal length in clutter only case is stochastically less than or equal to the traversal length in mixture case which is also stochastically less than or equal to the traversal length in true obstacle case only. Concerning the precision of sensor, as the sensor of NAVA increases the traversal length tends to be the more accurate and yields closer value to optimal solution. In our future research, we are going to investigate the case where OPA places both true and false obstacles deterministically. We want to investigate whether knowing the exact locations of obstacles gains an advantage for OPA or not. Besides, concerning the theoretical results OPD has many similarities with classical CTP problem. We will prove our results for more general graphical settings by inspiring from current theoretical results belonging to CTP problem. In OPD problem only disambiguation capability was considered, but we also like to consider the problem with neutralization capability. Under feasible conditions, we will study the OPD problem by both disambiguation and neutralization capabilities together depending on the circumstances that NAVA and OPA encounters. Another aspect of OPD problem is considering the study window in a 3dimensional setting. That is to say, we would like to investigate the OPD problem in higher dimension as well starting from three dimensional case. In 3D case, NAVA may represent the submarine that wishes to reach from one source point to a target destination avoiding underwater mines. And, OPA may be the opponent forces wishing to place mines so as to maximize the total traversal length of NAVA. Chapter 3 M2K ALGORITHM FOR THE OPD PROBLEM 3.1 Introduction In this section, we investigate how traversal length behaves for various M2k algorithms. We will use the same experimental setup of Aksakalli and Ceyhan (2012), but compute the traversal length by M2k algorithm for various integer values of k. Based on our Monte Carlo simulations, we observe that the trends for mean traversal length computed by RD algorithm and M2k algorithm are essentially similar. So, instead using the greedy algorithm we recommend using M2k algorithm where few disambiguations take place, and hence decrease the complexity cost compared to the original RD algorithm. 3.2 Experimental Setting 3.2.1 Background Clutter Generation In our simulation setting, we use 6 different types of point processes for sampling centers of diskshaped clutters. These are homogeneous (HPP) and inhomogeneous (IP) Poisson processes, Matérn and Thomas point processes, and Hardcore and Strauss point processes. Among these Matérn and Thomas processes are clustered point processes, while Hardcore and Strauss processes are regular point processes (Baddeley, 2010). The number of clutter is fixed to 100, and the number of obstacles are 20,30,40,50 and 60 respectively. As for obstacle window forms, we use a total of 19 different obstacle placement patterns. Obstacles are uniformly sampled within four different window forms: the entire background window itself (P), linear strips (L), Vshaped (V) and Wshaped (W) polygonal windows. 46 Chapter 3: M2k Algorithm for the OPD Problem Formally, a spatial point process X is a finite random subset of a bounded region R2. A realization of this point process, on the other hand, is called a spatial point pattern. Mainly there are three types of spatial point patterns; independent patterns, cluster patterns where points tend to be close to one another and regular patterns where points tend to repel each other. In this section, we consider two patterns from each one of these three groups and the background clutter disk centers are generated from those six spatial point processes (Aksakalli and Ceyhan (2012)). The homogeneous Poisson process with constant intensity is also called complete spatial randomness (CSR), where the intensity will be denoted by CSR( ). For any region , the CSR point process has four properties: (1) the number of points in is a Poisson random variable, (2) number of points in any two disjoint regions and 0 are independent random variables, (3) the expected number of points in is area( ), and (4) points in are independently and uniformly distributed (given the number of points). In our case, is taken to be 100. As for the inhomogeneous Poisson process, it is a modification of CSR where the intensity is not constant, but varies from location to location. Specifically, the intensity is a function in two dimensional Euclidean space. Let IP( (h)) denote the inhomogeneous Poisson process with intensity (h) where h 2 R2. Here, the intensity function (h) specifies the value of on the plane. Properties of IP( (h)) are the same as those of CSR( ) with the last two properties modified as follows: (30) the expected number of points in is R (h)dh, and (40) points in are independently identically distributed (i.i.d) with probability density f(h) = (h) R (h)dh 1. In our case, we take the intensity function as (x; y) = 0:037e(10y)=40 as in Aksakalli and Ceyhan (2012). Notice that, the intensity only depends on y and decreases as y increases. Here, obstacles get denser as one gets closer to a target point. An illustration of both CSR and IP is shown in Figure 3.1. For clustering, the Matérn point process, denoted by M( ; ; ), is constructed by first generating a Poisson point process of “parent” points with intensity . Each parent point is then replaced by a random cluster of points where the number of points in each cluster is sampled from a Poisson distribution with parameter . These so Chapter 3: M2k Algorithm for the OPD Problem 47 l l l l l l l l l l l l l l l l l l l l ll l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l (a) CSR l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l (b) Inhomogeneous Poisson Figure 3.1: Sample realizations from homogeneous and inhomogeneous point processes. The parameters are: (a) CSR(100) and (b) IP 0:037e(10y)=40 . Indeed, on the average 100 points are generated by using these distribution parameters, but by using the rejection sampling we fix them to exactly 100 points. called “child” points are placed independently and uniformly inside a disk with fixed radius r centered at the parent point. In our case, we work with M(10; 10; 10). Similar to the Matérn point process, the Thomas process, denoted by T( ; ; ), is constructed by first generating a Poisson point process of “parent” points with intensity . A random cluster of points replaces each parent point with the number of points per cluster being sampled from a Poisson distribution with parameter . In contrast with the Matérn point process, positions of these child points in the Thomas point process are isotropic Gaussian displacements centered at the cluster parent location with standard deviation . In our case, we work with T(10; 10; 5) as in Aksakalli and Ceyhan (2012). An illustration of both Matérn and Thomas is shown in Figure 3.2. For regular, the probability density function of the hardcore process is that of the Poisson process with intensity function conditioned on the event that no two points generated by the process are closer than d units apart, hence denoted by 48 Chapter 3: M2k Algorithm for the OPD Problem l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l ll l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l (a) Matérn l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l (b) Thomas Figure 3.2: Sample realizations from Matérn and Thomas point processes. The parameters are: (a) M(10; 10; 10) and (b) T(10; 10; 5). Indeed, on the average 100 points are generated by using these distribution parameters, but by using the rejection sampling we fix them to exactly 100 points. HC( ; d). The Strauss process, denoted S( ; d; ), on the other hand, generalizes the hardcore process by incorporating a 2 [0; 1] parameter that controls of the interaction between points. The process exhibits more regularity for smaller values of , and less regularity for large . For = 0, the Strauss process becomes hardcore process, and for = 1, it reduces to CSR. In our case, we work with HC(100; 5) and S(100; 5; 0:5) as in Aksakalli and Ceyhan (2012). An illustration of both Hardcore and Strauss is shown in Figure 3.3. In our computational experiment (see Section 2.2), the graph G = (V;E) is the 8 adjacency integer discretization of [0; 100] [0; 100] with s = (50; 100) and t = (50; 1). Each disk has a fixed radius of r = 4:5 units and the disk centers are sampled inside [10; 90] [10; 90] ensuring that there always exists(possibly very long) a s; t walk. The disambiguation cost is taken to be c = 5. And, clutter probabilities are sampled from Beta(2,6), whereas obstacle probabilities are sampled from Beta(6,2). These choices Chapter 3: M2k Algorithm for the OPD Problem 49 l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l (a) Hardcore l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l (b) Strauss Figure 3.3: Sample realizations from Hardcore and Strauss point processes. The parameters are: (a) HC(100; 5) and (b) S(100; 5; 0:5). Indeed, on the average 100 points are generated by using these distribution parameters, but by using the rejection sampling we fix them to exactly 100 points. are made in line with the ones in Aksakalli and Ceyhan (2012) and Priebe et al. (2005). Also, we let the significance level of the test be 0:01. In particular, let P = [10; 90] [10; 90] which will be the window for clutter center points. In all six types of clutter distributions, the sample size generated is equal to exactly 100 points. As for obstacle window forms, we consider a total of 19 different sampling windows. The first is the polygon P = [10; 90] [10; 90], there are 8 different linear windows of width equals to 10 units and with their top left corner y coordinate being 90,80,...,20, and 5 different Vshaped and Wshaped windows, respectively, with their top left corner y coordinate being 90,80,...,50. The difference between the top and bottom y coordinates of each one of these 10 polygons is taken to be 50 units. The width of polygonal shape is 10 units (Aksakalli and Ceyhan, 2012). For example, L70 is the polygon whose four corner points are (10,70), (90,70), (90,60) and (10,60) clockwise starting with the top left corner. We also take number 50 Chapter 3: M2k Algorithm for the OPD Problem of obstacles to be 20, 30, 40, 50, and 60 for each of the 19 obstacle sampling windows. Thus, the realization of obstacle patterns are denoted by the sampling window followed by the number of obstacles. For example, P:40 and L70:40 refer to the obstacle patterns sampled within the P and L70 windows, respectively, with 40 obstacle center points inside their respective windows. These choices also ones made as in Aksakalli and Ceyhan (2012) for comparative purposes. Hence, the treatment factors are the “background clutter type”, the “obstacle placement window” and the “number of the obstacles”. The first has 6 different types, the second has 19 types and the third has 5 different types resulting in a total of 570 treatment combinations. Our main goal is to investigate how traversal length changes according to treatment factors when the NAVA uses the greedy RD algorithm and its variants M2k algorithm. 3.3 M2k Algorithm In the original version of RD algorithm, the average number of edges that diskshaped obstacles intersect in a 8discretization setting is 88. So, prior to the traversal, NAVA assigns edge weight to all edges intersecting the disks using the cost of disambiguation and the probability of being a true obstacle of a disk (Chapter 5). But, M2k algorithm is based on the effective choice of the number disambiguations. As an example let us consider the case k = 3, then NAVA updates only 23 edges for each diskshaped obstacle and assigns 1 for the rest. An example of the choice of 8 disambiguation points for disks are shown below (see Figure 3.3). M16 and M4 algorithms are defined analogously. The advantage of using the M2k algorithm is that the complexity time is reduced when computing the traversal length of NAVA and the mean traversal length is well estimated. For example, the complexity time of running M16 algorithm is at least 5 times faster than the RD algorithm, and the mean traversal length estimated by M16 algorithm deviates at most 2:5% relative error from the traversal length estimated by RD algorithm. Chapter 3: M2k Algorithm for the OPD Problem 51 Figure 3.4: A total of 8 disambiguation points are labeled in each diskshaped obstacle. 3.4 Repeated Measures ANOVA Our data set consists of traversal lengths computed by the RD algorithm and its variants under various conditions that we have described above. Hence, the background clutter types are Complete Spatial Randomness (CSR), inhomogeneous Poisson (IP) pattern, Matérn (M) pattern, Thomas (T) pattern, hardcore (HC) pattern, and Strauss (S) pattern. For simplicity the clutter types are numbered from 1 to 6, which in turn, correspond to CSR, IP, M, T, HC, and S patterns, respectively. Similarly, the obstacle window types are numbered from 1 to 19 corresponding to P, L90, L80,..., L20, V90, V80,..., V50, W90, W80,..., W50, respectively. The obstacle number levels are also numbered from 1 to 5 corresponding to 20, 30, 40, 50, 60, respectively. Thus, we denote the traversal length as Lijkl which is the traversal length of the measurement l for clutter type i, obstacle window type j, obstacle number level k with l = 1; 2; :::; 100; i = 1; 2; :::; 6; j = 1; 2; :::; 19; and k = 1; 2; :::; 5, respectively. Note that Lijkl; Lij0kl; Lijk0l; Lij0k0l are estimated on the same background clutter type i, and hence they are potentially correlated. Similarly, the expected traversal lengths within the respective obstacle window types or obstacle number levels can also correlated (positively or negatively). In order to deal with and take into account such possible correlations, we use repeated measures ANOVA. We use the repeated mea 52 Chapter 3: M2k Algorithm for the OPD Problem sures ANOVA to compare the traversal length differences between treatment factors. The conditions of repeated measures ANOVA are similar to that of usual ANOVA, except that independence is not required and an assumption about the relations among the repeated measures is added. The repeated measures ANOVA assumptions are; (i) the dependent variable is normally distributed, (ii) the homogeneity of covariance matrices is required, (iii) independence between predictor factors, and (iv) sphericity, which refers that the variance of repeated measures are all equal, and the correlations among the repeated measures are all equal (Aksakalli and Ceyhan, 2012). The main advantage of using the repeated measures ANOVA rather than standard ANOVA is that we obtain more precise information in comparison of
Click tabs to swap between content that is broken into logical sections.
Title  charyyev_polat_diss_2017 
Author  Charyyev, Polat 
Subject  The optimal obstacle placement with disambiguation problem 
Faculty Advisor  Yılmaz, Atilla 
Institute  Koç University Graduate School of Sciences & Engineering 
Program  Mathematics 
Physical Description  xxv, 143 leaves : illustrations ; 30 cm. 
Place of Publication  İstanbul 
Publisher  Koç University 
Resource Type  charyyev_polat_diss_2017.pdf 
Date  2017 
Collection  KU Theses and Dissertations 
Transcription  The Optimal Obstacle Placement With Disambiguation Problem by Polat Charyyev A Dissertation Submitted to the Graduate School of Sciences and Engineering in Partial Fulfillment of the Requirements for the Degree of Doctor of Philosophy in Mathematics 2017 The Optimal Obstacle Placement With Disambiguation Problem Koç University Graduate School of Sciences and Engineering This is to certify that I have examined this copy of a doctoral dissertation by Polat Charyyev and have found that it is complete and satisfactory in all respects, and that any and all revisions required by the final examining committee have been made. Committee Members: Assoc. Prof. Atilla Yılmaz Assoc. Prof. Mine Çaglar Assoc. Prof. Elvan Ceyhan Asst. Prof. Özgür Asar Asst. Prof. Ümit Islak Date: This thesis is dedicated to my parents. iii ABSTRACT In the optimal obstacle placement with disambiguation (OPD) problem, we investigate how traversal length depends on the spatial pattern of the obstacles. In the OPD problem an obstacle placing agent (OPA) wishes to insert (diskshaped) obstacles of two types as true or false obstacles in an environment so as to maximize the traversal length of a navigating agent (NAVA). NAVA is equipped with a sensor that can only assign probabilities to each obstacle as being a true obstacle, but does not know the actual status of the obstacle until it reaches the boundary of the obstacle. When NAVA comes by the obstacle, it disambiguates the status of the obstacle with a cost added to the traversal length. We first investigate the case when OPA equips the overall working window with false and/or true obstacles together where the whole obstacle pattern changing from uniformness to regularity and from uniformness to clustering, then on the average, the mean traversal length tends to increase (decrease) as the obstacle pattern changes from uniformness to regularity (clustering). Secondly, we introduce M2k algorithm which is the modified version of RD algorithm and mainly based on the effective choice of a subset of possible disambiguations. We observed that the trends for mean traversal length estimated by M2k algorithm is similar to RD algorithm except for reducing the complexity time and keeping relative error less than 2:5%. Moreover, we study the case when obstacles are distributed inside various obstacle window types such as linear strips, Vshaped, semicircular, and elliptical where we change the parameters such as location, orientation and curvature of these obstacle window forms. We also consider the case where the true obstacles are placed randomly proportional to the areas of Voronoi polygons or Delaunay triangles based on the allocation of the clutter points. On the average, the elliptical window type (a continuous version of Vshaped) reveals to be the best iv performing in maximizing the traversal length of NAVA and as for tessellations, the mean traversal length is essentially the same as the mean traversal length when obstacles are distributed uniformly. On the other hand, we provide extensions of the existing suboptimal algorithms in the OPD problem, and introduce new ones for NAVA. The goal is to find an algorithm to minimize the expected traversal length of NAVA. We generalize the penaltybased functions used within the existing heuristic algorithms, and combine possibly related algorithms in a single family. We provide a guidance for choosing the algorithm from the defined family when the performance of NAVA’s sensor varies from poor to almost perfect detection (of true obstacles). Our results are supported by extensive Monte Carlo simulations and theoretical results for some special types of graph structures are also provided. ÖZETÇE Belirsizligi giderme özellikli optimal engel yerlestirme (OPD) probleminde, yol uzunlugunun uzaysal desen türlerine göre nasıl etkilendigini arastırıyoruz. OPD probleminde, navigasyon aracının (NAVA) gidecegi yolu mümkün oldugunca uzun tutmak için yüzeye engel yerlestirme aracı (OPA) tarafından gerçek veya sahte engeller yerlestirilmektedir. NAVA her diskin gerçek engel olma ihtimalini belirleyen sensör ile donatılmıs olup, disklerin gerçek veya sahte oldugunu diskin sınırlarına gelene kadar bilmemektedir. Fakat NAVA diskin sınırlarında iken belirli bir maliyetin toplam süreye/uzunluga eklenmesi karsılıgında disklerin gerçek veya sahte oldugunu ögrenebilmektedir. ?lk olarak, OPA’nın çalısma bölgesine sahte ve/veya gerçek engelleri tüm engel desenin tekdüzelikten düzenlilige ve tekdüzelikten kümelenmeye göre yerlestirilmesi sonucunda toplam geçis uzunlugunun engel desenin tekdüzelikten düzenlilige göre artmakta ve tekdüzelikten kümelenmeye göre ise azalmaktadır. Ikinci olarak, RD algoritmasının degistirilmis versiyonu olan ve temel olarak disk basına düsen belirsizlik nokta sayısının akıllıca seçilmesine baglı olan M2k algoritmasını tanıtmaktayız. M2k algoritması tarafından hesaplanan yol uzunlugunun RD algoritması tarafından hesaplanan yol uzunlugu ile benzer egilimler gösterdigini gözlemledik ve dahası hesaplama süresi azaltılmıs olup, toplam geçis uzunlugu en fazla %2:5 sapmaktadır. Buna ek olarak, engellerin lineer, Vseklinde, yarı çembersel, ve eliptik gibi degisik sekil içinde dagılımları engel sekillerin lokasyon, oryantasyon, ve kurvatür gibi parametrelerine göre incelenmistir. Ayrıca, sahte engellerin yerlesimine baglı olarak Voronoi çokgen veya Delaunay üçgen alanlarına orantılı olacak sekilde gerçek engellerin yerlestirilme durumu ele alınmıstır. Ortalama olarak, NAVA’nın toplam geçis uzunlugunu maksimuma çıkarmak için engel sekillerin arasından eliptik engel sekli (Vseklinin sürekli versiyonu) en optimal degeri vermektedir ve Dirichlet vi mozaigi gibi düzenlemeler için ise geçis uzunlugu engellerin tekdüze dagılımındakine yakın degeri vermektedir. Diger taraftan, OPD problemindeki NAVA için mevcut optimal olmayan algoritmaları genisletmekteyiz ve yenilerini ortaya koymaktayız. Buradaki asıl amaç, NAVA’nın beklenen geçis uzunlugunu minimuma indiren algoritma gelistirmektir. Mevcut sezgisel algoritmalarda kullanılan agırlıga dayalı fonksiyonları genellestiriyoruz, ve benzer algoritmaları tek çatı altında birlestiriyoruz. NAVA’nın sensör algılama (gerçek engel olma ihtimali) performans gücünün en zayıftan mükemmel dereceye kadar durumlarda birlestirilen algoritma kümesinden en optimal olanı seçmeyi gösteriyoruz. Bizim sonuçlarımız kapsamlı Monte Carlo simülasyonları ile desteklenmekle beraber, bazı özel graf biçimleri için teorik sonuçlar göstermekteyiz. ACKNOWLEDGMENTS I would like to express my sincere gratitude to my advisors Assoc. Prof. Elvan Ceyhan and Assoc. Prof. Atilla Yılmaz for the continuous support of my Ph.D study and related research, for their patience, motivation, and immense knowledge. Their guidance helped me in all the time of research and writing of this thesis. Besides my advisor, I would like to thank Assoc. Prof. Vural Aksakallı for his guidance and help on designing and understanding the related algorithms. I thank my thesis committee members Assoc. Prof. Atilla Yılmaz and Assoc. Prof. Mine Çaglar for their insightful comments and encouragement. I also thank thesis jury members Asst. Prof. Özgür Asar and Asst. Prof. Ümit Islak for accepting and participating my thesis defense. I thank my Ph.d colleagues, especially Artür Manukyan for the stimulating discussions and for all the fun we have had in the last five years. I thank Mathematics department Professors for creating academic environment and all GSSE staff, especially Emine Büyükdurmus and Elif Tüysüz for their continual support and guidance. I would like to thank Koç University and TUBITAK for providing me with financial support which made this study possible. I would like to thank my family: my parents, my brother and sisters, my wife and beloved son for supporting me spiritually throughout writing this thesis and my life in general. viii TABLE OF CONTENTS List of Tables xii List of Figures xv Nomenclature xxv Chapter 1: Introduction 1 1.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2 Continuous SOS and OPD Problems . . . . . . . . . . . . . . . . . . 5 1.3 Discretized SOS and OPD Problems . . . . . . . . . . . . . . . . . . 6 1.4 Organization of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . 7 Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent 8 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2 Experimental Setting . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.3 Obstacle Pattern Ranging from Uniformness to Regularity . . . . . . 11 2.3.1 Clutter Only Case . . . . . . . . . . . . . . . . . . . . . . . . 12 2.3.2 True Obstacles Only Case . . . . . . . . . . . . . . . . . . . . 19 2.3.3 True and False Obstacles Together . . . . . . . . . . . . . . . 22 2.4 Obstacle Pattern Ranging from Uniformness to Clustering . . . . . . 24 2.5 Stochastic Ordering of Traversal Lengths . . . . . . . . . . . . . . . . 27 2.6 Mean Traversal Length Versus Ratio of Number of True to False Obstacles 31 2.6.1 Obstacle Pattern Ranging from Uniformness to Regularity . . 32 2.6.2 Obstacle Pattern Ranging from Uniformness to Clustering . . 38 ix 2.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 Chapter 3: M2k Algorithm for the OPD Problem 45 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 3.2 Experimental Setting . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 3.2.1 Background Clutter Generation . . . . . . . . . . . . . . . . . 45 3.3 M2k Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 3.4 Repeated Measures ANOVA . . . . . . . . . . . . . . . . . . . . . . . 51 3.4.1 Overall Comparison of Traversal Lengths . . . . . . . . . . . . 52 3.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 Chapter 4: Dependence of Traversal Length on Obstacle Window Types and Tessellations 62 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 4.2 Obstacle Window Types . . . . . . . . . . . . . . . . . . . . . . . . . 63 4.2.1 Linear Strip Window . . . . . . . . . . . . . . . . . . . . . . . 63 4.2.2 VShaped Window . . . . . . . . . . . . . . . . . . . . . . . . 66 4.2.3 Semicircular Window . . . . . . . . . . . . . . . . . . . . . . . 71 4.3 Placing True Obstacles in a Regular Fashion . . . . . . . . . . . . . . 74 4.4 Voronoi and Delaunay Tessellations . . . . . . . . . . . . . . . . . . . 80 4.4.1 Results and Analysis . . . . . . . . . . . . . . . . . . . . . . . 81 4.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 Chapter 5: Heuristic Algorithms for the OPD Problem 87 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 5.2 Algorithms for NAVA . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 5.3 A Unifying Framework for FRD, FP , and FDT . . . . . . . . . . . . . 91 5.4 Experimental Setting . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 5.5 ALG(k) Algorithm and Sensor Precision . . . . . . . . . . . . . . . . 101 x 5.6 ALG(k) Algorithm and the Disambiguation Cost . . . . . . . . . . . 107 5.7 Convergence of Traversal Length Under ALG(k) Algorithm . . . . . . 109 5.8 MT(~k) Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 5.9 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 Chapter 6: Theoretical Results 123 6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 6.2 RD Algorithm for the Discrete SOSP . . . . . . . . . . . . . . . . . . 124 6.3 Graphs with Two Nodes . . . . . . . . . . . . . . . . . . . . . . . . . 125 6.3.1 Empirical Results . . . . . . . . . . . . . . . . . . . . . . . . . 131 6.4 Generalization of OPD Problem . . . . . . . . . . . . . . . . . . . . . 131 6.4.1 Higher Dimensional Discretization . . . . . . . . . . . . . . . . 133 6.5 Future Research . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 Chapter 7: Conclusions and Discussion 137 xi LIST OF TABLES 2.1 Intercept and slope values of regression lines for each categorical group nc. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.2 Significant level of differences (pvalues) in intercept (a) and slope (b) for each pair of groups. . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.3 Coefficients of quadratic polynomial fitted to the data at each clutter number level. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.4 Significant level of differences (pvalues) of coefficient c (intercept) (a), coefficient b (linear term) (b), and coefficient a (quadratic term) (c) at each pair of clutter level. . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.5 Intercept and slope values of regression lines for each categorical group no. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.6 Significant level of differences (pvalues) in intercept (a) and slope (b) for each pair of groups. . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.7 Intercept and slope values of regression lines for each categorical group . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 3.1 The comparisons of the models in Equation (1) when the traversal length is estimated by RD algorithm. . . . . . . . . . . . . . . . . . 53 3.2 The shortest and longest traversal lengths and the corresponding treatment types for overall comparisons, and comparisons at specific clutter types, obstacle types, and obstacle numbers when the traversal length is computed by RD algorithm. . . . . . . . . . . . . . . . . . . . . . 59 xii 3.3 The shortest and longest traversal lengths and the corresponding treatment types for overall comparisons, and comparisons at specific clutter types, obstacle types, and obstacle numbers when the traversal length is computed by M8 algorithm. . . . . . . . . . . . . . . . . . . . . . 60 4.1 Comparison of mean traversal lengths for obstacle number levels no = 40 and no = 50. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 4.2 Comparison of mean traversal lengths for obstacle number levels no = 50 and no = 60. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 4.3 Mean traversal length versus d2 values for no = 20 inside L10 obstacle form with background clutter type Hardcore(nc = 100; d) where d = 5; 6; 7; 8. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 4.4 Mean traversal length versus d2 values for no = 30 inside V90 obstacle form with background clutter type Hardcore(nc = 100; d) where d = 5; 6; 7; 8. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 4.5 Mean traversal length versus d2 values for no = 30 inside SC90 obstacle form with background clutter type Hardcore(nc = 100; d) where d = 5; 6; 7; 8. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 5.1 Comparison of mean traversal lengths estimated by the RD (shown in bold) and ALG(2) algorithms for various pairs of (nc; no) with percentage error less than 2%. . . . . . . . . . . . . . . . . . . . . . . . . . 98 5.2 Comparison of mean traversal lengths computed by the P (shown in bold) and ALG(3) algorithms for various pairs of (nc; no) with percentage error less than 0:5% . . . . . . . . . . . . . . . . . . . . . . . . . 98 5.3 Comparison of mean traversal lengths computed by the DT (shown in bold) and ALG(5) algorithms for various pairs of (nc; no) with percentage error less than 1%. . . . . . . . . . . . . . . . . . . . . . . . . . 100 xiii 6.1 For any fixed values of a and n, there are 100 realizations of values of p selected randomly from uniform (0; 1) distribution. And, we exhibit the corresponding mean values. . . . . . . . . . . . . . . . . . . . . . 132 6.2 Some values of k in ddimensional case . . . . . . . . . . . . . . . . . 135 xiv LIST OF FIGURES 2.1 A realization of clutter disks (dashed circles) with nc = 40 from the Strauss(nc = 40; d = 9; = 0) process. . . . . . . . . . . . . . . . . . 12 2.2 Mean traversal length versus values for groups nc = 25; 50; 75; 100 together with overall plot (i.e., the average of all groups combined). . 13 2.3 Mean traversal length versus d values for groups nc = 25; 50; 75; 100 with overall plot (i.e., the average of all groups combined). . . . . . . 15 2.4 Mean traversal length versus d values for nc = 25; 50; 75; 100 together with quadratic polynomial fit and (nonparametric) smoothing spline with smoothing parameter p = 0:9863 . Notice that vertical axes are differently scaled. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.5 Contour plots of mean traversal length versus and d values for nc = 25; 50; 75; 100. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.6 Mean traversal length versus values for groups no = 25; 50; 75; 100 together with overall plot (i.e., the average of all groups combined). . 21 2.7 Contour plots of mean traversal length versus and d values for no = 75; 100. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.8 The pattern is from the Strauss(nc + no = 50; d = 9; = 0) process where dashed circles (nc = 25 with centers in XC) are the 25 false obstacles and solid circles (no = 25 with centers in XO) are the 25 true obstacles. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.9 Contour plots of the mean traversal length versus and d values when (a) (nc; no) = (25; 50), (b) (nc; no) = (25; 75). . . . . . . . . . . . . . . 24 xv 2.10 (a) A realisation of clutter disks from the Matérn( = 2; r0 = 15; = 10) process shown in dashed circles. (b) The pattern is from the Matérn(8,15,10) process where dashed circles indicate the false obstacles (nc = 60) and solid circles indicate the true obstacles (no = 20). . 26 2.11 Mean traversal length versus cluster radius values when there are (a) only clutter disks with nc = 20; 40; 60; 80 together with overall plot (i.e., the average of all groups combined), (b) only true obstacles with no = 20; 40; 60; 80 together with overall plot (i.e., the average of all groups combined). Notice that vertical axes are differently scaled. . . 27 2.12 Mean traversal length versus values for groups (a) = 0; 1=4; 1=2; 1 together with overall plot (the average of all 7 distinct groups), (b) = 1; 2; 4;1 together with overall plot (the average of all 7 distinct groups). Notice that vertical axes are differently scaled. . . . . . . . . 33 2.13 (a) Mean traversal length versus values for groups = 0; 0:4; 0:6; 1, (b) average contour plot of mean traversal length versus and values. 34 2.14 Mean traversal length versus d values for groups (a) = 0; 1=4; 1=2; 1 together with overall plot (the average of all 7 distinct groups), (b) = 1; 2; 4;1 together with overall plot (the average of all 7 distinct groups). Notice that vertical axes are differently scaled. . . . . . . . . 35 2.15 (a) Mean traversal length versus values for groups d = 1; 4; 6; 10, (b) average contour plot of mean traversal length versus d and values. 36 2.16 Overall average contour plots of the mean traversal length versus and d values for (a) = 0, (b) = 1=4, (c) = 1=2, and (d) = 1. . . . . 37 2.17 Overall average contour plots of the mean traversal length versus and d values for (a) = 2, (b) = 4, (c) = 1, and (d) overall (the average of all levels). . . . . . . . . . . . . . . . . . . . . . . . . . . 38 xvi 2.18 Mean traversal length versus r0 values for groups (a) = 0; 1=4; 1=2; 1 together with overall plot (the average of all 7 distinct groups), (b) = 1; 2; 4;1 together with overall plot (the average of all 7 distinct groups). Notice that vertical axes are differently scaled. . . . . . . . . 39 2.19 Mean traversal length versus values for groups (a) = 0; 1=4; 1=2; 1 together with overall plot (the average of all levels), (b) = 1; 2; 4;1 with overall plot (the average of all levels). Notice that vertical axes are differently scaled. . . . . . . . . . . . . . . . . . . . . . . . . . . 40 2.20 (a) Mean traversal length versus values for groups r0 = 5; 15; 30; 50, (b) average contour plot of mean traversal length versus r0 and values. 41 2.21 (a) Mean traversal length versus values for groups = 1; 3; 6; 10, (b) average contour plot of mean traversal length versus and values. 41 2.22 Overall average contour plots of the mean traversal length versus no and nc values when (a) (d; ) = (6; 0), (b) (d; ) = (7; 0), and (c) (d; ) = (8; 0). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 3.1 Sample realizations from homogeneous and inhomogeneous point processes. The parameters are: (a) CSR(100) and (b) IP 0:037e(10y)=40 . Indeed, on the average 100 points are generated by using these distribution parameters, but by using the rejection sampling we fix them to exactly 100 points. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 3.2 Sample realizations from Matérn and Thomas point processes. The parameters are: (a) M(10; 10; 10) and (b) T(10; 10; 5). Indeed, on the average 100 points are generated by using these distribution parameters, but by using the rejection sampling we fix them to exactly 100 points. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 xvii 3.3 Sample realizations from Hardcore and Strauss point processes. The parameters are: (a) HC(100; 5) and (b) S(100; 5; 0:5). Indeed, on the average 100 points are generated by using these distribution parameters, but by using the rejection sampling we fix them to exactly 100 points. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 3.4 A total of 8 disambiguation points are labeled in each diskshaped obstacle. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 3.5 The interaction plots for each pair of treatment factors (obstacle type/form, clutter type, and obstacle number) when the other factor is ignored. The traversal length is estimated by RD algorithm. . . . . . . . . . . 57 3.6 The interaction plots for each pair of treatment factors (obstacle type/form, clutter type, and obstacle number) when the other factor is ignored. The traversal length is estimated by M8 algorithm. . . . . . . . . . . 58 3.7 The plots of mean traversal length versus obstacle window type, clutter type, and obstacle number level when computed by RD, M16, M8, and M4 algorithms, respectively. . . . . . . . . . . . . . . . . . . . . . . . 58 4.1 The background clutter pattern is from the Hardcore(100; 5) (dashed circles) process and no = 20 true obstacles are uniformly distributed inside the linear strip of width ` = 10 (solid circles). . . . . . . . . . . 64 4.2 Mean traversal length versus (a) width ` of linear strip and (b) location of linear strip for no = 20; 30; 40; 50; 60 provided that background clutter type is Hardcore(100; 5). Notice that vertical axes are differently scaled. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 4.3 Mean traversal length versus (a) width ` of linear strip and (b) location of linear strip for no = 20; 30; 40; 50; 60 provided that background clutter type is Hardcore(100; 6). Notice that vertical axes are differently scaled. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 xviii 4.4 Mean traversal length versus (a) width ` of linear strip and (b) location of linear strip for no = 20; 30; 40; 50; 60 provided that background clutter type is Hardcore(100; 7). Notice that vertical axes are differently scaled. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 4.5 Mean traversal length versus (a) width ` of linear strip and (b) location of linear strip for no = 20; 30; 40; 50; 60 provided that background clutter type is Hardcore(100; 8). Notice that vertical axes are differently scaled. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 4.6 The background clutter pattern is from the Hardcore(100; 5) (dashed circles) process and no = 20 true obstacles are uniformly distributed inside the Vshaped obstacle window with distance v = 80 between two upper lips (solid circles). . . . . . . . . . . . . . . . . . . . . . . . 68 4.7 Mean traversal length versus (a) v value and (b) location of Vshaped window for no = 20; 30; 40; 50; 60 together with v = 80 provided that the background clutter type is Hardcore(100; 5). Notice that vertical axes are differently scaled. . . . . . . . . . . . . . . . . . . . . . . . . 69 4.8 Mean traversal length versus (a) v value and (b) location of Vshaped window for no = 20; 30; 40; 50; 60 with v = 80 provided that background clutter type is Hardcore(100; 8). Notice that vertical axes are differently scaled. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 4.9 The background clutter pattern is from the Hardcore(100; 5) (dashed circles) process and no = 20 true obstacles (solid circles) are uniformly distributed inside the Vshaped obstacle window with distance w = 10 between the vertex of the obstacle from and the point (50; 10). . . . 70 4.10 Overall mean traversal length versus w values for no = 20; 30; 40; 50; 60. 71 4.11 The background clutter pattern is from the Hardcore(100; 5) (dashed circles) process and no = 20 true obstacles are uniformly distributed inside the semicircular obstacle window form (solid circles). . . . . . . 72 xix 4.12 Mean traversal length versus location of semicircular obstacle window form for no = 20; 30; 40; 50; 60 provided that the background clutter type is (a) Hardcore(100; 5) and (b) Hardcore(100; 8). . . . . . . . . 73 4.13 The background clutter pattern is from the Hardcore(100; 5) (dashed circles) process and no = 20 true obstacles (solid circles) are uniformly distributed inside the elliptical obstacle with distance u = 20 between the vertex of the obstacle from and the point (50; 10). . . . . . . . . 74 4.14 Overall mean traversal length versus u values for no = 20; 30; 40; 50; 60. 75 4.15 Mean traversal length versus d2 values (regularity parameter for no) for no = 20; 30; 40 provided that the background clutter type is Hardcore (overall average of Hardcore(nc = 100; d) with d = 5; 6; 7; 8). . . . . . 75 4.16 Mean traversal length versus d2 values (regularity parameter for no) for no = 20; 30; 40 provided that the background clutter type is Hardcore (overall average of Hardcore(nc = 100; d) with d = 5; 6; 7; 8). . . . . . 77 4.17 Mean traversal length versus d2 values (regularity parameter for no) for no = 20; 30; 40 provided that the background clutter type is Hardcore (overall average of Hardcore(nc = 100; d) with d = 5; 6; 7; 8). . . . . . 78 4.18 Mean traversal length versus d2 values (regularity parameter for no) for no = 20; 30; 40 provided that the background clutter type is Hardcore (overall average of Hardcore(nc = 100; d) with d = 5; 6; 7; 8). . . . . . 79 4.19 Mean traversal length versus d2 values (regularity parameter for no) for no = 20; 30; 40 provided that the background clutter type is Hardcore (overall average of Hardcore(nc = 100; d) with d = 5; 6; 7; 8). . . . . . 80 4.20 (a) Voronoi diagram and (b) Delaunay triangulation of 100 sample points. 82 4.21 For the CSR background clutter type, the mean traversal length (a) when true obstacles are placed around vertices and centroids of tessellations, and (b) when true obstacles are placed proportional to tile areas of tessellations. . . . . . . . . . . . . . . . . . . . . . . . . . . 82 xx 4.22 For the Hardcore(nc = 100; d) background clutter type (combined all d = 5; 6; 7; 8 cases), the mean traversal length (a) when true obstacles are placed around vertices and centroids of tessellations, and (b) when true obstacles are placed proportional to tile areas of tessellations. . 83 5.1 Pairwise comparison of the penalty functions FRD, FP , FDT with the penalty function Fk for k = 2; 3; 5. Note that both vertical and horizontal values are differently scaled. . . . . . . . . . . . . . . . . . . . 93 5.2 Disambiguation cost c versus k(c) values when p 2 (0; 1) (when the penalty function FRD approximated by the penalty function Fk). . . . 95 5.3 Comparison of mean traversal lengths computed by the RD and ALG(2) algorithms, (a) when there are only clutter disks with nc 2 f50; 75; : : : ; 200g, (b) and when there are only true obstacles with nc =2 f50; 75; : : : ; 200g with 95% confidence intervals for the mean traversal length computed by the RD and ALG(2) algorithms, respectively. . . . . . . . . . . . 96 5.4 Comparison of mean traversal lengths estimated by the P and ALG(3) algorithms, (a) when there are only clutter disks with nc 2 f50; 75; : : : ; 200g, (b) and when there are only true obstacles with nc =2 f50; 75; : : : ; 200g with 95% confidence intervals for the mean traversal length computed by the P and ALG(3) algorithms, respectively. . . . . . . . . . . . . 99 5.5 Comparison of mean traversal lengths estimated by the DT and ALG(5) algorithms, (a) when there are only clutter disks with nc 2 f50; 75; : : : ; 200g, (b) and when there are only true obstacles with no 2 f50; 75; : : : ; 200g with 95% confidence intervals for the mean traversal length computed by the DT and ALG(5) algorithms, respectively. . . . . . . . . . . . 100 xxi 5.6 Comparison of average number of disambiguations when the mean traversal length is estimated by the RD, P, and DT algorithms, (a) when there are only clutter disks with nc 2 f50; 75; : : : ; 200g, (b) and when there are only true obstacles with no 2 f50; 75; : : : ; 200g. Note that vertical axes are differently scaled. . . . . . . . . . . . . . . . . 102 5.7 Comparison of mean traversal lengths estimated by the ALG(k) algorithms, (a) when there are only clutter disks with nc = 50; 75; 100; 125, (b) and when there are only true obstacles with nc = 50; 75; 100; 125. Notice that vertical axes are differently scaled. Note that vertical axes are differently scaled. . . . . . . . . . . . . . . . . . . . . . . . . . . 103 5.8 Comparison of mean traversal lengths estimated by the ALG(k) algorithms when there are total nc + no number of obstacles uniformly generated with nc = 25; 50; 75; 100 and no = 25; 50; 75; 100. . . . . . . 105 5.9 Comparison of mean traversal lengths estimated by the ALG(k) algorithms, (a) for (nc; no) = (25; 75), (b) for (nc; no) = (50; 50), (c) and for (nc; no) = (75; 25). Notice that vertical axes are differently scaled. 106 5.10 Comparison of mean traversal lengths estimated by the ALG(k) algorithms when there are total nc + no number of obstacles (combination of all (nc; no) pairs) uniformly generated with nc; no 2 f25; 50; 75; 100g. 108 5.11 Comparison of mean traversal lengths estimated by the ALG(k) algorithms, (a) for (nc; no) = (25; 75), (b) for (nc; no) = (50; 50), (c) and for (nc; no) = (75; 25). Notice that vertical axes are differently scaled. 109 5.12 (a) Mean traversal length estimated by benchmark, ALG(1), ALG(2) algorithms versus nc with nc 2 f50; 75; : : : ; 325g. (b) Mean traversal length estimated by the benchmark, ALG(4), ALG(5) algorithms versus no with no 2 f50; 75; : : : ; 250g . Notice that horizontal axes are differently scaled. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 xxii 5.13 (a) Mean traversal length versus nc computed by the B, ALG(2), T(0:5) algorithms with nc 2 f50; 75; : : : ; 325g. (b) Mean traversal length versus no computed by the B, ALG(5), T(0:5) algorithms with no 2 f50; 75; : : : ; 250g . Note that horizontal axes are differently scaled. 113 5.14 (a) Mean traversal length versus nc estimated by the B, DT, MT(7) algorithms with nc 2 f50; 75; : : : ; 325g. (b) Mean traversal length versus no computed by the B, DT, MT(7) algorithms with no 2 f50; 75; : : : ; 250g with 95% confidence intervals for the benchmark value. Notice that horizontal axes are differently scaled. . . . . . . . . . . . . . . . . . . 114 5.15 Comparison of mean traversal lengths estimated by the B, DT, MT(7) algorithms, (a) for nc = 25 with no 2 f25; 50; : : : ; 200g, (b) and for nc = 75 with no 2 f25; : : : ; 200g with 95% confidence intervals for the benchmark value. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 5.16 Comparison of mean traversal lengths estimated by the B and MT(~k) algorithms, (a) for nc = 25 with no = 25; 50; 75; 100, (b) and for nc = 50 with no = 25; 50; 75; 100 with 95% confidence intervals for the benchmark value. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 5.17 Comparison of mean traversal lengths estimated by the B and MT(~k) algorithms, (a) for nc = 75 with no 2 f25; 50; : : : ; 100g, (b) and for nc = 100 with no 2 f25; 50; : : : ; 100g with 95% confidence intervals for the benchmark value. . . . . . . . . . . . . . . . . . . . . . . . . . . 116 5.18 Comparison of mean traversal lengths estimated by the B and ALG(k) algorithms, (a) for nc = 25 with no = 25; 50; 75; 100, (b) and for nc = 50 with no = 25; 50; 75; 100 with 95% confidence intervals for the benchmark value. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 xxiii 5.19 Comparison of mean traversal lengths estimated by the B and ALG(k) algorithms, (a) for nc = 75 with no = 25; 50; 75; 100, (b) and for nc = 100 with no = 25; 50; 75; 100 with 95% confidence intervals for the benchmark value. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 xxiv NOMENCLATURE Abbreviations CTP Canadian Traveler’s Problem DSOS Discretized Stochastic Obstacle Scene DTA Distance to Termination Algorithm NAVA Navigating Agent OPD Obstacle Placement with Disambiguation OPA Obstacle Placing Agent RDA Reset Disambiguation Algorithm SOS Stochastic Obstacle Scene SRA Simulated Risk Algorithm xxv Chapter 1 INTRODUCTION The optimal obstacle placement with disambiguation (OPD) problem was first introduced by Aksakalli and Ceyhan (2012). The OPD problem is the dual of the stochastic obstacle scene (SOS) problem (Papadimitriou and Yannakakis, 1991), where the discrete version is called the Canadian traveler’s problem (CTP) (BarNoy and Schieber, 1991). In the SOS problem, the main goal is finding the shortest path through an unknown environment wherein a navigating agent (NAVA) plans the route from a given starting point to a designated target point through randomly positioned disk shaped regions that represent obstacles. In the version of the OPD problem of Aksakalli and Ceyhan (2012), the navigation environment already contained clutter, i.e., false natural obstacles, and an obstacle placing agent (OPA) placed true obstacles in the same environment. In practice this setting may arise in various situations, for example, OPA can represent a naval warfare vehicle placing mines (i.e., true obstacles) on the surface of a water body (such as a sea or ocean) which already has natural or artificial obstacles (like rocks or debris). And, NAVA could be a battleship (from the opponent forces to OPA) and wants to traverse from a source point to a target point which might be located at the coast defended by OPA and its affiliates. Prior to NAVA’s traversal, NAVA obtains the respective probabilities of the obstacle disks being true obstacles by using its sensor. Throughout the traversal, when NAVA reaches a disk’s boundary, it can disambiguate the disk and learn the actual status of it, i.e., whether it is a true or false obstacle. The cost of the disambiguation for each disk is added to the total traversal length (which contributes to the total cost in our optimization problem). If the disambiguated disk is a false obstacle, then NAVA can pass through 2 Chapter 1: Introduction or over it; otherwise NAVA has to replan its route from the current location avoiding the true obstacles until it reaches the target. From NAVA’s perspective, the task is then finding the optimal path for reaching from the source point to the target, i.e., the path with minimum expected traversal length. Conversely, the OPA’s goal is placing the obstacles in a such a way that NAVA’s traversal length is maximized. Here, we assume that NAVA uses a greedy algorithm called the RD algorithm (Aksakalli et al., 2011) in choosing the optimal path. Hence, NAVA disambiguates any obstacle it runs into and then always seeks a better policy and updates the algorithm accordingly. On the other hand, OPA will search for a better placement of obstacles. We also consider the version of the OPD problem where OPA has the capability of inserting both true and false obstacles in the navigation environment. Although these optimization problems have gained considerable attention in literature, few theoretical and efficient optimal results have been found. In particular, Papadimitriou and Yannakakis (1991) showed that the SOS problem is NPhard, and as for the CTP with its variants, one can find many heuristics for special cases wherein the optimal solution is attained in some special graph structures (Nikolova and Karger, 2008; Xu et al., 2009; Bnaya et al., 2009; Fried, 2013). Among these references, the work of Bnaya et al. (2009) is the closest to ours. They introduce the sensing cost of an edge in the CTP problem which is equivalent to the disambiguation cost of an obstacle in the SOS problem. In this variant of CTP, additional actions, called remote sensing, are allowed where each such action reveals the status of a nonincident edge for a certain cost. Indeed, allowing remotesensing makes CTP NPhard even on disjointpath graphs (Fried et al., 2013). Regarding the suboptimal algorithms for SOS problem, the BAO* algorithm of Aksakalli (2007a), the simulated risk disambiguation (SRA) of Fishkind et al. (2007) and the reset disambiguation algorithm (RDA) of Aksakalli et al. (2011) are among the examples. Indeed, the RD algorithm is an efficient algorithm for discretized SOS problem and yields an optimal value for graphs with two nodes (called parallel graphs G = (V;E) with jV j = 2), and for disjointpath graphs. In general, the discrete SOS Chapter 1: Introduction 3 problem for parallel graphs can be solved in O(jEj!) time complexity, but using the policy dictated by the RD algorithm the complexity of solving the same problem reduces to O(jEj log jEj). Successful adaptations of all these heuristics to the discretized SOS problem and the generalizations of both SRA and RDA were given in Aksakalli and Ari (2014), which in turn is called the "distance to termination" (DT) algorithm. The DT algorithm exploits the distance from current position of any obstacle to the target point together with the corresponding probabilities of obstacles being true obstacles. As for CTP, several variants of it have been introduced and effective heuristic algorithms are proposed. For example, in BarNoy and Schieber (1991) the recoverable CTP was introduced where a blocked edge does not remain blocked forever, and each vertex v has a recovery time `(v) 2 [0;1) for edges adjacent to v. They also introduced the kCTP, in which an upper bound of k blocked edges is given. Nikolova and Karger (2008) studied another variant of the CTP where the cost of edges comes from independent and identical distributions. Bnaya et al. (2008) introduced the sensing cost in CTP which is closely related to our work. In the original CTP, the status of an edge (i.e., whether it is blocked or not) can only be revealed upon reaching a vertex incident to that edge. This kind of sensing is called the local sensing, and the remote sensing refers to revealing the status of an edge from a distant location (Bnaya et al., 2009). The sensing cost in the CTP is equivalent to the disambiguation cost in SOS problem. Bnaya et al. (2015) studied the repeatedtask CTP where a number of navigating agents need to travel with the same goal, minimizing their combined travel cost. Moreover, recently Aksakalli et al. (2016) developed an AO* based exact algorithm, called the CAO* algorithm, for the CTP and they showed that the empirical performance is better than other exact algorithms. 4 Chapter 1: Introduction 1.1 Preliminaries The most common notion of comparison of random variables is the stochastic order. For any real valued random variable X, let FX(x) = P(X x) be the cumulative distribution function of X. Definition 1.1.1 If X and Y are random variables defined on the same sample space , then X is stochastically smaller than Y (X st Y ) if FX(!) FY (!) for each ! 2 . Similar definition holds for ‘ st’. There are many equivalent definitions describing the stochastic ordering of random variables. The following is the most common way of characterizing the stochastic ordering. Definition 1.1.2 If X and Y are random variables defined on the same sample space , then X st Y () Ef(X) Ef(Y ) for all nondecreasing functions f. Where Ef(X) represents the expected value of f(X) with respect to the density function of random variable X. Analogous definition holds for ‘ st’. Definition 1.1.3 Let Xn be a sequence of random variables defined on a sample space . We say that Xn is convergent in probability to a random variable X defined on if and only if lim n!1 P(jXn Xj > ) = 0 for any > 0. X is called the probability limit of the sequence and the convergence in probability is denoted by Xn P ! X: Chapter 1: Introduction 5 1.2 Continuous SOS and OPD Problems The continuous SOS problem is formally defined as follows: Consider a bounded obstacle field R2. False obstacles (such as rocks, debris, fake mines) are assumed to be located at points, XC, from a spatial point process C. Then, an Obstacle Placing Agent (OPA) places true obstacles at the points, XO, where centers are from another spatial point process O, possibly different from C. All false obstacles (respectively true obstacles) are assumed to be disk shaped and centered at the points in XC (respectively XO). A Navigating Agent (NAVA) wishes to traverse from a given starting point, s 2 , to a target point, t 2 , and is equipped with a sensor that assigns random probabilities pC : XC ! [0; 1] and pO : XO ! [0; 1] prior to NAVA’s traversal. When observing a realization of these processes, the NAVA only sees X := XC [ XO as obstacles, some of which maybe true obstacles. Let p(x) be the probability that x 2 XO, that is, x is a true obstacle for all x 2 X. Then NAVA’s detector assigns p(x) = pO for x 2 XO and p(x) = pC for x 2 XC. For every disk center x, the obstacle disk Dx is an open region with a fixed radius r > 0. The NAVA seeks to traverse a continuous (s; t) curve without hitting any true obstacle at shortest achievable arc length (i.e., in shortest traversal length). We further suppose that there is a dynamic disambiguation capability. Specifically, for all x 2 X, when the traversal curve is on the boundary of the disk, denoted as @Dx, (i.e., NAVA comes right at the boundary of the obstacle), it has an option to disambiguate x, that is, to learn x 2 XO or not, but at a cost c > 0 added to the length of the traversal curve. The NAVA can pass through disks that have been disambiguated and found to be clutter (i.e., false obstacle), but has to avoid ambiguous disks as well as disks that have been disambiguated and found to be true obstacles. How the NAVA should route the continuous (s; t) traversal curve  and where and when the disambiguations should be performed  in order to minimize the expected length (including the disambiguation cost) of this curve is called the continuous SOS problem (Papadimitriou and Yannakakis, 1991). On the other hand, the problem of placing the obstacles so as to maximize the 6 Chapter 1: Introduction NAVA’s traversal length in the SOS problem, namely the optimal obstacle placement with disambiguations (OPD) problem was introduced by Aksakalli and Ceyhan (2012). Indeed, the OPD problem can be formulated as max XO E[L(XO [ XC)] such that XO \Wc = ;; jXOj = n; where L(X) is the traversal length of NAVA given a set of hindrance (obstacle or clutter) points of X and W is the window where obstacles are placed by the OPA. 1.3 Discretized SOS and OPD Problems For computational efficiency and convenience, we consider a discrete approximation of the continuous setting on the 8adjacency integer lattice as in Aksakalli et al. (2011). Specifically, this discretization is stored as a graph G whose vertices are all of the pairs of integers i; j such that 1 i imax and 1 j jmax where imax and jmax are given integers. The obstacle field is partitioned by an imax jmax grid consisting of unit squares and the vertices of the squares in the grid constitute the vertices of G. The edges of G are determined by the adjacency of the vertices in the grid. That is, there are edges between all pairs of the following four types of vertices: (1) (i; j) and (i+1; j) with unit length, (2) (i; j) and (i; j + 1) with unit length, (3) (i; j) and (i + 1; j + 1) with length p 2, and (4) (i + 1; j) and (i; j + 1) with length p 2 for i; j = 0; 1; : : : ; 99. Also, we add corner edges of unit length with pairs of vertices connecting (100; j) and (100; j + 1), and vertices connecting (i; 100) and (i + 1; 100) for i; j = 0; 1; : : : ; 99. This discretization is called the 8adjacency integer discretization of . One vertex in G is designated as the starting point, s, and another vertex in G is designated as the target point, t (starting and target points are totally arbitrary). The NAVA wishes to traverse from s to t in G, using only the edges that do not intersect any true obstacle or ambiguous disks in the environment. If an edge intersects any ambiguous disk, then a disambiguation of the disk may be performed from either endpoint of the edge that are outside of the disk. The goal is to devise an algorithm (to be implemented Chapter 1: Introduction 7 by NAVA) that minimizes its expected traversal length by effecient exploitation of the disambiguation capability and the information on the locations of the disks. We call this discretization as the discretized SOS problem (DSOSP), which in effect, is a special case of the Canadian traveler’s problem. 1.4 Organization of the Thesis The rest of this thesis is organized as follows: In Chapter 2 we discuss choosing the optimal obstacle pattern against a disambiguating navigating agent. In Chapter 3 we introduce M2k algorithm for the OPD problem and investigate the trends for mean traversal length by statistical analysis tools such as repeated measures ANOVA. In Chapter 4 we investigate how the traversal length depends on obstacle window types and tessellations. In Chapter 5 we consider heuristic algorithms for the OPD problem and provide a guidance for choosing the best performing algorithm given the problem setting. In Chapter 6 we present some theoretical results in the discrete SOS problem for some special graphs and present directions for future research. In Chapter 7 presents conclusions and discussion. Chapter 2 CHOOSING THE OPTIMAL OBSTACLE PATTERN AGAINST A DISAMBIGUATING NAVIGATION AGENT 2.1 Introduction In Aksakalli and Ceyhan (2012), NAVA uses the RD algorithm (Aksakalli et al., 2011) to find the shortest path and authors mainly focus on two problems. First, given a background clutter pattern, what would be the optimal number of obstacles and the obstacle pattern to use so as to maximize the NAVA’s total traversal length. Second, if OPA is given a certain number of obstacles, then what would be the optimal way to place these obstacles among the given clutter locations. OPA places the true obstacles uniformly inside various obstacle windows such as linear strips, Vshaped and Wshaped windows together with the possibly natural pattern scenarios of false obstacles with different pattern types such as uniform (homogeneous Poisson process), clustered (Thomas and Matérn) and regular (hardcore and Strauss point process) patterns (Baddeley et al., 2008). Aksakalli and Ceyhan (2012) provided same evidence that on the average the traversal length of NAVA increases as the level of regularity increases and decreases as the level of clustering increases. In overall comparison, the mean traversal length of NAVA attains its maximum value when the background clutter type is hardcore, and the obstacle form is Vshaped with 50 uniformly sampled obstacles. In this section, we investigate how traversal length depends on obstacle pattern changing from uniformness to regularity and from uniformness to clustering in a more detailed fashion. For regularity, the effects of two parameters, the pairwise distance between disk shaped obstacles and the number of such obstacles (i.e., its Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent 9 density) are investigated. As for clustering, the effects of the radius in which obstacles accumulate around one or more cluster centers and the number of such cluster centers are investigated. In Aksakalli and Ceyhan (2012) a few clutter types were considered, but here we address more types of obstacle patterns and also study the case where OPA can insert both false and true obstacles. 2.2 Experimental Setting For simplicity, we take the study window (i.e., the navigation environment) to be = [0; 100] [0; 100] and we insert a grid of unit squares on the study window, so that we partition the window with 104 such squares. In each square we also insert the diagonal line segments connecting nonadjacent vertices. We represent this square grid partition (together with diagonals) as a graph G = (V;E) such that V is comprised of vertices of the squares in the grid and edges are the edges of the squares together with diagonals. Hence, we have edges between all pairs of the following four types of vertices : (1) (i; j) and (i + 1; j) with unit length, (2) (i; j) and (i; j + 1) with unit length, (3) (i; j) and (i + 1; j + 1) with length p 2, and (4) (i + 1; j) and (i; j + 1) with length p 2 for i; j = 0; 1; : : : ; 99. Also, we add corner edges of unit length with pairs of vertices connecting (100; j) and (100; j + 1), and vertices connecting (i; 100) and (i + 1; 100) for i; j = 0; 1; : : : ; 99. This discretization is called the 8adjacency integer discretization of . Without loss of generality, we take a starting point s on the upper boundary of the study window, say s = (50; 100). And, for the target we take a point on the opposite side of rectangular window, say t = (50; 1). In practice, we can think of as a section of sea near the coast which is going to be defended by OPA, where NAVA could be a ship trying to navigate over the sea to reach the target at the coast. Here, OPA inserts disk shaped obstacles whose centers are generated from a random point process. In this version, OPA determines only the distribution of the obstacles, but not their exact locations. Each disk is either traversable (i.e., false or clutter obstacle) or nontraversable (i.e., true obstacle) with their respective proba 10 Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent bilities of being a true obstacle. In the OPD problem an obstacle is traversable if it is of clutter type and nontraversable if it is a true obstacle. The traversable (respectively, nontraversable) obstacles, i.e., clutter (respectively, true) obstacles, are denoted with a set of circles whose centers are the set of points denoted by XC (respectively, XO). NAVA wishes to traverse from the given starting point s to the target point t inserted with a sensor assigning (random) probabilities pc : XC ! [0; 1] and po : XO ! [0; 1] prior to its traversal. That is, the sensor assigns the status of disks with the probability function f(x), f(x) = 8>>>>>< >>>>>: pc; x 2 XC po; x 2 XO 0; otherwise where pc and po are also random variables with density functions FC and FO, respectively. The sensor would (preferably) attach high probabilities for true obstacles compared to clutter. NAVA knows the exact locations of X = XC [ XO, but not the actual status of disks, i.e., whether a disk is traversable or not, but only have a probability which is suggestive of the actual status of the disks. Also suppose that when the NAVA is located on the boundary of a disk, it disambiguates a disk at a cost c > 0 added to the traversal length; i.e., NAVA can learn the actual status of the disk with the specific cost c. NAVA disambiguates the obstacle and if the obstacle is of clutter type, NAVA is able to traverse through it and can not traverse otherwise. Each disk has a fixed radius of r = 4:5 units and the disk centers are sampled inside [10; 90] [10; 90] ensuring that there always exists a (possibly very long ) s; t walk. The existence of such a long traversable path is based on the assumption that NAVA must reach the target, but in an untimely manner (i.e., traversal length being larger than a threshold) and for larger traversal times/lengths NAVA’s arrival at the target (is assumed to) pose no threat to defending entities (including OPA). That is, NAVA’s arrival on time to the target could make a difference for the state of affairs and if arrival is sufficiently late, then we assume it is irrelevant from OPA’s perspective. The disambiguation cost of a disk is taken to be c = 5, and in each part clutter proba Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent 11 bilities pc are from Beta(2; 6) distribution, whereas true obstacle probabilities po are from Beta(6; 2) distribution. From NAVA’s perspective, small probabilities indicate that it is more likely to be traversable, whereas high probabilities show that it is less likely to be traversable. The means of random variables sampled from Beta(2; 6) and Beta(6; 2) are 0:25 and 0:75, respectively, which resonates with the idea that the sensor assigning high probabilities to true obstacles. So, it is reasonable to work with these skewed distributions for sensor’s capability of obstacle detection. These choices (of the cost c and sensor probability distributions) are made in line with those of Aksakalli and Ceyhan (2012) and Priebe et al. (2005). However, if one wants to increase the sensor’s sensitivity, one might pick Beta( ; ) with < 2; > 6 for false obstacles and Beta( ; ) with > 6; < 2 for true obstacles. 2.3 Obstacle Pattern Ranging from Uniformness to Regularity In the OPD problem, we investigate how the traversal length varies as the obstacle pattern changes. First, we equip the whole window with only false or only true obstacles whose pattern changes from uniformness to regularity. We denote the number of clutter (false obstacles) by nc and the number of true obstacles by no. We compute the traversal lengths for nc = 25; 50; 75; 100 and no = 25; 50; 75; 100. For inserting obstacles conforming to regularity, the points that constitute the centers of disk shaped obstacles are chosen from the Strauss process (Baddeley et al., 2008), denoted as Strauss(n; d; ), where n stands for the number of points, is the intensity of the number of pairs of distinct points lying closer than d units; i.e., the parameter controls ‘strength’ of interaction between points. For any fixed value of d, if = 1 the density reduces to a uniform point process (i.e., the pattern becomes uniformness), and if = 0 the density is a hard core process (i.e., completely regular pattern). For values 0 < < 1, the process exhibits negative association (i.e., inhibition) between points. Thus, in our simulations we choose the values from 0 to 1 with an increment size of 0:1 units and we also consider various values of d varying from 0:5 to 11 with an increment size of 0:5 units. Moreover, the whole window is inserted with both 12 Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent false and true obstacles together where the whole pattern changes from uniformness to regularity for nc = 25; 50; 75 and no = 25; 50; 75 such that nc + no = 50; 75; 100. In our data set , d and the number of obstacles (hence implicitly obstacle density) are the main factors that influence the traversal length. In Aksakalli and Ceyhan (2012), in the regularity pattern Strauss(nc; d; ), the number of clutter was fixed to be nc = 100, d was taken to be 5 and values were 0, 0.5, and 1. And, the number of true obstacles no was taken to be 20, 30, 40, 50, and 60. They observed that the NAVA tends to have higher traversal lengths for smaller values. In the current study, we want to address how the traversal length changes when both d and change under regularity by considering various values of d and simultaneously. Based on our Monte Carlo simulations, on the average the traversal lengths tend to increase as the obstacle pattern changes from uniformness to regularity. 2.3.1 Clutter Only Case In this section, we consider the case of only clutter type obstacles being inserted into the study window where obstacle pattern ranges from uniformness to regularity. Since 0 20 40 60 80 100 0 20 40 60 80 100 s t Figure 2.1: A realization of clutter disks (dashed circles) with nc = 40 from the Strauss(nc = 40; d = 9; = 0) process. Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent 13 there are 11 different values of , 22 different values of d and together with 100 Monte Carlo replication for each clutter number level nc, we have 11 22 100 = 24200 measurements. For each realization, the traversal length is computed by using RD algorithm described in Aksakalli et al. (2011). An example for the realization of this setting is given in Figure 2.1. We investigate the trends in the mean traversal length of NAVA as a function of the level of regularity of clutter points. First, we only consider the influence of values (ignore d values) on the traversal length for each clutter number level. We model the traversal length in this scenario as follows, Yij = j + jXij + ij (2.1) where i = 1; 2; :::; 24200 and j = 1; 2; 3; 4; Yij (i.e., the dependent variable) is the ith traversal length of NAVA at jth clutter level, j is the mean for clutter number level j, j is the rate of change in mean traversal length in clutter number level j, Xij (continuous covariate) is the corresponding gamma value of ith observation at jth categorical group, and ij is the associated error term. Since nc takes a few values, CSR 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 Regular . 100 105 110 115 120 125 130 mean traversal length n c =25 n c =50 n c =75 n c =100 overall Figure 2.2: Mean traversal length versus values for groups nc = 25; 50; 75; 100 together with overall plot (i.e., the average of all groups combined). we take the number of clutter levels as a categorical variable rather than a numerical 14 Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent variable. Recall that for any fixed d, when = 1 the point pattern is uniform and when = 0 the point pattern becomes completely regular. In Figure 2.2, we provide interaction plots for different clutter number levels versus values and also overall plot of the average of all groups versus values. In Figure 2.2, when the point pattern changes from uniformness to regularity the average traversal lengths seem to remain unchanged or increase slightly for all clutter number levels. We record the intercept and slope values of regression lines for each clutter number level nc (see Table 2.1). So, using ANCOVA (Seltman, 2012) with model given in Equation (2.1), we find nc = 25 nc = 50 nc = 75 nc = 100 intercept 103.84 108.36 113.79 119.96 slope 0 0.03 0.12 0.26 Table 2.1: Intercept and slope values of regression lines for each categorical group nc. out that there is a significant interaction between clutter number levels and values (pvalue<0.001). Hence, not all j’s are equal, i.e., the lines in Figure 2.2 are not all parallel to each other although the lines in the plot suggest otherwise. The next intercept nc = 50 nc = 75 nc = 100 nc = 25 <0.001 <0.001 <0.001 nc = 50 <0.001 <0.001 nc = 75 <0.001 (a) slope nc = 50 nc = 75 nc = 100 nc = 25 0.003 <0.001 <0.001 nc = 50 <0.001 <0.001 nc = 75 <0.001 (b) Table 2.2: Significant level of differences (pvalues) in intercept (a) and slope (b) for each pair of groups. natural question would be which clutter number levels have significantly different Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent 15 trends than other(s). To explain this, we repeat the model in Equation (2.1) for each pair of groups to get the pairwise significance level of differences in intercept and slope (see Table 2.2). From Table 2.2 it follows that both intercepts and slopes for clutter number levels 25, 50, 75 and 100 are significantly different from each other. Thus, the lines in Figure 2.2 have significantly different slopes except for nc = 25; 50. So far, we have not taken into consideration the influence of the d values. Figure 2.3 shows the plots of the average traversal length versus d values. Observe that the 0 2 4 6 8 10 d 100 105 110 115 120 125 130 mean traversal length n c =25 n c =50 n c =75 n c =100 overall Figure 2.3: Mean traversal length versus d values for groups nc = 25; 50; 75; 100 with overall plot (i.e., the average of all groups combined). change in d values influences the traversal lengths considerably for larger nc values. The Figure 2.3 also suggest choosing nc 75 and d 6 for larger traversal length. We fit the data set into the best quadratic polynomial because the curves in Figure 2.3 suggest that there is a concave down trend at least for nc = 75 and 100. In Figure 2.4, we provide graphs separately for each clutter number level and show corresponding fitted quadratic polynomial. Clearly, the concave down trend gets more emphasized as the number of clutter increases. Also, for any fixed value of and when d ranges from 0 to 8 the obstacle pattern gets more regular and hence yields higher traversal length. But, when d is larger than 9 units the average traversal length decreases sharply because the obstacle pattern leaves obstaclefree spaces in the region through 16 Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent which NAVA can quickly traverse without encountering any obstacle. These specific 0 2 4 6 8 10 12 d 103.4 103.5 103.6 103.7 103.8 103.9 104 104.1 mean traversal length n c =25 smoothingspline quadratic fit (a) 0 2 4 6 8 10 12 d 107.2 107.4 107.6 107.8 108 108.2 108.4 108.6 108.8 109 109.2 mean traversal length n c =50 smoothingspline quadratic fit (b) 0 2 4 6 8 10 12 d 111 112 113 114 115 116 117 mean traversal length n c =75 smoothingspline quadratic fit (c) 0 2 4 6 8 10 12 d 115 116 117 118 119 120 121 122 123 124 125 mean traversal length n c =100 smoothingspline quadratic fit (d) Figure 2.4: Mean traversal length versus d values for nc = 25; 50; 75; 100 together with quadratic polynomial fit and (nonparametric) smoothing spline with smoothing parameter p = 0:9863 . Notice that vertical axes are differently scaled. threshold values of d are closely related to the radius of disk shaped obstacle (i.e., r = 4:5 units). When d = 9, recalling that r = 4:5, the diskshaped obstacles become tangent to each other. Thus, for values of d larger than 9 the obstacles are no longer tangent and, so distances between obstacles increase resulting in a shorter path. Regarding the plots in Figure 2.4, we consider the following model for the traversal Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent 17 coefficients n groups nc = 25 nc = 50 nc = 75 nc = 100 overall 103.73 108.73 112.75 117.95 110.65 0.12 0.39 1.20 2.20 0.98 0.01 0.04 0.12 0.21 0.10 Table 2.3: Coefficients of quadratic polynomial fitted to the data at each clutter number level. intercept nc = 50 nc = 75 nc = 100 nc = 25 <0.001 <0.001 <0.001 nc = 50 <0.001 <0.001 nc = 75 <0.001 (a) linear term nc = 50 nc = 75 nc = 100 nc = 25 0.17 <0.001 <0.001 nc = 50 <0.001 <0.001 nc = 75 <0.001 (b) quadratic term nc = 50 nc = 75 nc = 100 nc = 25 0.07 <0.001 <0.001 nc = 50 <0.001 <0.001 nc = 75 <0.001 (c) Table 2.4: Significant level of differences (pvalues) of coefficient c (intercept) (a), coefficient b (linear term) (b), and coefficient a (quadratic term) (c) at each pair of clutter level. length of NAVA, Yij = j + jXij + jX2 ij + ij (2.2) where i = 1; 2; : : : ; 24200 and j = 1; 2; 3; 4 standing for nc = 25; 50; 75; 100, respec 18 Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent tively; Yij is the ith traversal length of NAVA at jth group, Xij is the value of d at ith treatment within jth group, and ij is an error term. The index j denotes the group membership (i.e., clutter level). The coefficient estimates in Model (2.2) are presented in Table 2.3. Table 2.4 suggests that the intercept values of all fitted polynomials in Figure 2.4 are statistically different from each other. The linear and quadratic trends for mean traversal length of clutter levels 25 and 50 are quite similar (see Table 2.4(b) and Table 2.4(c)), whereas the other pairs significantly different. nc = 25 1 2 3 4 5 6 7 8 9 10 11 d 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 . 103 103.2 103.4 103.6 103.8 104 104.2 104.4 104.6 (a) nc = 50 1 2 3 4 5 6 7 8 9 10 11 d 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 . 106.5 107 107.5 108 108.5 109 109.5 110 110.5 (b) nc = 75 1 2 3 4 5 6 7 8 9 10 11 d 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 . 110 111 112 113 114 115 116 117 118 119 120 (c) nc = 100 1 2 3 4 5 6 7 8 9 10 11 d 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 . 115 120 125 130 (d) Figure 2.5: Contour plots of mean traversal length versus and d values for nc = 25; 50; 75; 100. Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent 19 We also consider the contour plot of the mean traversal lengths where the impacts of both the and d values can be seen simultaneously (see Figure 2.5). The traversal lengths are within a small range, especially for nc = 25; 50 (see Figures 2.5(ab)). However, for nc = 75; 100, there is much wider range for traversal length and also a trend can be observed in these cases (see Figures 2.5(cd)). Empirically the mean traversal length is maximized when is less than 0.1 and when d is around 7 (from 6 to 8). On the average, for moderate values of d and the smaller values of we obtain longer traversal lengths. Also observe that for large values of d, values have almost no influence on the traversal length. In summary, if the whole window is going to be inserted only with the false obstacles with capability of varying the parameters of regularity (i.e., d and values), then on the average, traversal lengths tend to increase as the clutter pattern changes from uniformness to regularity. The values (esp. 0.11.0) have only mild influence on the traversal length, while d (that is especially large for d values between 68) has a substantial influence. Considering them together, from OPA’s perspective we recommend choosing moderate values of d (within 6 to 8) and smaller values ( < 0:1) in this setting so as to maximize the total traversal length of NAVA. We also observe that the value d is closely related with the radius r of diskshaped obstacle. From OPA’s perspective the case d > 2r is not desirable since for d > 2r obstacles become too sparse in the environment, whereas the optimal value of d takes place when the ratio d=r is within the interval (1:33; 1:77) together with = 0. 2.3.2 True Obstacles Only Case The simulation setting is as in the false obstacle only case in Section 2.3.1, with nc being replaced by no. We repeat the same analysis done in Section 2.3.1, but emphasize on the main differences here. For the same levels of number of obstacles, and d values, the mean traversal lengths with the true obstacles tend to be longer compared to the false obstacles. Using the model as in the Equation (2.1), we observe that on the average the traversal length tends to increase as the true obstacle pattern 20 Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent changes from uniformness to regularity provided that d < 2r. The trends in traversal length as increases is similar to the clutter only case (Figure 2.2), and the slopes and intercept estimates (Table 2.5) are significantly different from each other (Tables 2.6). no = 25 no = 50 no = 75 no = 100 intercept 104.06 111.78 137.63 204.21 slope 0 0.03 2.06 0.93 Table 2.5: Intercept and slope values of regression lines for each categorical group no. intercept no = 50 no = 75 no = 100 no = 25 <0.001 <0.001 <0.001 no = 50 <0.001 <0.001 no = 75 <0.001 (a) slope no = 50 no = 75 no = 100 no = 25 0.812 <0.001 <0.001 no = 50 <0.001 <0.001 no = 75 <0.001 (b) Table 2.6: Significant level of differences (pvalues) in intercept (a) and slope (b) for each pair of groups. When no equals 25 or 50, there still remains some obstaclefree spaces in the environment where NAVA can traverse even without any disambiguation. So, the values have almost no effect on the traversal length. When no = 75, the small values of becomes more important. When obstacles are distributed more regularly, NAVA starts to take risks (due to the greedy nature of the RD algorithm) rather than circumnavigate the zero risk route. When no = 100, then the value again loses its importance because we already have 100 obstacles which saturates the area regardless of values. The mean traversal lengths versus d values are presented in Figure 2.6. Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent 21 Note that the trends are concave down and similar to the clutter only case (see Figure 2.3). By using a model as in Equation (2.2) we observe that fitted polynomials for 0 2 4 6 8 10 d 100 120 140 160 180 200 240 260 100 mean traversal length n c =25 n c =50 n c =75 n c =100 overall Figure 2.6: Mean traversal length versus values for groups no = 25; 50; 75; 100 together with overall plot (i.e., the average of all groups combined). true obstacle levels 25 and 50 are similar (hence have similar trends), but the others are significantly different from each other. We also present the contour plot of the mean traversal lengths versus and d values in Figure 2.7 for no = 75; 100 only since for no = 25; 50 traversal length weakly depends on d and values (hence are omitted). But, when no = 75 mean traversal length is maximized for d values around 7 together with = 0. As for obstacle number level no = 100, mean traversal length tends to have higher value for values between 0.1 and 0.4, and for d values from 6 to 8. In summary, if the whole window is to be inserted only with true obstacles with capability of varying the regularity parameters (i.e., d and values), then on the average traversal length tends to increase as true obstacle pattern changes from uniformness to regularity. From OPA’s perspective, considering and d values together, we recommend choosing moderate values of d (around 6 to 8) and smaller values (especially, 0.1< < 0:4). 22 Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent no = 75 1 2 3 4 5 6 7 8 9 10 11 d 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 . 120 140 160 180 200 220 240 (a) no = 100 1 2 3 4 5 6 7 8 9 10 11 d 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 . 120 140 160 180 200 220 240 260 280 (b) Figure 2.7: Contour plots of mean traversal length versus and d values for no = 75; 100. 2.3.3 True and False Obstacles Together In this section we consider the setting in which OPA has the capability of inserting both true and false obstacles simultaneously. The obstacle pattern changes from uniformness to regularity for nc = 25; 50; 75 and no = 25; 50; 75 such that nc + no = 50; 75; 100. An example for the realization of this setting is given in Figure 2.8. From our simulations (see Sections 2.3.1 and 2.3.2), we observe that true obstacles make the traversal length much longer compared to false obstacles when the number of true and false obstacles are same. Hence, from OPA’s perspective it is more desirable to insert true obstacles rather than false obstacles (assuming OPA has sufficient amount of both true and false obstacles). For the sake of simplicity, we only present the case where nc = 25 and no = 25; 50; 75 such that nc + no = 50; 75; 100. The trend for traversal length versus values for no = 25; 50; 75 with fixed nc = 25 false obstacles is similar to the one in Figure 2.2. When the whole pattern is uniform (i.e., = 1) the average traversal lengths are smaller and when the pattern is completely regular (i.e., = 0) the average traversal lengths are larger. Based on our analysis, we Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent 23 0 20 40 60 80 100 0 20 40 60 80 100 s t Figure 2.8: The pattern is from the Strauss(nc +no = 50; d = 9; = 0) process where dashed circles (nc = 25 with centers in XC) are the 25 false obstacles and solid circles (no = 25 with centers in XO) are the 25 true obstacles. find no significant difference between the true obstacle number levels 25 and 50 (p value=0.190), but the trend for true obstacle number level 75 is totally different from the others. Regarding the influence of d, for obstacle number levels 25, 50, and 75 we still have a concave down trend similar to Figure 2.3 for mean traversal length as d values increase. The mean traversal length is maximized when d is from 5:5 to 6:5. We also present the contour plot of the mean traversal length versus and d values in Figure 2.9 for (nc; no) = (25; 50) and (nc; no) = (25; 75). In the case (nc; no) = (25; 25), traversal length seems to be not affected by d and values (hence not presented). Notice that on the average the traversal lengths tend to have larger values when values are less than 0:1 and when d values are from 6 to 8 units. For the cases when the number of false obstacles are fixed 50 and 75, we obtain very similar results as the case when the false obstacle number level is fixed to 25. Hence, the plots for nc = 50 with no = 25; 50; 75 and nc = 75 with no = 25; 50; 75 cases are not presented. 24 Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent 1 2 3 4 5 6 7 8 9 10 11 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 110 115 120 125 130 135 140 (a) 1 2 3 4 5 6 7 8 9 10 11 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 120 140 160 180 200 220 240 (b) Figure 2.9: Contour plots of the mean traversal length versus and d values when (a) (nc; no) = (25; 50), (b) (nc; no) = (25; 75). In summary, if the whole window is to be inserted with both false and true obstacles together where the overall pattern changes from uniformness to regularity, then on the average traversal lengths tend to increase. Based on our observation, in order to maximize NAVA’s traversal length, we suggest choosing small values (less than 0.1) and moderate d values (from 6 to 8) for OPA to insert obstacles in the environment. If feasible, we also recommend OPA insert more true obstacles than false obstacles, and mix them so as to trick NAVA to run into more true obstacles and hence do more disambiguations and replan its route to a longer path. 2.4 Obstacle Pattern Ranging from Uniformness to Clustering In this section, we consider the case that OPA inserts obstacles from patterns changing from uniformness to clustering. To investigate this scenario we use the Matérn clustering point process denoted Matérn( ; r0; ) wherein a given window, , first we uniformly generate ‘parent points’, and then for each parent point we generate ‘offspring points’, independently and uniformly distributed in a ball of radius r0 cen Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent 25 tered around the parent. In the Matérn( ; r0; ) process, is the intensity of ‘parent’ points from Poisson process, each parent has a Poisson( ) number of offsprings independently and uniformly distributed in a disc of radius r0 centered around the parent (Baddeley et al., 2008). Then parents are discarded from the region, and only offspring points are kept. Throughout this section the average number of points (i.e., offsprings ) per parent point is taken to be 10, and the radius of a ball (r0) around the parent varies from 5 to 50 with an increment size of 5 units. Notice that as the radius gets larger, the pattern gets closer to uniformness. In Aksakalli and Ceyhan (2012), the clustering pattern Matérn( ; r0; ), was employed with parameters = 10; r0 = 10, and = 10 so that on the average there are = 100 clutter points. And, the number of true obstacles no was taken to be 20, 30, 40, 50, and 60. They observed that NAVA tends to have lower traversal length for clustered point pattern. In the current study, we want to address how the traversal length changes when both (hence ) and r0 change under clustering by considering various values of and r0 simultaneously. We investigate three different cases. In line with Section 2.1, the whole window is inserted with clutter disks (i.e., false obstacles) only or true obstacles only, then the whole window is inserted with both true and false obstacles together (see Figure 2.10). The number of parent points is chosen to be 2, 4, 6 and 8 and for each parent there are on the average = 10 offsprings. We present the mean traversal length versus clustering radius for the false obstacle only and true obstacle only cases in Figure 2.11. If there are only false obstacles, then as the pattern changes from uniformness to clustering, the average traversal length decreases, especially for small values of cluster radius. For large values of cluster radius the trend is almost same as in the uniformness pattern. Similarly, if there are only true obstacles, as the pattern changes from uniformness to clustering, the average traversal length decreases as the clustering radius decreases; and the rate of decrease is remarkably sharp for smaller radius values. For the case when there are both false and true obstacles, we investigate the situations where the number of false 26 Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent 0 20 40 60 80 100 0 20 40 60 80 100 s t (a) 0 20 40 60 80 100 0 20 40 60 80 100 s t (b) Figure 2.10: (a) A realisation of clutter disks from the Matérn( = 2; r0 = 15; = 10) process shown in dashed circles. (b) The pattern is from the Matérn(8,15,10) process where dashed circles indicate the false obstacles (nc = 60) and solid circles indicate the true obstacles (no = 20). obstacles is fixed to nc = 20 and the number of true obstacles no takes values 20; 40, and 60. That is to say, we consider the pairs (nc; no) = (20; 20); (20; 40), and (20; 60). The trend is similar to the cases in Figure 2.11 (hence not presented). Based on our Monte Carlo simulation results, we observe that on the average traversal length tends to decrease for true obstacles, false obstacle and both as the clustering radius decreases and at a sharper rate for smaller radius values. When the pattern gets more clustered, obstacles accumulate around one or multiple points (i.e., cluster centers) and as a result it is more likely to have more empty spaces inside the window with a shorter length from s to t and this enables NAVA to attain a quick traversal with encountering few or no obstacles. Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent 27 CSR 50 45 40 35 30 25 20 15 10 Clust cluster radius (r0) 100 102 104 106 108 110 112 114 116 118 120 mean traversal length n c =20 n c =40 n c =60 n c =80 overall (a) CSR 50 45 40 35 30 25 20 15 10 Clust cluster cadius (r0) 100 110 120 130 140 150 160 170 mean traversal length n o =20 n o =40 n o =60 n o =80 overall (b) Figure 2.11: Mean traversal length versus cluster radius values when there are (a) only clutter disks with nc = 20; 40; 60; 80 together with overall plot (i.e., the average of all groups combined), (b) only true obstacles with no = 20; 40; 60; 80 together with overall plot (i.e., the average of all groups combined). Notice that vertical axes are differently scaled. 2.5 Stochastic Ordering of Traversal Lengths We next consider the stochastic ordering of traversal lengths under various obstacle patterns. Recall that NAVA is designed to traverse from source s to target t on an (s; t) walk, with each edge weighted by the Euclidean distance and the disambiguation cost of an obstacle. Given n (i.e., no+nc), let = no=nc be the ratio of true obstacles to false obstacles. Then, for any fixed value, suppose that there are m many distinct distances (avoiding loops) with ith distance occurring ki times. So, denote such an (s; t) path as ij , i = 1; 2; : : : ;m and j = 1; 2; : : : ; ki so that there are in total M = Pm i=1 ki many (s; t) paths on the usual integer grid. When there are no obstacles (n = 0) in the environment, let `ij be the corresponding Euclidean length for path ij and without loss of generality we can assume that `1j < `2j < : : : < `mj. Notice that for any fixed i, there are ki paths of equal length, i.e., `ij = `ij0 for any 28 Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent j; j0 = 1; 2; : : : ; ki. Now, let Lij be the traversal length for path ij in the presence of true or false obstacles. In the absence of obstacles (n = 0) we have the equality Lij = `ij for all i; j. When there are only false obstacles (n > 0 and = 0, i.e., no = 0), then we need to update the value of Lij by using the weight function defined by the RD algorithm. Recall that, when there are only clutter disks the set X = XC where XC is the set of points of centers of disk shaped obstacles Dr(x) (a disc of radius r centered at a point x) for x 2 XC with fixed radius r > 0. And, for x 2 X, p(x) is the probability that Dr(x) is a true obstacle with c(x) being the disambiguation cost of Dr(x). In our case, the disambiguation cost c(x) = c > 0 is fixed. If we ignore the probabilities, we have Lij = `ij + wij c with wij = X x2XC 1Dr(x)\ ij 6=; where wij gives the number of obstacles intersecting the edges of path ij . On the other hand, if we do consider the probabilities of disk shaped obstacle being true obstacle, then we update each edge of path ij . Namely, if e 2 ij then, w(e) = `(e) + 1 2 F(e) with F(e) = X x2XC 1fDr(x)\e6=;g c 1 p(x) So that Lij = P e2 ij w(e). Notice that in the updated version for any fixed i, Lij 6= Lij0 in general, because the number of obstacles intersecting the paths of same Euclidean length ij and ij0 may not be equal. If we consider all Lij values in the clutter only case in an array (1 by M) with M many entries so that L(k) is the kth smallest length, then RD algorithm choses L(k) over L(k0) for k < k0. Let LS ij and LU ij be the traversal lengths of path ij under regularity ( = 0) and uniformness ( = 1), respectively. Under regularity, the path ij is more likely to intersect an obstacle compared to uniformness. So, it is more likely that LU ij st LS ij , i.e., the traversal length is stochastically smaller under the uniformness compared to that under regularity. Indeed, one can extend the above argument to the case Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent 29 that at fixed d, let L ij denote the traversal length for Strauss(n; d; ) pattern. Then, L ij st L 0 ij whenever < 0. Similarly, Lr0 ij be the traversal length for Matérn( ; r0; ) pattern and let LM ij denote the traversal length of path ij under clustering (r0 0) for fixed ; . Then for r0 < r00 , Lr0 ij st Lr00 ij since under Matérn( ; r0; ) pattern any ij is less likely to hit an obstacle compared to that under Matérn( ; r00 ; ) whenever r0 < r00 . So, we have proved the following: Proposition 2.5.1 : Whenever X = XC (i:e:;OPA only inserts false obstacles to our standard window [0; 100] [0; 100]), we have (i) LM ij st LU ij st LS ij (defined as above). (ii) L ij st L 0 ij for < 0. (iii) Lr0 ij st Lr00 ij for r0 < r00 . In the true obstacle only case (n > 0 and = 1, i.e., nc = 0), if an obstacle intersects a path then it renders that path nontraversable. So, if a shorter path hits a true obstacle, RD resets the algorithm whenever NAVA hits the obstacle and then picks another longer path. That is to say, when we have true obstacles the total number of distinct traversable paths reduces compared to the clutter only case. Hence, traversal length in the true obstacle case tends to be larger compared to that in the false obstacle only case. Furthermore, by the same reason as above the same stochastic orderings occur under regularity, clustering and uniformness patterns. Proposition 2.5.2 : Whenever X = XO (i:e:;OPA only inserts true obstacles to our standard window [0; 100] [0; 100]), we have (i) LM ij st LU ij st LS ij (ii) L ij st L 0 ij for < 0. (iii) Lr0 ij st Lr00 ij for r0 < r00 . 30 Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent One can also write stochastic ordering for clutter only and true obstacle only cases as follows. Let LC ij be the traversal length of path ij under the clutter only case and LO ij be the traversal length of path ij under the true obstacle only case. Then with the same obstacle pattern of nc = n in the clutter only case and no = n in the true obstacle only case we have, Proposition 2.5.3 : With the same obstacle pattern and the same number of obstacles, LC ij st LO ij : This holds because if true obstacles were also clutter, then we would have LC ij d=LO ij . But, when NAVA runs into a true obstacle, then it has to stop and choose a longer traversable path while if the obstacle was false NAVA would traverse through it. Since the cost of disambiguation is same, we have a reduction in the number of traversable paths under true obstacle only case with LC ij values being more likely to be smaller than LO ij values. Let LC;O ij be the traversal length of path ij under the clutter & true obstacle cases. Corollary 2.5.3.1 : With the same obstacle pattern and the same number of obstacles, LC ij st LC;O ij st LO ij : The result also extends to the mixed obstacle case. One can also show that with everything else being same, and = no=nc and keeping the number of clutter equal, we have L ij st L 0 ij whenever < 0 (but, notice that this result does not extend if the number of clutter values are different). Indeed, this case can be generalized whenever total number of obstacles is fixed (we will be studied in detail in Section 2.6). Proposition 2.5.4 : Whenever X = XC [ XO, and nc is fixed, then for < 0 (i) LM ij st LU ij st LS ij Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent 31 (ii) L ij st L 0 ij for < 0. (iii) Lr0 ij st Lr00 ij for r0 < r00 . To conclude, at any path ij , the cost under regularity would tend to be higher compared to uniformness. The main reason for this is that under regularity, it is more likely for an obstacle to be placed on an edge on ij compared to uniformness, since under regularity obstacles will be more evenly distributed compared to uniformness. On the other hand, for any path ij the cost under clustering would tend to be lower compared to uniformness. Because, under clustering the obstacle is less likely to hit an edge on ij compared to uniformness. Since, under clustering obstacles will be accumulated around parents or hotspots and thus form clumps so that ij has more chance of not falling inside these clumps compared to uniformness. Thus, if the obstacle pattern is regular then the probability of maximizing the mean traversal length of NAVA is higher than any other cases. 2.6 Mean Traversal Length Versus Ratio of Number of True to False Obstacles So far we denote the number of clutter (false obstacles) by nc and the number of true obstacles by no, and n = nc +no and we compute the traversal lengths for each nc; no combinations. In this section, we investigate the trends for mean traversal length with respect to the ratio = no=nc when the sum no + nc is fixed. In our experimental setting the total number of obstacles to be inserted into the study window is equal to 100. So, the case no = 0 corresponds to deploying the study window only with clutter, and nc = 0 means inserting only true obstacles. To measure the traversal length for intermediate values of pairs of (no; nc), we introduce a new variable = no=nc taking the values f0; 1=4; 1=2; 1; 2; 4;1g. Thus, extreme cases of = 0 is equivalent to the case no = 0 and = 1 is equivalent to the case nc = 0. In the following subsections, we investigate the case where the obstacle pattern changes from the complete spatial uniformness (uniformness) to regularity. We 32 Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent use 11 11 partition of ( ; d) 2 (0; 1) (1; 11) (i.e., and d are parameters of Strauss(n; d; )), so our current investigation is much more detailed for compared to Aksakalli and Ceyhan (2012), and investigation for d is different from that in Aksakalli and Ceyhan (2012). We also investigate the case where the obstacle pattern changes from the uniformness to clustering. In our experimental setting, we choose the values f1; 2; 3; :::; 10; 11g and the radius r0 around the parent varies from 5 to 50 units with an increment size of 5 units (i.e., and r0 are parameters of Matérn( ; r0; )). As the radius gets larger, the pattern formed is getting closer to uniformness. In Aksakalli and Ceyhan (2012), the cluster radius r0 and the average offspring per parent were both taken to be 10. In our study, we increase the range of r0 and values. 2.6.1 Obstacle Pattern Ranging from Uniformness to Regularity Our goal is to determine the trend for the mean traversal length of NAVA as a function of the level of regularity. In our experimental setting, there are 11 different values of d (1; 2; :::; 10; 11), 11 different values of (0; 0:1; :::; 0:9; 1), 7 different values of (0, 1/4, 1/2, 1, 2, 4, inf), and 100 Monte Carlo simulations for each of these combinations. First, we only consider the influence of values, and then we will discuss the effect of d values. We model the traversal length as in Equation (2.1) where the categorical level will be . Since there are 7 categorical groups, for simplicity we split the corresponding interaction plots into two parts. In Figure 2.12(a) we show the interaction plot of mean traversal length versus values for groups = 0; 1=4; 1=2; 1 and the overall plot (i.e., the average of all 7 distinct groups). And, in Figure 2.12(b) we show the interaction plot of mean traversal length versus values for groups = 1; 2; 4;1 and the overall plot. We observe that the intercept values for = 1=4; 1=2 are not significantly different from = 0 (pvalues 0.4071, 0.0524, respectively). And, the slopes of regression lines for = 1=4; 1=2; 1 are not significantly different than the slope of group = 0 (p values 0.9817, 0.7207, 0.1984, respectively). Moreover, the slope values for all groups Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent 33 CSR 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 Regular . 120 125 130 135 140 145 150 155 160 mean traversal length ;=0 ;=1/4 ;=1/2 ;=1 overall (a) CSR 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 Regular . 120 130 140 150 160 170 180 190 200 210 220 230 mean traversal length ;=1 ;=2 ;=4 ;=Inf overall (b) Figure 2.12: Mean traversal length versus values for groups (a) = 0; 1=4; 1=2; 1 together with overall plot (the average of all 7 distinct groups), (b) = 1; 2; 4;1 together with overall plot (the average of all 7 distinct groups). Notice that vertical axes are differently scaled. are positive (Table 2.7), which means that the mean traversal length tends to increase as the gamma ( ) values decrease. In all groups, the average traversal length is maximized when = 0 (i.e., when the pattern is completely regular) and the mean traversal length tends to increase as gets larger (i.e., intercept value increases as increases). It is also interesting that the overall trend of mean traversal length is almost the same as the case = 2 (see Figure 2.12(b)). Moreover, in Figure 2.13 we show the plot of mean traversal length versus values for various choices of and the contour plot of mean traversal length versus and values. In Figure 2.13(a), the mean traversal length tends to be higher (and thus maximized) when = 0 for each values. And, in Figure 2.13(b) layers of color are formed for each different values of implying that the mean traversal length tends to be larger as value increases. For fixed value, the trend when = 0 is different from other values of showing that the traversal length is maximized when = 0. Figure 2.13(b) also summarizes the plots given in Figure 2.12. 34 Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent 0 1/4 1/2 1 2 4 Inf ; 120 140 160 180 200 220 mean traversal length .=0 .=0.4 .=0.6 .=1.0 (a) 0 1/4 1/2 1 2 4 Inf ; 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 . 120 130 140 150 160 170 180 190 200 210 (b) Figure 2.13: (a) Mean traversal length versus values for groups = 0; 0:4; 0:6; 1, (b) average contour plot of mean traversal length versus and values. = 0 = 1=4 = 1=2 = 1 = 2 = 4 = 1 intercept 119.50 120.69 122.29 126.73 137.52 154.55 201.07 slope 0.29 0.29 0.36 0.56 1.15 2.33 1.14 Table 2.7: Intercept and slope values of regression lines for each categorical group . We also record the intercept and slope values of regression lines for each categorical group (see Table 2.7). If we repeat the model as in Equation (2.1) for each pair of groups, then we will get the pairwise significance levels of differences in intercept and slope similar to Table 2.2. Thus, we have more information about how exactly each categorical group differs from one another. For instance, Table 2.7 and Figure 2.12 shows that although the intercepts are different for = 2 and = 1 groups, the trend for mean traversal length of NAVA is similar since their slopes (1:15 and 1:15, respectively) are not significantly different (pvalue=0:974). Next, we consider the effect of d values on mean traversal length of NAVA for different groups. Similar to Figure 2.3, we will fit the data set into the best quadratic Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent 35 1 2 3 4 5 6 7 8 9 10 11 d 115 120 125 130 135 140 145 150 155 160 165 mean traversal length ;=0 ;=1/4 ;=1/2 ;=1 overall (a) 1 2 3 4 5 6 7 8 9 10 11 d 120 140 160 180 200 220 240 260 mean traversal length ;=1 ;=2 ;=4 ;=Inf overall (b) Figure 2.14: Mean traversal length versus d values for groups (a) = 0; 1=4; 1=2; 1 together with overall plot (the average of all 7 distinct groups), (b) = 1; 2; 4;1 together with overall plot (the average of all 7 distinct groups). Notice that vertical axes are differently scaled. polynomial and record the corresponding coefficients because the curves in Figure 2.14 suggest a concave down trend. In Figure 2.14, we provide graphs separately for levels = 0; 1=4; 1=2; 1 and = 1; 2; 4;1 together with overall plot (the average of all 7 distinct groups) in order to observe the general trend. Clearly, mean traversal length gets higher, reaches a peak and then decreases as d values increase. And, concave down trend gets more emphasized as the increases. Moreover, in Figure 2.15 we show the plot of mean traversal length versus values for various choices of d and the contour plot of mean traversal length versus d and values. In Figure 2.15(a), the mean traversal length tends to be higher when d = 6 (and similarly between 5 and 8) for each values. Observe that when d gets smaller values (less than 3) or larger values (greater than 9), then the mean traversal length tends to be smaller than the case d is between 5 and 8. In Figure 2.15(b) layers of color are formed for each different values of implying that the mean traversal length tends to be larger as value increases. Figure 2.15(b) also summarizes the 36 Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent 0 1/4 1/2 1 2 4 Inf ; 100 150 200 250 mean traversal length d=1 d=4 d=6 d=10 (a) 0 1/4 1/2 1 2 4 Inf ; 1 2 3 4 5 6 7 8 9 10 11 d 120 140 160 180 200 220 (b) Figure 2.15: (a) Mean traversal length versus values for groups d = 1; 4; 6; 10, (b) average contour plot of mean traversal length versus d and values. plots (concave down trend) given in Figure 2.14. We also present the contour plot of the mean traversal lengths versus and d values in Figures 2.16 and 2.17. Notice that on the average the traversal length tends to have larger values when values are less than 0.1 and when d values are concentrated around 7 for levels = 0; 1=4; 1=2; 2. As the values increases, the contour plots get more emphasized and for = 1 level the mean traversal length is maximized when is less than 0.1 and d is around 5 and 7. In Figure 2.17, for = 4 the average traversal length is maximized when is less than 0.1 and d is around 5 and 8. Unlike previous cases, for = inf the mean traversal length tends to have higher values when is between 0.1 and 0.4 together with d values between 6 and 8. Based on the overall contour plot of levels (see Figure 2.17(d)), we observe that the NAVA tends to have higher mean traversal length for smaller values (i.e., smaller than 0.1) and moderate d values around 7. As a consequence, for fixed number of obstacles n = no+nc the ratio = no=nc is also important in maximizing the traversal length of NAVA. So, Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent 37 ; = 0 1 2 3 4 5 6 7 8 9 10 11 d 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 . 110 115 120 125 130 (a) ; = 1=4 1 2 3 4 5 6 7 8 9 10 11 d 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 . 110 115 120 125 130 135 (b) ; = 1=2 1 2 3 4 5 6 7 8 9 10 11 d 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 . 110 115 120 125 130 135 140 (c) ; = 1 1 2 3 4 5 6 7 8 9 10 11 d 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 . 110 120 130 140 150 160 (d) Figure 2.16: Overall average contour plots of the mean traversal length versus and d values for (a) = 0, (b) = 1=4, (c) = 1=2, and (d) = 1. Proposition 2.6.1 : Whenever X = XC [ XO, and n = nc + no is fixed, then L ij st L 0 ij for < 0. Thus, from OPA’s perspective considering and d values together, we recommend choosing moderate values of d (around 7) and smaller values (less than 0:1). And, given the total number of obstacles (n = nc + no is fixed), we recommend to choose value as large as possible so as to maximize the total traversal length of NAVA. 38 Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent ; = 2 1 2 3 4 5 6 7 8 9 10 11 d 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 . 120 130 140 150 160 170 180 190 200 210 220 (a) ; = 4 1 2 3 4 5 6 7 8 9 10 11 d 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 . 120 140 160 180 200 220 240 (b) ; = 1 1 2 3 4 5 6 7 8 9 10 11 d 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 . 120 140 160 180 200 220 240 260 (c) Overall (the average of all ; levels) 1 2 3 4 5 6 7 8 9 10 11 d 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 . 120 130 140 150 160 170 (d) Figure 2.17: Overall average contour plots of the mean traversal length versus and d values for (a) = 2, (b) = 4, (c) = 1, and (d) overall (the average of all levels). 2.6.2 Obstacle Pattern Ranging from Uniformness to Clustering In this Section, we investigate the trend for mean traversal length of NAVA as a function of the level of clustering. To generate the clustering point pattern we use Matérn( ; r0; ) as in Section 2.4. In our experimental setting, there are 11 different values of (i.e., 1; 2; : : : ; 11), 11 different values of cluster radius r0 (i.e., 5; 10; : : : ; 50), Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent 39 7 different values of (i.e., 0; 1=4; 1=2; 1; 2; 4;1), and 100 Monte Carlo simulations for each these combinations. Since the total number of obstacle is fixed to n = 100, so on the average the value automatically equals to n= . Ignoring , in Figure 2.18 we observe that the mean traversal length tends to decrease as the cluster radius r0 decreases for each level (concave down decrease trend). That is to say, the mean traversal length tends to decrease as the obstacle pattern changes from uniform to clustering. In all groups, the average mean traversal length is maximized when the obstacle pattern is uniform and minimized when the obstacle pattern is clustered. The trends is concave down, and as the value increases the decrease for mean traversal length gets more emphasized. CSR 50 45 40 35 30 25 20 15 10 Clust r0 100 105 110 115 120 125 130 135 140 145 150 mean traversal length ;=0 ;=1/4 ;=1/2 ;=1 overall (a) CSR 50 45 40 35 30 25 20 15 10 Clust r0 100 120 140 160 180 200 220 mean traversal length ;=1 ;=2 ;=4 ;=Inf overall (b) Figure 2.18: Mean traversal length versus r0 values for groups (a) = 0; 1=4; 1=2; 1 together with overall plot (the average of all 7 distinct groups), (b) = 1; 2; 4;1 together with overall plot (the average of all 7 distinct groups). Notice that vertical axes are differently scaled. Ignoring r0, in Figure 2.19 the mean traversal length tends to increase as the number of parent points increases for each level (concave down increase trend). But, the increase in trend slows down after = 5 because as the number of parent points increases the obstacles pattern gets less clustered. In both Figures 2.18 and 40 Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent 1 2 3 4 5 6 7 8 9 10 11 5 100 115 120 125 130 135 140 mean traversal length ;=0 ;=1/4 ;=1/2 ;=1 overall (a) 1 2 3 4 5 6 7 8 9 10 11 5 110 120 130 140 150 160 170 180 mean traversal length ;=1 ;=2 ;=4 ;=Inf overall (b) Figure 2.19: Mean traversal length versus values for groups (a) = 0; 1=4; 1=2; 1 together with overall plot (the average of all levels), (b) = 1; 2; 4;1 with overall plot (the average of all levels). Notice that vertical axes are differently scaled. 2.19, the overall plot is similar to the group level = 2. Moreover, in Figure 2.20 we show the plot of mean traversal length versus values for various choices of r0 and the contour plot of mean traversal length versus r0 and values. In Figure 2.20 (a), the mean traversal length tends to be higher when r0 = 50 (i.e., eventually CSR) for each values. In Figure 2.20 (b) layers of color are formed for each different values of implying that the mean traversal length tends to be larger as value increases. Figure 2.20 (b) also summarizes the plots (concave down trend) given in Figure 2.18. Similarly, in Figure 2.21 (a) as the number of parent points ( ) decreases (i.e., eventually clustering) the mean traversal length tends to be smaller for each value. And, in Figure 2.21 (b) the mean traversal length increases as the value increases. In summary, we observe that from uniformness to clustering, traversal length tends to decrease. Hence, clustering obstacle patterns are not preferable in OPA’s perspective. That is, OPA should avoid clustering obstacle patterns as much as possible and simply choose uniformness if uniformness and various clustering schemes Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent 41 0 1/4 1/2 1 2 4 Inf ; 100 120 140 160 180 200 220 mean traversal length r0=5 r0=15 r0=30 r0=50 (a) 0 1/4 1/2 1 2 4 Inf ; 5 10 15 20 25 30 35 40 45 50 CSR r0 110 120 130 140 150 160 170 180 190 200 (b) Figure 2.20: (a) Mean traversal length versus values for groups r0 = 5; 15; 30; 50, (b) average contour plot of mean traversal length versus r0 and values. 0 1/4 1/2 1 2 4 Inf ; 110 120 130 140 150 160 170 mean traversal length 5=1 5=3 5=6 5=10 (a) 0 1/4 1/2 1 2 4 Inf ; 1 2 3 4 5 6 7 8 9 10 11 5 115 120 125 130 135 140 145 150 155 160 165 (b) Figure 2.21: (a) Mean traversal length versus values for groups = 1; 3; 6; 10, (b) average contour plot of mean traversal length versus and values. are the only available options. So far, we have observed that the mean traversal length is maximized for moderate values of d (from 6 to 8) together with small values of (less than 0.1). We also observed that to maximize the traversal length of navigating 42 Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent agent (NAVA), obstacle placing agent (OPA) should insert more true obstacles than false obstacles. Under these circumstances, we can also decide in what proportion of true obstacles to false obstacles should be used so as to maximize the traversal length of NAVA. We plot the mean traversal length versus no and nc values for pairs (d; ) = (6; 0), (d; ) = (7; 0), and (d; ) = (8; 0). In Figure 2.22, we see that on the average the mean traversal length is maximized when no is around 80 together with nc less than 20. Mean Traversal Length 10 20 30 40 50 60 70 80 90 100 nc 10 20 30 40 50 60 70 80 90 100 no 120 140 160 180 200 220 240 (a) Mean Traversal Length 10 20 30 40 50 60 70 80 90 100 nc 10 20 30 40 50 60 70 80 90 100 no 120 140 160 180 200 220 240 (b) Mean Traversal Length 10 20 30 40 50 60 70 80 90 100 nc 10 20 30 40 50 60 70 80 90 100 no 120 140 160 180 200 220 240 260 (c) Figure 2.22: Overall average contour plots of the mean traversal length versus no and nc values when (a) (d; ) = (6; 0), (b) (d; ) = (7; 0), and (c) (d; ) = (8; 0). Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent 43 2.7 Summary We investigate how the traversal length of NAVA changes as the obstacle pattern changes from uniformness to regularity, and from uniformness to clustering for various pairs of numbers of clutter and true obstacles nc; no. In our experimental setting, we simulated various combinations of both false and true obstacle number levels. Based on our investigation with extensive Monte Carlo simulations, we found that traversal lengths are higher under regularity than those under uniformness which tend to be higher that those under clustering. Under regularity, we investigate the influence of the two parameters d and . Given the number of obstacles, the is the intensity of the number of pairs of distinct points lying closer than d units. In all cases, clutter only, true obstacle only and mixture of false and true obstacle, we recommend choosing moderate values of d (around 7) together with small values of (between 0 and 0:1). Moreover, given the total number of obstacles, the ratio of true versus false obstacles is another important factor for the traversal length. Taking all of these into consideration, to achieve optimal value we recommend choosing moderate values of d (around 7) and smaller values (less than 0:1). And, given the total number of obstacles (i.e., n = nc + no is fixed), we also recommend choosing value as large as possible in order to maximize the total traversal length of NAVA. Under clustering obstacle pattern, the cluster radius r0 and the number of parent points are found to be important. Here, the stands for the number of accumulation points and r0 stands for the radius at which obstacles accumulate around the accumulation point. We do not recommend choosing clustering point pattern since it is not feasible. The number of true obstacles clearly dominates the number of false obstacles, again the parameter plays an important role in determining the trend of traversal length when the total number of given obstacles is fixed. Hence, all things considered for optimal values we do not recommend using the clustering obstacle pattern in order to maximize the total traversal length of NAVA. When the obstacle pattern and the number of obstacles kept same, then the traver 44 Chapter 2: Choosing the Optimal Obstacle Pattern Against a Disambiguating Navigation Agent sal length under cluttering pattern is stochastically less than or equal to the traversal length under uniformness, and which is also stochastically less than or equal to the traversal length under regularity. Thus, mean traversal length is maximized then the obstacle pattern is regular. Moreover, the traversal length in clutter only case is stochastically less than or equal to the traversal length in mixture case which is also stochastically less than or equal to the traversal length in true obstacle case only. Concerning the precision of sensor, as the sensor of NAVA increases the traversal length tends to be the more accurate and yields closer value to optimal solution. In our future research, we are going to investigate the case where OPA places both true and false obstacles deterministically. We want to investigate whether knowing the exact locations of obstacles gains an advantage for OPA or not. Besides, concerning the theoretical results OPD has many similarities with classical CTP problem. We will prove our results for more general graphical settings by inspiring from current theoretical results belonging to CTP problem. In OPD problem only disambiguation capability was considered, but we also like to consider the problem with neutralization capability. Under feasible conditions, we will study the OPD problem by both disambiguation and neutralization capabilities together depending on the circumstances that NAVA and OPA encounters. Another aspect of OPD problem is considering the study window in a 3dimensional setting. That is to say, we would like to investigate the OPD problem in higher dimension as well starting from three dimensional case. In 3D case, NAVA may represent the submarine that wishes to reach from one source point to a target destination avoiding underwater mines. And, OPA may be the opponent forces wishing to place mines so as to maximize the total traversal length of NAVA. Chapter 3 M2K ALGORITHM FOR THE OPD PROBLEM 3.1 Introduction In this section, we investigate how traversal length behaves for various M2k algorithms. We will use the same experimental setup of Aksakalli and Ceyhan (2012), but compute the traversal length by M2k algorithm for various integer values of k. Based on our Monte Carlo simulations, we observe that the trends for mean traversal length computed by RD algorithm and M2k algorithm are essentially similar. So, instead using the greedy algorithm we recommend using M2k algorithm where few disambiguations take place, and hence decrease the complexity cost compared to the original RD algorithm. 3.2 Experimental Setting 3.2.1 Background Clutter Generation In our simulation setting, we use 6 different types of point processes for sampling centers of diskshaped clutters. These are homogeneous (HPP) and inhomogeneous (IP) Poisson processes, Matérn and Thomas point processes, and Hardcore and Strauss point processes. Among these Matérn and Thomas processes are clustered point processes, while Hardcore and Strauss processes are regular point processes (Baddeley, 2010). The number of clutter is fixed to 100, and the number of obstacles are 20,30,40,50 and 60 respectively. As for obstacle window forms, we use a total of 19 different obstacle placement patterns. Obstacles are uniformly sampled within four different window forms: the entire background window itself (P), linear strips (L), Vshaped (V) and Wshaped (W) polygonal windows. 46 Chapter 3: M2k Algorithm for the OPD Problem Formally, a spatial point process X is a finite random subset of a bounded region R2. A realization of this point process, on the other hand, is called a spatial point pattern. Mainly there are three types of spatial point patterns; independent patterns, cluster patterns where points tend to be close to one another and regular patterns where points tend to repel each other. In this section, we consider two patterns from each one of these three groups and the background clutter disk centers are generated from those six spatial point processes (Aksakalli and Ceyhan (2012)). The homogeneous Poisson process with constant intensity is also called complete spatial randomness (CSR), where the intensity will be denoted by CSR( ). For any region , the CSR point process has four properties: (1) the number of points in is a Poisson random variable, (2) number of points in any two disjoint regions and 0 are independent random variables, (3) the expected number of points in is area( ), and (4) points in are independently and uniformly distributed (given the number of points). In our case, is taken to be 100. As for the inhomogeneous Poisson process, it is a modification of CSR where the intensity is not constant, but varies from location to location. Specifically, the intensity is a function in two dimensional Euclidean space. Let IP( (h)) denote the inhomogeneous Poisson process with intensity (h) where h 2 R2. Here, the intensity function (h) specifies the value of on the plane. Properties of IP( (h)) are the same as those of CSR( ) with the last two properties modified as follows: (30) the expected number of points in is R (h)dh, and (40) points in are independently identically distributed (i.i.d) with probability density f(h) = (h) R (h)dh 1. In our case, we take the intensity function as (x; y) = 0:037e(10y)=40 as in Aksakalli and Ceyhan (2012). Notice that, the intensity only depends on y and decreases as y increases. Here, obstacles get denser as one gets closer to a target point. An illustration of both CSR and IP is shown in Figure 3.1. For clustering, the Matérn point process, denoted by M( ; ; ), is constructed by first generating a Poisson point process of “parent” points with intensity . Each parent point is then replaced by a random cluster of points where the number of points in each cluster is sampled from a Poisson distribution with parameter . These so Chapter 3: M2k Algorithm for the OPD Problem 47 l l l l l l l l l l l l l l l l l l l l ll l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l (a) CSR l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l (b) Inhomogeneous Poisson Figure 3.1: Sample realizations from homogeneous and inhomogeneous point processes. The parameters are: (a) CSR(100) and (b) IP 0:037e(10y)=40 . Indeed, on the average 100 points are generated by using these distribution parameters, but by using the rejection sampling we fix them to exactly 100 points. called “child” points are placed independently and uniformly inside a disk with fixed radius r centered at the parent point. In our case, we work with M(10; 10; 10). Similar to the Matérn point process, the Thomas process, denoted by T( ; ; ), is constructed by first generating a Poisson point process of “parent” points with intensity . A random cluster of points replaces each parent point with the number of points per cluster being sampled from a Poisson distribution with parameter . In contrast with the Matérn point process, positions of these child points in the Thomas point process are isotropic Gaussian displacements centered at the cluster parent location with standard deviation . In our case, we work with T(10; 10; 5) as in Aksakalli and Ceyhan (2012). An illustration of both Matérn and Thomas is shown in Figure 3.2. For regular, the probability density function of the hardcore process is that of the Poisson process with intensity function conditioned on the event that no two points generated by the process are closer than d units apart, hence denoted by 48 Chapter 3: M2k Algorithm for the OPD Problem l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l ll l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l (a) Matérn l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l (b) Thomas Figure 3.2: Sample realizations from Matérn and Thomas point processes. The parameters are: (a) M(10; 10; 10) and (b) T(10; 10; 5). Indeed, on the average 100 points are generated by using these distribution parameters, but by using the rejection sampling we fix them to exactly 100 points. HC( ; d). The Strauss process, denoted S( ; d; ), on the other hand, generalizes the hardcore process by incorporating a 2 [0; 1] parameter that controls of the interaction between points. The process exhibits more regularity for smaller values of , and less regularity for large . For = 0, the Strauss process becomes hardcore process, and for = 1, it reduces to CSR. In our case, we work with HC(100; 5) and S(100; 5; 0:5) as in Aksakalli and Ceyhan (2012). An illustration of both Hardcore and Strauss is shown in Figure 3.3. In our computational experiment (see Section 2.2), the graph G = (V;E) is the 8 adjacency integer discretization of [0; 100] [0; 100] with s = (50; 100) and t = (50; 1). Each disk has a fixed radius of r = 4:5 units and the disk centers are sampled inside [10; 90] [10; 90] ensuring that there always exists(possibly very long) a s; t walk. The disambiguation cost is taken to be c = 5. And, clutter probabilities are sampled from Beta(2,6), whereas obstacle probabilities are sampled from Beta(6,2). These choices Chapter 3: M2k Algorithm for the OPD Problem 49 l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l (a) Hardcore l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l l (b) Strauss Figure 3.3: Sample realizations from Hardcore and Strauss point processes. The parameters are: (a) HC(100; 5) and (b) S(100; 5; 0:5). Indeed, on the average 100 points are generated by using these distribution parameters, but by using the rejection sampling we fix them to exactly 100 points. are made in line with the ones in Aksakalli and Ceyhan (2012) and Priebe et al. (2005). Also, we let the significance level of the test be 0:01. In particular, let P = [10; 90] [10; 90] which will be the window for clutter center points. In all six types of clutter distributions, the sample size generated is equal to exactly 100 points. As for obstacle window forms, we consider a total of 19 different sampling windows. The first is the polygon P = [10; 90] [10; 90], there are 8 different linear windows of width equals to 10 units and with their top left corner y coordinate being 90,80,...,20, and 5 different Vshaped and Wshaped windows, respectively, with their top left corner y coordinate being 90,80,...,50. The difference between the top and bottom y coordinates of each one of these 10 polygons is taken to be 50 units. The width of polygonal shape is 10 units (Aksakalli and Ceyhan, 2012). For example, L70 is the polygon whose four corner points are (10,70), (90,70), (90,60) and (10,60) clockwise starting with the top left corner. We also take number 50 Chapter 3: M2k Algorithm for the OPD Problem of obstacles to be 20, 30, 40, 50, and 60 for each of the 19 obstacle sampling windows. Thus, the realization of obstacle patterns are denoted by the sampling window followed by the number of obstacles. For example, P:40 and L70:40 refer to the obstacle patterns sampled within the P and L70 windows, respectively, with 40 obstacle center points inside their respective windows. These choices also ones made as in Aksakalli and Ceyhan (2012) for comparative purposes. Hence, the treatment factors are the “background clutter type”, the “obstacle placement window” and the “number of the obstacles”. The first has 6 different types, the second has 19 types and the third has 5 different types resulting in a total of 570 treatment combinations. Our main goal is to investigate how traversal length changes according to treatment factors when the NAVA uses the greedy RD algorithm and its variants M2k algorithm. 3.3 M2k Algorithm In the original version of RD algorithm, the average number of edges that diskshaped obstacles intersect in a 8discretization setting is 88. So, prior to the traversal, NAVA assigns edge weight to all edges intersecting the disks using the cost of disambiguation and the probability of being a true obstacle of a disk (Chapter 5). But, M2k algorithm is based on the effective choice of the number disambiguations. As an example let us consider the case k = 3, then NAVA updates only 23 edges for each diskshaped obstacle and assigns 1 for the rest. An example of the choice of 8 disambiguation points for disks are shown below (see Figure 3.3). M16 and M4 algorithms are defined analogously. The advantage of using the M2k algorithm is that the complexity time is reduced when computing the traversal length of NAVA and the mean traversal length is well estimated. For example, the complexity time of running M16 algorithm is at least 5 times faster than the RD algorithm, and the mean traversal length estimated by M16 algorithm deviates at most 2:5% relative error from the traversal length estimated by RD algorithm. Chapter 3: M2k Algorithm for the OPD Problem 51 Figure 3.4: A total of 8 disambiguation points are labeled in each diskshaped obstacle. 3.4 Repeated Measures ANOVA Our data set consists of traversal lengths computed by the RD algorithm and its variants under various conditions that we have described above. Hence, the background clutter types are Complete Spatial Randomness (CSR), inhomogeneous Poisson (IP) pattern, Matérn (M) pattern, Thomas (T) pattern, hardcore (HC) pattern, and Strauss (S) pattern. For simplicity the clutter types are numbered from 1 to 6, which in turn, correspond to CSR, IP, M, T, HC, and S patterns, respectively. Similarly, the obstacle window types are numbered from 1 to 19 corresponding to P, L90, L80,..., L20, V90, V80,..., V50, W90, W80,..., W50, respectively. The obstacle number levels are also numbered from 1 to 5 corresponding to 20, 30, 40, 50, 60, respectively. Thus, we denote the traversal length as Lijkl which is the traversal length of the measurement l for clutter type i, obstacle window type j, obstacle number level k with l = 1; 2; :::; 100; i = 1; 2; :::; 6; j = 1; 2; :::; 19; and k = 1; 2; :::; 5, respectively. Note that Lijkl; Lij0kl; Lijk0l; Lij0k0l are estimated on the same background clutter type i, and hence they are potentially correlated. Similarly, the expected traversal lengths within the respective obstacle window types or obstacle number levels can also correlated (positively or negatively). In order to deal with and take into account such possible correlations, we use repeated measures ANOVA. We use the repeated mea 52 Chapter 3: M2k Algorithm for the OPD Problem sures ANOVA to compare the traversal length differences between treatment factors. The conditions of repeated measures ANOVA are similar to that of usual ANOVA, except that independence is not required and an assumption about the relations among the repeated measures is added. The repeated measures ANOVA assumptions are; (i) the dependent variable is normally distributed, (ii) the homogeneity of covariance matrices is required, (iii) independence between predictor factors, and (iv) sphericity, which refers that the variance of repeated measures are all equal, and the correlations among the repeated measures are all equal (Aksakalli and Ceyhan, 2012). The main advantage of using the repeated measures ANOVA rather than standard ANOVA is that we obtain more precise information in comparison of 
Format  
Material type  Text / Dissertation 
Rating 



A 

B 

H 

J 

K 

S 

U 

V 



