Back to search

University of Waterloo

Geometric On-line Ray Searching Under Probability of Placement Scenarios

Abstract

dc:description.abstract

Online computation is a model for formulating decision making under uncertainty. In an online problem, the algorithm does not know the entire input from the beginning; the input is revealed in a sequence of steps. At each step, the algorithm should make its decisions based on the past and without any knowledge about the future. Many important real-life problems such as robot navigation are intrinsically online and thus the design and analysis of online algorithms is one of the main research areas in theoretical computer science. Competitive analysis is the standard measure for analysis of online algorithms. It has been applied to many online problems in diverse areas ranging from robot navigation, to network routing, to scheduling, to online graph coloring. In this thesis, we first survey three classic online problems, namely the cow-path problem, the Processor-Allocation problem and the Robots-Search-Rays problem and highlight connections between them. Second, the main result is for the One-Robot-Searches-Two-Rays problem for which we consider the weighted scenario, in which the robot is located on a ray with a preferential probability p. We term the One-Robot-Searches-Two-Rays-And-Weighted problem as 1-STRAW (and in general k-STRAW for k searchers). In the 1-STRAW problem, we propose a search strategy which is optimal among weighted geometric states. In addition, we prove a tight lower bound of the worst case competitive ratio and conjecture a lower bound of the average case competitive ratio for the 1-STRAW problem. Additionally, we compare our search strategy and its performance with the doubling strategy and the SmartCow algorithm.

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2010

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Liu, Ying

Subjects

dc:subject × 2

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/10012/5520

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Liu, Ying. Geometric On-line Ray Searching Under Probability of Placement Scenarios. University of Waterloo, 2010. http://hdl.handle.net/10012/5520