I would like to move a piano. Having a mathematical background, I was trying to figure out whether I can get it into the new apartment. In my research I stumbled upon the already explored "moving sofa problem" as illustrated below:

moving sofa gif

Now, my question is:

Is there a computational model that is able (or at least tries) to find solution for this problem for any (or at least some) arbitrary shape? By solution I mean a path along the object can be moved that brings it around the corner.

I stumbled on some interesting concepts in motion planing. Most importantly on: "Potential field method" in motion control and navigation functions

Now to my two new subquestions:

  • Exists a publicly available "Potential field model" for arbitrary movable object shapes, or something similiar?
  • Is there a method that lets me construct an (optimal) navigation function if I know the potential field and the shape of the movable object?

Keep in mind that my special interest is in cases where there is almost no "free space". Hence, where it is hard to move it around the corner.

Thank you!


Potential field methods usually model the moving object as a point. There is another concept in robotics called configuration space, which allow condensing the moving object to a point while expanding obstacles "with the robots geometry" (to simplify the method to one sentence). This essentially allows you to plan a path for a point while making sure that the actually geometry of the robot is considered.

To solve the above problem with potential fields the combination of these methods would be needed. Similar to the approach detailed here. However tight corridors are not well suited for potential field planning, since the potential fields do not exactly represent the shape of the obstacles, they just approximate it. There are potential fields which can better approximate shapes (IIRC they are called harmonic potential fields, based on partial differential equations to describe the potential function), still potential fields methods are usually not well suited for tight corridors.

The advantage of potential field methods is in their "reactive" nature. They can react to changes in the environment (moving obstacles) with a low amount of required computation. These are also called online methods, because the path is planned online, as the robot/moved object advances in contrast to the offline problems where a full path is computed prior to any motion of the robot/moved object.

The piano (or ladder or sofa) movers problem, since it does not include changing environment, can be solved using offline planning (like the a* algorithm). More details are given here.

  • $\begingroup$ I don't see how in my problem a potential field is just an approximation. I am not actually measuring a surrounding but defining one by hand. Hence, It would be exact or am I mistaken? I understand the configuration space approach. However, I do not see how one can easily incorporate an arbitrarily shaped object into such a model. The same goes for an A* ansatz. I would either have to constantly update the distance to any "visible" "border" which should be computationally very expansive or check after the move if it is "clipping" and reject that potential move. Is there a better way? $\endgroup$
    – ls.
    Dec 14 '19 at 11:37
  • $\begingroup$ Virtual potential is summed up when there are two or more obsticles, thus shape of one obsticle will not be accuratly represented anymore. Furthermore, the shape of the robot (or piano) is not considered. The attracting potential of the target point also alteres the virtual potential field. The L shaped tunnel is difficult because the target would not create a potential field that changed direction around the corner of the L. Tha walls of the L shaped tunnel would also not cause the cornering motion required. So...shapes are not accurately reflected $\endgroup$
    – 50k4
    Dec 15 '19 at 23:40
  • $\begingroup$ C-Space and A* might be computationally demanding, but they work genrally (you might be able to tune the potential functions to solve this exact problem you posted, but the same parameters will definely fail if you significantly alter the environment. A* and C-space will work in any environment (given enough time/memory for the computations)...so it is a tradeoff. The more cluttered the environment, the worse will potential field methods perform and the more computation time/memory will global (offline) methods require. $\endgroup$
    – 50k4
    Dec 15 '19 at 23:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.