The moving sofa problem

[jmount]

In static analysis of forces you can in fact have an irreversible couch/sofa event (as in Dirk Gently's ). It is usually is described as jamming or wedging of the peg in hole problem (see here http://www.cs.cmu.edu/afs/cs/academic/class/16741-s07/www/ol... ) and arises when the implied forces can oppose any force to move the object. In this model you can stick a peg in at the wrong angle and it will jam and never come out.

I ran into this when I tried to explain the sofa stuck in the staircase mystery in Dirk Gently's Holistic Detective Agency. She (a Ph.D. in robotics specializing in dynamics and physics) pointed out an idealized rigid system could jam in this way without any additional exotic explanation (beyond the exoticness of idealized rigid physics).

[jschwartzi]

Is this simply because the coefficient of friction between two surfaces is typically smaller when the surfaces are in motion than when they are at rest? If you wanted to reverse the insertion of a peg into a hole, you would have to halt it's motion for an instant, and at that point in time I would imagine you have to overcome static friction to make it move in the opposite direction. Friction forces can be dependent on the normal force between the two surfaces, so it's possible to jam a peg into a hole so that you can't get it out.

[conistonwater]

Wait, I don't get it: what is the diagram on page 6 supposed to show? How is it jammed exactly?

[pjc50]

I'm rather surprised that an idealised system isn't simply time-reversible, given the trouble physicists had in developing entropy to explain the arrow of time in the first place.

Edit: ah, you've explained below that the model includes a non-reversible term of friction which is applied at the time of contact.

[mr_spothawk]

Relevant novel: https://en.wikipedia.org/wiki/Dirk_Gently%27s_Holistic_Detec...

Further reading for anybody who enjoys Adams, Wodehouse was said to be one of his influences: https://en.wikipedia.org/wiki/P._G._Wodehouse

[eridius]

IIRC, in Dirk Gently's, the couch wasn't jammed, it was simply that there was no way in which it could be rotated that would allow it to progress either further up the stairs or back down the stairs.

[johansch]

This reminds me quite a bit of the awesome Kuru Kuru Kururin game:

https://en.wikipedia.org/wiki/Kuru_Kuru_Kururin

Gameplay: https://www.youtube.com/watch?v=VYvUZXT_43k

[chronial]

There is a modern game with similar gameplay: http://store.steampowered.com/app/303430/

[shasheene]

An absolute classic. One of the most underrated games for the Gameboy Advance! :)

[Jaruzel]

When I first read dirk Gently shortly after it was published, and got to the Sofa bit, I really wanted a wireframe simulation of it as described in the book, but as screen-saver[1].

These days most if not all people no longer have screen savers, so that wish is likely to forever remain unfulfilled.

--

[1] I also wanted the rotating Starbug wireframe from Red Dwarf, but to my knowledge no-one has done that either.

[LeoPanthera]

"Holistic Sofa" is available as an After Dark screensaver for pre-OSX Macs. Completely useless today, of course.

[gpderetta]

You should ask jwz, he might add it to screensaver.

[lisper]

I faced this problem in real life, not with a sofa, but with a bed mattress platform. Just out of grad school, my wife and I were moving in to an old craftsman-style house with a staircase that made a 180-degree bend at a landing with a fairly low ceiling. We squeezed the mattress through because it was bendable, but the platform was rigid and no matter what we did it just would not fit. Some measurement revealed that it would not go through the upstairs windows either. We ended up sawing the platform in half (it was made of wood covered in fabric) and re-assembling it upstairs. I screwed L-brakcets to the two halves and connected them with bolts so that we could easily repeat the process when it came time to move out.

[dawnerd]

That's pretty much how they solved the problem on This Old House. Seems like a pretty common tactic.

[bluedino]

Of course, in the real world, furniture is 3D, and the obstacles you move move furniture around are also 3D. Bannister that's 3 feet high, couches with curved arms, ceilings have heights, stairwells...

Part of the fun of moving is trying to figure out how to orientate furniture to get it into a room - or out of the room, since someone already got in there so of course it must come out.

[lb1lf]

>(...) or out of the room, since someone already got in there so of course it must come out.

-Not necessarily; while a student, I looked after the apartment of a friend of mine, who was overseas. When he moved there, we were _just_ able to eke his sofa around the last corner from the stairwell and through the door to his apartment. Just. After much cursing and several failed attempts.

So, what does a good (cough) friend do while the owner is overseas? Get some hardwood mouldings/trimmings/whatever you call those long, thin pieces of wood typically put where wall transitions to ceiling or floor and nail them to the exterior doorframes, making both door openings perhaps 3/8" or so narrower, paint them in the color of the doorframe, sit back and wait.

Then, years later, as he is about to leave town, moving company comes along and everything runs smoothly until one item remains. The sofa. Obviously, it got in - so it'll (as obviously) come out.

Only it doesn't.

We (everybody except the owner and the moving guys were in on the joke) managed to keep a straight face for several minutes.

