Recalculation of center of mass on a grid

[x0rr]

Hi,
I checked the forum rules and homework / coursework is not allowed so I am not sure if this is appropriate or not. Feel free to guide me through appropriate forum and/or lock this thread if such questions are not allowed. The question I have is mostly related with my research and since I am not good at physics, I stumbled upon a problem which I couldn't solve. The problem seemed more like a physical problem rather than an optimization problem so here I am. Anyway here is the story.

Info:
Assume that there is a square grid plate with cells having same dimensions. Plate has no weight. Each cell has its own associated weight and weights located at symmetrical positions are equal. Now, I randomly remove some weights from cells and this may shift the center of mass from central cell. Here is an image

http://imgur.com/13338Lf

What I want to do is that, on a given "plate system", recalibrate remaining weights in a such way that the center of mass should be on central cell (or center of the plate). But there is a restriction

- While recalibrating, I do not want drastic changes on remaining weights. Assigning symmetrical weights to 0 would balance the system but that's not what I want. The reclibration should be reflected to many weights instead of focusing on just 1. As suggested on the image I uploaded. We could increase the weights at some side, or decrease from otherside. Or both of them for a more evenly distributed weight change.

Now, this is some sort of optimization/graph-search problem and can be solved with AI algorithms. However, that's not what I want for various irrelevant reasons.

Question:
Is it possible to achieve such recalibration with trivial functions (linear etc.)? If so, can you give me some information or insight about the solution.

 

[ellipsis]

I believe I may have an answer, using Excel. I'll edit this post with the details once I have them.

Okay, I've thought about this problem enough. I'll make a few assumptions:

- The goal is to minimize the most drastic weight change in the whole grid.
- The dimension of each plate is 1x1.
- The default weight of each plate is 1.
- The origin of the system is the center.

Now, for this specific solution, I'll assume the top-left plate is removed, and the whole system is a 3x3 array of plates (as drawn in your picture). I'll avoid the general case for my own sanity.

For ease of explanation, I'll label each panel, going from left to right then top to bottom, A through I.

Assuming the above figures, the new center of mass, with A removed, is (.1875, -.1875). Draw a line from this center to the origin. Now, draw a line perpendicular to this line, bisecting the whole diagram.

Whatever is below this line, has a weight that will decrease, and whatever is above this line has a weight that will increase. I am 100% confident of that fact.

Now, where I'm not so confident: I suspect the magnitude of the change in weight for each panel is proportional to the distance of each panel midpoint to the aforementioned line of balance.

 

[ellipsis]

Update: For this specific solution, I have found the following weights:
A: 0, B: .5, C: 1, D: .5, E: 1, F: .75, G: 1, H: .75, I: .75

I am amazed this works, and had to confirm it several times before I was convinced. I have no idea why it works, and why the numbers are so even. (I suspected roots to be in the answer). I found it by simple trial and error. I know it isn't optimal (In terms of the minimal mass-change)

Ah, I found a better solution:

• 0_____1.4_____1
• 1.4_____1_____.6
• 1______.6_____.8

I strongly suspect this is the optimal solution - I found it in a deterministic way, as well. The key is to consider only one dimension at a time.

 

[x0rr]

First of all, thank you for your reply. However, your third assumption is not correct. Weights can be and in fact are different. Only weights at symmetrical positions are equal. Also, I need a formulation because this is going to be executed many many times. I do not have a fixed system, the selection of positions to remove weights is random and the number of weights removed is controlled by a probability value. Also, the grid size is not fixes however it is always a square grid with cells being equal in size. So, the solution must be applicable to different weights on a given system as well and should generalize to any number of weights on the system.

 

[ellipsis]

Okay, I figured out another aspect of this problem... this is difficult, I'm not surprised nobody else has been commenting.

There exists a solution to a given grid, such that the mass offset magnitude for each plate is equal (and minimal).

This is the optimal solution for the simple example you drew:

• 0_____1.333_____1
• 1.333_____1_____.666
• 1______.666_____.666

I use 'optimal' in the sense that the maximum change in a specific plate is minimized, not that the total mass-change is minimized. In this case, the maximum change is .333, and by no coincidence, that's the only change-value used.

 

