I'm walking towards my car - when should I try the remote, in an optimal sense?

Question

I'm interested to learn about how discrete/'event' based elements are incorporated into optimisation problems. Hopefully this is an interesting problem in its own regard, it's inspired by a daily occurrence in my life.

The problem stated in english is:

What is the optimal strategy to unlock my car with its remote, soonest, as I walk towards it?

The function that determines when the remote will be able to unlock the car is dependent on the battery voltage $V$ and the distance I am from the car $d$:

$$f(V,d) = \alpha \frac{V}{d^2}$$

• If this value goes over some threshold $\tau$, the car will unlock.
• $\alpha$ accounts for some fun (but unknown) stuff like the permeability of air and so on (let it be 1 if you like).
• I am walking towards the car at a constant velocity $u$, from an initial distance $D$.
• The car is not unlockable at $D$.
• The initial voltage $V_0$ is positive but unknown.
• After each attempt to unlock the car the remote the voltage $V$ is reduced by a multiplicative factor $\{\beta\in \mathbb{R}\mid 0 < \beta < 1\}$:

$$ V_{n+1} = \beta V_{n}$$

I think that's about it in terms of required information...

_{(please comment if not, thanks)}

Can an optimal schedule (strategy over time) of unlocking attempts be defined, given no initial values?

In order to avoid making the question too broad, the following aren't specific questions, but 'discussion points' :)

• Obviously if we're given enough values we can figure out a $d$ and use one optimal attempt $(V = V_0)$, but it's more interesting having to account for the Voltage loss in an unknown setting (right?).
• In general, how are non-linear thresholds like $\tau$ and the event driven schedule of attempts dealt with in problems like this?
• Is there a difference if the problem states that the complete schedule must be derived prior to the 'walk'? ...That is, compared to adjusting the schedule dependent on new information such as 'the last attempt didn't work'?

Answer 1

Let's note $d_n$ the distance you are from you car at you $n$-th attempt. The voltage at the moment of the $n$-th attempt is $\beta^nV_0$. So if you want to suceed, there must be an $n$ such that

$$\alpha\dfrac{\beta^n V_0}{d_n^2} \geq \tau.$$ As you have no information at all on $V_0$ (which may be extremely small), we must choose a sequence of distances $(d_n)_{n \in \mathbb{N}}$ such that $$\dfrac{\beta^n}{d_n^2} \xrightarrow[n \to +\infty]{} +\infty.$$ Therefore we must have $$d_n = \beta^{n/2} \times D \times a_n$$ where $a_n \xrightarrow[n \to +\infty]{} 0$. Reciprocally, any $(d_n)_{n \in \mathbb{N}}$ that can be written that way ensures that your problem is solved, as long as the sequence $(d_n)$ is decreasing, which can be translated as $a_{n+1} > \dfrac{1}{\sqrt{\beta}} a_n$.

Let's note $C= D\sqrt{\dfrac{\tau}{\alpha V_0}}$ which is $>1$ by your assumption). The car opens when $a_n \leq \dfrac{1}{C}$. We must then choose the sequence $(a_n)$ such that $d_n$ is as big as possible for the first integer $n$ such that $a_n \leq \dfrac{1}{C}$. Therefore, when we open the car, $d_n \leq \beta^{n/2} D\dfrac{1}{C} \leq \dfrac{D}{C}$. Thus the best strategy (if it exists) will open the car at a distance $\dfrac{D}{C}$. More reasonably, as we have no reliable information on $C$, I can't imagine a strategy that can get it on the first try without any other information on $V_0$. Thus I expect an optimal strategy to open the car at a distance $\beta^{1/2}\dfrac{D}{C}$

$\rhd$ Here is a try to find a strategy which reach or at least approach this upper bound. Let $a_n = \dfrac{1}{q^n}$ for some $q >1$. The smallest $n$ such that $a_n \leq \dfrac{1}{C}$ is $n= \lceil \log_q(C)\rceil$. Then the distance at which we open the car is $$d_n = \beta^{(\lceil \log_q(C)\rceil )/2} \times D \times \dfrac{1}{q^{\lceil \log_q(C)\rceil}} $$ thus $$\beta^{(\lceil \log_q(C)\rceil )/2} \times D \times \dfrac{1}{C\times q} \leq d_n\leq \beta^{(\lceil \log_q(C)\rceil )/2} \times D \times \dfrac{1}{C} $$ Taking $q= C$, this gives $$\beta^{1/2} \dfrac{D}{C^2} \leq d_n \leq \beta^{1/2}\dfrac{D}{C} .$$ Of course, this is cheating as we don't have access to $C$ to build our strategy. If we have access to $C$, simply choosing $a_0=\dfrac{1}{C}$ solve the problem on the first attempt.

$\rhd$ Thus, without any additional information on $V_0$ (or more precisely on $C$), such that a probability distribution from which we could build a strategy that maximize the expected value for the distance from which we open the car, it is not possible to build an optimal strategy. Indeed, is $V_0$ is very small (the battery is almost depleted), it is much more strategic to approach the car quite a bit before our first attempt ; whereas if $V_0$ is quite big (we could open the car by getting just a little bit closer from the distance $D$), then it is much more strategic to try quickly some attempts.

Answer 2

By choosing our units suitably, we can make the condition be that unlocking at distance $d$ is successful if $V \ge d^2$. Since $V_0$ is unknown, but it's guaranteed that unlocking at distance $D$ will not work, a reasonable starting point is to think about solving the problem when $V_0$ is uniformly chosen from the interval $[0,D^2]$.

What happens if we click the key at a distance $d < D$? With probability $1 - \frac{d^2}{D^2}$, we have $V_0 \ge d^2$ and succeed, "scoring $d$ points" in the game of unlocking the car from as far away as possible. With probability $\frac{d^2}{D^2}$, we fail. We learn that $V_0 \le d^2$, conditional on which $V_0$ is uniform on $[0, d^2]$; however, now we are dealing with $V_1$, which is uniform on $[0, \beta d^2]$. In the second case, we have a smaller instance of the same problem: with $D$ replaced by $\sqrt{\beta d^2} = \sqrt{\beta} d$.

Scaling all distances by a constant factor in this problem leaves all the mechanics unchanged (but scales our points scored by the same factor as well). So whatever the optimal strategy is, it is specified by a constant $c$ such that we first click the key at distance $d = c D$. If that doesn't work, we are back at the same problem but with $D$ replaced by $\sqrt{\beta} c D$, and the optimal strategy will treat that the same as before. So in fact such a strategy is fully specified by the choice of $c$.

Suppose a strategy with constant $c$ earns $f(c)D$ points in expectation. Then with probability $1-c^2$, it succeeds on the first try and earns $cD$ points; with probability $c^2$, it fails on the first try, and continuing in the same way earns $f(c) \sqrt{\beta} c D$ points in expectation. Therefore $$ f(c) D = (1-c^2)c D + c^2 f(c) \sqrt{\beta} c D \implies f(c) = \frac{c - c^3}{1 - c^3 \sqrt{\beta}}. $$ To find the optimal strategy, we maximize $f(c)$ over all $c \in [0,1]$. This does not require fancy methods - just set $f'(c)=0$ - but we have to solve an ugly polynomial equation. To get a sense of the answer, we can look at special cases.

• As $\beta \to 1$ (in the limit, the battery does not drain at all when used), the optimal $c$ approaches $1$ as well. This makes sense; in this case, we lose nothing at all by clicking, so we want to click all the time.
• For $\beta = (\frac{22}{27})^2 \approx 0.66$, the equation is particularly nice and gives us $c = \frac34$ as the solution. We click at distances $\frac34D, \frac{11}{24}D, \frac{121}{432}D$, and so on, multiplying by $c\sqrt{\beta} = \frac{11}{18}$ each time. Each time we click, we have a $1-c^2 = \frac{7}{16}$ chance of winning.
• For $\beta = \frac14$, the optimal $c$ is about $0.653$ and satisfies $c^3-3c^2+1 = 0$. We click at distances $cD, \frac12c^2D, \frac14 c^3D, \frac18 c^4 D$, and so on (multiplying by $c\sqrt{\beta} = \frac12c$ at each step).
• For $\beta=0$, the optimal $c$ is $\frac1{\sqrt3} \approx 0.577$. Here, we click at distance $\frac{D}{\sqrt 3}$ and win with probability $\frac23$; the remaining $\frac13$ of the time, we must go all the way to the car. (This is probably best understood as a limit $\beta \to 0$.)

Assuming $V_0$ is sampled from a uniform distribution is only one possible situation. Other situations are more complicated, since the distribution changes shape as we update on the key not working; our strategy can no longer be described by a simple procedure.