Wednesday, November 01, 2006

The Snowblowing (or leaf raking) problem

Lifehacker asks:
Reader David wants to know the best way to rake leaves. My first thought: "Get someone else to do it." But seriously, assuming you have a square or rectangular yard, what's the most efficient raking pattern? Should you make multiple smallish piles or aim for one big one (the latter being best for running jumps, of course)? Surely there's a mathematical or engineering principle that can be applied here.
As it turns out, this year's WAFR (Workshop on the Algorithmic Foundations of Robotics) has a paper on essentially this problem (with leaves replaced by snow), by Arkin, Bender, Mitchell and Polishchuk:
We introduce the snowblower problem (SBP), a new optimization prob-
lem that is closely related to milling problems and to some material-handling prob-
lems. The objective in the SBP is to compute a short tour for the snowblower to
follow to remove all the snow from a domain (driveway, sidewalk, etc.). When a
snowblower passes over each region along the tour, it displaces snow into a nearby
region. The constraint is that if the snow is piled too high, then the snowblower
cannot clear the pile.
This is not to be confused with the Snowplow problem, a puzzle in elementary differential equations:
One day it started snowing at a heavy and steady rate. A snowplow started
out at noon, going 2 miles the first hour and 1 mile the second hour. What
time did it start snowing?
p.s Actually, it's true. The slides are more interesting...


1 comment:

  1. The slides, in fact, are more fun than the paper


Disqus for The Geomblog