[x0rr]

Are you solving these by hand? Because, as I told you, I am going to need a formulation. I don't want to sound lazy, I would even appreciate if you give me the type of calculus you used and idea behind solution. Also, one more thing I forgot to mention is that central cell has to be empty but this can be achieved by simply not including it to calculation.

 

[ellipsis]

The first step to devising any novel algorithm is to do it by hand. If I can't do it by hand, then of course I'm not going to be able to teach a computer how to do it. Some context might help: What are you using this for/with?

Also, your no-center-plate restriction is trivial - The center plate is never used in the calculation. It can have a weight of 100, or 0, and it isn't used. (In other words, you can't balance the system by making the center heavier)

 

[mfb]

What do you want to optimize? There are many possible solutions - given two different solutions, how do we decide which one is better?

The solution for "minimal sum of mass changes" is typically "remove mass of one or multiple points at the opposite edge/corner" (where edge/corner depends on the tile where the mass change happens). This can get more complicated with larger areas (maybe for 5x5, and I'm quite sure it gets more complicated for some tiles on a 7x7 grid).
The solution for "minimal [maximal mass change]" is always "add mass to all points on the same side, remove mass from all points at the other side" (where "side" is defined based on the tile where the mass change happens).

Also, what is the symmetry of the problem? A single diagonal axis? Multiple axes? Do the mass changes have to keep that symmetry?

 

[x0rr]

I want to optimize in a sense that no weight changes drastically. Removing weights (or masses) is not acceptable. That should not happen. If you want a good solution. ellipses supplied one in his/her previous posts. I want you to help me to formalize (eg. a linear equation) such solution. Symmetry is on both of diagonal axes. An example would be

2__1__2
1__0__1
2__1__2

Mass change should not reflect any sort of symmetry. The system has no symmetry at initial condition (weights are removed randomly). Only objective is to bring center of mass (or gravity) to middle. Also, I am not even sure if its possible to balance the system while preserving symmetry.

 

[mfb]

ellipses supplied one in his/her previous posts

He reduced masses?

Also, I am not even sure if its possible to balance the system while preserving symmetry.

Certainly not, as you remove mass at one point and the mass at the opposite side is not allowed to get removed.

The smallest maximal weight change for a 3x3 grid
A B C
D E F
G H I
is then given by:
"if A gets reduced by an amount X, add X to both B and D"
"if B gets reduced by an amount X, add X/2 both to A and C"
The other cases follow from the symmetry of the problem.

5x5:
A B C D E
F G H I J
K L M N O
P Q R S T
U V W X Y
"if A gets reduced by an amount X, add X/4 to B,C,D,F,G,H,K,L,P"
... and 4 similar rules for B C G H, the others again follow from symmetry.

Is that what you are looking for?
I can see how a computer program can find those rules with a set of several basic steps.

 

[x0rr]

ellipses decreased some of them, increased rest without "drastic" increment or decrements which in the end balanced the system. That's the solution I want but I need to express it with formulas rather than an algorithm if possible. So, unfortunately, this is not what I want. I do not want an "algorithm". I need a mathematical (or physical) model to balance such system rather writing a series of decision based calculations. I came here with being fully aware that this is an easy problem for AI algorithms.

Anyway, I think I will stop now because this seems a bit harder (for physicists) than I initially imagined. I am not implying you can't solve it but I thought this would be pretty trivial for folks in here. Maybe I am failing to express myself.

Either way, thank you for your help.

 

[mfb]

This is not going forwards. You need some clear rule to decide which mass redistributions you prefer. If you just do that "by eye", it is impossible to find a general optimal solution.

A formula for the center of mass is easy, there is a general formula to find it, you can simply set its coordinates equal to the center of your grid to get a condition on the weights. Every distribution that satisfies these conditions has the right center of mass.
For the 3x3 grid, those formulas simplify to A+B+C=G+H+I and A+D+G=C+F+I.
For the 5x5 grid, it is 2*(A+B+C+D+E) + (F+G+H+I+J) = (P+Q+R+S+T) + 2*(U+V+W+X+Y) for the rows and similar for the columns.