What is the optimal path between $2$ fixed points around an invisible obstructing wall?

Every day you walk from point A to point B, which are $3$ miles apart. There is a $50$% chance each walk that there is an invisible wall somewhere strictly between the two points (never at A or B). The wall extends $1$ mile in each direction perpendicular to the line segment (direct path) between A and B, and its position can be at any random location between the two points. That is, it can be any distance between A and B such as $0.1$ miles away from A, $1.5$ miles away, $2.9$ miles away…. You don’t know if the wall is present or where it is until you walk into it. You must walk around the wall if present as there is no other way to circumvent it. Assume the wall is negligible thickness (like a force field), all ground is perfectly flat, and the y coordinates at both A and B are $0$ (although I don’t think the optimal path will change much if they weren’t).

What strategy minimizes the average expected walk distance between A and B? How do we know for certain this strategy yields the shortest average walking distance?

To get the $100$ bounty points, I would like a convincing argument from you as to why you feel your solution is optimal and cannot be beaten. For those of you using computer simulation, anything reasonably close to optimal is a candidate for the bounty.

Can anyone beat the optimal solutions submitted so far? There are still a few days to try. Even a slight beat (if not due to roundoff error or some other error) would help prove previous solutions are non-optimal. You can just use the table of $31$ points (x-y coordinates) and compute that path length and then if you can find better then I will accept that answer. I think by Sunday night I may have to award the bounty otherwise it may get auto-awarded.

Solutions Collecting From Web of "What is the optimal path between $2$ fixed points around an invisible obstructing wall?"

enter image description here
Using this, and the fact the shortest Euclidean distance between two points is a straight line, we can see that the minimum distance between the points A and B is. (Note: that the green segments denote the shortest lengths from A to the wall and the wall to B)


This is a long answer, if you’re interested in specifics here’s a layout. In the Lower Bound section, I establish the best possible scenario for the situation. The Linear Solution section assumes that the optimal path is linear. The Best Solution section finds a extremal path by using Variational Calculus. Everything in the solution is exact. Proving The Soltution is The Global Minima is a section on using the Second Variational Derivative to prove we have the solution. The Computer Algorithm section discusses how we might approximate solutions.

Lower Bound


Where, $H(X)$ is the Heaviside step function and $X$ is either $0$ or $1$ with equal probability. Note that I’m assuming that $L$ is a uniform random variable on the interval $(0,3)$. The expected value of $D_m(L)$ is,

$$E(D_m(L,X))=\frac{1}{6} \cdot \int_0^3 D_m(L,0)+D_m(L,1) \ dL$$
$$(1) \quad \Rightarrow E(D_m(L,X))=\cfrac{\ln \left(\cfrac{\sqrt{10}+3}{\sqrt{10}-3} \right)+6 \cdot (\sqrt{10}+3)}{12}=3.3842…$$

So, the minimum possible value is (1).

The Linear Solution

Referencing the above diagram, we see that this essentially non-deterministic problem, has a very deterministic property associated with it. Namely, after the wall encounter, the rest of the optimal path can be determined. However, the optimal path before the wall encounter is indeterminate. In other words, we can only know what path we should’ve taken; we can’t actually take that path.

Imagine we have some optimal strategy that picks an optimal path $f(x)$. Since the problem has no memory, the optimal path is unique. In addition, this memory property rules out the possibility of a mixed strategy solution.

Putting these facts together, we see that $f(x)$ is deterministic for $x \lt L$ and random for $x \gt L$. However, some things about $f(x)$ are known,

$$(a) \quad f(0)=0$$
$$(b) \quad \lim_{x \to L^+} f(x)=1$$
$$(c) \quad f(3)=0$$
$$(d) \quad f(x) \le 1$$

If we now consider all possible paths $p(x)$ satisfying the conditions (a-d) we can investigate the path $p_m(x)$ that minimizes the length. The length of a path $p(x)$ from $x=0$ to $x=L$ is given by,

$$L_p=\int_0^3 \sqrt{1+\left(\cfrac{dp}{dx} \right)^2} \ dx+(1-p(L)) $$

By inspection, we see that the right hand side is minimized for $p(L)$, evaluated from the left, closer to $1$. However, this means that the average slope of $p(x)$ will therefore have to be equal to $\cfrac{p(L)}{L}$. Since the shortest curve with an average slope equal to that amount is a line, we know that $p_m(x)$ must be linear*. This means we can derive an explicit formula for $L_p$ using $\cfrac{dp_m}{dx}=\lambda$. Note that if a path overshoots the wall, it can only keep going in the same direction. There’s no knowledge that it over shot the wall, until the instant before it reaches point B.

If we take the expected value of $L_p$ we can find the value of $\lambda$ that minimizes the length. This value of $\lambda$ determines the slope of the optimal path. The other conditions determine $p_m(x)$ and thus $f(x)$. Note, that the resulting equations are explicit, they are just too complicated to effectively represent here. In fact, I actually didn’t even solve it right on the first try! (I still might not have, i.e physical answer)

I get that $\lambda=0$ solves the problem. This gives an expected path length of,

$$E(L_p)=\cfrac{3 \cdot (\sqrt{10}+11)-\ln(\sqrt{10}-3)}{12}=3.6921$$


Here’s why the $\lambda=0$ solution should work. Since a wall is just as likely to be present as to not be present, we can analyze the total vertical distances traveled in both cases. In the case with a wall, the total distance is $1-\lambda \cdot L$. In the case without a wall, the total distance is $3 \cdot \lambda$. Thus the average vertical distance travelled is $1/2+\lambda \cdot (3-L)$. Which is minimized for $\lambda=0$.

*Bonus points if you realize this only guarantees optimal solutions, within the linear space.

The Best Solution

I’ve been motivated to provide a full solution so here we’ll take a look at better paths that aren’t linear.

Realizing that the argument for a linear path is rather contrived, and only possibly locally optimal, we’ll see what happens if look at all possible functions in an unbiased manner. Then the average length of an arbitrary path, $p(x)$, is given by,

