76 lines
2.9 KiB
Markdown
76 lines
2.9 KiB
Markdown
|
# Searching in an unknown environment - An optimal randomized algorithm for the cow-path problem
|
||
|
|
|
||
|
|
## Introduction
|
||
|
|
|
||
|
|
* Classical search problems: **cost of a search == number of queries **made to an oracle which knows the position of the goal.
|
||
|
|
* w-lane Cowpath Problem: **position unknown (no oracle)**. **Cost: proportional to the distance between queries**. Example: time required to travel between two query points.
|
||
|
|
|
||
|
|
*(problem description)*
|
||
|
|
*(problem application - robotics/hybrid algorithms/AI examples etc.)*
|
||
|
|
|
||
|
|
This problem has various common points (*see later*) with **online algorithms** and because of this we use the notion of **competitive analysis of online algorithms** to measure the **efficiency** of the w-lane Cowpath problem. [Quick description of online algorithms.](https://en.wikipedia.org/wiki/Online_algorithm) - [Competitive analysis of OA](https://en.wikipedia.org/wiki/Competitive_analysis_(online_algorithm)).
|
||
|
|
|
||
|
|
### Competitive ratio for the Cow-Path problem
|
||
|
|
|
||
|
|
Competitive analysis uses an optimal offline algorithm (read: one in which **all data is avaiable from the start**) and defines a **competitive ratio** by comparing the performance of the online and offline algorithms.
|
||
|
|
An algorithm is ***competitive*** if its competitive ratio is **bounded**.
|
||
|
|
|
||
|
|
We define a competitive ratio for the w-lane Cowpath problem:
|
||
|
|
***The competitive ratio for an algorithm solving the cow-path problem is the worst-case ratio of the expected distance traveled by the algorithm to the shortest-path distance from origin to goal.***
|
||
|
|
|
||
|
|
In particular, if the worst-case expected distance traveled by a randomized algorithm is at most `cn+d`, where `n` is the distance to the goal and `d` is a fixed constant, then `c` is the competitive ratio of this algorithm.
|
||
|
|
|
||
|
|
## Deterministic algorithm
|
||
|
|
|
||
|
|
*(baeza-yaetes paper)*
|
||
|
|
|
||
|
|
## Randomized algorithm
|
||
|
|
|
||
|
|
*(quick abstract, see paper for detailed version / formulas)*
|
||
|
|
|
||
|
|
### Definitions
|
||
|
|
|
||
|
|
A deterministic algorithm for the cow-path problem has competitive ratio `c` if:
|
||
|
|
|
||
|
|
```
|
||
|
|
cost(goal) <= c*dist(goal) + d // c,d are constants independent from g
|
||
|
|
```
|
||
|
|
|
||
|
|
Considering a **randomized algorithm**, the distance traveled to find a given goal position is **no longer fixed**. This means that cost(goal) is a **random variable**, and the competitive ratio `c` is computed on the **expected value of that random variable**.
|
||
|
|
```
|
||
|
|
E[cost(goal)] <= c*dist(g) + d
|
||
|
|
```
|
||
|
|
|
||
|
|
This means that **a randomized algorithm has competitive ratio c if the expected value of the distance it has to travel is at most** `c*n + /small constant/`.
|
||
|
|
|
||
|
|
### Algorithm
|
||
|
|
|
||
|
|
*(see paper)*
|
||
|
|
|
||
|
|
### Theorems
|
||
|
|
|
||
|
|
#### 3.1
|
||
|
|
|
||
|
|
***For any fixed geometric ratio r*** *(explain)* ***the algorithm has competitive ratio R(r,w)***
|
||
|
|
|
||
|
|
#### 4.1
|
||
|
|
|
||
|
|
*(see paper)*
|
||
|
|
|
||
|
|
### Lower Bound Analysis
|
||
|
|
|
||
|
|
*(see paper)*
|
||
|
|
|
||
|
|
### Minimization of the competitive ratio
|
||
|
|
|
||
|
|
*(see paper)*
|
||
|
|
|
||
|
|
### Growth w. number of paths
|
||
|
|
|
||
|
|
*(see paper)*
|
||
|
|
|
||
|
|
*Note: here we could prove that the algorithm is optimal with w=2*
|
||
|
|
|
||
|
|
|
||
|
|
|