The moving sofa problem | Hacker News Reader

The moving sofa problem

math.ucdavis.edu

690 pointsvinnyglennon64 comments

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).

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

Sorry I could not find a good enough non-book reference.

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.

Unfortunately it is merely a math problem. Until the peg comes in contact there is no friction. After it is in contact there is friction, and if the geometry is just wrong enough "virtual forces" to oppose any force. Real matter (which bends) can't have this problem- it is from the rigid model. The non-reversaiblity is this flaw plus the fact there is no friction in the model prior to contact (so there is a non-reverisble feature in the model).

It makes sense. After all, in real life I would just wiggle the peg to "walk" it back out of the hole, and that only works if the body is not perfectly rigid, and no body is perfectly rigid.

In reality your body could have barbed hooks which insert easily but dig into the walls when you try to pull it out. Wiggling doesn't help there.

I'm currently repairing some 1940s windows and replacing the hinges. I can say with confidence that some things are completely rigid and will never be moved despite use of hand and power tool. Old hardwood and steel construction.

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.

But your original feeling is right- most complete models are in fact time reversible. The static analysis toolkit is a simplified physics for engineering analysis.

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

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.

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

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

Also: Duet (http://www.duetgame.com), for iOS, Android and on Steam is an IMO brilliant variation on this theme.

- the player piece isn’t a stick, but only two dots, one at each end of an imaginary stick.

- there is no way to move the stick. Instead, the player controls its rotation, and the ‘enemy’ pieces approach it.

That simplifies the controls to two fingers: one to rotate the stick one way, and one to rotate it the other way.

This game also gets rid of most of the graphics; enemies are simple white rectangles on an almost black background, making the playing field look highly abstract (except for the paint splats left behind when one hits an enemy)

Thanks for the recommendation. I've been playing for half an hour, and this game is fun and well made.

Very nice. Saw the other responder's comment and decided to try it, am impressed. I don't play mobile games often; wish I found more simple but creative games like this.

After the first couple levels I was thinking "oh god I will never be able to do this" but now I've cleared the "anger" stage and have started to develop strategies to approach several different situations. Pleasant feeling.

I second the recommendation for Duet. It's one of the best iOS games I've ever played.

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

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.

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

YouTube link: https://www.youtube.com/watch?v=9A92PMGcquo

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

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.

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

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.

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

>(...) 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.

We ran into this at our house. Queen box-spring went up the stairs fine. A year or so later, we re-build the stairs in wood, including the bannisters. A few years later, we bought a new bed, and the old one wouldn't come back down, so out the 2nd level window it went.

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.)

Or people who build boats in their basement.

http://movies.stackexchange.com/questions/8969/how-does-gibb...

>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.

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.

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.

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

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.

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

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

Is that not how you keep yours?

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

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

The formulation of the fitness function seems to be an interesting problem. The best idea I can think of right now is to randomly apply forces within ±90° of the direction that moves the center of mass roughly in the correct direction in a 2D rigid body simulator.

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

I guess if you look hard enough pi really is everywhere

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

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

yes, that is it

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

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."

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.

We should create flexible walls. Disrupt walls.

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."

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

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

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

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

Clearly, the PIVOT point is the key.

Is my browser broken or does this page have a max-width on the content that's narrower than the animations?

It's not just you. All the images have absolute pixel positioning, making them overlap the text if you change font size or similar.

Text is clipped on my tablet, too.

What is the longest sofa you can move around in a Klein-Bottle?

What do you mean 'in' a klein bottle.

One does not simply....

A Klein bottle is a topological thingie, rather than a Euclidean geometry thingie. Given the nature of these beasts the sofa will be both inside and outside the bottle at the same time.

The sofa will need a pretty odd shape to not be able to move around the bottle - say a torus which is around the "handle" of the bottle. Any shape that does not snag the handle will of course be able to be moved around it as needed.

Reply on news.ycombinator.com