$$F(L,p(x))=\cfrac{1}{2} \cdot \left (\int_0^L \sqrt{1+\left(\cfrac{dp}{dx} \right)^2} \ dx+(1-p(L))+\sqrt{1+(3-L)^2} \right)+\cfrac{1}{2} \cdot \int_0^3 \sqrt{1+\left(\cfrac{dp}{dx} \right)^2} \ dx$$

The expected path length $E(F(L))$ is therefore given by,

$$E(p(x))=\cfrac{1}{3} \cdot \int_0^3 F(L,p(x)) \ dL$$

I have to thank @user5713492 for the idea to change the order of integration, here’s the quick sketch of why

enter image description here

$$\int_0^3 \int_0^L \sqrt{1+\left(\cfrac{dp}{dx} \right)^2} \ dx dL =\int_0^3 \sqrt{1+\left(\cfrac{dp}{dx} \right)^2} \int_x^3 dL dx$$
$$=\int_0^3 (3-x) \cdot \sqrt{1+\left(\cfrac{dp}{dx} \right)^2} \ dx$$

The second double integral is much easier, and I’ll leave it to the reader to verify that it can be contracted to, $3 \cdot \int_0^3 \sqrt{1+\left(\cfrac{dp}{dx} \right)^2} \ dx$. Substituting this information in and simplifying we get,

$$E(p(x))=\frac{1}{6} \int_0^3 (6-x) \cdot \sqrt{1+\left(p'(x) \right)^2}+(1-p(x))+\sqrt{1+(3-x)^2} \ dx$$

$$=\frac{1}{6} \int_0^3 L \left(x, p(x), p'(x) \right) \ dx$$

Note that we switched $L$ to $x$ so that we could combine the integrals. The fact that $E(p(x))$ can be written as integral over a kernel, occasionally called the lagrangian, is very important. Now we have the problem framed in such a way it can be solved using the mathematical subject known as ‘Calculus of Variations’. Effectivley, this subject studies how to minimize/maximize ‘functionals’, essentially functions of functions. We’ll be using Euler-Lagrange’s Equation essentially. First, we want to see how $E(p(x))$ changes if we change $p(x)$. We’ll make a small perturbation $\epsilon \cdot \eta(x)$ and demand that this small change in the path disappear at the boundaries. In other words $\eta(0)=\eta(3)=0$. It’s essential to note $\eta(x)$ is the perturbation while $\epsilon$ is just a control parameter.

Using this we change the function undergoes a transformation,

$$p(x) \rightarrow p(x)+\epsilon \cdot \eta(x)=p_{\eta}(x)$$

Now essentially, we want to know the change in the expected length between the perturbed and unperturbed case. Essentially we want to know,

$$\delta E=\int_0^3 \cfrac{\delta E}{\delta p} \cdot \eta(x) \ dx=\cfrac{E(p_{\eta}(x))-E(p(x))}{\epsilon}=\cfrac{d}{d \epsilon} \left[ E(p_{\eta}(x)) \right]$$

Note that we take the limit as $\epsilon$ goes to zero. Essentially, in the above, $\delta E$, or the first variation, is expressed in terms of summing over each part of the perturbation $\eta(x)$ against the functional derivative. The other two equalities, follow naturally. Now we have,

$$E(p_{\eta}(x))=\int_0^3 L \left(x, p(x), p'(x) \right) \ dx$$

We can find the first variation by using the above formulas. After integrating by parts and noting boundary conditions, we can also obtain the functional derivative. Since we want an optimal solution, we want the functional derivative to be equal to zero*. The functional derivative for $\int L \left(x, p(x), p'(x) \right)$ has been derived countless times so I’ll simply redirect you to Euler-Lagrange. After substituting our particular form for the lagrangian we get,

$$\cfrac{dE}{dp}-\cfrac{d}{dt} \left[ \cfrac{dE}{dp’} \right]=0$$
$$\Rightarrow \cfrac{d}{dx} \left[ \cfrac{(6-x) \cdot p'(x)}{\sqrt{1+(p'(x))^2}} \right]=-1$$

This equation can be solved by demanding $p(0)=p(3)=0$ for the boundary conditions. We can immediately integrate this equation with respect to $x$ and obtain,

$$ \cfrac{(6-x) \cdot p'(x)}{\sqrt{1+(p'(x))^2}}=-x+c_0$$

After solving for the velocity, we obtain,

$$p'(x)=-(x+c_0) \cdot \sqrt{\cfrac{1}{(c_0+6) \cdot (6-2 \cdot u-c_0)}}$$

We can directly integrate this equation and obtain the optimal path,

$$p(x)=c_1-\int (x+c_0) \cdot \sqrt{\cfrac{1}{(c_0+6) \cdot (6-2 \cdot x-c_0)}} \ dx$$

$$\Rightarrow p(x)=c_1-\cfrac{1}{3} \cdot (2 \cdot c_0+x+6) \cdot (c_0+2 \cdot x-6) \cdot \sqrt{\cfrac{1}{(c_0+6) \cdot (6-2 \cdot x-c_0)}}$$


Since we have two boundary conditions and two constants, this solution is perfectly valid. In fact we can explicitly solve for $c_0$ and $c_1$.

$$c_1=-\cfrac{\sqrt{14 \cdot (\sqrt{57}+85)} \cdot (3 \cdot \sqrt{19}+49 \cdot \sqrt{3})}{2688}=-1.17247$$

The value for $E(p(x))$ for this path is and a plot is shown below. The length of the arc itself is about $3.065$. I don’t want to do the integral, sorry 🙁 , so you’ll have to settle for the numerical approximation there.

$$E(p(x))=\cfrac{\operatorname{sinh^{-1}}(3)}{12}+\cfrac{5 \cdot \sqrt{42} \cdot (3235-279) \cdot \sqrt{57})}{672}+\cfrac{\sqrt{14 \cdot (\sqrt{57}+85)} \cdot (3 \cdot \sqrt{19}+43 \cdot \sqrt{3})}{5376}+\cfrac{2+\sqrt{10}}{4}$$

enter image description here

Proving the Solution is the Global Minima

