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.

  • 4
    $\begingroup$ Nice question! What have you done so far? $\endgroup$ Apr 16, 2016 at 14:49
  • $\begingroup$ I am contemplating possible computer simulations. So far I just started with a simple "base case" where I just walk straight along the AB path and if I hit the wall, I just walk around it and then directly to point B. That is clearly non optimal but a good starting point to try to beat. Using that method I got $3.6918$ miles on average. My idea for near optimal is to walk at an angle up from A such that it will hit the wall (if present) $0.5$ miles (midway) up from direct AB path the gradually turn back more towards B as we pass the midway ($1.5$ mile ) marker. $\endgroup$
    – David
    Apr 16, 2016 at 14:54
  • $\begingroup$ I suggest that you add the comment above in the text of your question, to prevent down-votes. $\endgroup$ Apr 16, 2016 at 14:56
  • 1
    $\begingroup$ Makes sense, thanks (I'll withdraw the close vote). It's a great question....the Psychic strategy (where you know everything about the wall) isn't that much better than realizable strategies. You have to work awfully hard for marginal improvements. $\endgroup$
    – lulu
    Apr 16, 2016 at 15:18
  • 4
    $\begingroup$ Part of the problem is we don't know where the wall is if it is anywhere. So we could change direction a lil bit each second we haven't hit the wall because we learn something new from not hitting it (yet). $\endgroup$ Apr 16, 2016 at 15:59

7 Answers 7


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_0=\cfrac{\sqrt{57}-21}{8}=-1.68127$$ $$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. Luckily, @Trefox did the computation which results in a path length of $3/2 \cdot \sqrt{1/2 \cdot (31 - 3 \sqrt{57})} $

$$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}$$ $$=3.64827...$$

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.

  • $\begingroup$ What is the actual optimal walked path? Can you describe it and/or draw it? $\endgroup$
    – David
    Apr 16, 2016 at 17:08
  • $\begingroup$ @David The optimal path is walked if the walker correctly "guesses" where the wall will be. Then that walker would walk directly from point A to the tip of the wall, then from the tip of the wall to point B. $\endgroup$
    – Zach466920
    Apr 16, 2016 at 17:10
  • $\begingroup$ Oh I see so this is best case but not achievable. This would be the correct solution if they could somehow cheat so now we have the correct answer being "sandwiched" between this lower bound ($3.3842$) and my 1st effort very simple algorithm which produced $3.6918$ miles. So the correct answer must be somewhere close to $3.5$ miles I would assume based on the "logic" that the solution must be somewhere between best case (which is un-achievable) and some non-optimal valid solution. $\endgroup$
    – David
    Apr 16, 2016 at 17:14
  • 1
    $\begingroup$ @Michael Sorry I meant to put 3. I slipped up I guess. Honestly, my solution only works if my argument for a linear function is correct. There's a lot of functions so it's possible something, possibly likely, something better exists... $\endgroup$
    – Zach466920
    Apr 16, 2016 at 19:56
  • 1
    $\begingroup$ For anyone curious, the exact length of this optimal path is 3/2 Sqrt[1/2 (31 - 3 Sqrt[57])] $\endgroup$
    – Nico A
    Jun 3, 2018 at 20:37

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 $$\frac1B\int_0^B\left[\int_0^u\sqrt{1+\left(y^{\prime}(x)\right)^2}dx+w-y(u)+\sqrt{w^2+(B-u)^2}\right]du$$ On a non-wall day, our average distance is the uninterrupted path length, $$\int_0^B\sqrt{1+\left(y^{\prime}(x)\right)^2}dx=\frac1B\int_0^BB\sqrt{1+\left(y^{\prime}(u)\right)^2}du$$ Since half of the days are wall days, the average distance is $$\frac1{2B}\int_0^B\left[\int_0^u\sqrt{1+\left(y^{\prime}(x)\right)^2}+w-y(u)+\sqrt{w^2+(B-u)^2}+B\sqrt{1+\left(y^{\prime}(u)\right)^2}\right]du$$ Now, we can change the order of integration of that double integral to get $$\begin{align}\int_0^B\int_0^u\sqrt{1+\left(y^{\prime}(x)\right)^2}dx\,du&=\int_0^B\sqrt{1+\left(y^{\prime}(x)\right)^2}\int_x^Bdu\,dx\\ &=\int_0^B(B-x)\sqrt{1+\left(y^{\prime}(x)\right)^2}dx\end{align}$$ 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 $$\frac{y^{\prime}+\left(y^{\prime}\right)^3-(2B-x)y^{\prime\prime}}{\left(1+\left(y^{\prime}\right)^2\right)^{\frac32}}-1=0$$ This is a variables separable differential equation for $y^{\prime}$ and we are going to write it as $$\frac{dx}{2B-x}=\frac{dy^{\prime}}{y^{\prime}\left(1+\left(y^{\prime}\right)^2\right)-\left(1+\left(y^{\prime}\right)^2\right)^{\frac32}}$$ Letting $y^{\prime}=\sinh\theta$, we have $$\frac{dx}{2B-x}=-\left(\frac{\sinh\theta}{\cosh\theta}+1\right)d\theta$$ And we have an integral: $$-\ln(2B-x)=-\ln(\cosh\theta)-\theta-C_1$$ $$2B-x=C\sqrt{1+\left(y^{\prime}\right)^2}\left(y^{\prime}+\sqrt{1+\left(y^{\prime}\right)^2}\right)$$ 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: $$v=\frac{2B-x}C=y^{\prime}\sqrt{1+\left(y^{\prime}\right)^2}+1+\left(y^{\prime}\right)^2$$ Then isolate the radical and square out: $$(v-1)^2-2(v-1)\left(y^{\prime}\right)^2+\left(y^{\prime}\right)^4=\left(y^{\prime}\right)^2+\left(y^{\prime}\right)^4$$ Then we can simplify a little to $$(v-1)^2=(2v-1)\left(y^{\prime}\right)^2$$ Now we will make the final substitution of $\xi=2v-1$ so that $v=\frac{\xi+1}2$ and $$\frac{(v-1)^2}{2v-1}=\frac{(\xi-1)^2}{4\xi}=\left(y^{\prime}\right)^2$$ Taking square roots, $$\frac{\xi-1}{2\sqrt{\xi}}=y^{\prime}=\frac{dy}{dx}=\frac{dy}{d\xi}\frac{d\xi}{dv}\frac{dv}{dx}=-\frac2C\frac{dy}{d\xi}$$ We can integrate to $$\frac13\xi^{\frac32}-\xi^{\frac12}=-\frac2Cy+C_1$$ 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 $$\frac13\xi^{\frac32}-\xi^{\frac12}-\frac13\xi_f^{\frac32}+\xi_f^{\frac12}=-\frac2Cy$$ At $x=0$, $y=0$, $\xi=\xi_0=\frac{4B}C-1=2\xi_f+1$ and $$\frac13\xi_0^{\frac32}-\xi_0^{\frac12}-\frac13\xi_f^{\frac32}+\xi_f^{\frac12}=0$$ Isolating like radicals and squaring out, $$(2\xi_f+1)^3-6(2\xi_f+1)^2+9(2\xi_f+1)=\xi_f^3-6\xi_f^2+9\xi_f$$ Simplifying, $$7\xi_f^3-6\xi_f^2-9\xi_f+4=(\xi_f+1)(7\xi_f^2-13\xi_f+4)=0$$ With solution set $$\xi_f\in\left\{0,\frac{13+\sqrt{57}}{14},\frac{13-\sqrt{57}}{14}\right\}\cap(0,1)=\left\{\frac{13-\sqrt{57}}{14}\right\}$$ Since $$\xi_f=\frac{13-\sqrt{57}}{14}=\frac{2B}C-1$$ $$C=\frac{(27+\sqrt{57})B}{24}$$ $$\xi_0=2\xi_f+1=\frac{20-\sqrt{57}}7$$ $$x=2B-Cv=2B-C\frac{(\xi+1)}2=\left(\frac{69-\sqrt{57}}{48}-\frac{27+\sqrt{57}}{48}\xi\right)B$$ We can find the initial slope $$y^{\prime}(0)=\frac{\xi_0-1}{2\sqrt{\xi_0}}=\frac{\xi_f}{\sqrt{\xi_0}}=\frac{13-\sqrt{57}}{98}\sqrt{20+\sqrt{57}}$$ The path reaches the farthest from the straight line when $y^{\prime}=0$, $\xi=1$, so $$x=\frac{21-\sqrt{57}}{24}B$$ $$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}\\ &=-\frac{(27+\sqrt{57})B}{144}\left[\xi_f^{\frac32}+3\xi_f^{\frac12}-\xi_0^{\frac32}-3\xi_0^{\frac12}\right]\\ &=\frac{75+\sqrt{57}}{72}\sqrt{\frac{20-\sqrt{57}}7}-\frac{51+\sqrt{57}}{72}\sqrt{\frac{13-\sqrt{57}}{14}}\end{align}$$ 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{C^2}{48B}\int_{\xi_0}^{\xi_f}\left[-5\xi^{\frac32}-3\xi^{-\frac12}+2\xi_f^{\frac32}-6\xi_f^{\frac12}\right]d\xi\\ &=\frac{C^2}{48B}\left[-2\xi^{\frac52}-6\xi^{\frac12}+2\xi_f^{\frac32}\xi-6\xi_f^{\frac12}\xi\right]_{\xi_0}^{\xi_f}\\ &=\frac{C^2}{48B}\left[-6\xi_f^{\frac12}-6\xi_f^{\frac32}+2\xi_0^{\frac52}+6\xi_0^{\frac12}-2\xi_f^{\frac32}\xi_0+6\xi_f^{\frac12}\xi_0\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$: $$f(y^{\prime})=\sqrt{1+\left(y^{\prime}\right)^2}\left(y^{\prime}+\sqrt{1+\left(y^{\prime}\right)^2}\right)-\frac{2B-x}C=0$$ We can differentiate this to set up Newton's method for solving for $y^{\prime}$ given $x$: $$f^{\prime}\left(y^{\prime}\right)=\frac{\left(y^{\prime}+\sqrt{1+\left(y^{\prime}\right)^2}\right)^2}{\sqrt{1+\left(y^{\prime}\right)^2}}+\frac1C$$ Then we can solve the differential equation, keeping track of the extra length $$v^{\prime}(x)=\frac1{2B}\left[(2B-x)\sqrt{1+\left(y^{\prime}\right)^2}-y\right]$$ 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 3&3.66067701\\ 5&3.65156744\\ 9&3.64914214\\ 17&3.64852287\\ 33&3.64836712\\ 65&3.64832813\\ \end{array}$$ 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.

  • $\begingroup$ I had a "hunch" the solution would be something like this (a curved shape). It makes sense since for the 2nd half of the trip, the probability of not seeing the wall increases as we successfully walk without hitting it. Also in the first half of the trip, it makes sense to walk at a "steep" angle North (up) anticipating a wall, getting in a reasonable position if the wall is present (but not too far North). My simple solution path of y peaking at $0.5$ at x=$1.5$ was a reasonable try and yielded $3.68881557$ miles which is not bad. $\endgroup$
    – David
    Apr 18, 2016 at 11:01
  • $\begingroup$ Also if I had instead made y peak at only $0.25$ instead of $0.5$, I would have had a shape very close to this curve and likely a similar answer (but slightly longer). It is interesting to me how the curved peaks slightly past $1.5$ miles (at about $1.75$ miles) and is asymmetrical. $\endgroup$
    – David
    Apr 18, 2016 at 11:06
  • 1
    $\begingroup$ interesting, i can confirm you get a curve slightly better than mine, so I guess my considerations about the curvature aren't as powerful as i thought they were. $\endgroup$
    – mercio
    Apr 18, 2016 at 14:51
  • 1
    $\begingroup$ In other words, if we know we are supposed to be at $0.53$ y position if the wall is at the midpoint (mile $1.5$), shouldn't the curve pass thru that point? If it doesn't, should that mean that the partial solution (in that case) is suboptimal? This is the part I don't quite understand. How can the continuous solution (of any wall position) have different partial solutions than any single random wall position we pick? What would happen if we just solved for the $31$ discrete points you have listed in your table and then connect those dots? What would be that average walk distance? $\endgroup$
    – David
    Apr 20, 2016 at 12:11
  • 1
    $\begingroup$ @David see my latest edits. I have implemented a Golden Section Search to find optimal $y$-values and the program is producing some interesting results. This search effectively does computationally what the Variational Principle achieves mathematically, similar to the way my get_lengths.m function does numerically what my $\bar s$ integral does mathematically. $\endgroup$ Apr 29, 2016 at 20:17

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.

  • $\begingroup$ It seems the solution needs to start with a slope of around $4/5$, and has a length of $3.3102...$, barring programming / implementation mistakes $\endgroup$
    – mercio
    Apr 17, 2016 at 11:49
  • $\begingroup$ and expected total length of $3.71...$ miles... ... :s $\endgroup$
    – mercio
    Apr 17, 2016 at 12:03
  • $\begingroup$ I'm still super confused at why my path is not optimal at all, since it's worse than your triangle (which isn't even the best triangle) and worse than a simple arc of radius 3. $\endgroup$
    – mercio
    Apr 17, 2016 at 14:43
  • $\begingroup$ Also everything breaks down for $p \ge 0.64$ I must be doing something really wrong or this is really strange. $\endgroup$
    – mercio
    Apr 17, 2016 at 14:53
  • $\begingroup$ Suppose I use x and y axis to denote x = wall position and y = height above centerline, both in units, (miles in this case). How do I use this solution to implement it in code to check it? That is, how can I "draw" the curve you describe so that I can get the correct y value based on a changing x value?. For example in my simple solution where y becomes 0.5 miles when x is 1.5 miles, then y goes back down to 0 when x is 3 miles is a simple function but how do I implement yours? How do I define y (the rise above centerline I need to be at during the walk) in terms of x (the wall position)? $\endgroup$
    – David
    Apr 17, 2016 at 22:54

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

  • $\begingroup$ Aiming at $0.53$ miles up (or down) the wall from A is optimal if the wall is at the midpoint ($1.5$ mile marker) but the wall appears at a random point along the AB path so you would not know what angle to walk at to intercept the wall (if present) at $0.53$ miles up (or down) from its center. $\endgroup$
    – David
    Apr 16, 2016 at 15:03
  • $\begingroup$ @David : I assumed it was in the middle, because the problem is unsolvable if you don't give the distribution of probablity where the wall will appear. If the point where the wall appear is random, the problem is indeed more complex $\endgroup$
    – Tryss
    Apr 16, 2016 at 15:26
  • $\begingroup$ The wall, (if present), is equally likely to appear at any point between A and B. In my computer simulation, I place the wall at every $1/100$th of a mile away from A so at $0.01$ miles, $0.02$ miles... $2.99$ miles. Assume the wall can appear anywhere including an inch before you get to B in which case you will have to detour about $2$ miles just to finish that last inch between A and B. (if you use the walk straight at B strategy). $\endgroup$
    – David
    Apr 16, 2016 at 15:54
  • $\begingroup$ Also I wanted to say I am somewhat surprised that the optimal and near optimal paths never rise more than about $1/4$ the distance of the wall before they actually hit the wall. I would expect close to $1/2$ the distance but that is not the case. I also wonder if I put a restriction on the wall position such that it could only appear between mile markers $1$ and $2$ if that would be about the same complexity as this original question where the wall could be anywhere in the $3$ miles. I wonder how it would change the path. $\endgroup$
    – David
    Apr 19, 2016 at 13:48
  • $\begingroup$ Also, for some strange unknown reason to me, you can use this fixed wall position formula to help solve the uniformly distributed (random) wall problem. Just take the y values for the fixed wall problem (such as your $0.53$ answer when the wall is at position $1.5$, and divide that answer by $2$ (to get $.265$). Do this for all possible wall positions (or at least a good amount of them), and you will have a nice path for the more difficult problem (but slightly worse than optimal). Nobody yet has mentioned why this method works. $\endgroup$
    – David
    Apr 24, 2016 at 12:28

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:

\begin{align} 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] \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)} $$

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]$} \end{array} \right.$$