The moving guys even laughed as they (eventually) left, mollified by a bottle filled with a Scottish export product which we'd kept on hand to ensure no feelings were hurt afterwards.

[WalterBright]

It's the classic problem people have who home-build an airplane in their living room. (They end up having to demo an exterior wall.)

[ghaff]

>since someone already got in there so of course it must come out.

Assuming it was brought in assembled and assuming that no obstacles (door frames etc.) were temporarily removed to allow it to get in.

[Jill_the_Pill]

Sofas have a bit of squish to them. If there was some directionality to the stuffing or springs, you could get a fishhook effect where parts that would collapse on the way in might resist on the way out.

[dexterdog]

But always be sure that it was not built in the room first.

[mathgenius]

There is a similar problem, "Lebesgue’s Universal Covering Problem", also unsolved:

https://golem.ph.utexas.edu/category/2015/02/lebesgues_unive...

I wonder if the maths is related at all.

[pfd1986]

Neat. I thing I remember reading about this problem on Azimuth...

[soheil]

Must be said that the final shape looks very similar to animal feces probably because twisting intestines pose a challenge similar to that of the moving sofa problem.

[kristopolous]

Does that have a little more flexibility in it's geometry?

[acqq]

Are you sure? 90 degrees angles with the sharp corners?

[spacehacker]

I am wondering what kind of solutions an evolutionary algorithm would come up with.

[Ericson2314]

I wouldn't be surprised if it could evolve from semi-circle segments roughly the current best.

[xuva]

Perhaps coincidentally, the ambidextrous sofa has an area scarily close to the sum of inverse squares, \pi^2/6 \approx 1.6449341...

[j_koreth]

I guess if you look hard enough pi really is everywhere

[chrisallick]

If you like this, a student at SFPC in New York built a kinetic sculpture about this problem.

[fatihpense]

I think this is it: https://www.instagram.com/p/BNXT5EQAsKY/?taken-by=sfpc_nyc

[millxing]

"PIVOT!...PIVOT!" https://www.youtube.com/watch?v=B_PklVas9cA

[Cerium]

I showed this to my dad (a math teacher), he said: "When you get to the corner, tilt the sofa up, and then tilt down the other hallway."

[lkrubner]

Indirectly, this raises a concern I have with so-called "Artificial Intelligence" or "Deep Learning".

My first thought about this moving sofa problem is that it would yield an answer to brute-force analysis.

If not, then what about a long series of brute-force approximations to establish increasingly narrow upper and lower bounds? Which might yield an insight about the maximum pattern?

And then this thought occurred to me: if we have such amazing tools nowadays, for doing pattern analysis, and Big Data analysis, how is that we are not able to find patterns in a problem such as this? I mean, could we not find patterns in the ways we find upper and lower bounds, and then use techniques of Artificial Intelligence to see some underlying pattern in the bounds?

This problem is not like "What is the incidence of tuberculosis in Peru?" where we work with incomplete data. This moving sofa problem is an issue where we can work with perfect data.

And yet out current Big Data tools are unable to find a pattern that would provide a conclusion about the maximum?

Problems such as this help establish the limit on what our current Artificial Intelligence can do. If our pattern finding tools can not find patterns in numbers, where we work with perfect access to unlimited data, then we should not think that AI is going to achieve dramatic breakthroughs when working with imperfect data in the real world.

[foxhop]

We should create flexible walls. Disrupt walls.

[Johnythree]

No doubt this was Douglas Adams's original inspiration..

"Right Said Fred" Bernard Cribbins https://www.youtube.com/watch?v=Ge_4SlJWfl0

"I said to Charlie, "We'll just have to leave it Standing on the landing, that's all.

You see the trouble with Fred is, he's too hasty You'll never get nowhere if you're too hasty."

[anonaggie08]

Apropos considering Davis has a semi-permanent population of itinerant couches which migrate almost every other summer. I really could've used this algorithm when some friends and I moved a huge custom couch into a townhome in downtown San Jose which had to navigate narrow stairwells like frickn 3D chess.

Btw: our first house off-campus (right next to the railroad tracks on I St., wish I were joking) had probably three (3) couches, which mostly my mom made a million times more domesticated.

Fun-fact: up until 2002, Davis didn't have an open container ordinance, so it was possible to legally drink in the alley, King of the Hill-style, or just walk around with a beer just like in London, etc. That was back in the day when Velvet Elvis was trying to survive and get an alcohol permit. [0,1]

0. https://localwiki.org/davis/Open_Container_Ordinance

1. https://localwiki.org/davis/The_Velvet_Elvis

[amelius]

I wonder what shapes an automated heuristic approach (e.g. using genetic programming) would come up with.

[DonHopkins]

Nancy the Van Seat [1] was a mobile robotic platform developed at the Stupid Fun Club that was useful for performing moving sofa experiments, but we never tried taking her down a staircase!

[1] https://www.youtube.com/watch?v=fvXG4gQ2FWI

[Neliquat]

Why is right side cut off on mobile? Looked interesting.

[masterponomo]

Clearly, the PIVOT point is the key.