The optimal solution is also the function that minimizes $E(p(x))$, which is called a functional by the way. This can be proven by taking the second variation and solving an eigenvalue problem. Physically this is obvious as the maximum solution doesn’t exist. However, proving non-existence of saddle points is difficult.

If you’re interested in the proof of this, we have the second variation provided enter link description here, see page 18. Using this, can we set up the eigenvalue problem with,

$$\int dx’ \cfrac{\delta E}{\delta p(x) \delta p(x’)} \cdot \eta(x’)= \lambda \cdot \eta(x’)$$

Similarly to the case with functions, if the second derivative is positive, we have a minimum. So, to do this, we must prove that for all possible perturbations $\eta$, $\lambda \gt 0$. If this is true, then the second functional derivative must be positive, and thus we have a minimum. If use the reference, we find out just how lucky we are! The only term that survives is the third coefficient term,

$$C(x)=\cfrac{6-x}{(1+(p'(x))^2)^{3/2}} \gt 0$$

Hopefully it’s clear that this term is strictly larger than zero. Since, we can construct an arbitrarily high value for $E(p(x))$ by picking non-differentiable continuous paths, and the solution to the differential equation is unique, there are no other paths that have a vanishing functional derivative. Therefore, this local minima must also be a global minima for the functional $E(p(x)))$.

There was someone who suggested that there might suggest an infinum for $E$ that doesn’t have a vanishing derivative. The analogy with $f(x)=\frac{1}{x}$ was presented. However, taking the derivative yields $f'(x)=-\cfrac{1}{x^2}$ which clearly goes to zero as x approaches infinity. In addition since there is a lower bound for $E$, which was presented above, it’s impossible for such a infinum, which is non-existent, to be unboundedly better than our solution. In other words my argument above is still valid, I just thought it was important to highlight some of the details involved in the argument.

Computer Algorithms

This is a math site, so forgive my lack of expertise on specifics…

If I was completely oblivious to how to solve the problem exactly, I’d need to investigate the problem numerically. My first choice would be to setup a neural network with inputs being the various lengths along the x-axis and the outputs being the y coordinates of a path. The Fitness function would be the expected value of the length.

However, not everyone just has neural networks lying around. My second choice would be to use gradient descent. I’d pick the initial path to be $0.15 \cdot x \cdot (3-x)$ and discretized into an arbitrary number of chunks. Then I’d raise or lower a random part of the path by an amount $\Delta$. If there was improvement to $E(p(x))$ I’d keep the change, otherwise it’d have to go. Since, its fairly trivial to probe that there’s only one extrema in the path space, there’s no risk of settling on local extrema.

I think a have a plausible solution. If we follow the curve $y=y(x)$ on a wall day, then we travel a distance of $\int_0^u\sqrt{1+\left(y^{\prime}(x)\right)^2}dx$ before hitting the wall at $u$. Then we have to go $w-y(u)$ to go around the wall of half-width $w$, and then a further $\sqrt{w^2+(B-u)^2}$ to get to our goal at $x=B$. Assuming uniform distribution of wall placements $u$, the average distance on a wall day is
On a non-wall day, our average distance is the uninterrupted path length,
Since half of the days are wall days, the average distance is
Now, we can change the order of integration of that double integral to get
So now our average distance reads
$$\bar s=\frac1{2B}\int_0^B\left[(2B-x)\sqrt{1+\left(y^{\prime}(x)\right)^2}dx+w-y(x)+\sqrt{w^2+(B-x)^2}\right]dx$$
Now we want to vary the optimal solution by a small adjustment, $\delta y$. Expanding that first square root for small $\delta y$,
$$\sqrt{1+\left(y^{\prime}+\delta y^{\prime}\right)^2}\approx\sqrt{1+\left(y^{\prime}\right)^2+2y^{\prime}\delta y^{\prime}}\approx\sqrt{1+\left(y^{\prime}\right)^2}+\frac{y^{\prime}}{\sqrt{1+\left(y^{\prime}\right)^2}}\delta y^{\prime}$$
Integrating by parts,
$$\begin{align}\int_0^B(2B-x)\frac{y^{\prime}}{\sqrt{1+\left(y^{\prime}\right)^2}}\delta y^{\prime}dx&=\left.(2B-x)\frac{y^{\prime}}{\sqrt{1+\left(y^{\prime}\right)^2}}\delta y\right|_0^B-\\
&\int_0^B\delta y\left\{-\frac{y^{\prime}}{\sqrt{1+\left(y^{\prime}\right)^2}}+(2B-x)\frac{y^{\prime\prime}}{\sqrt{1+\left(y^{\prime}\right)^2}}-(2B-x)\frac{\left(y^{\prime}\right)^2y^{\prime\prime}}{\left(1+\left(y^{\prime}\right)^2\right)^{\frac32}}\right\}dx\\
&=\int_0^B\delta y\cdot\frac{y^{\prime}+\left(y^{\prime}\right)^3-(2B-x)y^{\prime\prime}}{\left(1+\left(y^{\prime}\right)^2\right)^{\frac32}}dx\end{align}$$
The integrated term above drops out because we assume that $\delta y(0)=\delta y(B)=0$ So combining with the $-\delta y$ from the big integral, we have the condition
$$\int_0^B\left[\delta y\cdot\frac{y^{\prime}+\left(y^{\prime}\right)^3-(2B-x)y^{\prime\prime}}{\left(1+\left(y^{\prime}\right)^2\right)^{\frac32}}-\delta y\right]dx=0$$
for arbitrary small adjustments $\delta y$ so it follows that
This is a variables separable differential equation for $y^{\prime}$ and we are going to write it as
Letting $y^{\prime}=\sinh\theta$, we have
And we have an integral:
EDIT: At this point I had initially missed that the above differential equation was capable of routine solution. First multiply out the right hand side and make a substitution:
Then isolate the radical and square out:
Then we can simplify a little to
Now we will make the final substitution of $\xi=2v-1$ so that $v=\frac{\xi+1}2$ and
Taking square roots,
We can integrate to
At $x=B$, $y=0$, $\xi=\xi_f=\frac{2B}C-1$ and $\frac13\xi_f^{\frac32}-\xi_f^{\frac12}=C_1$ so now the solution in terms of $\xi$ is
At $x=0$, $y=0$, $\xi=\xi_0=\frac{4B}C-1=2\xi_f+1$ and
Isolating like radicals and squaring out,
With solution set
We can find the initial slope
The path reaches the farthest from the straight line when $y^{\prime}=0$, $\xi=1$, so
$$y=\frac C2\left(\frac13\xi_f^{\frac32}-\xi_f^{\frac12}-\frac13+1\right)=\left(\frac{27+\sqrt{57}}{72}-\frac{15+\sqrt{57}}{36}\sqrt{\frac{13-\sqrt{57}}{14}}\right)B$$
On a non-wall day, the path length is
$$\begin{align}s_{\text{min}}&=\int_0^B\sqrt{1+\left(y^{\prime}\right)^2}dx=\int_{\xi_0}^{\xi_f}\sqrt{1+\frac{(\xi-1)^2}{4\xi}}\left(-\frac C2\right)d\xi\\
&=-\frac C2\int_{\xi_0}^{\xi_f}\frac{\xi+1}{2\sqrt{\xi}}d\xi=-\frac C2\left[\frac13\xi^{\frac32}+\xi^{\frac12}\right]_{\xi_0}^{\xi_f}\\
The mean path length is
$$\begin{align}\bar s&=\frac1{2B}\int_0^B\left[(2B-x)\sqrt{1+\left(y^{\prime}\right)^2}+w-y+\sqrt{w^2+(B-x)^2}\right]dx\end{align}$$
We already have the invariant part of the integral at hand so we only need
$$\begin{align}\frac1{2B}\int_0^B\left[(2B-x)\sqrt{1+\left(y^{\prime}\right)^2}-y\right]dx&=\frac1{2B}\int_{\xi_0}^{\xi_f}\left[\frac C2(\xi+1)\frac{(\xi+1)}{2\sqrt{\xi}}+\frac C6\left(\xi^{\frac32}-3\xi^{\frac12}-\xi_f^{\frac32}+3\xi_f^{\frac12}\right)\right]\left(-\frac C2d\xi\right)\\
&=\frac B{24^2}\left[\sqrt{\frac{20-\sqrt{57}}7}(299+\sqrt{57})+\sqrt{\frac{13-\sqrt{57}}{14}}(1+3\sqrt{57})\right]\end{align}$$
After simplification. So overall the mean length of the optimal path is
$$\begin{align}\bar s&=\frac B{24^2}\left[\sqrt{\frac{20-\sqrt{57}}7}(299+\sqrt{57})+\sqrt{\frac{13-\sqrt{57}}{14}}(1+3\sqrt{57})\right]+\\
&\frac14\sqrt{B^2+w^2}+\frac{w^2}{4B}\ln\left(\frac{B+\sqrt{B^2+w^2}}w\right)+\frac w2\end{align}$$
For comparison, our analytical results are $y^{\prime}(0)=0.291906063555883$, $x_{\text{max}}=1.681270695591156$, $y_{\text{max}}=0.267103189302944$, minimum path length $s_{\text{min}}=3.065013667336774$, and mean path length $\bar s=3.648267343901591$.


We can set the value of $C$ by applying initial conditions for $y^{\prime}(0)$ and so we have a relation between $y^{\prime}$ and $x$:
We can differentiate this to set up Newton’s method for solving for $y^{\prime}$ given $x$:
Then we can solve the differential equation, keeping track of the extra length
that weren’t taken into account by integrating those ‘constant’ terms
$$\frac1{2B}\int_0^B\left(w+\sqrt{w^2+(B-x)^2}\right)dx=\frac14\sqrt{B^2+w^2}+\frac{w^2}{4B}\ln\left(\frac{B+\sqrt{B^2+w^2}}w\right)+\frac w2$$
Then we mess around with that initial slope $y^{\prime}(0)$ until our trajectory reaches $(B,0)$ and we have a solution. The derivative function:

% f.m

function yprime = f(t,y);

global B C y0p

yp = y0p;
v = y(2);
x = t;
err = 1;
tol = 1.0e-6;

while abs(err) > tol,
    g = sqrt(1+yp^2)*(yp+sqrt(1+yp^2))-(2*B-x)/C;
    gp = (yp+sqrt(1+yp^2))^2/sqrt(1+yp^2)+1/C;
    err = g/gp;
    yp = yp-err;
y0p = yp;

yprime = [yp; ((2*B-x)*sqrt(1+yp^2)-y(1))/(2*B); sqrt(1+yp^2)];

The program:

% Wall.m

global B C y0p

B = 3;
y0p = 0.29190595656;
C = 2*B/(sqrt(1+y0p^2)*(y0p+sqrt(1+y0p^2)));
w = 1;
y0 = [0 0 0];

xspan = [0 B];
options = odeset('AbsTol',1.0e-12);
[t,y] = ode45(@f,xspan,y0,options);
format long;
err = y(end,1)
meanlen = y(end,2)+1/4*sqrt(B^2+w^2)+w^2/(4*B)*log((B+sqrt(B^2+w^2))/w)+w/2
minlen = y(end,3)

The trajectory:
Figure 1

The final result for initial slope was $y^{\prime}(0)=0.29190595656$ and the optimal length was $3.648267344782407$. On a non-wall day, the path length was $3.065013635851723$.

EDIT: By popular demand I have included a Matlab program that simulates the walk for a given polygonal path. I hope the comments and your thinking about the problem will permit you to write a similar program. Here is the subroutine that does the simulation.

% get_lengths.m

% get_lengths.m simulates the walk between points A and B

% inputs:
% nPoints = number of vertices of the polygonal path
% x = array of the nPoints x-coordinates of the vertices
% y = array of the nPoints y-coordinates of the vertices
% B = distance between points A and B
% w = half-width of wall
% nWall = number of wall positions to be simulated
%         nWall must be big enough that the distance between
%         simulation points is less than smallest distance
%         between to consecutive values in array x

% outputs:
% meanlen = mean path length on wall day as determined
%           by simulation
% minlen = path length on non-wall day

function [meanlen,minlen] = get_lengths(nPoints,x,y,B,w,nWall);
% Initially we haven't gone anywhere
meanlen = 0;
minlen = 0;
current_y = y(1);
current_x = x(1);
nextx = 2; % index of next path vertex
% find dimensions of first triangle in path
base = x(2)-x(1);
altitude = y(2)-y(1);
hypotenuse = sqrt(base^2+altitude^2);
% length of step in wall position
dx = B/(nWall-1);
% simulation loop
for k = 1:nWall,
    xWall = (k-1)*dx; % Next wall position
    % Now the tricky part: we have to determine whether
    % the next wall placement will go beyond the next
    % path vertex
    if xWall <= x(nextx),
        % Find steps in path length and y using similar triangles
        xstep = xWall-current_x;
        minlen = minlen+xstep*hypotenuse/base;
        current_y = current_y+xstep*altitude/base;
        current_x = xWall;
        % get length of path after we hit the wall
        meanlen = meanlen+minlen+(w-current_y)+sqrt((B-current_x)^2+w^2);
        % We have to update triangle because the next wall placement
        % is past the next vertex
        % get path length to next vertex
        % Step to next vertex
        xstep = x(nextx)-current_x;
        minlen = minlen+xstep*hypotenuse/base;
        % update triangle
        base = x(nextx+1)-x(nextx);
        altitude = y(nextx+1)-y(nextx);
        hypotenuse = sqrt(base^2+altitude^2);
        % Step to next wall position
        xstep = xWall-x(nextx);
        minlen = minlen+xstep*hypotenuse/base;
        current_y = y(nextx)+xstep*altitude/base;
        current_x = xWall;
        % get length of path after we hit the wall
        meanlen = meanlen+minlen+(w-current_y)+sqrt((B-current_x)^2+w^2);
        % update vertex index
        nextx = nextx+1;
% turn sum of simulation lengths into mean
meanlen = meanlen/nWall;

Here is a test program that runs a couple of sample paths

% sample.m

% sample.m -- tests get_lengths with a sample set of points
B = 3; % length of gauntlet normally 3 miles
w = 1; % half-width of wall, normally 1 mile
nPoints = 7; % number of vertices
nWall = 1000; % number of wall positions
% here are the x-coordinate of the vertices
x = [0.0 0.5 1.0 1.5 2.0 2.5 3.0];
% here are the x-coordinate of the vertices
y = [0.0000 0.1283 0.2182 0.2634 0.2547 0.1769 0.0000];
% Simulate!
[meanlen, minlen] = get_lengths(nPoints,x,y,B,w,nWall);
% print out results
fprintf('Results for optimal path\n');
fprintf('Average wall day length = %17.15f\n',meanlen);
fprintf('Average non-wall day length = %17.15f\n',minlen);
fprintf('Average overall length = %17.15f\n', (meanlen+minlen)/2);
% simulate another set of wall parameters
y = [0.0000 0.1260 0.2150 0.2652 0.2711 0.2178 0.0000];
% Simulate!
[meanlen, minlen] = get_lengths(nPoints,x,y,B,w,nWall);
% print out results
fprintf('Results for another path\n');
fprintf('Average wall day length = %17.15f\n',meanlen);
fprintf('Average non-wall day length = %17.15f\n',minlen);
fprintf('Average overall length = %17.15f\n', (meanlen+minlen)/2);

Output of the test program

Results for optimal path
Average wall day length = 4.237123943909202
Average non-wall day length = 3.062718632179695
Average overall length = 3.649921288044449
Results for another path
Average wall day length = 4.228281363535175
Average non-wall day length = 3.074249982789312
Average overall length = 3.651265673162244


EDIT: Since my program might be awkward for others to adapt, I have provided a program that computes optimal polygonal paths. It starts with a $3$-point path and varies the free point using Golden Section Search until it finds an optimal path. Then it subdivides each interval of the path, creating a $5$-point path. It makes repeated sweeps through the $3$ free points of the path until the changes are small enough. Then it subdivides again until a $65$-point path is optimized. Here is the new program:

% wiggle.m

% wiggle.m attempts to arrive at an optimal polygonal solution to
% the wall problem. It starts with a 3-point solution and wiggles
% free point up an down until it is optimally placed. Then it
% places points halfway between each pair of adjacent points and
% then wiggles the free points, back to front, until each is
% optimal for the other point locations and repeats until the
% changes from sweep to sweep are insignificant. Then more intermediate
% points are added...

clear all;
close all;
B = 3; % Length of gauntlet
w = 1; % Wall half-width
% Next two parameters increase accuracy, but also running time!
nWall = 4000; % Number of wall positions to simulate
tol = 0.25e-6; % Precision of y-values
fid = fopen('wiggle.txt','w'); % Open output file for writing
phi = (sqrt(5)+1)/2; % Golden ratio
x = [0 B]; % initial x-values
y = [0 0]; % initial guess for y-values
npts = length(y); % Current number of points
legends = []; % Create legends for paths
nptsmax = 65; % Maximum number of points
% Main loop to generate path for npts points
while npts < nptsmax,
    % Subdivide the intervals
    npts = 2*npts-1;
    % Create x-values and approximate y-values for new subdivision
    xtemp = zeros(1,npts);
    yold = zeros(1,npts);
    for k = 2:2:npts-1,
        xtemp(k) = (x(k/2)+x(k/2+1))/2;
        xtemp(k+1) = x(k/2+1);
        yold(k) = (y(k/2)+y(k/2+1))/2;
        yold(k+1) = y(k/2+1);
    x = xtemp;
    y = yold;
    maxerr = 1;
    % Each trip through this loop optimizes each point, back to front
    while maxerr > tol,
        % Each trip through this loop optimizes a single point
        for n = npts-1:-1:2,
            ytest = y; % Sample vector for current path
            % Guess range containing minimum
            if npts == 3,
                y1 = 0.0;
                y3 = 0.5;
                y1 = min([y(n-1) y(n+1)]);
                y3 = max([y(n-1) y(n) y(n+1)]);
            % Third point for golden section search
            y2 = y1+(y3-y1)/phi;
            % Find lengths for all 3 candidate points
            ytest(n) = y1;
            [u,v] = get_lengths(length(ytest),x,ytest,B,w,nWall);
            L1 = (u+v)/2;
            ytest(n) = y2;
            [u,v] = get_lengths(length(ytest),x,ytest,B,w,nWall);
            L2 = (u+v)/2;
            ytest(n) = y3;
            [u,v] = get_lengths(length(ytest),x,ytest,B,w,nWall);
            L3 = (u+v)/2;
            % It's really difficult to bracket a minimum.
            % If we fail the first time, we creep along for
            % a little while, hoping for success. Good for npts <= 65 :)
            nerr = 0;
            while (L2-L1)*(L3-L2) > 0,
                y4 = y3+(y3-y2)/phi;
                ytest(n) = y4;
                [u,v] = get_lengths(length(ytest),x,ytest,B,w,nWall);
                L4 = (u+v)/2;
                y1 = y2;
                L1 = L2;
                y2 = y3;
                L2 = L3;
                y3 = y4;
                L3 = L4;
                nerr = nerr+1;
                if nerr > 10,
                    error('error stop');
            % Now we have bracketed a minimum successfully
            % Begin golden section search. Stop when bracket
            % is narrow enough.
            while abs(y3-y1) > tol,
                % Get fourth point and length
                y4 = y3-(y2-y1);
                ytest(n) = y4;
                [u,v] = get_lengths(length(ytest),x,ytest,B,w,nWall);
                L4 = (u+v)/2;
                % Update bracketing set
                if L4 < L2,
                    y3 = y2;
                    L3 = L2;
                    y2 = y4;
                    L2 = L4;
                    y1 = y3;
                    L1 = L3;
                    y3 = y4;
                    L3 = L4;
            % Record our new optimal point
            y(n) = y2;
        % Find maximum change in y-values
        maxerr = max(abs(y-yold));
        yold = y;
    % Save optimal length to file
    fprintf(fid,'N = %d, L = %10.8f\n', npts, L2);
    % Only plot early curves and final curve
    if (npts <= 9) || npts >= nptsmax,
        % Add legend entry and plot
        legends = [legends {['N = ' num2str(npts)]}];
        hold on;
% Print legend
% Print labels
title('Optimal Polygonal Paths');

Here are the lengths of the optimal paths found:
$$\begin{array}{rr}\text{Points}&\text{Length}\\ \hline
And of course a graphical depiction of the paths:
Figure 2
This was counterintuitive to me in that the paths with fewer points lay entirely below the paths with more points.

Let $l$ be the length $AB$ ($3$ miles), $h$ the size of the wall ($1$ mile), $p$ the probability that the wall appears $(1/2)$

Suppose our strategy is to walk along the curve $y = f(x)$ where $f(0) = f(l) = 0, 0 \le f(x) \le h$ for $x \in [0 ; l]$ until we hit the wall and then go around it then make a straight path to $B$.

Call $g(x)$ the length of the curve $(t,f(t))$ for $t \in [0;x]$.

The expected length of the trip is then :

$E(f) = (1-p)g(l) + \frac pl \int_0^l (g(x)+(h-f(x))+\sqrt{(l-x)^2+h^2}) dx$.

Minimizing $E(f)$ is then equivalent to minimizing $(1-p)g(l) + \frac pl \int_0^l (g(x)-f(x)) dx$, which is a combination of the total curve length, the mean curve length, and the area under $f$.

Suppose we modify $f$ locally near a point $x$, making an increase in length of $dg$ and increase in area of $da$.

This modifies $E(f)$ by $(1-p)dg + p/l((l-x)dg – da) = (1-px/l)dg – (p/l)da$, so we improve $f$ when $dg/da < p/(l-px)$ when $da,dp > 0$ and when $dg/da > p/(l-px)$ when $da,dp < 0$.

This shows that if we ever have a convex portion in our curve, we really should just cut straight through it since this modification has $dg/da < 0 (< p/(l-px))$. Therefore the optimal $f$ is concave.

The threshold on $dg/da$ translates directly into the curvature at which we can’t improve our score anymore by changing the curvature. When making an infinitesimal change of curvature of an arc or radius $r$, we get an efficiency $dg/da = \kappa = 1/r$ (this is a restatement of the isoperimetric theorem)

If the curvature didn’t vary this would be exact, but this method yields only a simple approximation by finding the curve from $(0,0)$ to $(l,0)$ where $\kappa = p/(l-px)$.
the curvature is a increasing function of $x$, we get $r = l/p = 2l$ at the start, down to $r = l(1-p)/p = l$ at the other end.

Interestingly, it seems the solution doesn’t care about what $h$ actually is until it crosses the line $y=h$

In our case, starting at $y=0$ with a slope of about $y’=0.3236$ and then numerically solving the differential equation

$y” = \kappa(x) (1 + y’^2)^\frac 32= \frac{1}{6-x} (1 + y’^2)^\frac 32$

we obtain a curve of length about $3.0621$ miles, and an expected trip length of about $3.648$ miles

enter image description here

Here is what the curve looks like with the two osculating circles at the endpoints.

The correct curvature to minimize $\int A \sqrt{1+f'(x)^2} dx + \int (\int_0^{f(x)} B dy)dx$ is given by $A\kappa = \vec \nabla A . \vec n + B$ where $\vec n$ is the unit vector normal to the curve.

Taking this correction into account, you get @user5713492’s solution.

Suppose you walk in a straight line and follow the wall if you encounter the wall. Let’s call $x$ the distance between the middle of the wall and the point where you would intercept the wall if there was one.

If there is no wall, your travel distance will be $2\sqrt{x^2+1.5^2}$
If there is a wall, your travel distance will be $\sqrt{x^2+1.5^2}+1-x+\sqrt{1+1.5^2}$ (suppose $x>0$)

Hence, your expected travel distance is

$$f(x) = \sqrt{x^2+1.5^2}+ \frac{ \sqrt{x^2+1.5^2}+1-|x|+\sqrt{1+1.5^2} }{2}$$

A quick study of this function gives you a minimum at $x = \frac{3}{4\sqrt{2}} \simeq 0.53 \text{miles}$

Well, I had given this answer last night on the post here, which scaled everything by a factor of 3:
Optimal path around an invisible wall

To save time, I will copy-and-paste my answer here, and will assume the length of AB is 1 and the wall length is 1/3 in each direction. You can multiply everything by a factor of 3 later.

[I am changing my $y$-discretization to make it finer, in response to another Michael comment below.]

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 $m$ segments of length $\delta_y = (1/3)/m$. 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:

J((k-1)\delta_x, y) &= P[\mbox{wall is here | have not yet seen it}]\left[1/3-y + \sqrt{1/9+ (1-(k-1)\delta_x)^2}\right]\\
&+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]
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)} $$