The best $f(x)$ over this class gives a minimum average distance of:
\begin{align} 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 \end{align} 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.

  • $\begingroup$ Overall, I would just do the naive policy of going straight until we bump into the wall. Better yet: Throw a tennis ball and see if it bounces back: Measure the time required to bounce back and infer the location of the invisible wall, if any. $\endgroup$
    – Michael
    Apr 16, 2016 at 19:02
  • 1
    $\begingroup$ @David : The trapezoid policy starts out with a slope of 1/3, which is indeed "aiming" at the center point of a virtual wall located halfway, as you were suggesting. However, about halfway to this virtual wall, we stop increasing to this target and stay flat. $\endgroup$
    – Michael
    Apr 16, 2016 at 22:36
  • 2
    $\begingroup$ You have quantized the y-values in a way that the slope must be a multiple of 1/3. Could you try fewer x-values but more y-values? $\endgroup$
    – Empy2
    Apr 17, 2016 at 2:46
  • 1
    $\begingroup$ There are two new answers that suggest a curvy trajectory is better, which reduces my $1.21973$ number to about $1.216$. I will try to look if I have time. If true, that would disprove my conjecture, although in that case I do not know why my DP is giving me trapezoids. Upon closer inspection, my DP generates a trapezoid that is not completely symmetric, though that may be due to a discretization issue. I wonder what optimizing over asymmetric trapezoids with thresholds $\theta_1$ and $\theta_2$ would give. I could also try finer-grained discretization to see if my trapezoid turns curvy. $\endgroup$
    – Michael
    Apr 18, 2016 at 17:50
  • 1
    $\begingroup$ @Michael : I finally got your point on the restricted slopes: I was discretizing $x$ and $y$ axes the same and you are right it was not giving enough options. Giving 100 more $y$ options turns my trapezoid into a curvy trajectory! $\endgroup$
    – Michael
    Apr 19, 2016 at 4:19

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.

  • 1
    $\begingroup$ When i simulate this i get an expectancy of $3.688...$ miles.... could you share your code ? $\endgroup$
    – mercio
    Apr 17, 2016 at 13:36
  • 1
    $\begingroup$ if I read correctly, at the end when you do the case where the wall doesn't appear, you assume that your character know this and walks 3 miles straight to B, while he shouldn't know that there is no wall and he should walk the whole triangle instead $\endgroup$
    – mercio
    Apr 17, 2016 at 14:37
  • $\begingroup$ Also I wonder if this problem can be optimized just by using fewer x values (to save computation time) but checking many y values. For example, maybe only have 30 equally spaced wall positions (every 0.1 miles) but check many y values to be at to see which results in lower overall path distances. Then when you think you found a "winner", crank up the # of x "slices" to get a better approximation to the continuous solution. I am having trouble accepting that a symmetric trapezoid shape walk is optimal. I think it should be some type of smoothed curve thru some "optimal" points. $\endgroup$
    – David
    Apr 18, 2016 at 2:03
  • 1
    $\begingroup$ No, your solution implies only straight line travel. You are forgetting the important second step: after you find a path you think is optimal, have a further simulation where you follow that exact path and place the wall at all possible positions (well, approximately that path and many uniformly spaced positions) and keep track of path length for each trial and then get the average of those data. It takes another loop to find the length of the curved part of the path for each trial. $\endgroup$ Apr 21, 2016 at 4:22
  • 1
    $\begingroup$ I have that integral for $\bar s$ in my post that allows you to evaluate trial functions efficiently. But if you don't like that, make a path of a few line segments and then evaluate the distance traveled for several uniformly spaced wall placements. No calculus required because you know the length of a line segment from $(x_i,y_i)$ to $(x_{i+1},y_{i+1})$ is $\sqrt{(x_{i+1}-x_i)^2+(y_{i+1}-y_i)^2}$. If this goes quickly enough you can wiggle endpoints up and down and look for improvement. Start with the far point and work backwards. Maybe you can make a few passes and get a good result. $\endgroup$ Apr 22, 2016 at 4:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .