Mathematics PhD Thesis Defense by Polat Charyyev

*******************************************************************

KOÇ UNIVERSITY

GRADUATE SCHOOL OF SCIENCES & ENGINEERING

MATHEMATICS

PhD THESIS DEFENSE BY POLAT CHARYYEV

******************************************************************

Title: The Optimal Obstacle With Disambiguation Problem

Speaker: Polat Charyyev

Time: August 04, 2017, 16.00

Place: ENG 208

Koç University

Rumeli Feneri Yolu

Sariyer, Istanbul

Thesis Committee Members:

Assoc. Prof. Atilla Yılmaz (Advisor, Koç University)

Assoc. Prof. Mine Çağlar (Koç University)

Assoc. Prof. Elvan Ceyhan (North Carolina State University)

Asst. Prof. Özgür Asar (Acıbadem University)

Asst. Prof. Ümit Işlak (Boğaziçi University)

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 (disk shaped) 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.

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 M2^k 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 M2^k 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, V-shaped, 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 V-shaped) reveals to be the best 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 sub-optimal 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 penalty-based 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.