Category Archives: Great Inventions

Getting There

Posted on by

About the Traveling Salesman Problem

USA1mapLet's say there's a traveling salesman trying to hit a certain group of towns during a week. (I know, I know: eCommerce is eclipsing the traveling salesman these days, but I’m Old School, so bear with me.) To save time, this traveling salesman wants to calculate the best possible route between all the cities—the route with the absolute shortest possible distance—before he returns to the starting city.

Sounds easy: just add up all the shortest distances between cities. Right?

Wrong.

In fact, if you tried the calculations on a home computer, the sun would have already devoured the Earth in its death-throes, billions of years in the future, by the time your computer finished the calculations. (The problem is actually what they call an NP-complete problem, and it’s really complicated, and it makes my head spin, and good luck.)

That's why Google Maps only optimizes routes with no more than ten waypoints in them because going beyond that just requires too much time and computing power. For those of us without the patience to wait billions of years, there are workarounds to the Traveling Salesman Problem.

A Solution to the Problem

A Solution to the Problem

One of the best ways is to use something called a genetic algorithm, which begins with a handful of random solutions to the problem…and usually ends up being terrible. So, it then tinkers slowly with each one, discarding all but the best solutions. Eventually, after enough cycles of this, the algorithm produces a route that, while not the absolute best, seems reasonable enough.

The practical applications of the Traveling Salesman problem should be obvious. To shipping companies alone, it represents a ton of time and money. Other industries that are concerned with it include semiconductor manufacturers and paper mills.

We also have a large number of variants in this challenge, including the appropriately named Traveling Politician Problem.

A New Old-School Castle

Posted on by

Or: Undraining the Moat

gueldonThere's a castle under construction in France. Not a Disney-style castle at a theme park. An actual castle using medieval designs, materials, and construction methods.

Guédelon Castle started construction in 1997 and won't be completed until sometime in the 2020s. The designers aim to create an authentic 13th century-style medieval castle.

Oh, and when they say authentic, they mean authentic:

  • They only use local materials.
  • The site for the castle was chosen very carefully, located near an old stone quarry, a pond, and right in the middle of a forest.
  • All of the materials are gathered and hauled to the site using only medieval methods, including horse drawn carts.
  • The construction workers all wear period-appropriate garb, use period-appropriate tools, and use period-appropriate construction methods.
  • They have on-site blacksmiths, stone masons, carpenters, etc.
  • No modern tools are used anywhere. Not even ramps; sorry, Yard Ramp Guy.

The project has created 55 jobs and attracted more than 200 volunteers. On-site professional training is provided to disadvantaged youth, some of whom have earned stone-masonry and other certifications. More than 300,000 tourists a year visit the project, and it is open to schools for educational purposes. The construction has definitely proven itself worthwhile in those regards, but none of those were the original intention.

This is all part of experimental archaeology, which reconstructs and uses ancient tools, structures, and artifacts and allows archaeologists to actually study which methods work best and produce results most like the actual artifacts.

One way they do that is by looking for construction quirks (not the actual scientific term they use). Anyone who uses a lot of tools knows that you'll end up with certain quirks in your project, depending on which tools you use. For example: the same cut will be slightly different with different saws. When you're using tools that aren't mass-produced like ours, those little quirks get magnified even more.

During experimental archaeology, you can look to see if the methods you are using produce quirks like the historical ones.

