11 ms·
Bellman's lost in a forest problem
- core-questions 8y agoI wonder if this could be reduced to the kind of optimization problem that can be solved with an Ising model.
- crb002 8y agoI'd discretize it into squares and get all four orientations. You are then looking for a set of directions (forward ,turn left, turn right) where forwards are minimized that works on every square in all four orientations. We have grammars over the alphabet {F,L,R} where "escape" accepts a word. We want the smallest accepted word contained in all grammars (only counting Forwards). Brute force enumeration works but is exponential. Faster is taking every place/orientation grammar where the finite state automata is the grid labeled with transitions. Then recursively merge them in pairs like mergesort. The resulting big automata you then want the shortest path to an escape state (only counting Forwards).
- crb002 8y agoSecond optimization I would apply would be quadtrees. Start with huge squares subdivide them after solving at that level down to your specified tollerence.
- crb002 8y agoIf you need even more precision either tiled hexagon automata or subdivide into K instead of four compass orientations. There is also probably some Pressburger arithmetic formulation treating it as vectors in 2D you could whack with an SMT solver? I'd have to sleep on that. Might be easier to code than all the finite state automata merging.
- caf 8y agoThere aren't four (or any finite) number of orientations. You start off facing an arbitrary bearing.
- crb002 8y agoMentioned below. You can increase from 4 orientations to K and use quad trees to drill down distance of steps taken.
- bertil 8y agoI’m confused: how is “walk-straight ahead” not an obvious best solution? It’s minimum performance is null, average performance, half of the diameter of any (compact) shape, and worst, the diameter. Is the problem implicitly with infinite distance, multiple dimention or fractal?
- crb002 8y agoWalk straight ahead could be worst case if you are near the edge and oriented to walk all the way across the width of the forest.
- cperciva 8y agoThe shape and size of the forest is known. If you know that the forest is long and thin, you're better off walking in a curved path so that you're guaranteed to hit the "side" of the forest rather than walking straight and potentially continuing until you hit the "end".
- paulpauper 8y agoIf you know the dimensions, you know that if you walked more then the width , then you have to make a left or right turn.
- cuboidGoat 8y agoWhat if the shape is the set of all finite curves arranged as a star and given equal length? If you accidentally start in the middle, there will always be a worst case scenario route determined for any arbitrary curve and no way to pick between curves to find the best one.
- andrewflnr 8y agoI'd like to see some solutions in specific cases. I bet they're mostly simple shapes.
- FabHK 8y agoHere's a nice version to find a solution for, the half plane: You're 1 km away from the (straight) edge of a forest (that extends infinitely in the other directions). What's the optimal path for you to walk to get out? (with the best worst case, ie the shortest path that is guaranteed to touch the edge.) This was an interview question at investment banks back when brain teasers were still en vogue. There is a fairly evident solution, and then two improvements can be made. EDIT to add: The solution was described by Isbell in 1957, and proved optimal by Joris in 1980. It's contained in the paper below, but don't deprive yourself of the pleasure of finding it yourself (and its length, if you're so inclined... :-) https://www.maa.org/sites/default/files/pdf/upload_library/22/Ford/Finch645-654.pdf https://www.maa.org/sites/default/files/pdf/upload_library/2...
- maxander 8y agoWonderful bit of synchronicity- seeing this on the front page of HN right after I got back from being (deliberately) lost in the Fells reservation north of Cambridge. (In this case, of course, my algorithm was made simpler via access to a GPS oracle, when it started to get dark. :) ) > It was included in a list of 12 problems described by the mathematician Scott W. Williams as "million buck problems" because he believed that the techniques involved in their resolution will be worth at least a million dollars to mathematics. Does that mean it would be worth that much via (perhaps indirect?) applications, or worth that much to mathematicians? What does it even mean to say that a non-applied mathematical theorem is “worth” some sum of money? (Absent a rich mathematician willing to pay a bounty, at least.)
- derefr 8y ago> What does it even mean to say that a non-applied mathematical theorem is “worth” some sum of money? The aggregate increase in lifetime earnings of the set of of maths grad students who earn their Ph.D off of a dissertation in the subfield built on the back of the knowledge gained from the solution to the problem?
- maweki 8y agoThen a million dollars is nothing. That's not even one graduate's earnings.
- daveFNbuck 8y agoThat's the total salary, not the amount that the discovery changes the salary by.
- phyzome 8y agoIt's hard to get too lost in the Fells when you can hear the highways. :-P
- mrtnmcc 8y agoHope they didn't lock the gate on you at the Sheepfold parking lot. Had to chop down a tree after sunset once..
- paulpauper 8y agoThe shape can be given by any 2-d parameterization and then this seems like a optimization problem solvable with variational calculus
- wyldfire 8y agoReally? Even without knowing your orientation or location within the 2d shape? I doubt this solution is a general one. Apparently there's an abstract "bounty" of a million bucks [of value to be reaped by mathematics]. Likely means that solutions that grad students could execute within a day have already been tried.
- YeGoblynQueenne 8y ago>> Bellman's lost-in-a-forest problem is an unsolved minimization problem in geometry originated in 1955 by the American applied mathematician Richard E. Bellman[1]. As an aside, I've always found it funny how a person who studies (and, er, applies?) applied maths is an "applied" mathematician. That makes it sound like what is being applied is the mathematician, not her maths. I guess it's funny - haha to think of it that way, but it's also funny - strange that this is the most natural way to say the thing being said (that someone is a mathematician working in applied maths). In fact, I can't think of a different way to say the same thing at all, not in so few words.
- _emacsomancer_ 8y agoSo then what you think a "theoretical physicist" is? ;)
- chii 8y agoThey are theoretically paid to do physics!
- adrianratnapala 8y agoDo you mean that they are paid, and in theory, they do physics. Or that they do physics and, in theory, they get paid?
- _emacsomancer_ 8y agoI assumed it would be something ?x[person(x) & does.physics(x)] where '?' is like the existential operator, but doesn't guarantee existence in the current world of evaluation (but in at least some possible worlds).
- gmueckl 8y agoThe later - especially the kind that is also a teaching/research assistant at university.
- 8y ago
- nabla9 8y agoInteresting problem. First I thought that I would formulate the problem as finding a path that in every step minimizes the number of possible starting positions for the current travel length. Then I thought about adversarial forest designer who would design a forest where following optimal path for lengths smaller than X produces solution that is not optimal overall. What kind of forest that would be? Do they exist?
- pizza 8y agoThis would be somewhat easier if the forest had 'holes' in it, right? But then it wouldn't be much of a (convex) forest, would it.. (I'm assuming the forest totally covers the area it occupies.) It would be interesting to find the computational complexity of escape as a function of the geometry (a set of n vertices)
- ggggtez 8y agoI was a bit surprised it attempts to optimize worst case, not average case. I feel like average case is a more practical problem, and one which likely has some pretty nice results by thinking of the map as a probability distribution. Simply walk in the direction which narrowed down your possible location the most.
- estomagordo 8y agoHaving an upper bound on how long one has got to stay in the forest has got to be very practical, though.
- Patient0 8y agoI disagree - I think if you described this to a layman they would always be more interested in optimising for the worst case. For example if I had an algorithm that on average will get me out in 1 mile but in the worst case might take me 100 miles then that's not very useful if I was trying to decide how much supplies to take. The concept of an arithmetic mean is quite artificial - there's other ways you could define "average" such as the median. Also, in my experience, optimising for the average case is often the easier problem to solve.
- rocqua 8y ago> The concept of an arithmetic mean is quite artificial - there's other ways you could define "average" such as the median. I'd give some pushback on that. It is the only linear mean, and linearity matters. More importantly though, it corresponds to the Expected Value. That is, the average of n samples of a distribution f converges to E[f]. In fact, I believe the arithmetic mean is the best unbiased estimator for the expected value of a distribution. Now, expected values matter because they are the basis of robust decision-making.
- FabHK 8y agoYou can consider mean, mode, and the other centrality measures as points that minimise some sort of average deviation. And depending on which norm you use to measure your deviation, you get different centrality measures: * L_0 -> mode * L_1 -> median * L_2 -> mean * L_infinity -> midrange, I think where roughly L_p(x) = [ sum_i |x-x_i|^p]^(1/p) ]
- fetbaffe 8y agoNorwegian, a Dane & Bellman were lost in a forest...
- bjoli 8y agoFor all you non-swedes out there: https://en.wikipedia.org/wiki/Bellman_joke https://en.wikipedia.org/wiki/Bellman_joke As an example: A Russian, a German and Bellman were bragging about their football skills. - I once kicked a football over a flag pole, the russian said - What did you get for that?, the others asked - Bronze. - Well, I once kicked a football over a 4 story building, the German said - What did you get for that feat?, the others asked. - Silver. Bellman was not so easily trumped, though - I once kicked a brick over a skyscraper, he said. - Wow! What did you get?! the others asked - A broken foot.
- deleted 8y ago[deleted]
- sdfuihsdfusdf 8y agoWouldn't the most optimal strategy be to walk in an outwards expanding spiral? Even if it's the longest walking solution for simple examples, it would beat all these "infinite distance into one way" solutions. Ofcourse the rate of expansion is something else to think about.
- deleted 8y ago[deleted]
- baalimago 8y agoI'm pretty sure someone clever could form a proof which links the solution to the golden ratio somehow, unfortunately that clever person isn't me.
- fullstackchris 8y agoI'm starting to think that any sort of general solution would have to be extremely complex... The optimum path would be something like a function of itself and the shape of the forest. That is, there is probably a general solution to the INITIAL 'optimum' path based on the forest shape, but then your optimum path changes at any nth 'step', because as you haven't found the border of the forest yet, you learn a bit more (at least probabilistically) about where you could be in the forest... I think that makes sense, but I have no idea how a solution method like that could be presented analytically.
- asah 8y agoIIUC you know the shape apriori. It's still hard.
- SilasX 8y agoIIRC in practice you can exploit a regularity that's common in the real world, which is that "people live near flowing water". So, just identify the downhill direction and follow it to a stream/river, which will guide you to people.
- caf 8y agoThis also works as a "lost in an ocean" problem as well, though.
- de_watcher 8y agoThe solution to each forest is a curve with the 'start' and the 'end' point. We minimize the length of the curve for that forest. Constraint: if the starting point of the curve is placed anywhere in that specific forest then some point of it must be outside regardless of the orientation of the curve. That's for avoiding thinking about the function of itself.
- deleted 8y ago[deleted]
- Fri31Aug 8y agoJust to be sure, "path" must be understood as "trajectory" here? If the hiker doesn't know the starting position then it cannot be "path" as in "line between point A and point B" since there is no point A or B. So the solution would be something like: "go ahead 10 meters, then turn 45° right, then go ahead 50 meters, then take a Bézier curve left with such parameters, etc" > The best path is taken to be the one that minimizes the worst-case distance to travel before reaching the edge of the forest. Again, just to be sure, the "worst-case distance to travel" is the longest distance achieved by the "trajectory" when you apply it starting from any point of the forest? So basically (assuming you walk at constant speed): 1. Determine a trajectory to follow that guaranties that you would get out of the forest under N seconds (easy). 2. What is smallest possible N and the associated trajectory under which #1 is true? (hard)
- dmcclurg 8y agoThe complexity of this problem is absurd. If the biker precisely know the terrain then he is capable of knowing where he is in that terrain. This is the basis of terrain-association.