Trayectoria óptima alrededor de un muro invisible

Question

El problema

En un plano infinito hay dos puntos, $A$ y $B$ una distancia de una unidad. Hay un $50\%$ probabilidad de que haya un muro invisible en algún lugar entre los dos puntos. El muro se extiende $1/3$ unidad en cada dirección perpendicular a la línea entre $A$ y $B$ y su posición se distribuye uniformemente entre los dos puntos. No se sabe si la pared está presente o dónde está hasta que se topa con ella.

¿Qué estrategia minimiza la distancia esperada para viajar al punto $B$ desde el punto $A$ ?

(Este problema originalmente proviene de Puzzling.SE pero fue cerrado por ser "demasiado matemático").

Mi solución

Utilizo un $x$ / $y$ sistema de coordenadas en el plano con el origen en $A$ y $B$ en lo positivo $x$ -eje.

Una vez que se conoce la posición del muro (es decir, cuando se topa con él) la mejor estrategia es caminar en línea recta a lo largo del muro hasta el extremo más cercano, y luego viajar en línea recta hasta $B$ . Por lo tanto, la mejor estrategia debería ser seguir una ruta fija desde $A$ a $B$ hasta llegar a $B$ o golpear la pared; si golpeas la pared, sigue el camino indicado anteriormente alrededor de la pared.

Divido la parte fija del camino en varios segmentos pequeños. Un segmento determinado cubre una distancia horizontal $\delta x$ y la distancia vertical $\delta y$ . La longitud de cada segmento se pondera por la probabilidad de que sea recorrido, que es $\frac{1}{2} + \frac{1}{2}\left(1-x\right)$ . También consideramos la probabilidad de que tenga que rodear el muro, que para un segmento dado es $\frac{1}{2}\delta x$ . La distancia que se necesita para rodear el muro es sólo $(H-y) + \sqrt{H^2 + (1-x)^2}$ , donde $H=\frac{1}{3}$ La mitad de la longitud de la pared.

Por lo tanto, la distancia esperada $E$ debe ser igual a:

$$ E = \sum_{i=1}^N\frac{2-x}{2}\sqrt{\delta x_i^2 + \delta y_i^2} + \frac{\delta x_i}{2}\left((H-y_i) + \sqrt{H^2 + (1 - x_i)^2}\right) $$

Si tratamos $y$ en función de $x$ (suponiendo que el camino óptimo no se desplaza hacia atrás) podemos factorizar $\delta x$ ya que $\delta y = y'(x)\delta x$ y luego tomando el límite como $\delta x\to 0$ obtenemos una integral:

$$ E = \frac{1}{2}\int_{0}^{1}(2 - x)\sqrt{1 + y'(x)^2} + H - y(x) + \sqrt{H^2 + (1-x)^2}~\mathrm{d}x $$

Ahora trato de usar el Ecuaciones de Euler-Lagrange para encontrar el camino $y(x)$ que minimiza $E$ :

$$ E = \int \mathcal{L}(x, y(x), y'(x))~\mathrm{d}x \\ \mathcal{L}(x, y(x), y'(x)) = \frac{1}{2}\left((2 - x)\sqrt{1 + y'(x)^2} + H - y(x) + \sqrt{H^2 + (1-x)^2}\right) \\ \frac{\partial \mathcal{L}}{\partial y(x)} - \frac{\mathrm{d}}{\mathrm{d}x}\frac{\partial \mathcal{L}}{\partial y'(x)} = 0 \\ \left[-\frac{1}{2}\right]-\frac{\mathrm{d}}{\mathrm{d}x}\left[\frac{(2-x)y'(x)}{2\sqrt{1+y'(x)^2}}\right]=0 \\ 1 = \frac{y'(x)(1 + y'(x)^2) - (2-x)y''(x)}{\left(1+y'(x)^2\right)^{3/2}} \\ y''(x) = \left(1+y'(x)^2\right)\frac{y'(x)-\sqrt{1+y'(x)^2}}{2-x} $$

Una solución a esta ecuación diferencial debería ser un camino de distancia mínima, siempre que satisfaga $y(x) \le H$ para todos $x\in[0,1]$ . Las condiciones de contorno son $y(0)=y(1)=0$ . Mathematica encuentra una solución explícita, pero es extremadamente compleja. La forma más simple que puedo conseguir es:

$$ y(x) = \frac{168 \left(9 \sqrt{6}+\sqrt{38}\right) \xi -\sqrt{131-9 \sqrt{57}} \xi^3 - 448 \sqrt{3710+378\sqrt{57}}}{2688 \left(27+\sqrt{57}\right)} \\ \xi = \sqrt{7 \left(43+\sqrt{57}\right)-8 \left(27+\sqrt{57}\right) x} \\ y(x) \approx 0.3929 x\sqrt{1.2802-x} +0.3454 \sqrt{1.2802-x}-0.3908 $$

La solución es la siguiente:

La pregunta

¿Es válido este planteamiento y son correctos mis cálculos?

Answer 1

Un enfoque es a través de la programación dinámica (que trabaja la solución hacia atrás). Para simplificar, vamos a cortar el $x$ -eje en $n$ segmentos de tamaño $\delta_x = 1/n$ y supongamos que la pared está en uno de estos puntos de corte (incluyendo el punto 0, pero no el punto 1). Corta el $y$ -eje en $n$ segmentos de longitud $\delta_y = (1/3)/n$ . Definir la función de valor $J(x,y)$ como la distancia restante esperada hasta el destino bajo la política óptima, dado que estamos a una distancia horizontal $x$ , una distancia vertical $y$ y ninguno de nuestros movimientos anteriores se encontró con un muro. El $J(x,y)$ se define sobre: $$ x \in \mathcal{X} = \{0, \delta_x, 2\delta_x, ..., 1\} \quad , \quad y \in \mathcal{Y}=\{0, \delta_y, 2\delta_y, ..., 1/3\}$$

Supongamos que empezamos en $(x_0,y_0)=(0,0)$ . Trabajando hacia atrás, y asumiendo que no hay un muro en $x=1$ obtenemos:

$$J(1,y) = y \quad \forall y \in \mathcal{Y} $$

Supongamos ahora que $J(k\delta_x, y)$ es conocido por todos $y$ y para algunos $k$ . Entonces:

\begin {align} J((k-1) \delta_x , y) &= P[ \mbox {la pared está aquí | aún no la han visto}] \left [1/3-y + \sqrt {1/9+ (1-(k-1) \delta_x )^2} \right ] \\ &+P[ \mbox {la pared no está aquí | no la han visto todavía}] \min_ {v \in\mathcal {Y}} \left [J(k \delta_x ,v)+ \sqrt { \delta_x ^2 +(y-v)^2} \right ] \end {align} Dado que hemos discretizado el problema, si existe una pared entonces se encuentra uniformemente sobre uno de los $n$ puntos $\{0, \delta_x, ..., (n-1)\delta_x\}$ . Por lo tanto, si estamos en el lugar $(k-1)\delta_x$ y aún no han visto un muro en ninguno de los lugares $\{0, \delta_x, ..., (k-2)\delta_x\}$ obtenemos: $$ P[\mbox{Wall here | not before}]=\frac{\frac{1}{2n} }{\frac{1}{2}+\frac{1}{2}\left(\frac{n-(k-1)}{n}\right)} $$

Answer 2

Mi solución a este problema (que publiqué originalmente en el sitio del rompecabezas), sería apuntar al punto medio de la pared asumiendo que está a mitad de camino entre A y B. Después de eso, bajaría mi camino hacia la línea central de A y B. Tendría que usar una computadora para probar muchos caminos diferentes y ángulos de bajada. Por ejemplo, si no veo la pared a mitad de camino entre A y B, podría intentar ir directamente a B, pero esto no parece óptimo porque piensa en el peor caso en el que la pared está un poco antes de B. Entonces te desvías bastante sólo para terminar una pequeña distancia a B. Creo que una solución simple y casi óptima sería después de no ver la pared por el punto medio de la ruta directa AB, trazar algunos puntos más discretos en los que la pared podría estar (como $5/8$ del camino, $3/4$ s del camino, $7/8$ del camino), optimizar sólo esos caminos, y luego encontrar una fórmula que pase por esos $3$ puntos (creo que se llama suavizado de curvas). No estoy seguro de si eso será óptimo para todas las posiciones de la pared más allá del punto medio, pero es un buen comienzo para tratar de superar.