Optimal path around an invisible wall The Problem


  On an infinite plane there are two points, $A$ and $B$, a unit distance apart.  There is a $50\%$ probability that there is an invisible wall somewhere between the two points.  The wall extends $1/3$ unit in each direction perpendicular to the line between $A$ and $B$, and its position is uniformly distributed between the two points.  You don't know if the wall is present or where it is until you run into it.
  
  What strategy minimizes the expected distance to travel to point $B$ from point $A$?


(This problem originally came from Puzzling.SE but was closed for being "too mathy.")

My Solution

I use an $x$/$y$ coordinate system on the plane with the origin at $A$, and $B$ on the positive $x$-axis.

Once the position of the wall is known (i.e. when you run into the wall) the best strategy is to walk straight along the wall to the nearest end, then travel straight to $B$.  The best strategy should therefore be to follow a fixed path from $A$ to $B$ until you reach $B$ or hit the wall; if you hit the wall, follow the previously stated path around the wall.

I break up the fixed part of the path into a number of small segments.  A given segment covers a horizontal distance $\delta x$ and vertical distance $\delta y$.  The length of each segment is weighted by the probability it gets traveled, which is $\frac{1}{2} + \frac{1}{2}\left(1-x\right)$.  We also consider the probability that you have to walk around the wall, which for a given segment is $\frac{1}{2}\delta x$.  The distance it takes to get around the wall is just $(H-y) + \sqrt{H^2 + (1-x)^2}$, where $H=\frac{1}{3}$, the half-length of the wall.

Therefore the expected distance $E$ should be equal to:

$$
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)
$$

If we treat $y$ as a function of $x$ (assuming that the optimal path doesn't travel backward) we can factor out $\delta x$, since $\delta y = y'(x)\delta x$; then taking the limit as $\delta x\to 0$ we obtain an 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
$$

Now I try to use the Euler-Lagrange equations to find the path $y(x)$ that minimizes $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}
$$

A solution to this differential equation should be a minimum-distance path, as long as it satisfies $y(x) \le H$ for all $x\in[0,1]$.  The boundary conditions are $y(0)=y(1)=0$.  Mathematica finds an explicit solution, but it it is extremely complex.  The simplest form I can get it in is:

$$
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
$$

The solution looks like this:



The Question

Is this approach valid, and are my calculations correct?
One approach is via dynamic programming (which works the solution backwards). For simplicity, let's chop the $x$-axis into $n$ segments of size $\delta_x = 1/n$, and suppose the wall is on one of these chopping points (including point 0, but not point 1).  Chop the $y$-axis into $n$ segments of length $\delta_y = (1/3)/n$.  Define the value function $J(x,y)$ as the expected remaining travel distance to the destination under the optimal policy, given we are at a horizontal distance $x$, a vertical distance $y$, and none of our previous moves encountered a wall. The $J(x,y)$ function is defined over: 
$$ 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\}$$ 

Suppose we start at $(x_0,y_0)=(0,0)$. Working backwards, and assuming there is no wall at $x=1$, we get: 

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

Now assume $J(k\delta_x, y)$ is known for all $y$ and for some $k$.  Then: 

\begin{align}
J((k-1)\delta_x, y) &amp;= P[\mbox{wall is here | have not yet seen it}]\left[1/3-y + \sqrt{1/9+ (1-(k-1)\delta_x)^2}\right]\\
&amp;+P[\mbox{wall is not here | have not yet seen it}]\min_{v\in\mathcal{Y}}\left[J(k\delta_x,v)+\sqrt{\delta_x^2 +(y-v)^2}  \right]
\end{align}
Since we have discretized the problem, if a wall exists then it is located uniformly over one of the the $n$ points $\{0, \delta_x, ..., (n-1)\delta_x\}$.
Thus, if we are at location $(k-1)\delta_x$ and have not yet seen a wall at any of the locations $\{0, \delta_x, ..., (k-2)\delta_x\}$, we get: 
$$ P[\mbox{Wall here | not before}]=\frac{\frac{1}{2n} }{\frac{1}{2}+\frac{1}{2}\left(\frac{n-(k-1)}{n}\right)} $$
My solution to this problem (which I originally posted on the puzzle site), would be to aim for the midpoint up the wall assuming it is midway between A and B.  After that, I would lower my path back towards the centerline of A and B.  I would have to use a computer to try many different paths and lowering angles.  For example, if I don't hit the wall by midway between A and B, I could try going directly at B but this seems non optimal cuz think of the worst case where the wall is slightly before B.  You then get diverted quite a bit just to finish a small distance to B.  I think a simple and near optimal solution would be after not seeing the wall by the midpoint of the direct AB path, plot a few more discrete points that the wall could be at (such as $5/8$th of the way, $3/4$s of the way, $7/8$ths of the way), optimize just those paths, then find a formula that passes thru those $3$ points (called curve smoothing I think?). Not sure if that will be optimal for all wall positions past the halfway point but it is a good start to try to beat.