A surprising new application of GPS technology.
April 1, 1999.
From aiming intercontinental ballistic missiles to picking wild mushrooms – such is the evolution path of one once classified defense technology. A group of Silicon Valley geeks is combining their love of high tech with their other passion – hunting wild mushrooms in the pine groves of Northern California. A group of enthusiast within San Francisco Mycological Society is going to employ GPS (Global Positioning System) technology to increase precision of determining the location of wild mushrooms in the forests.
Until recently, mushroom hunting was virtually unknown in the U.S. In other part of the world, including Italy, France, and China, it’s extremely popular. In Russia, it’s a national pass-time, compared in popularity only to playing ice hockey and drinking vodka. In fact, it were Russians who first began using GPS technology for hunting mushrooms in the thick forest surrounding Moscow. Now, Russian programmers working in Silicon Valley are importing the technology and share it with their new American colleagues.
Every experienced mushroom hunter knows that the mushrooms grow in the same place year after year. This is because the mushrooms are seasonal growths on vast underground structures, called mycelium. If a picker finds a group of mushrooms one year there are very good chances that there will be good bounty at the same location the next year, and year after. Being able to locate the place year later greatly improves the productivity of the hunter. In Russia, many babushkas have their secret spots they revisit for decades. They pick lots of premium mushrooms, to the envy of younger folks who are wandering in the forest at random, returning home with empty baskets.
It is not easy to find one specific pine tree among thousands or virtually identical ones in a thick forest. All trees look alike. And it’s harder to navigate as you step off the trail with its signs and trail blazes. Old ladies rely on their instincts. Impatient young geeks rely on cutting edge technology.
With right technology, it works like 1-2-3. Find a good mushroom (better a bunch of). Determine your position with a GPS device connected to a Palm Pilot. Enter the coordinates into a database. Go find next mushroom. Continue. Next year, load the map marked with last year’s spots into your Pilot, or directly into the GPS device, and go straight to the best secret spot. To the babushkas envy, the device will help you find the very same tree you visited a year ago, in minutes.
High tech gives the techno-savvy even sharper edge over the babushkas. Before the forage, in the comfort of your room, you examine the map and determine the optimal path. You do not want to wander too much back and forth, you want to visit your secret spots as fast as possible.
Here is where the geeks have an edge. The problem of visiting a set of given spots in minimal time is the well known traveling salesman problem. It has been studied by thousands of computer scientists, economists and mathematicians. It is almost as famous as recently proven Fermat’s last theorem. The exact solution of the traveling salesman problem is still not found, and many mathematicians believe will never be, but there are thousands of approximate solutions that give the paths that are only few percentage points longer than the minimal ones. For all practical purposes, a good approximate solution is as good as the absolutely minimal one.
With all this in mind, Alexander Shen and Fedor Sherstyuk, two Russian outdoor enthusiasts, avid mushroom pickers and GPS buffs have developed a software product, called Gribnik (Russian for “mushroom hunter”). The program maintains a data base of the promising spots and calculates the optimal path in seconds. The results are superimposed on a local map and downloaded into a Pilot or directly into a GPS device. The shareware program became so popular in Moscow that the friends are now working on a commercial version. An English language version of Gribnik will be available in the fall of 1999, in time for the season.
The standard accuracy of a typical GPS is about 50 m (150 ft), which is helpful but does not allow one to pinpoint the mushroom. A differential GPS which relies on a fixed ground station along with the usual three satellites could render the 10 cm (4’) accuracy. This leads the hunter straight to the mushroom. To take advantage of such an unprecedented accuracy the friends climb a toll tree in the middle of the forest and put a ground station there. Then they decent and search the surrounding forest.
Unfortunately, even 10 cm precision does not guarantee the mushroom is there. Even if the timing is right and the mushrooms grow well there is a chance that somebody has already picked them up. Knowing this fact in advance will be beneficial to the picker. He would merely skip the spot and go straight to the next one. Gribnik Pro, a soupped up version of the program, offers a solution even to this problem. When one member of a group of hunters picks a mushroom, or finds that the spot has been cleared by a low tech babushka, he marks the spot on the map and shares his knowledge with the others.
The sharing has a drawback. If a persons posts the coordinates of the spot he has just cleared all others become aware of the spot. A good hunter keeps best spots secret. Messrs. Shen and Sherstyuk founded a web site where the users of Gribnik Pro could post the coordinates of their spots in an encrypted form. (To be more precise, a so-called one-way hash function of the coordinates is posted on the web.) This way, the competitors cannot read the coordinates off the web. However, if two people know about one spot, the program would compare the hash function values of the coordinates from the data bases of the two hunters. This allows one hunter to post a note that the spot has been visited without revealing the coordinates of the spot. Those who also happen to be aware of the same spot will be able to understand the message. Others, who have not been to the spot will remain unaware of it. This yet another example of how, with little help from modern cryptography, one can eat a cake and still have it. The cryptographic part of Gribnik was contributed by Roman Avdanin of Invincible Data Systems, Inc. (http://www.incrypt.com)
What lies ahead? At a press conference on the 1st of April in Moscow Alexander Shen, Professor at Moscow Center of Continued Mathematical Education (http://mccme.ru), revealed his plans: “We are going to port the entire Gribnik, including the travelling salesman part, to Palm Pilot and Windows CE platforms and link it to a cell phone. This will allow a group of pickers to exchange data about spots in real time. When a spot is taken the program will remove it from the to-visit list and recalculate a new optimal path, on the fly. You will receive a brief phone call and your Palm Pilot will tell you to skip the birch 13 and proceed straight to the pine 21, across Pereplyujka river, 50 m south west of an abandoned tiny wooden church and log home, where at time of Ivan the Terrible a single hermit might have lived and picked his mushrooms from the same spot.”