Experimental archaeologists have produced Iron Age farmsteads and Greek triremes, hauled Stonehenge sized stones, sailed from Peru to Polynesia on a raft (Kon-Tiki), and, of course, built Guédelon Castle. (For a longer list, check out THIS. It's an incredibly productive line of research. And a heck of a lot of fun.

Guédelon Castle is proving to be one of the most productive of these lines of research. We've learned tremendously about castle construction from it. There was actually a companion castle being built in America: the Ozark Medieval Fortress. It ran out of funding and is currently on hiatus. We still need that European vacation to see a castle under construction. With any luck, though, that will change.

_____

Photo By Ronny Siegel (Château Guedelon) [CC BY 2.0], via Wikimedia Commons

Tokyo Gets Drained

Posted on by

Flooding (you with) Information

ugtokyoJPGThere's an enormous underground chamber just north of Tokyo. The Underground Temple—also known as the G-Cans Project, or the Metropolitan Area Outer Underground Discharge Channel—is a flood water diversion facility.

“Enormous” might be an understatement. It’s more than 25 meters high and 177 meters long. The concrete room is held up by 59 immense, 500-ton concrete pillars. In addition to the main chamber, there are five huge underground silos, each 65 meters deep and 32 m­ in diameter. You could quite literally fit Godzilla in one of those.

Construction on it began in 1992 and didn't complete until 2009. The whole thing is essentially the world's largest drain. The silos and the Temple are linked by hundreds of miles of underground pipes. The entire complex is nearly four miles across.

Tokyo has suffered from frequent floods throughout its history—not just from heavy rain, but also from typhoons and tornadoes. G-Cans was built to withstand even the most massive, once-every-other-century floods. Its 14,000 hp turbines and 78 pumps are capable of pumping more than 200 tons of water per second into the nearby Edogawa River.

The architects and construction crew faced a number of major difficulties in the construction. Earthquake proofing was one of the biggest hurdles. Another: preventing buckling and sagging in the ground overhead as they dug out the complex; it is directly underneath a city, after all.


There was a little criticism about the steep price tag ($2 billion) and the fact that Tokyo already possessed significant flooding defenses. Still, given how prone to natural disasters the city is, I certainly think they made the right call.

So, they have the flood prevention thing covered. Of course, there are still earthquakes, volcanic eruptions, tsunamis, typhoons, Godzilla, and those horrifying giant Japanese hornets to worry about.

Things, Explained

Posted on by

A Roboticist-Cartoonist Version of Things

Even though I read a lot, I usually don't recommend books to others. My favorites usually aren't too interesting to most people—lots of books on obscure parts of history, old pulp westerns, and dry technical volumes.

While Christmas shopping, though, I found a book that I loved so much that I bought copies, not only for my grandkids but myself, too.

Ducks in a (vertical) row.

His ducks in a (vertical) row.

It's called Thing Explainer, written by a former NASA roboticist turned cartoonist named Randall Munroe. The premise is pretty straightforward: the book is filled with diagrams of various gadgets, natural phenomena, and scientific concepts, but all the actual explaining is done using only the thousand most commonly-used words in the English language.

In practice, it can get a little silly. Bridges are called “tall roads,” planes are called “sky boats,” and the Saturn Five Rocket is called “Up Goer Five.” All of which earned more than a few chuckles from me.

Added bonus: The actual diagrams and explanations are absolutely top notch. I like to think I'm decently well educated when it comes to science, and yet I still learned quite a bit from Thing Explainer, often in the form of completely new tidbits of knowledge, sure, but just as often knowledge presented in a way that is novel and better for comprehension.

Thing Explainer isn't the kind of book you read in one or two sittings. It's more of a coffee table book you thumb through here and there. Of course, I read it all in one sitting, but I'm just not very good at delayed gratification when it comes to books. (Or when it comes to dinner. Or dessert. Or vacations.)

__________

Paying it Forward

Like book recommendations, I’m not too big on endorsements (unless it’s for ancient inventions that are perfectly great to help the 21st century keep on keeping on).

And then along comes that other Yard Ramp Guy, Jeff Mann, who just the other day introduced me to the Grasshopper Entrepreneur Scholarship. Since I don’t believe my School of Life credentials currently qualify me as an eligible entrant, I offer it up to all you legal young’uns—either in college or headed there.

Here’s the rub—and why I’m happy to present it to you: This year’s essay topic is, “What does market disruption mean to you as an entrepreneur? What would you do to create market disruption for your business?”

Me, I’m all about market disruption. (In my family, Maggie defines this as whatever I’ll do to get out of going to the grocery store.)

A $5,000 scholarship awaits the winner. Go get ‘em.

Earth Art

Posted on by

You’re Gonna Need a Bigger Boat

I am not a well educated man when it comes to art. Give me a ten-dollar painting of a sailing ship from a yard sale or thrift store and I'll be perfectly happy with it. Every once in a while, though, I find something that makes me take notice—in this case, it's a fella named Michael Heizer.

Heizer is known as what we call a land or earth artist—someone who builds immense outdoor pieces designed around and for their specific locations. These pieces are left out in the open to age and erode naturally. (Kinda like me.) Many of the earliest pieces from the 1960s don't exist anymore. If nothing else, Heizer's pieces are particularly notable for their sheer size.

dubnegOne of his best known pieces is a work called Double Negative, a pair of massive trenches cut into the edge of Mormon Mesa in Nevada. Each is 50 feet wide and 30 feet deep, and they have a combined length of 1,500 feet. The project involved moving 244,000 tons of rock.

Another project, Levitated Mass, involved the suspension of a massive, 21-foot tall, 340-ton boulder above a concrete trench that you can walk through. Moving the boulder itself was a massive feat of engineering. It only had 60 miles to travel, as the bird flies, but in order to get there they took it on a tangled 106-mile route through 22 cities in order to find bridges strong enough and streets wide enough.

The colossal custom transport could only move at seven miles an hour, and so they needed 11 days to get there, traveling only at night. Along the way, they had to cut down trees, temporarily remove traffic lights, and tow cars. The whole route turned into a series of parties at the transport's daytime resting places.

(The event was so cool that our other Yard Ramp Guy has blogged about it.)

Heizer’s current project, in the works for 20 years now, is by far his most impressive. Not yet open to the public, it is an enormous, mile-long monolithic structure known only as City, with two smaller complexes nearby.

To give you a comparison, it's about the size of the National Mall in DC. It's located in the brand new Basin and Range National Monument. As soon as it opens to the public, you can bet I'll be visiting.

City

_________

Clf23 at English Wikipedia [GFDL, CC-BY-SA-3.0], via Wikimedia Commons