User Tools

    Please register ( or log-in ) to create and edit pages
  • Register

Site Tools

Wikenigma - an Encyclopedia of Unknowns Wikenigma - an Encyclopedia of the Unknown Wikenigma - an Encyclopaedia of Unknowns Wikenigma - an Encyclopaedia of the Unknown

Bellman's 'Lost in a forest' problem

- can (colloquially) be stated like this :

“A hiker is lost in a forest whose shape and dimensions are precisely known to him. What is the best path for him to follow to escape from the forest?” It is usually assumed that the hiker does not know the starting point or direction he is facing. The best path is taken to be the one that minimizes the worst-case distance to travel before reaching the edge of the forest. Source: Wikipedia

It was first (formally) proposed by Richard E. Bellman in 1956, thus:

We are given a region R and a random point P within the region. Determine the paths which
(a) Minimize the expected time to reach the boundary, or
(b) Minimize the maximum time required to reach the boundary.
Consider, in particular, the cases
(a) R is the region between two parallel lines at a known distance d apart.
(b) R is the semi-infinite plane and we are given the distance d from the point P to the bounding line. (Received November 18, 1955.) Source: Bull. Amer. Math. Soc. 62 (1956), 270

Although some specific solutions have been found for special cases, no general solution has yet been found.

    Share this page :