Note: I wrote a C program to implement the above. Using $m=n$ restricts the slope options and leads to trapezoid-trajectories. That led me to incorrectly conjecture that trapezoids were optimal. Using a finer-grained slope option (as suggested by another Michael in a comment below), such as $m=100n$, gives curvy trajectories that seems consistent with two more recent answers here that look at optimizing the entire trajectory via variational analysis. Here is an optimization over the (suboptimal) trapezoid functions and for the continuous version of the problem: Let $f(x)$ be the height as a function of $x$, being the trajectory to follow until we bump into the wall (if we ever do). So we start at $f(0)=0$. A class of functions is:
$$ f(x) = \left\{ \begin{array}{ll}
x/3 &\mbox{ if $x \in [0, \theta]$} \\
\theta/3 & \mbox{ if $x \in [\theta, 1-\theta]$}\\
-(x-1)/3 & \mbox{ if $x \in [1-\theta, 1]$}

The best $f(x)$ over this class gives a minimum average distance of:
dist^* &= -7 + 5\sqrt{\frac{5}{2}} + \frac{1}{2}\int_{0}^1 \sqrt{1/9 + x^2}dx \approx 1.21973\\
3dist^* &\approx 3.6592
This is achieved by $\theta = 5 – 3\sqrt{5/2}$. This is strictly better than the naive policy of going straight until you bump into a wall, so it shows the naive policy is suboptimal.

At any point the ideal position would be either in the middle or at the corner, depending on if this point is the wall or not. The probability for this position $x_b$ being a wall position given that we already are at another point $x_a$ is $\frac{1}{2}\frac{1-x_a}{n}$ where $n$ is the resolution of a simulation. That is n steps in the dimension from start to goal.

So two cases for each pair of points $(x_a,x_b)$:

  1. direction $(x_b-x_a,y-y_a)$ with probability $\frac{1}{2}\frac{1-x_a}{n}$
  2. direction $(x_b-x_a,0-y_a)$ with probability $1-\frac{1}{2}\frac{1-x_a}{n}$

Calculting the expected vector from each ($x_a,y_a$) as a weighted sum of the above cases would give us a set of vectors from each point which we could interpolate our way forward through.

This is probably not the best way as I probably forgot something, but at least presents one important way to think : calculate a vector field which we then use as the help to calculate a path through following the arrows.

$UPDATE~~1$: I wrote a computer program to pick only $2$ slopes, one from miles $0$ to $1$ and the other from $1$ to $2$ and it told me $.2154$ was best for the first mile and $.0346$ was best for the 2nd mile. So only “wiggling” $2$ target points, the program is already converging on the optimal position to be in at miles $1$ and $2$. The program puts us at x,y coordinates ($1$, .$2154$) and ($2$, .$2500$) which are very close to the optimal positions of ($1$, .$2182$) and ($2$, .$2547$). My next step is to try $5$ wiggle points equi-spaced (each half mile) between endpoints A ($0$,$0$) and B ($3$,$0$) but using the previous slopes as guidelines so I only need to check values close to those. For example, I know the slope for miles $0$ to $1$ should be about $.2154$ so when I bisect that leg of the journey, I only need to check slopes close to that. When I get the results of the $5$ points I will post here as another update.

$UPDATE~~2$: The program is working very well as I can easily take the output of a previous run and use it to fine tune the next run. When I bisect each leg of the walk path to get double the number of slopes (thus better approximating a curved path), I use $3/4$ for the low limit of the slope to check and $5/4$ for the high limit. To better understand this, imagine the slope of $.2154$ given to me by my program (for the 1st mile) and then I want to bisect that into $2$ slopes. Those $2$ slopes need not be the same as the single slope but likely they will be “ballpark” so that is where I get the $3/4$ and $5/4$ bounds to check. So for example, I will check all slopes between (inclusive) $3/4$ of $.2154$ and $5/4$ of $.2154$ for the $2$ segments which are miles $0$ to $0.5$ and $0.5$ to $1.0$.
An even better algorithm would be to only check subslopes that are “complementary” in that the combination of them is “ballpark” to the slope they were derived from. For example: if the program tells me the slope from mile $0$ to $1$ should be around $.2154$ (which it did), then when I bisect that into $2$ slopes, if I am checking the first part of the slope for something like $0.25$, it wouldn’t make sense to also check the 2nd part of the slope also at $0.25$ cuz that would put us too high at mile $1$. The idea is when you increase the first subslope beyond that of its “source” slope, to accordingly decrease the 2nd subslope, so the 2 subslopes have a combined net slope very similar to the single slope it was derived from. So basically it can be thought of as putting a hinge at each bisection of existing points, and bending the slopes slightly at the hinge, but in such a way that the endpoints of the hinge pretty much stay stationary.

It is possible to have a fast computer try out many different (x,y) points but start with a few first to get a general idea of the optimal walk path, then use that data as a starting point to then make more points with an epsilon “allowance” up or down for the possible y values. For example, write a program that starts out with only $4$ (x,y) coordinates and attempts to optimize it. Then take those $4$ points and bisect them, turning it into $7$ points but only allowing a small deviation from the $4$ points you previously optimized so that you don’t have to recheck a bunch of points that are very likely not optimal. For example, suppose the first $4$ points your simulation program derives are $(0,0), (1, 0.2), (2, 0.25), (3,0)$. The next step would be to bisect those $3$ segments into $6$ but keep the $4$ previously known points close to their original values. For example, at x=$1$, only check y values from maybe $0.1750$ to $0.2250$ in small increments (perhaps $0.0001$ so only $500$ increments to check).

Also, what I like to do to help manage complexity (to help keep things as simple as possible), is after first solving the simplest case which is $4$ point, $2$ of which are the endpoints A and B (so those don’t need any optimizing), is to copy that code to another file in case when I bisect the existing segments if I mess up, I can easily go back to the simpler program and start over. Also it is useful for checking and comparing other things such as path length to see how the path length changes when we add more segments (thus more closely following a curve shape).

Also, it appears to me the optimal walk curve shape can be approximated very nicely by using $8$ subpaths using fixed slopes. The path length for this is $3.06357$ miles. When I use $2999$ equidistant wall positions from miles $0.001$ to $2.999$, I get about $3.6492$ miles average walk distance so that helps confirm it is an excellent approximation to optimal. The “granularity” is set for about $0.4$ miles (direction change every $0.4$ miles approximately) with a flat section between miles $1.5$ and $1.9$. I suspect that if $2$ people walked the entire $2$ paths on a non wall day, (one taking the curved path and one taking my $8$ slope simplified path), they would never be more than about $48$ feet away from each other (according to the table at mile marker $2.2$) and would bump into each other many times. The average distance between them would be about $19$ feet. At mile $1.0$, they would be only $1$ foot apart from each other.

\begin{array}{rrrr}segment&x~mile~range&slope&y~values\\ \hline1&0.0~~to ~~0.5&.256&.000~to~.128\\ 2&0.5~~to~~1.0&.18&.128~to~.218\\ 3&1.0~~to~~1.5&.09&.218~to~.263\\ 4&1.5~~to~~1.9&0&.263~to~.263\\ 5&1.9~~to~~2.4&-.13&.263~to~.198\\ 6&2.4~~to~~2.6&-.24&.198~to~.150\\ 7&2.6~~to~~2.9&-.35&.150~to~.045\\ 8&2.9~~to~~3.0&-.45&.045~to~.000\\ \end{array}

Here is the table of the data points from someone else’s solution and my simple solution where I compute the optimal y values based on a known wall position but not a known day (wall day or not). I divided my optimal y values by $2$ and they seem to almost match the other solution, especially around x=$1.4$. They are so close it is worth investigating why. The exception is they start to deviate significantly as x approaches $3$.

\begin{array}{rrrr}x&y&my~y/2&8~segment~y\\ \hline0.0&0.0000&0.0000&0.0000\\ 0.1&0.0285&0.0282&0.0256\\ 0.2&0.0556&0.0548&0.0512\\ 0.3&0.0813&0.0800&0.0768\\ 0.4&0.1056&0.1037&0.1024\\ 0.5&0.1283&0.1260&0.1280\\ 0.6&0.1495&0.1467&0.1460\\ 0.7&0.1692&0.1660&0.1640\\ 0.8&0.1872&0.1839&0.1820\\ 0.9&0.2036&0.2002&0.2000\\ 1.0&0.2182&0.2150&0.2180\\ 1.1&0.2310&0.2282&0.2270\\ 1.2&0.2421&0.2399&0.2360\\ 1.3&0.2512&0.2500&0.2450\\ 1.4&0.2583&0.2584&0.2540\\ 1.5&0.2634&0.2652&0.2630\\ 1.6&0.2663&0.2702&0.2630\\ 1.7&0.2671&0.2734&0.2630\\ 1.8&0.2654&0.2747&0.2630\\ 1.9&0.2614&0.2740&0.2630\\ 2.0&0.2547&0.2711&0.2500\\ 2.1&0.2453&0.2660&0.2370\\ 2.2&0.2331&0.2584&0.2240\\ 2.3&0.2177&0.2481&0.2110\\ 2.4&0.1991&0.2347&0.1980\\ 2.5&0.1769&0.2178&0.1740\\ 2.6&0.1508&0.1966&0.1500\\ 2.7&0.1206&0.1701&0.1150\\ 2.8&0.0858&0.1363&0.0800\\ 2.9&0.0458&0.0906&0.0450\\ 3.0&0.0000&0.0000&0.0000\\ \end{array}

enter image description here

A good way to approximate this table of optimal y values based on x is to use this formula (and set the endpoints to 0):

y = ($-0.00519876$ * $x^4$) + ($0.0122894$ * $x^3$) – ($0.090321$ * $x^2$) + ($0.300821$ * $x$) – $0.00014741$.

Also for simulation on a computer, I wonder if for starters (not knowing the general shape of the optimal path), if someone tried a “hold height” method, what would happen. For example, from point A, quickly (via slope $1$) go up to some fixed y (such as $0.5$) and hold it for almost the entire walk, then back down to B at the very end at slope $-1$. So the middle $2$ miles would be at y position $0.5$. Then the person could try different values for y, perhaps giving a clue of the maximum y value to never go above. This should help subsequent simulation. I may try to model this to see which y is best. It relates to this problem since it might help someone using a simulation method to narrow down the y values needed to test.

Another good yet very simple path to walk is the upper part of a trapezoid with slope $.18$ from miles $0$ to $1.5$, flat (at y=.$27$ ) from miles $1.5$ to $1.9$, then slope $-.2454545$… the rest of the way. This yields a non wall path distance of $3.0568$ and an average distance of about $3.656$ which is much closer to optimal (about $3.648$) than to naive (about $3.692$).

Lastly, someone should investigate why, when solving the known wall position problem but not knowing if it is a wall day or not, why the y values are almost exactly double those of this unknown wall position unknown wall day problem (see the graph with the $2$ plots). Up to about mile marker $1.5$ they appear to be almost identical, then start to deviate slightly and more than slightly when x approaches $3$. Why is this? It is worth investigating cuz someone could almost solve this more difficult variation simply by solving the simpler (known wall position if present) case, then just dividing the y value results by $2$. It is not optimal but is very close.